[OpenMP] libomp: minor changes to improve library performance

[AndreyChurbanov]

Summary

Three minor changes in this patch:

• added UNLIKELY hint to few rarely executed branches;
• replaced couple of run time checks with debug assertions;
• moved check of presence of ittnotify tool from inside the function call.

These three changes incrementally improve library performance on SpecOMP2012 376.kdtree test to 1.5% in total
(used Intel 19 compiler + libomp on 2x24-core Intel CLX system).

[jdoerfert]

UNLIKELY and assert seem ok, the third change not so much.

openmp/runtime/src/kmp_tasking.cpp

1926

This seems very unfortunate TBH. Now we duplicate the function body 3 times for some minor speedup somewhere? That is a slippery slope. What about a header implementation? Building the runtime with LTO?

[AndreyChurbanov]

Removed "if (UNLIKELY(itt_sync_create_ptr))" from kmp_itt_taskwait_object(), just to clarify previous change its usage.

[jdoerfert]

Is it necessary to manually inline __kmp_itt_taskwait_object three times? The rest of the changes look good to me.

[AndreyChurbanov]

In D95816#2547568, @jdoerfert wrote:

Is it necessary to manually inline __kmp_itt_taskwait_object three times? The rest of the changes look good to me.

Not sure I got your comment right, will try to clarify a bit.
I've just submitted update that removes "if (UNLIKELY(itt_sync_create_ptr))" from kmp_itt_taskwait_object() function.
Previous change #3 of the patch was to copy the "if" from the function. Now, to make thing clearer, the change is to move the "if" from inside the function.
It is not the inlining, it is just move of single "if" outside of the function.

So the scheme of the change #3 is to replace "call + if + return + if" with just "if" on the hot path of 99+% of execution (all those don't use an ittnotify tool). This change gives performance gain in both cases of library build - with and without LTO.

I named change1 the changes with "UNLIKELY" hint (except the last three); change2 = change1 + debug assertions; change3 = change2 + move of "if (UNLIKELY(__itt_sync_create_ptr))" in the following data:
Median time in sec of 3 runs of SpecOMP 2012 376.kdtree benchmark on 2x Xeon Gold 6252 (48 cores, 48 threads used):
trunk - 401
change1 - 399
change2 - 397
change3 - 395
trunk-LTO - 385
change1-LTO - 381
change2-LTO - 373
change3-LTO - 371

Similar performance trend seen on other platforms I have for testing (tried various families of Intel Xeon).

So all three changes in this patch give extra performance for both builds - with and without LTO.

Eventually I think we should enable LTO build, as it gives extra performance with tiny binary size increase - less than 1%. Link time increases, but still takes seconds.
I used trunk clang with -DLIBOMP_CXXFLAGS=-flto -DLIBOMP_LDFLAGS="-flto -fuse-ld=lld" cmake build options, and would prefer somebody more familiar with cmake do actual LTO enabling in cmake file(s).

[jdoerfert]

Granted, it's not inlining but partial inlining (the conditional from the 6 statement function).
I'm not happy about that either but I guess we can dot that. However, given that the
conditional is gone inside the function there is now an implicit calling invariant the user
has to know about. I don't use ITT but I feel this is not great. Two potential ways to
remedy this, neither is required to land the patch but they are simply suggestions:

1. Keep the conditional in the function. It will introduce minimal cost in ITT runs but none otherwise.
2. Create a wrapper in the header which encapsulates the __kmp_itt_taskwait_object call with the conditional exposed. This way we don't need to manually duplicate it in three locations.

ITT folks should accept the patch, no blocking objections from my side.

---

I agree, the CMake LTO stuff is unrelated and can be tackled independently.

[protze.joachim]

From my perspective, compiler support for final mergeable tasks would have a more significant impact for applications like kdtree. There is a broad misconception among OpenMP programmers what if(0) means/does.

The kdtree app could use if(A) final(a) mergeable in all cases which have if(A). Unfortunately, no compiler provides sensible support for final mergeable tasks. Even just adding mergeable to the if does not avoid the task creation with current compilers. Avoiding task creation could cut down the runtime by more than 50%. Any recursive tasking application with serial cut-off could profit from sensible compiler support for mergeable.

[jdoerfert]

In D95816#2549587, @protze.joachim wrote:

From my perspective, compiler support for final mergeable tasks would have a more significant impact for applications like kdtree. There is a broad misconception among OpenMP programmers what if(0) means/does.

The kdtree app could use if(A) final(a) mergeable in all cases which have if(A). Unfortunately, no compiler provides sensible support for final mergeable tasks. Even just adding mergeable to the if does not avoid the task creation with current compilers. Avoiding task creation could cut down the runtime by more than 50%. Any recursive tasking application with serial cut-off could profit from sensible compiler support for mergeable.

That seems unrelated (to some degree), let's talk about that via email ;)

[AndreyChurbanov]

Tried to address comments:
Restored the check in __kmp_itt_taskwait_object() just in case it could be used somewhere else in future.
Wrapped repeated code fragments into macros to reduce code duplication.

[jdoerfert]

LGTM

openmp/runtime/src/kmp_itt.h

103

Is there a reason to prefer macros over inline linkage functions?

[AndreyChurbanov]

openmp/runtime/src/kmp_itt.h

103

Using functions would need to make UNLIKELY macro visible here. The macro is defined in ompt-internal.h which does not look elegant to be included here. Duplicating the macro definition is also not a good solution. Moving the definition to some "neutral" place needs efforts, might be implemented separately if needed.

Hopefully ITT will eventually be removed from the code as non-standard profiling technique. But this may take (many) years until OMPT gets all the features ITT has, and then profilers (like Intel VTune) can shift from ITT to OMPT as it is a standard technique.

openmp/runtime/src/kmp_itt.h

 __kmp_inline void __kmp_itt_barrier_starting(int gtid, void *object);
 __kmp_inline void __kmp_itt_barrier_middle(int gtid, void *object);
 __kmp_inline void __kmp_itt_barrier_finished(int gtid, void *object);
 
 // --- Taskwait reporting ---
 __kmp_inline void *__kmp_itt_taskwait_object(int gtid);
 __kmp_inline void __kmp_itt_taskwait_starting(int gtid, void *object);
 __kmp_inline void __kmp_itt_taskwait_finished(int gtid, void *object);
+#define KMP_ITT_TASKWAIT_STARTING(obj) \
+    if (UNLIKELY(__itt_sync_create_ptr)) { \
+      obj = __kmp_itt_taskwait_object(gtid); \
+      if (obj != NULL) { \
+        __kmp_itt_taskwait_starting(gtid, obj); \
+      } \
+    }
+#define KMP_ITT_TASKWAIT_FINISHED(obj) \
+    if (UNLIKELY(obj != NULL)) \
+      __kmp_itt_taskwait_finished(gtid, obj);
 
 // --- Task reporting ---
 __kmp_inline void __kmp_itt_task_starting(void *object);
 __kmp_inline void __kmp_itt_task_finished(void *object);
 
 // --- Lock reporting ---
 #if KMP_USE_DYNAMIC_LOCK
 __kmp_inline void __kmp_itt_lock_creating(kmp_user_lock_p lock,
                                           const ident_t *);

openmp/runtime/src/kmp_tasking.cpp

static void __kmpc_omp_task_begin_if0_template(ident_t *loc_ref, kmp_int32 gtid,
                                                void *return_address) {
   kmp_taskdata_t *taskdata = KMP_TASK_TO_TASKDATA(task);
   kmp_taskdata_t *current_task = __kmp_threads[gtid]->th.th_current_task;
 
   KA_TRACE(10, ("__kmpc_omp_task_begin_if0(enter): T#%d loc=%p task=%p "
                 "current_task=%p\n",
                 gtid, loc_ref, taskdata, current_task));
 
-  if (taskdata->td_flags.tiedness == TASK_UNTIED) {
+  if (UNLIKELY(taskdata->td_flags.tiedness == TASK_UNTIED)) {
     // untied task needs to increment counter so that the task structure is not
     // freed prematurely
     kmp_int32 counter = 1 + KMP_ATOMIC_INC(&taskdata->td_untied_count);
     KMP_DEBUG_USE_VAR(counter);
     KA_TRACE(20, ("__kmpc_omp_task_begin_if0: T#%d untied_count (%d) "
                   "incremented for task %p\n",
                   gtid, counter, taskdata));
   }
#endif /* BUILD_TIED_TASK_STACK */
   }
 
   /* If the tasks' destructor thunk flag has been set, we need to invoke the
      destructor thunk that has been generated by the compiler. The code is
      placed here, since at this point other tasks might have been released
      hence overlapping the destructor invocations with some other work in the
      released tasks.  The OpenMP spec is not specific on when the destructors
      are invoked, so we should be free to choose. */
-  if (taskdata->td_flags.destructors_thunk) {
+  if (UNLIKELY(taskdata->td_flags.destructors_thunk)) {
     kmp_routine_entry_t destr_thunk = task->data1.destructors;
     KMP_ASSERT(destr_thunk);
     destr_thunk(gtid, task);
   }
 
   KMP_DEBUG_ASSERT(taskdata->td_flags.complete == 0);
   KMP_DEBUG_ASSERT(taskdata->td_flags.started == 1);
   KMP_DEBUG_ASSERT(taskdata->td_flags.freed == 0);
 
   bool detach = false;
-  if (taskdata->td_flags.detachable == TASK_DETACHABLE) {
+  if (UNLIKELY(taskdata->td_flags.detachable == TASK_DETACHABLE)) {
     if (taskdata->td_allow_completion_event.type ==
         KMP_EVENT_ALLOW_COMPLETION) {
       // event hasn't been fulfilled yet. Try to detach task.
       __kmp_acquire_tas_lock(&taskdata->td_allow_completion_event.lock, gtid);
       if (taskdata->td_allow_completion_event.type ==
           KMP_EVENT_ALLOW_COMPLETION) {
         // task finished execution
         KMP_DEBUG_ASSERT(taskdata->td_flags.executing == 1);

 }
 
 template <bool ompt>
 static void __kmpc_omp_task_complete_if0_template(ident_t *loc_ref,
                                                   kmp_int32 gtid,
                                                   kmp_task_t *task) {
   KA_TRACE(10, ("__kmpc_omp_task_complete_if0(enter): T#%d loc=%p task=%p\n",
                 gtid, loc_ref, KMP_TASK_TO_TASKDATA(task)));
-  __kmp_assert_valid_gtid(gtid);
+  KMP_DEBUG_ASSERT(gtid >= 0);
   // this routine will provide task to resume
   __kmp_task_finish<ompt>(gtid, task, NULL);
 
   KA_TRACE(10, ("__kmpc_omp_task_complete_if0(exit): T#%d loc=%p task=%p\n",
                 gtid, loc_ref, KMP_TASK_TO_TASKDATA(task)));
 
 #if OMPT_SUPPORT
   if (ompt) {
if (flags->tiedness == TASK_UNTIED && !team->t.t_serialized) {
     // of the deque should be enough.
     KMP_CHECK_UPDATE(
         encountering_thread->th.th_task_team->tt.tt_untied_task_encountered, 1);
   }
 
   // Detachable tasks are not proxy tasks yet but could be in the future. Doing
   // the tasking setup
   // when that happens is too late.
-  if (flags->proxy == TASK_PROXY || flags->detachable == TASK_DETACHABLE ||
-      flags->hidden_helper) {
+  if (UNLIKELY(flags->proxy == TASK_PROXY ||
+               flags->detachable == TASK_DETACHABLE || flags->hidden_helper)) {
     if (flags->proxy == TASK_PROXY) {
       flags->tiedness = TASK_UNTIED;
       flags->merged_if0 = 1;
     }
     /* are we running in a sequential parallel or tskm_immediate_exec... we need
        tasking support enabled */
     if ((encountering_thread->th.th_task_team) == NULL) {
       /* This should only happen if the team is serialized
static kmp_int32 __kmpc_omp_taskwait_template(ident_t *loc_ref, kmp_int32 gtid,
                                               void *frame_address,
                                               void *return_address) {
   kmp_taskdata_t *taskdata;
   kmp_info_t *thread;
   int thread_finished = FALSE;
   KMP_SET_THREAD_STATE_BLOCK(TASKWAIT);
 
   KA_TRACE(10, ("__kmpc_omp_taskwait(enter): T#%d loc=%p\n", gtid, loc_ref));
-  __kmp_assert_valid_gtid(gtid);
+  KMP_DEBUG_ASSERT(gtid >= 0);
 
   if (__kmp_tasking_mode != tskm_immediate_exec) {
     thread = __kmp_threads[gtid];
     taskdata = thread->th.th_current_task;
 
 #if OMPT_SUPPORT && OMPT_OPTIONAL
     ompt_data_t *my_task_data;
     ompt_data_t *my_parallel_data;

 #if USE_ITT_BUILD
 // Note: These values are used by ITT events as well.
 #endif /* USE_ITT_BUILD */
     taskdata->td_taskwait_counter += 1;
     taskdata->td_taskwait_ident = loc_ref;
     taskdata->td_taskwait_thread = gtid + 1;
 
 #if USE_ITT_BUILD
-    void *itt_sync_obj = __kmp_itt_taskwait_object(gtid);
-    if (UNLIKELY(itt_sync_obj != NULL))
-      __kmp_itt_taskwait_starting(gtid, itt_sync_obj);
+    void *itt_sync_obj = NULL;
+#if USE_ITT_NOTIFY
+    KMP_ITT_TASKWAIT_STARTING(itt_sync_obj);
+#endif /* USE_ITT_NOTIFY */
 #endif /* USE_ITT_BUILD */
 
     bool must_wait =
         !taskdata->td_flags.team_serial && !taskdata->td_flags.final;
 
     must_wait = must_wait || (thread->th.th_task_team != NULL &&
                               thread->th.th_task_team->tt.tt_found_proxy_tasks);
     // If hidden helper thread is encountered, we must enable wait here.
     must_wait =
         must_wait ||
         (__kmp_enable_hidden_helper && thread->th.th_task_team != NULL &&
          thread->th.th_task_team->tt.tt_hidden_helper_task_encountered);
 
     if (must_wait) {
       kmp_flag_32<false, false> flag(
           RCAST(std::atomic<kmp_uint32> *,
                 &(taskdata->td_incomplete_child_tasks)),
           0U);
       while (KMP_ATOMIC_LD_ACQ(&taskdata->td_incomplete_child_tasks) != 0) {
         flag.execute_tasks(thread, gtid, FALSE,
                            &thread_finished USE_ITT_BUILD_ARG(itt_sync_obj),
                            __kmp_task_stealing_constraint);
       }
     }
 #if USE_ITT_BUILD
-    if (UNLIKELY(itt_sync_obj != NULL))
-      __kmp_itt_taskwait_finished(gtid, itt_sync_obj);
+    KMP_ITT_TASKWAIT_FINISHED(itt_sync_obj);
     KMP_FSYNC_ACQUIRED(taskdata); // acquire self - sync with children
 #endif /* USE_ITT_BUILD */
 
     // Debugger:  The taskwait is completed. Location remains, but thread is
     // negated.
     taskdata->td_taskwait_thread = -taskdata->td_taskwait_thread;
 
 #if OMPT_SUPPORT && OMPT_OPTIONAL

 #if USE_ITT_BUILD
 // Note: These values are used by ITT events as well.
 #endif /* USE_ITT_BUILD */
     taskdata->td_taskwait_counter += 1;
     taskdata->td_taskwait_ident = loc_ref;
     taskdata->td_taskwait_thread = gtid + 1;
 
 #if USE_ITT_BUILD
-    void *itt_sync_obj = __kmp_itt_taskwait_object(gtid);
-    if (UNLIKELY(itt_sync_obj != NULL))
-      __kmp_itt_taskwait_starting(gtid, itt_sync_obj);
+    void *itt_sync_obj = NULL;
+#if USE_ITT_NOTIFY
+    KMP_ITT_TASKWAIT_STARTING(itt_sync_obj);
+#endif /* USE_ITT_NOTIFY */
 #endif /* USE_ITT_BUILD */
     if (!taskdata->td_flags.team_serial) {
       kmp_task_team_t *task_team = thread->th.th_task_team;
       if (task_team != NULL) {
         if (KMP_TASKING_ENABLED(task_team)) {
 #if OMPT_SUPPORT
           if (UNLIKELY(ompt_enabled.enabled))
             thread->th.ompt_thread_info.ompt_task_yielded = 1;
 #endif
           __kmp_execute_tasks_32(
               thread, gtid, (kmp_flag_32<> *)NULL, FALSE,
               &thread_finished USE_ITT_BUILD_ARG(itt_sync_obj),
               __kmp_task_stealing_constraint);
 #if OMPT_SUPPORT
           if (UNLIKELY(ompt_enabled.enabled))
             thread->th.ompt_thread_info.ompt_task_yielded = 0;
 #endif
         }
       }
     }
 #if USE_ITT_BUILD
-    if (UNLIKELY(itt_sync_obj != NULL))
-      __kmp_itt_taskwait_finished(gtid, itt_sync_obj);
+    KMP_ITT_TASKWAIT_FINISHED(itt_sync_obj);
 #endif /* USE_ITT_BUILD */
 
     // Debugger:  The taskwait is completed. Location remains, but thread is
     // negated.
     taskdata->td_taskwait_thread = -taskdata->td_taskwait_thread;
   }
 
   KA_TRACE(10, ("__kmpc_omp_taskyield(exit): T#%d task %p resuming, "
#endif
   if (__kmp_tasking_mode != tskm_immediate_exec) {
     // mark task as waiting not on a barrier
     taskdata->td_taskwait_counter += 1;
     taskdata->td_taskwait_ident = loc;
     taskdata->td_taskwait_thread = gtid + 1;
 #if USE_ITT_BUILD
     // For ITT the taskgroup wait is similar to taskwait until we need to
     // distinguish them
-    void *itt_sync_obj = __kmp_itt_taskwait_object(gtid);
-    if (UNLIKELY(itt_sync_obj != NULL))
-      __kmp_itt_taskwait_starting(gtid, itt_sync_obj);
+    void *itt_sync_obj = NULL;
+#if USE_ITT_NOTIFY
+    KMP_ITT_TASKWAIT_STARTING(itt_sync_obj);
+#endif /* USE_ITT_NOTIFY */
 #endif /* USE_ITT_BUILD */
 
 #if OMPT_SUPPORT && OMPT_OPTIONAL
     if (UNLIKELY(ompt_enabled.ompt_callback_sync_region_wait)) {
       ompt_callbacks.ompt_callback(ompt_callback_sync_region_wait)(
           ompt_sync_region_taskgroup, ompt_scope_begin, &(my_parallel_data),
           &(my_task_data), codeptr);
     }
#if OMPT_SUPPORT && OMPT_OPTIONAL
     if (UNLIKELY(ompt_enabled.ompt_callback_sync_region_wait)) {
       ompt_callbacks.ompt_callback(ompt_callback_sync_region_wait)(
           ompt_sync_region_taskgroup, ompt_scope_end, &(my_parallel_data),
           &(my_task_data), codeptr);
     }
 #endif
 
 #if USE_ITT_BUILD
-    if (UNLIKELY(itt_sync_obj != NULL))
-      __kmp_itt_taskwait_finished(gtid, itt_sync_obj);
+    KMP_ITT_TASKWAIT_FINISHED(itt_sync_obj);
     KMP_FSYNC_ACQUIRED(taskdata); // acquire self - sync with descendants
 #endif /* USE_ITT_BUILD */
   }
   KMP_DEBUG_ASSERT(taskgroup->count == 0);
 
   if (taskgroup->reduce_data != NULL) { // need to reduce?
     int cnt;
     void *reduce_data;