Комментарии 47
А мне казалось все современный компиляторы сами оптимизируют этот код:
int steps = 256 * 1024 * 1024;
int[] a = new int[2];
// первый
for (int i = 0; i < steps; i++) { a[0]++; a[0]++; }
// второй
for (int i = 0; i < steps; i++) { a[0]++; a[1]++; }
int steps = 256 * 1024 * 1024;
int[] a = new int[2];
// первый
for (int i = 0; i < steps; i++) { a[0]++; a[0]++; }
// второй
for (int i = 0; i < steps; i++) { a[0]++; a[1]++; }
За все сказать не могу, но C# нет, а VC да. В любом случае, этот код дан только для простоты иллюстрации концепции, в более сложных случаях оптимизаций не будет, а зависимости останутся.
В идеале должна быть такая оптимизация кода:
<тут кода нет>
Так как переменные нигде больше не используются, то и делать над ними операции, и выделять под них память не нужно :)
В детстве при отладке боролся с оптимизацией путём вывода значений переменных на печать и т.п., иначе компилятор их и все действия над ними игнорировал :)
<тут кода нет>
Так как переменные нигде больше не используются, то и делать над ними операции, и выделять под них память не нужно :)
В детстве при отладке боролся с оптимизацией путём вывода значений переменных на печать и т.п., иначе компилятор их и все действия над ними игнорировал :)
Еще как оптимизируют.
Без оптимизации:
первый: 1.148s
второй: 0.841s
gcc -O3:
первый: 0.008s
второй: 0.008s
Вывод: не пытаться играть в компилятор.
П.С. Особенно весело смотрится ассемблерный код до и после оптимизации:
До:
main:
.LFB0:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
movq %rsp, %rbp
.cfi_offset 6, -16
.cfi_def_cfa_register 6
movl $268435456, -4(%rbp)
movl $0, -8(%rbp)
jmp .L2
.L3:
movl -16(%rbp), %eax
addl $1, %eax
movl %eax, -16(%rbp)
movl -16(%rbp), %eax
addl $1, %eax
movl %eax, -16(%rbp)
addl $1, -8(%rbp)
.L2:
movl -8(%rbp), %eax
cmpl -4(%rbp), %eax
jl .L3
movl $0, %eax
leave
ret
.cfi_endproc
После:
main:
.LFB0:
.cfi_startproc
xorl %eax, %eax
ret
.cfi_endproc
Без оптимизации:
первый: 1.148s
второй: 0.841s
gcc -O3:
первый: 0.008s
второй: 0.008s
Вывод: не пытаться играть в компилятор.
П.С. Особенно весело смотрится ассемблерный код до и после оптимизации:
До:
main:
.LFB0:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
movq %rsp, %rbp
.cfi_offset 6, -16
.cfi_def_cfa_register 6
movl $268435456, -4(%rbp)
movl $0, -8(%rbp)
jmp .L2
.L3:
movl -16(%rbp), %eax
addl $1, %eax
movl %eax, -16(%rbp)
movl -16(%rbp), %eax
addl $1, %eax
movl %eax, -16(%rbp)
addl $1, -8(%rbp)
.L2:
movl -8(%rbp), %eax
cmpl -4(%rbp), %eax
jl .L3
movl $0, %eax
leave
ret
.cfi_endproc
После:
main:
.LFB0:
.cfi_startproc
xorl %eax, %eax
ret
.cfi_endproc
Да да, в Java если не печатать содержимое A, B… и тд. на экран, то она тоже выкидывает цикл и ничего не делает… так что с компиляторами шутки плохи :)
В C/C++ вывод значения в этом смысле равносилен модификации volatile-переменной. Обычно так получается аккуратнее и точнее.
Спасибо за перевод! Интересный материал, а главное — серьезный подход автора к изучению и освещени темы.
На практике вряд ли пригодится, но статья познавательная и интересная.
Спасибо!
Спасибо!
Очень познавательно, слабо представлял себе механизм работы кэша, спасибо.
Спасибо большое за статью. На одну «тайну покрытую мраком» стало меньше )
Очень странные результаты в последнем примере. В Java я не смог добиться такого же результата. На моей машине результаты для трёх случаев составили соответственно: 88ms, 90ms и 41ms.
Примечательно, что разниа между mixed mode и comp mode в пределах погрешности измерения.
Увеличил 200.000.000 до 800.000.000 и получил следующее диапазоны (по четыре запуска на каждый из трёх случаев):
(277ms — 286ms); (279ms — 291ms); (133ms — 142ms)
(277ms — 286ms); (279ms — 291ms); (133ms — 142ms)
Вероятно, на вашей машине сказываются какие-то побочные эффекты, связанные с процессором, системой, либо какая-то особенность .net JIT-компилятора.
PS: моя конфигурация
cy6ergn0m@cgmachine ~/test/mem $ uname -a
Linux cgmachine 2.6.31.12-desktop-3mnb #1 SMP Thu Mar 25 12:47:42 EDT 2010 x86_64 Intel® Core(TM)2 Duo CPU T5850 @ 2.16GHz GNU/Linux
cy6ergn0m@cgmachine ~/test/mem $ java -version
java version «1.6.0_20»
Java(TM) SE Runtime Environment (build 1.6.0_20-b02)
Java HotSpot(TM) 64-Bit Server VM (build 16.3-b01, mixed mode)
cy6ergn0m@cgmachine ~/test/mem $
PPS: эта конфигурация навела меня на мысль, что возможно у меня результаты отличаются от ваших из-за x86_64-платформы…
PS: моя конфигурация
cy6ergn0m@cgmachine ~/test/mem $ uname -a
Linux cgmachine 2.6.31.12-desktop-3mnb #1 SMP Thu Mar 25 12:47:42 EDT 2010 x86_64 Intel® Core(TM)2 Duo CPU T5850 @ 2.16GHz GNU/Linux
cy6ergn0m@cgmachine ~/test/mem $ java -version
java version «1.6.0_20»
Java(TM) SE Runtime Environment (build 1.6.0_20-b02)
Java HotSpot(TM) 64-Bit Server VM (build 16.3-b01, mixed mode)
cy6ergn0m@cgmachine ~/test/mem $
PPS: эта конфигурация навела меня на мысль, что возможно у меня результаты отличаются от ваших из-за x86_64-платформы…
Хм, потестировал C# на домашней машине (E8500): 549 мс, 271 мс, 381 мс, т.е. результаты подтверждаются.
Интересно, почему на яве так быстро работает.
Интересно, почему на яве так быстро работает.
… или почему C# такой медленный :)
Вы про абсолютное время? Так ведь тачки разные… нельзя тут в лоб сравнивать… я о том, что первые два случая равнозначны, а третий выполняется быстрее, таким образом результат соответствует ожидаемому…
Думаю, надо посмотреть что генерирует JIT-компилятор… можно как-нибудь .NET-VM пнуть, чтобы она дампила сгенерированный машинный код?
Таким вот незамысловатым методом проб и ошибок автор открыл для себя cache line size и особенности работы в SMP, которые тем, кто этим занимается известны давным давно :)
Вообще-то, об это написано в первых же советах по оптимизации алгоритмов на сайте developer.intel.com.
Что касается тестов и оптимизации компилятором, то, как правильно пишется выше в комментах, циклы эти могут распознаться, как бесполезные и тупо могут быть выброшены из финального кода. Просто статиком здесь не поможешь. В конце цикла для надежности неплохо бы поставить хотя бы ASSERT с проверкой требуемого значения — чтобы было зафиксировано обращение к участку памяти — тогда можно и оптимизированный компилером код протестить.
Вообще-то, об это написано в первых же советах по оптимизации алгоритмов на сайте developer.intel.com.
Что касается тестов и оптимизации компилятором, то, как правильно пишется выше в комментах, циклы эти могут распознаться, как бесполезные и тупо могут быть выброшены из финального кода. Просто статиком здесь не поможешь. В конце цикла для надежности неплохо бы поставить хотя бы ASSERT с проверкой требуемого значения — чтобы было зафиксировано обращение к участку памяти — тогда можно и оптимизированный компилером код протестить.
Во многих случаях из реальной жизни эти вопросы, кстати, решаются использованием заточенного под SMP кэширующего bulk-аллокатора памяти, который сам определит размер cache line size и будет действовать соответственно.
По крайней мере обычному программисту обычных задач об этом париться не стоит.
Прогеру работающему в области highload, который использует все свое — аллокаторы, хэш-таблицы, кэшы и т.п. — вот ему это нужно.
По крайней мере обычному программисту обычных задач об этом париться не стоит.
Прогеру работающему в области highload, который использует все свое — аллокаторы, хэш-таблицы, кэшы и т.п. — вот ему это нужно.
Вряд ли «автор открыл для себя cache line size», скорее на примерах подвёл читателя к пониманию cache line size.
Просто шикарная статья, спасибо за перевод.
Статья отличная, хотя несколько обидно, что труды человека по имени Igor Ostrovsky приходится переводить на русский :)
Спасибо, очень познавательно, а главное все понятно!
Как только взглянул на название статьи, — она сразу стала моей любимой!
«Эпическая работа» я бы сказал
У меня стирание буфера под экран заняло 2 миллисекунды. Делал примерно вот так:
unsafe
{
var uints = new Uint32[1024*768];
var size = uints.Length >> 1;
fixed(UInt32 *puints = uints)
{
UInt64 *strt = (UInt64 *)puints;
UInt64 *end = &((UInt64 *)puints)[size — 1];
UInt64 pixel = 0xffffff00ffffff00;
while(strt != end)
{
*strt++ = pixel;
}
}
}
Предлагаю попробовать сделать быстрее :)
unsafe
{
var uints = new Uint32[1024*768];
var size = uints.Length >> 1;
fixed(UInt32 *puints = uints)
{
UInt64 *strt = (UInt64 *)puints;
UInt64 *end = &((UInt64 *)puints)[size — 1];
UInt64 pixel = 0xffffff00ffffff00;
while(strt != end)
{
*strt++ = pixel;
}
}
}
Предлагаю попробовать сделать быстрее :)
Быстрее будет если:
1) Выровнять начало массива на границу 16 байт
2) Использовать sse регистр
3) Использовать non-temporary store инструкции
Эффект непосредственно от третьего пункта будет заключаться в невытеснении данных из L2/L3.
То есть, если до стирания экрана в L2/L3 находились данные, которые будут использоваться после стирания экрана — будет ускорение.
1) Выровнять начало массива на границу 16 байт
2) Использовать sse регистр
3) Использовать non-temporary store инструкции
Эффект непосредственно от третьего пункта будет заключаться в невытеснении данных из L2/L3.
То есть, если до стирания экрана в L2/L3 находились данные, которые будут использоваться после стирания экрана — будет ускорение.
респект за перевод. давно качественного материала не видел). безусловно, в золотой фонд хабра.
Как в данных тестах учитывалось влияние работы фоновых процессов и ядра операционной системы, ведь они используют тот же самый кэш?
зачем заниматься такой низкоуровневой оптимизацией?
где вы видели задачи, когда можно без ущерба для заказчика обсчитывать не каждый элемент массива, а только каждый 16-й?
как вы думаете, не лучше ли просто оптимизировать высокоуровневый алгоритм или вообще заменить его другим, чем пытаться оптимизировать под конкретную модификацию процессора?
где вы видели задачи, когда можно без ущерба для заказчика обсчитывать не каждый элемент массива, а только каждый 16-й?
как вы думаете, не лучше ли просто оптимизировать высокоуровневый алгоритм или вообще заменить его другим, чем пытаться оптимизировать под конкретную модификацию процессора?
Эммм… Компьютерные игры? :) Уверяю Вас, без оптимизации игра уровня Call Of Duty отрабатывала бы намного и намного медленнее :)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Галерея эффектов кэшей процессоров