Сообщение Re[38]: benchmark от 11.01.2017 23:34
Изменено 11.01.2017 23:41 Evgeny.Panasyuk
Re[38]: benchmark
Здравствуйте, lpd, Вы писали:
lpd>Во-первых, как я понял, ты пытаешься измерить задержки из-за cache-miss с помощью listа.
cache-miss'ы будут и в случае vector<int*> и в случае list<int>.
В случае с list<int> помимо cache-miss'а добавляется зависимость по данным — чтобы узнать адрес следующего узла, надо загрузить предыдущий и так далее — поэтому он и медленнее на два порядка, а не на один как vector<int*>.
Подобная зависимость по данным создаётся и в управляемом коде, где чтобы обратиться к полю под-объекта ... под-объекта объекта нужно сделать похожий забег по указателям, разве что цепочки не такие длинные.
Кстати, чтобы исключить эти cache-miss, достаточно закомментировать все сортировки — тогда получается следующий расклад:
* массив указателей в 2.5 раза медленее
* список медленее на порядок
lpd>Думаю, что это не очень хороший подоход,
Не очень хороший подход это компилировать без оптимизатора, а я сделал тест во вполне конкретных условиях, которые нисколько не скрывал
lpd>т.к. элементы list могут быть расположены в памяти последовательно.
Список обычно используется когда нужны какие-то фичи списка (внезапно, да) — типа splice'а, случайных удалений, вставок и т.п. — после чего узлы таки оказываются перемешанными
lpd>В моем же тесте, я точно обращаюсь к элементам в случайном порядке.
Я вообще-то сравниваю ТРИ варианта — в случае vector<int*> — как раз идёт обращение в случайном порядке
lpd>Во-вторых, ты измеряешь производительность stl контейнеров, а не процессора.
ШТА? Я уже выше привёл вывод ассемблера:
Покажи где тут "производительность stl контейнеров"
Итератор vector'а это по сути указатель, и даже если над ним тонкая обёртка в виде класса, то он всё равно оптимизируется в итоге до обычного указателя.
Или думаешь например там список как-то криво реализован с дополнительными индерекциями?
Я могу конечно всё расписать в рукопашную (и сравнить ASM выхлоп, который скорей всего будет идентичным), но пока не вижу в смысла
lpd>Результаты изменились:
lpd>Последовательное сложение с индирекцией оказалось ровно в два раза медленне, чем с индирекцией. Это ожидаемо, т.к. выполняется две инструкции, вместо одной.
Ты опять меряешь в инструкциях 
У тебя результат в примерно два раза медленней потому что тебе нужно перелопатить в два раз больший объём памяти, а алгоритм memory bandwidth bounded. Вместо одного массива, нужно выкачать два (причём одинакового размера). Замени массив четырёх-байтных индексов на массив восьми-байтных — и получишь другое соотношение, при том же количестве инструкций
lpd>Сложение со случайным доступом(и вечным cache-miss) оказалось еще в два раза медленнее, чем с последовательным. Это обозначает верхнюю границу эффективности кэша при доступе к данным, и для меня интересно.
Приведи конкретные цифры, в какой среде запускаешь, какие опции и т.п. Заполни map2 возрастающей последовательностью, а потом перетасуй std::random_shuffle — так чтобы у тебе гарантированно был обход всего массива.
lpd>Во-первых, как я понял, ты пытаешься измерить задержки из-за cache-miss с помощью listа.
cache-miss'ы будут и в случае vector<int*> и в случае list<int>.
В случае с list<int> помимо cache-miss'а добавляется зависимость по данным — чтобы узнать адрес следующего узла, надо загрузить предыдущий и так далее — поэтому он и медленнее на два порядка, а не на один как vector<int*>.
Подобная зависимость по данным создаётся и в управляемом коде, где чтобы обратиться к полю под-объекта ... под-объекта объекта нужно сделать похожий забег по указателям, разве что цепочки не такие длинные.
Кстати, чтобы исключить эти cache-miss, достаточно закомментировать все сортировки — тогда получается следующий расклад:
* массив указателей в 2.5 раза медленее
* список медленее на порядок
lpd>Думаю, что это не очень хороший подоход,
Не очень хороший подход это компилировать без оптимизатора, а я сделал тест во вполне конкретных условиях, которые нисколько не скрывал
lpd>т.к. элементы list могут быть расположены в памяти последовательно.
Список обычно используется когда нужны какие-то фичи списка (внезапно, да) — типа splice'а, случайных удалений, вставок и т.п. — после чего узлы таки оказываются перемешанными
lpd>В моем же тесте, я точно обращаюсь к элементам в случайном порядке.
Я вообще-то сравниваю ТРИ варианта — в случае vector<int*> — как раз идёт обращение в случайном порядке
lpd>Во-вторых, ты измеряешь производительность stl контейнеров, а не процессора.
ШТА? Я уже выше привёл вывод ассемблера:
.L152:
add edx, DWORD PTR [rax]
add rax, 4
cmp rcx, rax
jne .L152Покажи где тут "производительность stl контейнеров"
Итератор vector'а это по сути указатель, и даже если над ним тонкая обёртка в виде класса, то он всё равно оптимизируется в итоге до обычного указателя.
Или думаешь например там список как-то криво реализован с дополнительными индерекциями?
Я могу конечно всё расписать в рукопашную (и сравнить ASM выхлоп, который скорей всего будет идентичным), но пока не вижу в смысла
lpd>Результаты изменились:
lpd>Последовательное сложение с индирекцией оказалось ровно в два раза медленне, чем с индирекцией. Это ожидаемо, т.к. выполняется две инструкции, вместо одной.
Ты опять меряешь в инструкциях У тебя результат в примерно два раза медленней потому что тебе нужно перелопатить в два раз больший объём памяти, а алгоритм memory bandwidth bounded. Вместо одного массива, нужно выкачать два (причём одинакового размера). Замени массив четырёх-байтных индексов на массив восьми-байтных — и получишь другое соотношение, при том же количестве инструкций
lpd>Сложение со случайным доступом(и вечным cache-miss) оказалось еще в два раза медленнее, чем с последовательным. Это обозначает верхнюю границу эффективности кэша при доступе к данным, и для меня интересно.
Приведи конкретные цифры, в какой среде запускаешь, какие опции и т.п. Заполни map2 возрастающей последовательностью, а потом перетасуй std::random_shuffle — так чтобы у тебе гарантированно был обход всего массива.
Re[38]: benchmark
Здравствуйте, lpd, Вы писали:
lpd>Во-первых, как я понял, ты пытаешься измерить задержки из-за cache-miss с помощью listа.
cache-miss'ы будут и в случае vector<int*> и в случае list<int>.
В случае с list<int> помимо cache-miss'а добавляется зависимость по данным — чтобы узнать адрес следующего узла, надо загрузить предыдущий и так далее — поэтому он и медленнее на два порядка, а не на один как vector<int*>.
Подобная зависимость по данным создаётся и в управляемом коде, где чтобы обратиться к полю под-объекта ... под-объекта объекта нужно сделать похожий забег по указателям, разве что цепочки не такие длинные.
Кстати, чтобы исключить эти cache-miss, достаточно закомментировать все сортировки — тогда получается следующий расклад:
* массив указателей в 2.5 раза медленее
* список медленее на порядок
lpd>Думаю, что это не очень хороший подоход,
Не очень хороший подход это компилировать без оптимизатора, а я сделал тест во вполне конкретных условиях, которые нисколько не скрывал
lpd>т.к. элементы list могут быть расположены в памяти последовательно.
Список обычно используется когда нужны какие-то фичи списка (внезапно, да) — типа splice'а, случайных удалений, вставок и т.п. — после чего узлы таки оказываются перемешанными
lpd>В моем же тесте, я точно обращаюсь к элементам в случайном порядке.
Я вообще-то сравниваю ТРИ варианта — в случае vector<int*> — как раз идёт обращение в случайном порядке
lpd>Во-вторых, ты измеряешь производительность stl контейнеров, а не процессора.
ШТА? Я уже выше привёл вывод ассемблера:
Покажи где тут "производительность stl контейнеров"
Итератор vector'а это по сути указатель, и даже если над ним тонкая обёртка в виде класса, то он всё равно оптимизируется в итоге до обычного указателя.
Или думаешь например там список как-то криво реализован с дополнительными индерекциями?
Я могу конечно всё расписать в рукопашную (и сравнить ASM выхлоп, который скорей всего будет идентичным), но пока не вижу в смысла
lpd>Результаты изменились:
lpd>Последовательное сложение с индирекцией оказалось ровно в два раза медленне, чем с индирекцией. Это ожидаемо, т.к. выполняется две инструкции, вместо одной.
Ты опять меряешь в инструкциях
У тебя результат в примерно два раза медленней потому что тебе нужно перелопатить в два раз больший объём памяти, а алгоритм memory bandwidth bounded. Вместо одного массива, нужно выкачать два (причём одинакового размера). Замени массив четырёх-байтных индексов на массив восьми-байтных — и получишь другое соотношение, при том же количестве инструкций
lpd>Сложение со случайным доступом(и вечным cache-miss) оказалось еще в два раза медленнее, чем с последовательным. Это обозначает верхнюю границу эффективности кэша при доступе к данным, и для меня интересно.
Приведи конкретные цифры, в какой среде запускаешь, какие опции и т.п. Заполни map2 возрастающей последовательностью, а потом перетасуй std::random_shuffle — так чтобы у тебе гарантированно был обход всего массива.
lpd>Во-первых, как я понял, ты пытаешься измерить задержки из-за cache-miss с помощью listа.
cache-miss'ы будут и в случае vector<int*> и в случае list<int>.
В случае с list<int> помимо cache-miss'а добавляется зависимость по данным — чтобы узнать адрес следующего узла, надо загрузить предыдущий и так далее — поэтому он и медленнее на два порядка, а не на один как vector<int*>.
Подобная зависимость по данным создаётся и в управляемом коде, где чтобы обратиться к полю под-объекта ... под-объекта объекта нужно сделать похожий забег по указателям, разве что цепочки не такие длинные.
Кстати, чтобы исключить эти cache-miss, достаточно закомментировать все сортировки — тогда получается следующий расклад:
* массив указателей в 2.5 раза медленее
* список медленее на порядок
lpd>Думаю, что это не очень хороший подоход,
Не очень хороший подход это компилировать без оптимизатора, а я сделал тест во вполне конкретных условиях, которые нисколько не скрывал
lpd>т.к. элементы list могут быть расположены в памяти последовательно.
Список обычно используется когда нужны какие-то фичи списка (внезапно, да) — типа splice'а, случайных удалений, вставок и т.п. — после чего узлы таки оказываются перемешанными
lpd>В моем же тесте, я точно обращаюсь к элементам в случайном порядке.
Я вообще-то сравниваю ТРИ варианта — в случае vector<int*> — как раз идёт обращение в случайном порядке
lpd>Во-вторых, ты измеряешь производительность stl контейнеров, а не процессора.
ШТА? Я уже выше привёл вывод ассемблера:
.L152:
mov rcx, QWORD PTR [rax]
add rax, 8
add edx, DWORD PTR [rcx]
cmp rsi, rax
jne .L152.L152:
add edx, DWORD PTR [rax]
add rax, 4
cmp rcx, rax
jne .L152Покажи где тут "производительность stl контейнеров"
Итератор vector'а это по сути указатель, и даже если над ним тонкая обёртка в виде класса, то он всё равно оптимизируется в итоге до обычного указателя.
Или думаешь например там список как-то криво реализован с дополнительными индерекциями?
Я могу конечно всё расписать в рукопашную (и сравнить ASM выхлоп, который скорей всего будет идентичным), но пока не вижу в смысла
lpd>Результаты изменились:
lpd>Последовательное сложение с индирекцией оказалось ровно в два раза медленне, чем с индирекцией. Это ожидаемо, т.к. выполняется две инструкции, вместо одной.
Ты опять меряешь в инструкциях У тебя результат в примерно два раза медленней потому что тебе нужно перелопатить в два раз больший объём памяти, а алгоритм memory bandwidth bounded. Вместо одного массива, нужно выкачать два (причём одинакового размера). Замени массив четырёх-байтных индексов на массив восьми-байтных — и получишь другое соотношение, при том же количестве инструкций
lpd>Сложение со случайным доступом(и вечным cache-miss) оказалось еще в два раза медленнее, чем с последовательным. Это обозначает верхнюю границу эффективности кэша при доступе к данным, и для меня интересно.
Приведи конкретные цифры, в какой среде запускаешь, какие опции и т.п. Заполни map2 возрастающей последовательностью, а потом перетасуй std::random_shuffle — так чтобы у тебе гарантированно был обход всего массива.