Накладные расходы на структурное программирование

Когда речь заходит о структурном программировании, одним из аргументов противников того, чтобы кодировать исключительно структурно является вопрос производительности. На мой взгляд, структурный подход не может существенно понижать производительность, тем более при использовании оптимизирующих компиляторов. С другой стороны, большинство современных языков, используемых в производстве, не продвигают структурность, поэтому и их компиляторы не учитывают специфику подхода, что мешает использованию специальных оптимизаций. Так стоит ли волноваться по этому поводу? Для ответа на этот вопрос я написал небольшой тест, представляющий из себя несколько воплощений линейного поиска в трёхмерном массиве.

Сперва я написал декомпозицию из 3-х функций, являющихся почти копиями друг друга. Чем мне нравится этот вариант, так это тем, что он предоставляет сразу три поиска: для 1-о, 2-х и 3-х мерных массивов.

static bool search1d(int a[N3], bool match(int), int *i) {
  *i = 0;
  while ((*i < N3) && !match(a[*i])) {
    *i += 1;
  }
  return *i < N3;
}
static bool search2d(int a[N2][N3], bool match(int), int *j, int *i) {
  *j = 0;
  while ((*j < N2) && !search1d(a[*j], match, i)) {
    *j += 1;
  }
  return *j < N2;
}
extern bool search_decomposed(int a[N1][N2][N3], bool match(int), int *k, int *j, int *i) {
  *k = 0;
  while ((*k < N1) && !search2d(a[*k], match, j, i)) {
    *k += 1;
  }
  return *k < N1;
}

Затем я создал 1-ю версию неструктурного алгоритма с return из середины функции:

extern bool search_return_p(int a[N1][N2][N3], bool match(int), int *k, int *j, int *i) {
  for (*k = 0; *k < N1; *k += 1) {
    for (*j = 0; *j < N2; *j += 1) {
      for (*i = 0; *i < N3; *i += 1) {
        if (match(a[*k][*j][*i])) {
          return true;
        }
      }
    }
  }
  return false;
}

Первый же тестовый прогон показал, что этот неструктурный поиск оказался даже медленней декомпозиции. Эксперимент выявил, что дело было в непосредственном использовании указателей. Тогда я добавил такой вариант этого же алгоритма:

extern bool search_return(int a[N1][N2][N3], bool match(int), int *pk, int *pj, int *pi) {
  int i, j, k;
  for (k = 0; k < N1; k += 1) {
    for (j = 0; j < N2; j += 1) {
      for (i = 0; i < N3; i += 1) {
        if (match(a[k][j][i])) {
          *pk = k;
          *pj = j;
          *pi = i;
          return true;
        }
      }
    }
  }
  return false;
}

Этот код оказался быстрей первоначального. А вот игра с локальными переменными вместо указателей для структурной декомпозиции не выявила никаких изменений в скорости для gcc. Оптимизирующие компиляторы плохо предсказуемы и замедление может вылезть совсем не оттуда, откуда мы ожидаем.

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

extern bool search_outlimit(int a[N1][N2][N3], bool match(int), int *pk, int *pj, int *pi) {
  int i, j, k;
  for (k = 0; k < N1; k += 1) {
    for (j = 0; j < N2; j += 1) {
      for (i = 0; i < N3; i += 1) {
        if (match(a[k][j][i])) {
          *pk = k;
          *pj = j;
          *pi = i;
          k = N1;
          j = N2;
          i = N3;
        }
      }
    }
  }
  return N3 + 1 == i;
}

Следующий поиск был написан неструктурным сразу с двух точек зрения. В нём используется не только выход из середины функции, но и трёхмерный массив приводится к одномерному, что невозможно в более строго типизированных языках, чем C. Теоретически, такой поиск мог бы стать самым быстрым.

extern bool search_linear(int a[N1][N2][N3], bool match(int), int *pk, int *pj, int *pi) {
  int i;
  for (i = 0; i < (N1 * N2 * N3); i += 1) {
    if (match(((int *)a)[i])) {
      *pk = i / (N3 * N2);
      *pj = i / N3 % N2;
      *pi = i % N3;
      return true;
    }
  }
  return false;
}

Затем я повторил подход с линеаризацией поиска, но уже строго в рамках структурности.

extern bool search_structline(int a[N1][N2][N3], bool match(int), int *pk, int *pj, int *pi) {
  int i, j, k;
  i = 0;
  j = 0;
  k = 0;
  while ((k < N1) && !match(a[k][j][i])) {
    if (i < N3 - 1) {
      i += 1;
    } else {
      i = 0;
      if (j < N2 - 1) {
        j += 1;
      } else {
        j = 0;
        k += 1;
      }
    }
  }
  *pi = i;
  *pj = j;
  *pk = k;
  return k < N1;
}

Напоследок, я создал поиск с помощью многоветочного while, известного также, как цикл Дейкстры. Поскольку С не поддерживает в явном виде такой цикл, то для его демонстрации я использовал запрещённый приём - определил макросы для имитации синтаксиса цикла.

extern bool search_multibranch(int a[N1][N2][N3], bool match(int), int *pk, int *pj, int *pi) {
  int i, j, k;
  i = 0;
  j = 0;
  k = 0;
  While (i < N3) && !match(a[k][j][i]) Do
    i += 1;
  Elsif (i >= N3) && (j < N2 - 1)      Do
    i  = 0;
    j += 1;
  Elsif (i >= N3) && (k < N1 - 1)      Do
    i  = 0;
    j  = 0;
    k += 1;
  End
  *pi = i;
  *pj = j;
  *pk = k;
  return i < N3;
}

Тестовая платформа 1

Процессор	tcc	gcc	clang
Intel® Core™ i3-4160 3.60GHz	0.9.2.7	6.3.0	4.0.0

1. Минимальное время работы образцов в миллисекундах

	return_p	return	linear	decomposed	outlimit	structline	multibranch
tcc	1023	889	704	847	892	884	887
gcc -O0	794	607	527	2635	609	659	650
gcc -O1	413	351	341	354	302	405	464
gcc -O2	379	301	341	380	351	351	353
gcc -O3	380	302	341	381	352	350	354
gcc -Os	504	413	402	456	529	477	420
clang -O0	816	619	534	807	622	802	615
clang -O1	379	297	344	360	297	302	297
clang -O2	372	294	340	363	295	299	295
clang -O3	373	294	341	365	295	299	295
clang -Os	413	294	284	369	294	350	295
g++ -O0	807	627	540	728	626	698	678
g++ -O1	415	355	343	357	305	358	415
g++ -O2	420	306	343	415	413	416	354
g++ -O3	417	304	341	421	409	412	353
g++ -Os	504	415	404	466	529	417	418
clang++ -O0	819	616	569	805	616	799	616
clang++ -O1	371	294	340	357	294	299	294
clang++ -O2	379	297	342	367	297	302	297
clang++ -O3	372	294	340	363	294	299	295
clang++ -Os	417	296	285	372	296	351	298

Тестовая платформа 2

Процессор	tcc	gcc	clang
Allwinner H3 ARM Cortex-A7 1.6GHz	0.9.2.6	5.4.0	3.8.0

2. Минимальное время работы образцов в миллисекундах

	return_p	return	linear	decomposed	outlimit	structline	multibranch
tcc	15707	13488	11755	12030	13489	13126	12976
gcc -O0	11680	8774	7553	9880	8774	9436	9116
gcc -O1	4988	2930	2739	3468	2952	3459	3292
gcc -O2	4654	2787	2763	3812	3295	3805	3630
gcc -O3	4650	2781	2757	3806	3291	3797	3624
gcc -Os	4658	3969	2924	4159	3626	3795	3625
clang -O0	9613	7219	5661	8326	7219	8901	7054
clang -O1	4821	2791	2799	2979	2777	2774	2946
clang -O2	4815	2781	2761	3805	2778	2773	2948
clang -O3	4823	2795	2767	3812	2785	2777	2953
clang -Os	4812	2776	2756	3801	2776	2771	2944
g++ -O0	11632	8727	7509	10180	8728	9730	9414
g++ -O1	4986	2883	2750	3638	2953	3459	3291
g++ -O2	4661	2786	2765	3815	3298	4317	3632
g++ -O3	4646	2775	2754	3802	3286	4303	3619
g++ -Os	4653	3461	2920	4154	3621	3962	3624
clang++ -O0	9611	7216	5659	8326	7217	8899	7051
clang++ -O1	4821	2788	2769	2984	2784	2776	2953
clang++ -O2	4817	2783	2762	3807	2781	2774	2949
clang++ -O3	4830	2811	2803	3816	2787	2781	2955
clang++ -Os	4817	2780	2760	3807	2780	2774	2949

Тестовая платформа 3

Процессор	clang
Intel Core i7 2.3GHz	Apple LLVM version 8.1.0 (clang-802.0.42)

3. Минимальное время работы образцов в миллисекундах

	return_p	return	linear	decomposed	outlimit	structline	multibranch
clang -O0	2071	787	680	975	785	952	776
clang -O1	466	442	432	449	382	381	442
clang -O2	464	442	432	449	382	380	442
clang -O3	508	382	370	447	442	380	382
clang -Os	508	442	370	448	442	441	443
clang++ -O0	949	825	742	975	824	952	776
clang++ -O1	467	442	433	448	382	380	442
clang++ -O2	463	442	432	449	382	380	442
clang++ -O3	514	390	376	454	448	386	386
clang++ -Os	514	448	375	454	448	447	451

Результаты измерений можно охарактеризовать как беспорядочные. Здесь есть и эпичный провал gcc при -O0 для decomposed(проявлялся стабильно, но теперь не наблюдаю), и более быстрое выполнения алгоритма при сборке с формально более слабой оптимизацией, например, варианта outlimit для gcc -O1 и -O2, и обмен местами алгоритмов по скорости в зависимости от опций, например, для ARM gcc -Os return оказался медленней outlimit и multibranch, хотя для -O3 всё было наоборот, есть и ощутимое различие в скорости работы одних и тех же алгоритмов при сборке с помощью gcc как С и как С++, что в гораздо меньшей степени проявляется на clang. Также можно отметить, что clang, в целом, более благосклонен к структурным алгоритмам, чем gcc. Если gcc в среднем компилирует структурные алгоритмы поиска хуже, чем неструктурные, то clang показывает высокую прыть и для структурного кода. При этом для некоторых уровней оптимизации структурные алгоритмы оказываются быстрей неструктурных, что чаще всего проявляется на Mac OS X.

В целом же, отклонение времени работы структурных алгоритмов от неструктурных таково, что даже при компиляции менее удачным gcc, нет смысла всерьёз беспокоиться о производительности подхода, кроме особенных случаев, количество которых гораздо меньше того, что чудится тем горе оптимизаторам, что готовы с головой окунуться в копеечную экономию с помощь перестановок переменных до того, как обнаружат узкие места программы и подберут алгоритм меньшей вычислительной сложности.

Как обычно, тест доступен на github.