Здравствуйте, kaa.python, Вы писали:
KP>Ну а если еще Mill CPU доведут до промышленного исполнения, то победа будет еще более весомой. Кстати, из лекции видно, что побороли не только и не столько кэши, но еще и prefetcher (кстати, как его на русском завать?), что сильно заметно на схемах за переделами L1 и L2.
Prefetcher уже очень давно является частью любого современного x86 CPU. Есть даже инструкция (SSE PREFETCH0-2), позволяющая подсказывать prefetcher-у, какуие адреса вы собираетесь читать.
Здравствуйте, kaa.python, Вы писали:
KP> Кстати, из лекции видно, что побороли не только и не столько кэши, но еще и prefetcher (кстати, как его на русском завать?), что сильно заметно на схемах за переделами L1 и L2.
Помимо prefertcher'а, не менее важно КПД использования memory bandwidth. Из памяти приходят не отдельные байты, а целые куски размером с cache-line — по 64 байта.
При работе с массивом КПД=100%, так как все элементы расположены вплотную. При работе же со связанным списком, из 64 полученных байт, полезной нагрузкой являются только 4 байта (в этом тесте использовались int32).
Здравствуйте, Jack128, Вы писали:
KP>>замеры производительности на вставках в середину массива и списка были для меня удивительным открытием. J>Э-э-э, он же списки чисел обрабатывает. Это не интересно и очевидно. Гораздо интереснее, если бы были вставки больших объектов. Ну там вектор векторов vs linked_list векторов.
Учитывая rv-refs или swaptimization, не вижу принципиальной разницы между вектором/списком из слов (int32) и из групп по три слова (std::vector).
Возможно ты подразумевал вектор/список из std::array<char, big_N>?
Здравствуйте, Qbit86, Вы писали:
A>>>кеши побороли асимптотику EP>>"асимптотика" одинаковая — перед вставкой и удалением делается линейный поиск. Q>antropolog говорил про асимптотику вставки, а не про асимптотику поиска места для вставки.
Так измеряется ведь общее время, т.е. Θ(N) + Θ(1) = Θ(N)
Здравствуйте, Jack128, Вы писали:
J>Э-э-э, он же списки чисел обрабатывает. Это не интересно и очевидно. Гораздо интереснее, если бы были вставки больших объектов. Ну там вектор векторов vs linked_list векторов. Ну и набор графиков, что будет есть вектора пустые. Или в них по 500 байт данных. Или по 1КБ, или по 10КБ..
Здравствуйте, niXman, Вы писали:
X>Здравствуйте, kaa.python, Вы писали:
KP>>Как следствие, использовать компоненты под GPLv3 где-то за пределами Linux стало не возможно X>хм.. так это что получается, если в венде использовать mingw, то каждая программа собранная mingw`ом — нарушает лицензию? а если программа распространяется в исходниках, то автор этих исходников нарушителем не является? X>(не силен в лицензиях и подобной лабуде)
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Помимо prefertcher'а, не менее важно КПД использования memory bandwidth. Из памяти приходят не отдельные байты, а целые куски размером с cache-line — по 64 байта. EP>При работе с массивом КПД=100%, так как все элементы расположены вплотную. При работе же со связанным списком, из 64 полученных байт, полезной нагрузкой являются только 4 байта (в этом тесте использовались int32).
на самом деле всё гораздо хуже. при последовательном чтении памяти запросы конвейризуются, и можно выжать 20-30 ГБ/с. при случайном чтении от отправки запроса до получения ответа проходит 40-50 нс. т.е. разница в b/w будет не в 16 раз, а в 300
Здравствуйте, BulatZiganshin, Вы писали:
EP>>Помимо prefertcher'а, не менее важно КПД использования memory bandwidth. Из памяти приходят не отдельные байты, а целые куски размером с cache-line — по 64 байта. EP>>При работе с массивом КПД=100%, так как все элементы расположены вплотную. При работе же со связанным списком, из 64 полученных байт, полезной нагрузкой являются только 4 байта (в этом тесте использовались int32). BZ>на самом деле всё гораздо хуже. при последовательном чтении памяти запросы конвейризуются, и можно выжать 20-30 ГБ/с. при случайном чтении от отправки запроса до получения ответа проходит 40-50 нс. т.е. разница в b/w будет не в 16 раз, а в 300
Так это и есть prefertcher, то есть он помогает скрыть latency за счёт конвейрезации.
В общем тут два основных фактора:
1. КПД использования memory bandwidth. Для связного списка int32 оно крайне неэффективное, и душит производительность во много раз.
2. Эффективность сокрытия latency prefetcher'ом. В общем случае, у связного списка паттерны доступа рандомные, поэтому prefetcher неэффективен. Это также даёт падение производительности в разы.
Оба фактора умножаются друг с другом, что в итоге даёт крайне низкую фактически-полезную memory bandwidth (которая часто является bottleneck'ом).
Здравствуйте, BulatZiganshin, Вы писали:
BZ>при последовательном чтении памяти запросы конвейризуются, и можно выжать 20-30 ГБ/с.
Да, и кстати, даже при последовательном доступе, для получения такого bandwidth одного ядра недостаточно (что показывали простые тесты на Nehalem и Sandy Bridge).
