[flame] умеют ли компиляторы оптимизировать код? [re: так верст]

Sachaa

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

Maurog

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

Sachaa

Себя же цитирую:
умеет, например, объявлять и определять шаблонные функции в разных единицах трансляции
Для буквоедов: умеет экспортировать шаблоны.
Название этого компилятора не помню. И никогда им не пользовался. Под современными компиляторами я подразумеваю GNU компиляторы, Visual C++ и Intel C++. Хотя интеловские (вроде) что-то как-то умеют в этом плане. Да и дело не в этом. Дело в современности.

salamander

Компиляторы не умеют адекватно разворачивать, например, тройной вложенный цикл. Пример: произведение матриц.
У меня GCC-4.5.2, как и ожидалось, развернул внутренний цикл. ЧЯДНТ?
Элсо, хороший, годный тролль. Сумел обосрать всех и вся, не предъявив при этом никаких конкретных претензий, так что и возразить-то ему нечего.
Да, расскажи что-ли что такое по-твоему современный компилятор? А то только говоришь, что все современные компиляторы недостаточно современны...

marat7256

Да, расскажи что-ли что такое по-твоему современный компилятор?
Современный компилятор должен уметь сам писать и транслировать программу по команде "Хочу, чтобы было з@ебись!". Ну, в самом крайнем случае, должен уметь исправлять синтаксические ошибки в программе самостоятельно, а не выплевывая ошибки!

Sachaa

0) Как всегда, учимся читать.
1) Как ты понял, что он его развернул?
2) Внутренний цикл? Похвально! Я-то думал, что GCC один из самых современных среди современных... (Разъяснение для тугих: внутренний цикл почти любой сложности можно руками за считанные минуты развернуть (даже до шага 8). И? Говоря о современности, компиляторы это должны были уметь делать еще тогда, когда появились циклы. Напомнишь дату? )
Я написал пример, в котором компилятор бессилен, и даже gcc 4.5.2:


for (int i = 0; i < m; ++i)

{

 for (int j = 0; j < l; ++j)

 {

  r[l * i + j] = 0.0;

  for (int k = 0; k < n; ++k)

   r[l * i + j] += a[n * i + k] * b[l * k + j];

 }

}

Если ты не дурак, то ты поймешь, что значит бессилен. Если-таки непонятно, то это значит, что ускорения не будет.
Тебе истолковать значение слова "современный"?! Зачем ты вообще здесь отписался? А возражать бывает нечего еще тогда, когда возразить нечего. Подумай об этом, когда будешь разворачивать цикл в примере ;)
Короче, не кричи "гоп" пока не убежал.

apl13

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

salamander

Тебе истолковать значение слова "современный"?!
Мне истолковать, что ты понимаешь под "современный компилятор". Судя по контексту, это что-то отличное от русского прилагательного "современный" прицепленного к слову компилятор.
Зачем ты вообще здесь отписался?
Давно котлет из троллей не ел. Вот, решил сделать.
1) Как ты понял, что он его развернул?
Посмотрел полученный ассемблер.
2) Внутренний цикл? Похвально! Я-то думал, что GCC один из самых современных среди современных... (Разъяснение для тугих: внутренний цикл почти любой сложности можно руками за считанные минуты развернуть (даже до шага 8). И? Говоря о современности, компиляторы это должны были уметь делать еще тогда, когда появились циклы. Напомнишь дату? )
Эмм... А накой тебе разворачивать внешний-то понадобилось? При развороте внутреннего понятно откуда бонус приходит: экономии на переходах и инкрементах счетчика, даем больше пространства шедулеру (как в компиляторе, так и аппаратному, если у нас out-of-order).
Я написал пример, в котором компилятор бессилен, и даже gcc 4.5.2:
Громкое заявление. Сейчас проверим.
Если ты не дурак, то ты поймешь, что значит бессилен. Если-таки непонятно, то это значит, что ускорения не будет.
Ускорения относительно чего? Видимо оптимизированного кода относительно неоптимизированного, сгенерированного тем же самым компилятором?.. Мда, тяжело тебе дается формулирование мыслей, тяжело.
Ладно, поехали эксперименты делать.
mm2.c:
void fuu(double *a, double *b, double *r, int m, int l, int n)

{

	for (int i = 0; i < m; ++i)

	{

		for (int j = 0; j < l; ++j)

		{

			r[l * i + j] = 0.0;

			for (int k = 0; k < n; ++k)

				r[l * i + j] += a[n * i + k] * b[l * k + j];

		}

	}

}

mmm.c:
#include <stdio.h>



#define N 1000



void fuu(double *a, double *b, double *r, int m, int l, int n);



double a[N * N], b[N * N], c[N * N];



int main(void)

{

    int i;

    double res = 0.0;

    for (i = 0; i < N * N; i++) {

        a[i] = 2 * i + 3;

        b[i] = 3 * i + 7;

    }

    fuu(a, b, c, N, N, N);

    for (i = 0; i < N * N; i++)

        res += c[i];

    printf("%0.2f\n", res);

    return 0;

}

Строки компиляции (gcc (Ubuntu/Linaro 4.5.2-8ubuntu4) 4.5.2):


gcc -W -Wall -std=c99 -march=native mm2.c mmm.c -o mm_o0

gcc -W -Wall -std=c99 -march=native  -mfpmath=sse -msse -msse2 -msse3 -mssse3 -msse4.1 mm2.c mmm.c -o mm_o0_sse

gcc -W -Wall -O3 -funroll-loops -ftree-vectorize -std=c99 -march=native mm2.c mmm.c -o mm_o3

gcc -W -Wall -O3 -funroll-loops -ftree-vectorize -std=c99 -march=native -mfpmath=sse -msse -msse2 -msse3 -mssse3 -msse4.1 mm2.c mmm.c -o mm_o3_sse

gcc -W -Wall -O3 -fno-unroll-loops -std=c99 -march=native -mfpmath=sse -msse -msse2 -msse3 -mssse3 -msse4.1 mm2.c mmm.c -o mm_o3_nounroll_sse

Запуски:
$ time ./mm_o3_sse

1500508499510990995456.00



real	0m5.381s

user	0m5.296s

sys	0m0.036s  

$ time ./mm_o3

1500508499510992568320.00



real	0m5.645s

user	0m5.616s

sys	0m0.024s  

$ time ./mm_o0

1500508499510992568320.00



real	0m17.283s

user	0m17.245s

sys	0m0.036s  

$ time ./mm_o0_sse

1500508499510990995456.00



real	0m16.063s

user	0m15.905s

sys	0m0.056s

Комбинация анроллинга с векторизатором, кстати, тоже небольшой, но измеряемый, выигрыш дает, чего я не ожидал (тело цикла достаточно большое, а векторизатор на нем ничего не векторизует)
$ time ./mm_o3_nounroll_sse; time ./mm_o3_sse

1500508499510990995456.00



real	0m5.386s

user	0m5.372s

sys	0m0.012s

1500508499510990995456.00



real	0m5.342s

user	0m5.320s

sys	0m0.020s



$ time ./mm_o3_nounroll_sse; time ./mm_o3_sse

1500508499510990995456.00



real	0m5.451s

user	0m5.340s

sys	0m0.060s

1500508499510990995456.00



real	0m5.405s

user	0m5.364s

sys	0m0.040s



$ time ./mm_o3_sse; time ./mm_o3_nounroll_sse

1500508499510990995456.00



real	0m5.390s

user	0m5.352s

sys	0m0.036s

1500508499510990995456.00



real	0m5.473s

user	0m5.404s

sys	0m0.020s



$ time ./mm_o3_sse; time ./mm_o3_nounroll_sse

1500508499510990995456.00



real	0m5.464s

user	0m5.352s

sys	0m0.060s

1500508499510990995456.00



real	0m5.492s

user	0m5.392s

sys	0m0.048s

Ну так что там про бессилие комплятора?

salamander

Говоря о современности, компиляторы это должны были уметь делать еще тогда, когда появились циклы.
Кстати говоря, когда появились циклы компиляторов еще и в помине не было. Так что опять мимо.

Sachaa

Так ну что, как и предполагалось. Не убежал, а орешь.
запуски твоего кода fuu у меня:


$ time ./mm_o3_sse

1500508499510990995456.00

real	0m9.175s

user	0m9.169s

sys	0m0.008s



$ time ./mm_o3_nounroll_sse 

1500508499510990995456.00



real	0m9.282s

user	0m9.265s

sys	0m0.012s

btw, gcc version 4.4.5 (Debian 4.4.5-8)
Эмм... А накой тебе разворачивать внешний-то понадобилось? При развороте внутреннего понятно откуда бонус приходит: экономии на переходах и инкрементах счетчика, даем больше пространства шедулеру (как в компиляторе, так и аппаратному, если у нас out-of-order).
запуски моего кода fuu (накой-то все-таки я это сделал):


$ time ./mm_o3_sse

1500508499510990995456.00



real	0m2.867s

user	0m2.856s

sys	0m0.008s



$ time ./mm_o3_nounroll_sse 

1500508499510990995456.00



real	0m2.809s

user	0m2.796s

sys	0m0.012s

Подумай над этим.
Ты, я смотрю, очень много знаешь о компиляторах. Не пойму только зачем ты эти понты с SSE нарезаешь и прочим. За начитанного хотел сойти? Смешно.
Далее. Как я и говорил, компилятор ни насколько не ускорил программу своим разворачиванием цикла. Взгляни на свои цифери еще разок. А я ускорил в 4 раза. И без выебонов.
Отмечу вот кое что. Вот время развернутого цикла, но не оптизимрованного:


$ time ./mm_o0

1500508499510990995456.00



real	0m6.010s

user	0m5.988s

sys	0m0.020s

А вот время оптимизированного, но не развернутого:


$ time ./mm_o3

1500508499510990995456.00



real	0m9.204s

user	0m9.189s

sys	0m0.012s

Вывод сказать, или сам поймешь? Хотя сие вряд ли изменит твои знания о компиляторах...
Потом. Про циклы и компиляторы — это был сарказм, чтобы ты понял, что значит современность. Циклам уже как Христу, а разворачивать до сих пор не умеют.
Кинуть код развернутого цикла? или сам на досуге подумаешь?

salamander

Кинуть код развернутого цикла, или сам на досуге подумаешь?
Кидай-кидай. А то пока ты только понты кидаешь.

Sachaa

Понты пока только ты кидал ;)
На, внемли


void fuu(double *a, double *b, double *r, int m, int l, int n)

{

	double s1, s2, s3, s4;

	for(int i = 0; i < m - 1; i += 2)

	{

		for(int j = 0; j < n - 1; j += 2)

		{

			s1 = s2 = s3 = s4 = 0.0;

			for(int k = 0; k < l; ++k)

			{

				s1 += a[i * l + k    ] * b[k * n + j    ];

				s2 += a[i * l + k    ] * b[k * n + j + 1];

				s3 += a[i * l + k + l] * b[k * n + j    ];

				s4 += a[i * l + k + l] * b[k * n + j + 1];

			}

			r[i * n + j	   ] = s1;

			r[i * n + j + 1    ] = s2;

			r[i * n + j + n    ] = s3;

			r[i * n + j + n + 1] = s4;

		}

	}

	if(m & 1)

	{

		for(int j = 0; j < n - 1; j += 2)

		{

			s1 = s2 = 0.0;

			for(int k = 0; k < l; ++k)

			{

				s1 += a[m * l - l + k] * b[k * n + j    ];

				s2 += a[m * l - l + k] * b[k * n + j + 1];

			}

			r[m * n - n + j    ] = s1;

			r[m * n - n + j + 1] = s2;

		}

	}

	if(n & 1)

	{

		for(int i = 0; i < m - 1; i += 2)

		{

			s1 = s2 = 0.0;

			for(int k = 0; k < l; ++k)

			{

				s1 += a[i * l + k    ] * b[k * n + n - 1];

				s2 += a[i * l + k + l] * b[k * n + n - 1];

			}

			r[i * n + n - 1    ] = s1;

			r[i * n + n - 1 + m] = s2;

		}

	}

	if(m & n & 1)

	{

		s1 = 0.0;

		for(int k = 0; k < l; ++k)

			s1 += a[m * l - l + k] * b[k * n + n - 1];

		r[m * n - n + n - 1] = s1;

	}

}

По-хорошему, компиляторы могли бы еще делать и блочные реализации по требованию, т.к. оно сильно связано с процессором и памятью, но не с логикой программы. А это еще порядки в скорости. Вот где современность. А вместо этого они уже лет 15 мурыжат стандарт C++0x, который уже устарел...

Dasar

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

Sachaa

реализована лишь самая малость
лишь самое простое ;)

procenkotanya

Ты предъявляешь не разворачивание внешних циклов, а блокинг по двум внешним с размером блока 2х2 с последующим разворотом внутренних циклов, имеющих по две итерации. Выходит, у тебя с формулированием мыслей не всё в порядке. Сказал бы сразу нормально — никто бы не привязался. Любой специалист, занимающийся компиляторами, тебе подтвердит, что то, что ты показываешь, unrolling'ом внешних циклов не называют.

Sachaa

Ты предъявляешь не разворачивание внешних циклов, а блокинг по двум внешним с размером блока 2х2 с последующим разворотом внутренних циклов, имеющих по две итераци
Выходит, что кто-то занимается буквоедством. В данном примере относительно циклов происходит разворачивание с шагом 2. КЮ Богачев называл это разворачиванием, ему я верю.
Но тем не менее, существует unrolling внешних циклов? И чем оно отличается от этого?

procenkotanya

а существует unrolling внешних циклов?
Теоретически — можно представить, что существует, по аналогии с применяемым обычно для внутренних, на практике не встречал. Практический смысл неясен.
КЮ Богачев называл это разворачиванием, ему я верю.
Хм. Я бы назвал это неудачным выбором термина. Это существенно менее тривиальное преобразование по сравнению с обычным разворотом, и смешивать их не следовало бы.
И раз уж ты знаком с блочной оптимизацией циклов — ты согласен, что твой вариант, как я писал выше, это частный случай блокинга (2х2, по i и по j)?

Sachaa

частный случай блокинга (2х2, по i и по j)
Блоки 2х2, конечно, узреть можно. Перебираем по i и по j. Однако, я не вижу принципиального противоречия термину "разворачивание". Кроме того, что во внутренний цикл вставляем дополнительные инструкции.

salamander

Не хочу тебя огорчать... но твой код не работает в случае, когда массив r перекрывается с одним из a и b.

Sachaa

 :shocked: :shocked: :shocked:
, а ты говоришь о компиляторах и о специалистах :D
Я даже не знаю что и, главное, как тебе ответить...Но попробую:
Не хочу тебя огорчать... но мой код работает быстрее твоего в разы. А перекрыв эти массивы ты в любом из кодов получишь неверный результат. Вообще, откуда пришла идея перекрывать входные и выходные данные?..

procenkotanya

Однако, я не вижу принципиального противоречия термину "разворачивание".
Loop unrolling:
было


for (i = 0; i < 2*n; i++)

  S(i);

стало


for (i = 0; i < 2*n; i+=2)

  {

    S(i);

    S(i+1);

  }

Для сохранения корректности никаких дополнительных знаний о S не требуется.
Blocking 2x2
было


for (i = 0; i < 2*n; i++)

  for (j = 0; j < 2*m; j++)

    S(i, j);

стало


for (i = 0; i < 2*n; i+=2)

  for (j =0; j < 2*m; j+=2)

    {

      S(i, j);

      S(i, j+1);

      S(i+1, j);

      S(i+1, j+1);

    }

Для сохранения корректности требуется доказать, что S(2u+1, 2v) можно выполнять перед S(2u, 2v+2) (что в твоём примере, кстати, неверно — не хватает квалификаторов restrict).

procenkotanya

, а ты говоришь о компиляторах и о специалистах :D
Я даже не знаю что и, главное, как тебе ответить...
Можешь мне не отвечать. То, что я не написал об этой проблеме не означает, что я её не замечал.
Специалисты по компиляторам подсказывают, что в таких случаях компилятор может сделать [alias-based] loop versioning, что как и все эти блокинги и анроллинги экспоненциально увеличит размер кода функции.

Sachaa

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

salamander

Не хочу тебя огорчать... но мой код работает быстрее твоего в разы. А перекрыв эти массивы ты в любом из кодов получишь неверный результат.
Код выполняет вычисления, получает результат, нигде по пути не возникает undefined behaviour. С точки зрения компилятора код верен. То, что ответ не устраивает программиста - ошибка программиста, написавшего неверный алгоритм.
Если в результате оптимизации программа начала выдавать другой ответ - это ошибка компилятора.
Ты можешь изменять программу используя дополнительные знания про решаемую задачу, а компилятор - нет. Пока ты ему эти знания не передашь. В данном случае это делается просто и моноид уже написал как.
Но пока это не сделано данная оптимизация (как оптимизация, а не изменение кода программистом по своему усмотрению) является некорректной.
Вообще, откуда пришла идея перекрывать входные и выходные данные?..
Используется повсеместно. Например в сортировках.

Sachaa

В сортировке входные данные являются выходными. А тут есть отдельно входные и выходные. Защита от дураков на таком уровне в математических приложениях не делается. Запомни.

salamander

В сортировке входные данные являются выходными. А тут есть отдельно входные и выходные. Защита от дураков на таком уровне в математических приложениях не делается. Запомни.
"Как всегда, учимся читать"
А именно всю первую часть моего предыдущего поста. Ведь мы же про оптимизации в компиляторах сейчас говорим, не?

Sachaa

Оптимизированная корректная процедура, как и сама корректная процедура, гарантирует корректный результат только при корректных входных данных. Это если о корректности. Про корректность входных данных обычно пишется в мануалах, в остальных случаях — в голове у программиста.
Хочется спросить: "че доебался?". Разве непонятно? ты подаешь некорректные данные, результат не определен. Что удивительного?
Ты просил пример, я тебе его дал. Ты мне ничего кроме понтов с SSE и векторизатором не показал. Я это умел "в 4 года". Если ты такая загадочная и запутанная личность, расставляй рестрикты и прочее.

Dasar

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

bleyman

основная проблема, конечно, что компилятор сам не умеет отличать важное от неважного, а способы для описания такой информации на текущий момент не разработаны
Неправильно вопрос ставишь. Твой язык должен позволять тебе поставить задачу без упоминания неважных деталей, тогда и отличать важное от неважного не придётся. Посмотри на numpy например, не говоря уж о стрёмных вещах типа J или K. Или SQL, раз уж речь зашла.
Это С и потом С++ зашли в тупик: вначале было очень выгодно позволить программисту руками указывать всякие детали, а сейчас обнаруживается, что компилятор-то эти детали и получше указал бы, но не может, потому что программист их уже указал, а "декомпилировать" сурцы в идею и компилировать её обратно в код ужасно тяжело.

Dasar

Для сохранения корректности требуется доказать, что S(2u+1, 2v) можно выполнять перед S(2u, 2v+2) (что в твоём примере, кстати, неверно — не хватает квалификаторов restrict).
т.е. утверждается, что можно так разметить код, что тот же gcc сможет сгенерить код эквивалентный блокингу?

Sachaa

но компилятору же никто не мешал сделать две версии: быструю для неперекрывающихся массивов и медленную для перекрывающихся... выбор нужной версии даже в runtime-е о-малое по сравнению с работой самого алгоритма.
В данном примере обе версии давали бы неверный ответ (или некорректный). Так что говорить тут не о чем. Просто господин хочет хоть за что-то зацепиться.

Dasar

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

Dasar

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

Sachaa

Да, теперь понятно. Не я один плохо излагаю мысли :)

Dasar

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

elenangel

gcc 4.4.5 скомпилировал 
unsigned rol(unsigned x)

{

	size_t intlen = sizeof(x)*8-1;

	return x & (1<<intlen>>intlen)|(x<<1);

}

в ассемблерную инструкцию rol при -O2

deniska

А можно мне в вашей специальной олимпиаде поучавствовать?
Если уж разрешать переставлять порядок вычисления, то почему сразу не сделать так?


void fuu(double *a, double *b, double *r, int m, int l, int n)

{

    double * pr = r;

    for (int i = 0; i < (m*n); ++i)

        *pr++ = 0.0;

    for (int i = 0; i < m; ++i)

    {

        double * pb = b;

        for (int j = 0; j < l; ++j)

        {

            double d = *a++;

            pr = r + n*i;

            for (int k = 0; k < n; ++k)

                *pr++ += d * *pb++;

        }

    }

}

Вроде как это первое, что тут должно в голову приходить, а никак не умножение блоками 2 на 2. Ну и (по крайней мере на моем ноуте) это в 2 раза быстрее выходит, чем блоки 2 на 2.

Papazyan

поучавствовать
ПоучаВствуй, поучаВствуй.

apl13

основная проблема, конечно, что компилятор сам не умеет отличать важное от неважного
Профилирование же.
а способы для описания такой информации на текущий момент не разработаны
Прагмы ручные? А не устанешь каждую performance critical строчку описывать?

apl13

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

deniska

По-хорошему, компиляторы могли бы еще делать и блочные реализации по требованию, т.к. оно сильно связано с процессором и памятью, но не с логикой программы. А это еще порядки в скорости.
О, а можешь мой код ускорить на порядки, используя блочные реализации и развертывание циклов руками? При этом, конечно, не используя дополнительную память в большом размере, SSE, мульти трединг, видеокарты...
Вообще с моей точки зрения в данных задачах компилятор и не должен делать блочные развертки и остальное. Это все должно быть сделано в библиотеках, где авторы библиотеки знают и математику и ограничения на входные данные и что можно использовать для работы и на каких процессорах все это будет работать.
Требовать твоих оптимизаций от компилятора, мягко говоря, довольно сурово. Код после компилятора должен работать именно так, как написано (особенно если ты делаешь библиотеку и компилятор не знает как ее будут использовать). Ну и ты же не просишь компилятор заметить что у тебя идет умножение матриц и подменить его для больших матриц на алгоритм Штрассена? Разворачивает простые циклы и хорошо, больше в нормальной жизни почти и не надо. Для всех мат задач (собственно только в них время циклов сопоставимо с временем вычисления внутреннего блока) можно использовать библиотеки, например Numerical Recipes.

apl13

Код после компилятора должен работать именно так, как написано (особенно если ты делаешь библиотеку и компилятор не знает как ее будут использовать). Ну и ты же не просишь компилятор заметить что у тебя идет умножение матриц и подменить его для больших матриц на алгоритм Штрассена? Разворачивает простые циклы и хорошо, больше в нормальной жизни почти и не надо.
А автомобиль у тебя с ручной коробкой.

Papazyan

Требовать твоих оптимизаций от компилятора, мягко говоря, довольно сурово. Код после компилятора должен работать именно так, как написано (особенно если ты делаешь библиотеку и компилятор не знает как ее будут использовать). Ну и ты же не просишь компилятор заметить что у тебя идет умножение матриц и подменить его для больших матриц на алгоритм Штрассена? Разворачивает простые циклы и хорошо, больше в нормальной жизни почти и не надо. Для всех мат задач (собственно только в них время циклов сопоставимо с временем вычисления внутреннего блока) можно использовать библиотеки, например Numerical Recipes.
В случае перемножения матриц ограничение не в скорости процессора, а в размере кеша. Поэтому вменяемую универсальную оптимизацию вообще не сделать.

deniska

В случае перемножения матриц ограничение не в скорости процессора, а в размере кеша. Поэтому вменяемую универсальную оптимизацию вообще не сделать.
А что ты от компилятора С++ хочешь? Он, насколько я понимаю, не обязан собирать код привязанный к конкретной машине. Точнее даже наоброт, его код должен работать везде "примерно" одинаково. Вот какой-нить интерпритатор С# кода мог бы в теории это использовать.
Кроме того, даже если я знаю размеры кэшей всех уровней, я сходу все равно не смогу сказать, как надо умножать матрицы. Скорее всего будет несколько уровней блоков, но это очень не очевидно. А у бедного компилятора даже курсов линейной алгебры не было, ему еще труднее. Разве что все равернуть на N^3 присваиваний а потом попробовать выбрать оптимальный порядок присваиваний. Но боюсь даже если N зафиксировать, то компиляция будет очень долгой.
PS
Блоками на своем ноуте я смог еще ускорить где-то в 1.5 раза, но это все. Можно, конечно, попробовать развернуть циклы самому (через template) но не уверен, что это хоть как-то поможет. Дальше можно ускорить тем, что взять свободную память и изменить порядок как мы храним элементы в матрице. Впрочем, в итоге все равно видеокарты в этой задаче все вынесут с большим отрывом.

Serab

Оптимизированная корректная процедура, как и сама корректная процедура, гарантирует корректный результат только при корректных входных данных. Это если о корректности. Про корректность входных данных обычно пишется в мануалах, в остальных случаях — в голове у программиста.
ты дебил или прикидываешься? компилятор хуй знает что там для тебя корректно, а что нет, он просто не имеет права менять поведение, вот и все.

elenangel

вспоминается байка про компилятор C который запись значения в ячейку памяти и последующее чтение соптимизировал выкинув запись-чтение. А к этой ячейки памяти был привязан I/O порт у контроллера.

Papazyan

А к этой ячейки памяти был привязан I/O порт у контроллера.
Криворукие программисты забыли поставить volatile?

apl13

Ну какбе для этого и придумали volatile, не?

elenangel

тащем-та да, но это ж байка

apl13

Это не байка, а реальное, вроде, положение дел на рынке лет надцать назад.
Тогда т. наз. компиляторы не умели стандарт ANSI, зато охотно производили некорректные оптимизации.
Ну и т. наз. программисты от них не отставали. Мне памятна другая байка, про что-то вроде "mov ax, чего-то там; and ax, 0", которое компилятор вполне закономерно превратил в "mov ax, 0", после чего программа перестала работать. Потому что and на тех примитивных архитектурах был еще сильно медленным, а т. наз. программист таким вот изящным методом обеспечил необходимую паузу при инициализации видеорежима.

amkharchenko

Можно поподробнее про некорректность оптимизаций и про "надцать лет назад".

Dasar

Прагмы ручные? А не устанешь каждую performance critical строчку описывать?
но это проще, чем ручные оптимизации, и более универсальный и переносимый метод

apl13

Подробнее нельзя, потому что я это читал лет пять или шесть назад.
Вроде некие чуваки в 94-м году проводили обзор рынка, находили, например, компиляторы, игнорирующие этот самый volatile, etc.
Оставить комментарий
Имя или ник:
Комментарий: