HomePhabricator

Fix task dependency performance problem

Authored by jlpeyton on Jan 28 2016, 3:10 PM.

Description

Fix task dependency performance problem

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.

Differential Revision: http://reviews.llvm.org/D16640

llvm-svn: 259113

Details

Committed
jlpeytonJan 28 2016, 3:10 PM
Differential Revision
D16640: Fix task dependency performance problem
Parents
rGcd23fec756a0: [PlaceSafepoints] Misc. minor cleanups; NFC
Branches
Unknown
Tags
Unknown