Pull to refresh

Comments 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]++; }
За все сказать не могу, но C# нет, а VC да. В любом случае, этот код дан только для простоты иллюстрации концепции, в более сложных случаях оптимизаций не будет, а зависимости останутся.
UFO just landed and posted this here
В идеале должна быть такая оптимизация кода:
<тут кода нет>

Так как переменные нигде больше не используются, то и делать над ними операции, и выделять под них память не нужно :)

В детстве при отладке боролся с оптимизацией путём вывода значений переменных на печать и т.п., иначе компилятор их и все действия над ними игнорировал :)
UFO just landed and posted this here
Еще как оптимизируют.

Без оптимизации:
первый: 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… и тд. на экран, то она тоже выкидывает цикл и ничего не делает… так что с компиляторами шутки плохи :)
Delphi блок кода выбрасывает, но при этом выдаёт хинт, что мол у вас тут ненужные операции присутствуют :)
Не работает такая операция только при операциях над данными, доступными извне т.к. такие ситуации нельзя предусмотреть на стадии компиляции.
Эх, забыл про превью :)

>> Не работает такая оптимизация…
В C/C++ вывод значения в этом смысле равносилен модификации volatile-переменной. Обычно так получается аккуратнее и точнее.
Спасибо за перевод! Интересный материал, а главное — серьезный подход автора к изучению и освещени темы.
Пожалуйста. Мне тоже материал очень понравился, что и сподвигло.
На практике вряд ли пригодится, но статья познавательная и интересная.
Спасибо!
Очень познавательно, слабо представлял себе механизм работы кэша, спасибо.
Спасибо большое за статью. На одну «тайну покрытую мраком» стало меньше )
Очень странные результаты в последнем примере. В Java я не смог добиться такого же результата. На моей машине результаты для трёх случаев составили соответственно: 88ms, 90ms и 41ms.
Примечательно, что разниа между mixed mode и comp mode в пределах погрешности измерения.
Увеличил 200.000.000 до 800.000.000 и получил следующее диапазоны (по четыре запуска на каждый из трёх случаев):
(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-платформы…
Хм, потестировал C# на домашней машине (E8500): 549 мс, 271 мс, 381 мс, т.е. результаты подтверждаются.

Интересно, почему на яве так быстро работает.
… или почему C# такой медленный :)
Вы про абсолютное время? Так ведь тачки разные… нельзя тут в лоб сравнивать… я о том, что первые два случая равнозначны, а третий выполняется быстрее, таким образом результат соответствует ожидаемому…
Думаю, надо посмотреть что генерирует JIT-компилятор… можно как-нибудь .NET-VM пнуть, чтобы она дампила сгенерированный машинный код?
UFO just landed and posted this here
Да, действительно, я когда-то давно читал, а эта статья напомнила мне именно его книгу :) Я бы сказал, что там примеры, демонстирирующие были менее интересными — примеры, как правило, были больше.
В книге очень много железячных подробностей о том, как работает память, кэш и т.д.
Таким вот незамысловатым методом проб и ошибок автор открыл для себя cache line size и особенности работы в SMP, которые тем, кто этим занимается известны давным давно :)

Вообще-то, об это написано в первых же советах по оптимизации алгоритмов на сайте developer.intel.com.

Что касается тестов и оптимизации компилятором, то, как правильно пишется выше в комментах, циклы эти могут распознаться, как бесполезные и тупо могут быть выброшены из финального кода. Просто статиком здесь не поможешь. В конце цикла для надежности неплохо бы поставить хотя бы ASSERT с проверкой требуемого значения — чтобы было зафиксировано обращение к участку памяти — тогда можно и оптимизированный компилером код протестить.
Во многих случаях из реальной жизни эти вопросы, кстати, решаются использованием заточенного под SMP кэширующего bulk-аллокатора памяти, который сам определит размер cache line size и будет действовать соответственно.

По крайней мере обычному программисту обычных задач об этом париться не стоит.

Прогеру работающему в области highload, который использует все свое — аллокаторы, хэш-таблицы, кэшы и т.п. — вот ему это нужно.
Вряд ли «автор открыл для себя cache line size», скорее на примерах подвёл читателя к пониманию cache line size.
Просто шикарная статья, спасибо за перевод.
Статья отличная, хотя несколько обидно, что труды человека по имени Igor Ostrovsky приходится переводить на русский :)
И я подумал… Да и комментариев у оригинала больше…
Спасибо, очень познавательно, а главное все понятно!
Как только взглянул на название статьи, — она сразу стала моей любимой!
Все! распечатаю эту статью, буду носить ее с собой и молиться на нее.
ЗЫ какие хакеры оверклокеры это писали?!!!
Кому что не понравилось в моем комментарии!? еще и карму -2 сняли. я просто хотел сказать что это классная статья. разве важно какими эпитетами и сравнениями я это делаю?
хабрабыдло атакует
У меня стирание буфера под экран заняло 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;
}
}
}

Предлагаю попробовать сделать быстрее :)
Быстрее будет если:

1) Выровнять начало массива на границу 16 байт
2) Использовать sse регистр
3) Использовать non-temporary store инструкции

Эффект непосредственно от третьего пункта будет заключаться в невытеснении данных из L2/L3.
То есть, если до стирания экрана в L2/L3 находились данные, которые будут использоваться после стирания экрана — будет ускорение.
респект за перевод. давно качественного материала не видел). безусловно, в золотой фонд хабра.
Как в данных тестах учитывалось влияние работы фоновых процессов и ядра операционной системы, ведь они используют тот же самый кэш?
На некоторых графиках-диаграммах видно это влияние, например, кэш L2 немного раньше истощается.
зачем заниматься такой низкоуровневой оптимизацией?
где вы видели задачи, когда можно без ущерба для заказчика обсчитывать не каждый элемент массива, а только каждый 16-й?
как вы думаете, не лучше ли просто оптимизировать высокоуровневый алгоритм или вообще заменить его другим, чем пытаться оптимизировать под конкретную модификацию процессора?
Эммм… Компьютерные игры? :) Уверяю Вас, без оптимизации игра уровня Call Of Duty отрабатывала бы намного и намного медленнее :)
вы думаете на fps сильно влияют оптимизации такого уровня?
я считаю что не влияют. на fps в большей степени влияет видеокарта и то, что происходит внутри нее, а не в cpu
не каждая современная игра занимает все (много) ресурсов процессора
ну не правда. cpu тоже нагружается зачастую, например — ту же физику обсчитывает, и разве что PhysX и иже с ними иногда помогают.
Sign up to leave a comment.

Articles