This is an archive of the discontinued LLVM Phabricator instance.

[OpenMP] Adopt std::set in HostDataToTargetMap
ClosedPublic

Authored by ye-luo on Jun 20 2020, 12:55 PM.

Details

Summary

lookupMapping took significant time due to linear complexity searching.
This is bad for offloading from multiple host threads because lookupMapping is protected by mutex.
Use std::set for logarithmic complexity searching.

Before my change.
libomptarget inclusive time 16.7 sec, exclusive time 8.6 sec.
After the change
libomptarget inclusive time 7.3 sec, exclusive time 0.4 sec.

Most of the overhead of libomptarget (exclusive time) is gone.

Diff Detail

Event Timeline

ye-luo created this revision.Jun 20 2020, 12:55 PM
grokos added inline comments.Jun 23 2020, 5:19 PM
openmp/libomptarget/src/device.cpp
134

ExtendsBefore has not been checked so far, so it's still in its default false state. It can be removed from the condition.

openmp/libomptarget/src/device.h
18

I think including <list> is not necessary anymore.

ye-luo updated this revision to Diff 272883.Jun 23 2020, 6:15 PM
ye-luo marked 2 inline comments as done.Jun 23 2020, 6:18 PM
ye-luo added inline comments.
openmp/libomptarget/src/device.cpp
134

Fixed

openmp/libomptarget/src/device.h
18

PendingCtors and PendingDtors still use list.

grokos accepted this revision.Jun 23 2020, 6:34 PM

Looks good now. Thanks!

This revision is now accepted and ready to land.Jun 23 2020, 6:34 PM

Just out of curiosity, will unordered_set work here? In theory, it will have better performance than set.

The current lookup function needs to search by range instead of exact value. I need upper_bound functionality.

This revision was automatically updated to reflect the committed changes.

The current lookup function needs to search by range instead of exact value. I need upper_bound functionality.

Okay, I see. Thanks for the explanation.