Цена вызовов

Бытует мнение, что накладные расходы на вызов методов и организацию процесса выполнения не должны превышать 15% времени выполнения приложения, иначе стоит серьезно задуматься над вопросом рефакторинга приложения и оптимизации его логики. Вооружившись такими мыслями я наткнулся на метод QuickSort из стандартного класса ArraySortHelper<T> использующийся для сортировки массивов в .Net.

Интересным моментом здесь является сравнение элементов — для обеспечения гибкости его вынеслив отдельный класс реализующий интерфейс IComparer<T>. Вооружившись разнообразными мыслями и студией было решено оценить сколько же такая гибкость стоит и что с этим можно было бы сделать — под катом анализ затрат на сравнение элементов во временя работы QuickSort.



Итак у нас есть стандартная реализация быстрой сортировки Хоара, которая для сравнения элементов массива использует метод Compare(T x, T y) из объекта реализующего интерфейс IComparer<T>. Для наших опытов, при помощи рефлектора, получаем код метода сортировки в следующем виде:

Copy Source | Copy HTML

1. static public void Sort<T, TValue>(T[] keys, TValue[] values, int left, int right, IComparer<T> comparer)
2. {
3.     do
4.     {
5.         int index = left;
6.         int num2 = right;
7.         T y = keys[index + ((num2 - index) >> 1)];
8.         do
9.         {
10.             try
11.             {
12. /* Cmp 1 */     while (comparer.Compare(keys[index], y) <  0)
13.                 {
14.                     index++;
15.                 }
16. /* Cmp 2 */     while (comparer.Compare(y, keys[num2]) <  0)
17.                 {
18.                     num2--;
19.                 }
20.             }
21.             catch (IndexOutOfRangeException)
22.             {
23.                 throw new ArgumentException(null, "keys");
24.             }
25.             catch (Exception)
26.             {
27.                 throw new InvalidOperationException();
28.             }
29.             if (index > num2)
30.             {
31.                 break;
32.             }
33.             if (index < num2)
34.             {
35.                 T local2 = keys[index];
36.                 keys[index] = keys[num2];
37.                 keys[num2] = local2;
38.                 if (values != null)
39.                 {
40.                     TValue local3 = values[index];
41.                     values[index] = values[num2];
42.                     values[num2] = local3;
43.                 }
44.             }
45.             index++;
46.             num2--;
47.         }
48.         while (index <= num2);
49.         if ((num2 - left) <= (right - index))
50.         {
51.             if (left < num2)
52.             {
53. /* Call 1 */    Sort<T, TValue>(keys, values, left, num2, comparer);
54.             }
55.             left = index;
56.         }
57.         else
58.         {
59.             if (index < right)
60.             {
61. /* Call 2 */    Sort<T, TValue>(keys, values, index, right, comparer);
62.             }
63.             right = num2;
64.         }
65.     }
66.     while (left < right);
67. }

Поскольку исследовать мы будем исключительно вызов операции сравенния, то все изменения этой функции будут делаться только в строках 1, 12, 16, 53 и 61, которые помечены в листинге опознавательными комментариями.

Часть первая. Опыты с массивами чисел (int)

Для начала оценим вклад накладных расходов на вызов операции сравнения двух чисел в длительность выполнения процесса сортировки. Для этого в приведенной функции меняем вызовы «comparer.Compare(a, b)» на выражения вида «a - b». Замеряем время работы обеих версий и видим… Видим ужасную картину — практически две трети времени тратится на организацию вызова предиката сравниващего числа:



Что же могло так сильно замедлить работу? Очевидно что дело в излишней сложности процесса сравнения (и это при том, что сама операция сводится к вычитанию двух чисел!):

1. Проверка объекта comparer на null
2. Поиск метода Compare в виртуальной таблице объекта
3. Вызов метода Compare для объекта comparer
4. Вызов метода CompareTo
5. Собственно сравнение чисел

При этом первые два пункта являются отличием CIL-инструкции callvirt от call. Напомню, что callvirt, из-за наличия проверки на null, генерируется для вызова всех нестатических методов классов независимо от их виртуальности.

Ну а четвертый пункт вызван стандартной реализацией comparer-а (все проверки на null естественным образом убираются JIT-компилятором при подстановке int вместо T):

Copy Source | Copy HTML

1. class GenericComparer<T> : IComparer<T> where T : IComparable<T>
2. {
3.     public int Compare(T x, T y)
4.     {
5.         if (x != null)
6.         {
7.             if (y != null)
8.             {
9.                 return x.CompareTo(y);
10.             }
11.             return 1;
12.         }
13.         if (y != null)
14.         {
15.             return -1;
16.         }
17.         return  0;
18.     }
19. }

Будем убирать слои по одному, начнем с вызова CompareTo, благо это делается элементарно — написанием своего comparer'а следующего вида:

Copy Source | Copy HTML

1. class IntComparer : IComparer<int>
2. {
3.     public int Compare(int x, int y)
4.     {
5.         return x - y;
6.     }
7. }

Замеры показывают выиграш 15% по времени. И это при том, что мы рассматриваем массив целых чисел и вызов CompareTo для них, как и для всех методов для всех структур является невиртуальным. Следующий слой, отличие между callvirt и call при вызове, проверить сложнее, особенно в рамках тех же требований к гибкости функции сортировки. Впрочем нет ничего невозможного — при работе через инстанцию структуры, все методы всех структур вызываются при помощи операции call, в том числе реализации методов унаследованных от интерфейсов. Благодаря этому мы можем сделать следующую оптимизацию:

Copy Source | Copy HTML

1. static public void SortNoVirt<T, TValue, TCmp>(T[] keys, TValue[] values, int left, int right, TCmp comparer) where TCmp : IComparer<T>
2. {
3.     // ...
4. }
5.  
6. struct IntComparerNoVirt : IComparer<int>
7. {
8.     public int Compare(int x, int y)
9.     {
10.         return x - y;
11.     }
12. }

Благодаря передаче фактического типа в функцию сортировки, при разворачивании параметров генерика будет учтен реальный тип comparer'а и для вызова операции сравнения задействуется более эффективная инструкция call. Замеры времени показывают прирост произодительности около 35% от времени выполнения «стандартного» вызова, при этом прирост от последующей замены вызова Compare на отнимание составляет 18%.

На заметку: В библиотеке STL из C++ все предикаты передаются именно таким образом — тип идет через параметр шаблона. Дополнительно, благодаря этому трюку, компилятор C++ получает полную информацию о типах и как правило производит разворачивание (inlining) кода предиката, тем самым полностью исключая затраты на вызов метода. Мои опыты с дизассемблированием результатов работы .Net JIT показали, что вопреки всем ухищрениям, здесь никакого разворачивания не происходит. Судя по всему это либо связано с генериками, либо работает оно исключительно для статических методов.

На заметку #2: Сэкономить на передаче comparer'а при помомщи пустой структуры не удалось — размер (sizeof) структуры без полей в C# оказался равным единице (а не нулю, как хотелось). В VC++ размер пустой структуры также равен единице, при этом в стандарте говорится, что размер пустого класса (структуры) должен быть больше нуля. Сделано это из-за популярной конструкции для вычисления длины массива «sizeof(array) / sizeof(array[0])». В C#/.Net это видимо сделано для бинарной совместимости при взаимодействии с кодом написаным на C++.

Если свести данные в единую диаграмму, получим следующее распределение времени выполнения сортировки стандартным методом:



Напрашивающийся очевидный вывод — при разработке тяжелых в вычислительном плане библитек есть смысл частовызываемые предикаты делать структурами и их тип передавать через параметры генерика.

Часть вторая. А что с будет объектами?

Но не числами едиными живут наши приложения :) Возник вопрос влияния в контексте работы с массивами объектов, проверим? Легко! В качестве опытного образца берем вот такой простенький класс:

Copy Source | Copy HTML

1. class IntObj : IComparable<IntObj>
2. {
3.     public int value;
4.  
5.     public int CompareTo(IntObj other)
6.     {
7.         return value - other.value;
8.     }
9. }

И проводим аналогичные нехитрые опыты но уже с массивом объектов, в итоге получаем чуть другую ситуацию:



И если соотношение между частями процесса сравнения остались неизменными, то их вклад в общее время заметно уменьшился. Взникает вполне везонный вопрос: а в чем же дело, что замедляется? Беглого взгляда на код функции сортировки достаточно чтоб понять: замедлилась работа единственного отличающегося куска кода — обмена значений между элементами массива. Но ведь мы работает со ссылочным типом, переставляются только указатели, а они «в душе» числа! Раз интересно, значит будем смотреть что там так замедляется, чтение CIL пользы особо не дает — код обмена асболютно идентичный за исключением использования инструкций *.i4 для чисел и *.ref для объектов.

Раз не помог CIL, значит дело в выходе из JIT, значит будем смотреть ассемблер :) Здесь нас ждет весялая неприятность — независимо от крнфигурации (Debug/Release), JIT-компилятор смотрик на свое окружение и, в зависимости от наличия присоединенного к процессу отладчика, генерирует разный код. Поэтому для доступа к реальному коду через окно Disassembly мы будем запускать приложение без отладки а точки останова поставим в виде вызовов Debugger.Break();. Далее приведены листинги с кодом который генерируется для обмена местами значений в двух ячейках массива:

Copy Source | Copy HTML ; ============================================== ; swap in int array ;   124:  T local2 = keys[index];

Copy Source | Copy HTML ; ============================================== ; swap in IntObj array ;   124:  T local2 = keys[index];

00000142  movsxd  rcx,ebx  00000145  mov     rsi,qword ptr [rbp+68h]  00000149  mov     rax,qword ptr [rsi+8]  0000014d  cmp     rcx,rax  00000150  jae     0000000000000275  00000156  mov     edx,dword ptr [rsi+rcx*4+10h]  ;   125:  keys[index] = keys[num2]; 0000015a  movsxd  r8,edi  0000015d  cmp     r8,rax  00000160  jae     0000000000000275  00000166  mov     eax,dword ptr [rsi+r8*4+10h]  0000016b  mov     dword ptr [rsi+rcx*4+10h],eax  ;   126:  keys[num2] = local2; 0000016f  mov     dword ptr [rsi+r8*4+10h],edx

00000146  movsxd  r12,ebx  00000149  mov     rsi,qword ptr [rbp+68h]  0000014d  mov     rax,qword ptr [rsi+8]  00000151  cmp     r12,rax  00000154  jae     0000000000000285  0000015a  mov     r14,qword ptr [rsi+r12*8+18h]  ;   125:  keys[index] = keys[num2]; 0000015f  movsxd  r13,edi  00000162  cmp     r13,rax  00000165  jae     0000000000000285  0000016b  mov     r8,qword ptr [rsi+r13*8+18h]  00000170  mov     edx,ebx  00000172  mov     rcx,rsi  00000175  call    FFFFFFFFEF5F7CB0  ;   126:  keys[num2] = local2; 0000017a  mov     r8,r14  0000017d  mov     edx,edi  0000017f  mov     rcx,rsi  00000182  call    FFFFFFFFEF5F7CB0

В листингах сразу же бросается в глаза вызов некоторой функции для записи в массив объектов, причем вызов этот отсутствовал пока мы смотрели CIL. Очевидно, что эта функция делает нечто большее чем просто копирование адреса и помимо затрат на органицазию этого вызова мы получаем еще что-то, а значит детали лежат в реализации CLR. Действительно, почитав исходники публичной версии CLR 2.0 (пакет SSCLI 2.0), находим следующий код:

Copy Source | Copy HTML

1. /****************************************************************************/
2. /* assigns 'val to 'array[idx], after doing all the proper checks */
3.  
4. HCIMPL3(void, JIT_Stelem_Ref_Portable, PtrArray* array, unsigned idx, Object *val)
5. {
6.     if (!array)
7.     {
8.         FCThrowVoid(kNullReferenceException);
9.     }
10.     if (idx >= array->GetNumComponents())
11.     {
12.         FCThrowVoid(kIndexOutOfRangeException);
13.     }
14.  
15.     if (val)
16.     {
17.         MethodTable *valMT = val->GetMethodTable();
18.         TypeHandle arrayElemTH = array->GetArrayElementTypeHandle();
19.  
20.         if (arrayElemTH != TypeHandle(valMT) && arrayElemTH != TypeHandle(g_pObjectClass))
21.         {
22.             TypeHandle::CastResult result = ObjIsInstanceOfNoGC(val, arrayElemTH);
23.             if (result != TypeHandle::CanCast)
24.             {
25.                 HELPER_METHOD_FRAME_BEGIN_2(val, array);
26.  
27.                 // This is equivalent to ArrayStoreCheck(&val, &array);
28. #ifdef STRESS_HEAP
29.                 // Force a GC on every jit if the stress level is high enough
30.                 if (g_pConfig->GetGCStressLevel() !=  0
31. #ifdef _DEBUG
32.                     && !g_pConfig->FastGCStressLevel()
33. #endif
34.                    )
35.                     GCHeap::GetGCHeap()->StressHeap();
36. #endif
37.  
38. #if CHECK_APP_DOMAIN_LEAKS
39.                 // If the instance is agile or check agile
40.                 if (!arrayElemTH.IsAppDomainAgile() && !arrayElemTH.IsCheckAppDomainAgile() && g_pConfig->AppDomainLeaks())
41.                 {
42.                     val->AssignAppDomain(array->GetAppDomain());
43.                 }
44. #endif
45.                 if (!ObjIsInstanceOf(val, arrayElemTH))
46.                 {
47.                     COMPlusThrow(kArrayTypeMismatchException);
48.                 }
49.  
50.                 HELPER_METHOD_FRAME_END();
51.             }
52.         }
53.  
54.         // The performance gain of the optimized JIT_Stelem_Ref in
55.         // jitinterfacex86.cpp is mainly due to calling JIT_WriteBarrierReg_Buf.
56.         // By calling write barrier directly here,
57.         // we can avoid translating in-line assembly from MSVC to gcc
58.         // while keeping most of the performance gain.
59.         HCCALL2(JIT_WriteBarrier, (Object **)&array->m_Array[idx], val);
60.  
61.     }
62.     else
63.     {
64.         // no need to go through write-barrier for NULL
65.         ClearObjectReference(&array->m_Array[idx]);
66.     }
67. }
68. HCIMPLEND

Как видно отсюда, при записи элемента в массив объектов, помимо стандартной проверки границ массива, также проверяется совместимость типов и при необходимости производятся соответствующие конвертации. Стоит заметить, что будучи строко типизированным, сам C# также содержит контроль типов, но поскольку в CIL инструкцию информация уже приходит в виде System.Object, то CLR, для надежности, проверяет еще раз.

Часть третья. Подобие выводов

Какие из этого всего можно сделать выводы? Хардкорные оптимизации предлагать не буду, но есть смысл избегать виртуальных вызовов внутри больших циклов, особенно в миниатюрных функциях-предикатах. На практике это например:

• реализаця предикатов в виде структур, а не классов с последующей предачей информации о типе через параметры генерика
• замена мелких утилитарных методов классов на статические методы-расширения, которые из-за своей статичности будут вызваны в обход виртуальной таблицы

Конечно, это не единственные возможные выводы, но ведь надо же оставить читателю простор для мыслей :)