Fix task dependency performance problem

[jlpeyton]

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.

[tlwilmar]

LGTM

openmp/trunk/runtime/src/kmp.h

struct kmp_dephash_entry {
     kmp_intptr_t               addr;
     kmp_depnode_t            * last_out;
     kmp_depnode_list_t       * last_ins;
     kmp_dephash_entry_t      * next_in_bucket;
 };
 
 typedef struct kmp_dephash {
    kmp_dephash_entry_t     ** buckets;
+   size_t         size;
 #ifdef KMP_DEBUG
    kmp_uint32                 nelements;
    kmp_uint32                 nconflicts;
 #endif
 } kmp_dephash_t;
 
 #endif
 

openmp/trunk/runtime/src/kmp_taskdeps.cpp

 }
 
 #define KMP_ACQUIRE_DEPNODE(gtid,n) __kmp_acquire_lock(&(n)->dn.lock,(gtid))
 #define KMP_RELEASE_DEPNODE(gtid,n) __kmp_release_lock(&(n)->dn.lock,(gtid))
 
 static void
 __kmp_depnode_list_free ( kmp_info_t *thread, kmp_depnode_list *list );
 
-static const kmp_int32 kmp_dephash_log2 = 6;
-static const kmp_int32 kmp_dephash_size = (1 << kmp_dephash_log2);
+enum {
+    KMP_DEPHASH_OTHER_SIZE = 97,
+    KMP_DEPHASH_MASTER_SIZE = 997
+};
 
 static inline kmp_int32
-__kmp_dephash_hash ( kmp_intptr_t addr )
+__kmp_dephash_hash ( kmp_intptr_t addr, size_t hsize )
 {
     //TODO alternate to try: set = (((Addr64)(addrUsefulBits * 9.618)) % m_num_sets );
-    return ((addr >> kmp_dephash_log2) ^ addr) % kmp_dephash_size;
+    return ((addr >> 6) ^ (addr >> 2)) % hsize;
 }
 
 static kmp_dephash_t *
-__kmp_dephash_create ( kmp_info_t *thread )
+__kmp_dephash_create ( kmp_info_t *thread, kmp_taskdata_t *current_task )
 {
     kmp_dephash_t *h;
 
-    kmp_int32 size = kmp_dephash_size * sizeof(kmp_dephash_entry_t) + sizeof(kmp_dephash_t);
+    size_t h_size;
+
+    if ( current_task->td_flags.tasktype == TASK_IMPLICIT )
+        h_size = KMP_DEPHASH_MASTER_SIZE;
+    else
+        h_size = KMP_DEPHASH_OTHER_SIZE;
+
+    kmp_int32 size = h_size * sizeof(kmp_dephash_entry_t) + sizeof(kmp_dephash_t);
 
 #if USE_FAST_MEMORY
     h = (kmp_dephash_t *) __kmp_fast_allocate( thread, size );
 #else
     h = (kmp_dephash_t *) __kmp_thread_malloc( thread, size );
 #endif
+    h->size = h_size;
 
 #ifdef KMP_DEBUG
     h->nelements = 0;
+    h->nconflicts = 0;
 #endif
     h->buckets = (kmp_dephash_entry **)(h+1);
 
-    for ( kmp_int32 i = 0; i < kmp_dephash_size; i++ )
+    for ( size_t i = 0; i < h_size; i++ )
         h->buckets[i] = 0;
 
     return h;
 }
 
 static void
 __kmp_dephash_free ( kmp_info_t *thread, kmp_dephash_t *h )
 {
-    for ( kmp_int32 i=0; i < kmp_dephash_size; i++ ) {
+    for ( size_t i=0; i < h->size; i++ ) {
         if ( h->buckets[i] ) {
             kmp_dephash_entry_t *next;
             for ( kmp_dephash_entry_t *entry = h->buckets[i]; entry; entry = next ) {
                 next = entry->next_in_bucket;
                 __kmp_depnode_list_free(thread,entry->last_ins);
                 __kmp_node_deref(thread,entry->last_out);
 #if USE_FAST_MEMORY
                 __kmp_fast_free(thread,entry);
 #else
                 __kmp_thread_free(thread,entry);
 #endif
             }
         }
     }
 #if USE_FAST_MEMORY
     __kmp_fast_free(thread,h);
 #else
     __kmp_thread_free(thread,h);
 #endif
 }
 
 static kmp_dephash_entry *
 __kmp_dephash_find ( kmp_info_t *thread, kmp_dephash_t *h, kmp_intptr_t addr )
 {
-    kmp_int32 bucket = __kmp_dephash_hash(addr);
+    kmp_int32 bucket = __kmp_dephash_hash(addr,h->size);
 
     kmp_dephash_entry_t *entry;
     for ( entry = h->buckets[bucket]; entry; entry = entry->next_in_bucket )
         if ( entry->addr == addr ) break;
 
     if ( entry == NULL ) {
         // create entry. This is only done by one thread so no locking required
 #if USE_FAST_MEMORY
#endif /* OMPT_SUPPORT && OMPT_TRACE */
     bool serial = current_task->td_flags.team_serial || current_task->td_flags.tasking_ser || current_task->td_flags.final;
 #if OMP_41_ENABLED
     serial = serial && !(new_taskdata->td_flags.proxy == TASK_PROXY);
 #endif
 
     if ( !serial && ( ndeps > 0 || ndeps_noalias > 0 )) {
         /* if no dependencies have been tracked yet, create the dependence hash */
         if ( current_task->td_dephash == NULL )
-            current_task->td_dephash = __kmp_dephash_create(thread);
+            current_task->td_dephash = __kmp_dephash_create(thread, current_task);
 
 #if USE_FAST_MEMORY
         kmp_depnode_t *node = (kmp_depnode_t *) __kmp_fast_allocate(thread,sizeof(kmp_depnode_t));
 #else
         kmp_depnode_t *node = (kmp_depnode_t *) __kmp_thread_malloc(thread,sizeof(kmp_depnode_t));
 #endif
 
         __kmp_init_node(node);