Page MenuHomePhabricator

Fix task dependency performance problem
ClosedPublic

Authored by jlpeyton on Jan 27 2016, 10:51 AM.

Details

Summary

In: http://lists.llvm.org/pipermail/openmp-dev/2015-August/000858.html, a performance issue was found with libomp's task dependencies.

The task dependencies hash table has an issue with collisions. The current table size is a power of two. This combined with the current hash function causes a large number of collisions to occurr. Also, the current size (64) is too small for larger applications so the table size is increased.

This patch creates a two level hash table approach for task dependencies. The implicit task is considered the "master" or "top-level" task which has a large static sized hash table (997), and nested tasks will have smaller hash tables (97). Prime numbers were chosen to help reduce collisions.

Diff Detail

Repository
rL LLVM

Event Timeline

jlpeyton updated this revision to Diff 46152.Jan 27 2016, 10:51 AM
jlpeyton retitled this revision from to Fix task dependency performance problem.
jlpeyton updated this object.
jlpeyton set the repository for this revision to rL LLVM.
jlpeyton added a subscriber: openmp-commits.
tlwilmar accepted this revision.Jan 28 2016, 8:41 AM
tlwilmar edited edge metadata.

LGTM

This revision is now accepted and ready to land.Jan 28 2016, 8:41 AM
This revision was automatically updated to reflect the committed changes.