LINUX.ORG.RU

А существует ли СОВРЕМЕННОЕ годное чтиво на тему оптимальных укладок данных и доступа к ним в современных процах?

 


2

6

Было какое-то чтиво времён 2008 про пни третьи, но есть ли похожее про Core i7 / Xeon последние?

Ну там, например, не пробегайте массив тупым циклом с начала до конца, потому что при обращении к первым 4 байтам, проц полезет в оперативу за кеш линией, на что уйдёт 200 тактов, а потом потратит пару тактов на каждый элемент. Оптимальнее, типа там, как-то спровоцировать его грузить кеш-линии раньше чем они вам нужны каким-то хитрым доступом, шагая как-то хитро по этому массиву в порядке не линейном, а через кеш линию, а потом возвращаясь. Звучит как пердь конечно, но лучшего примера я не знаю, потому что я малолетний дебил.

Вот хочется почитать что-то по сабжу, но про новые камни, а не древние пни.

Царь красава, чотко отдоминировал в теме.

Все правильно пишут вменяемые комментаторы. Нет однозначных рекомендаций по этому поводу. Точнее, рекомендации которыми можно пользоваться на практике очень простые: хранить данные компактнее, обрабатывать по возможности линейнее. Ну и выравнивать в соответствии с мануалами, это особенно актуально для SIMD.

Сейчас узким местом считается передача данных между разными CPU и синхронизация. Вот тут все, мягко говоря, непросто. Есть рекомендуемые atomic variables (которые по крайней мере на x64 не очень быстры), есть разные сорта memory barriers ( https://www.kernel.org/doc/Documentation/memory-barriers.txt ), есть некоторое количество lock/wait-free алгоритмов, но если разрабатываешь современный (т.е. параллельный) алгоритм то скорее всего начнешь упираться где-нибудь в этом месте

Deleted
()

Предлагаю царю написать две программы — одну с тупым циклом, а вторую — которая по-хитрому обходит память, и забенчмаркить. Или царь как всегда сольётся, не в состоянии написать даже трехстрочный пример к своим простыням текста?

Тем не менее, в GCC и других компиляторах есть интрисинк для prefetch. Не думаю, что он сделает хоть что-то полезное для линейного обхода массива, по делу там только третий аргумент.

vzzo ★★★
()
Ответ на: комментарий от LjubaSherif

Или так и будешь в идиота играть?

Чего в тебя играть-то? Ты просто еда для разве что очень голодных троллей — настолько уныл и шаблонен.

anonymous
()
Ответ на: комментарий от xpahos

ты даже не знаешь о чем рассуждаешь, но все равно продолжаешь.

Так расскажи, каким образом «утилизация CPU на кластере даже до 60% не доходила. Выяснилось, что он намудрил что-то с кэшом», потому что промахи кэша и в самом деле не влияют на «утилизацию CPU». Ну разве что под «утилизацией» понимается что-то необычное вроде пропускной способности или производительности.

tailgunner ★★★★★
()
Последнее исправление: tailgunner (всего исправлений: 1)
Ответ на: комментарий от LjubaSherif

Чисто из интереса - а что там с iaca? Я когда пробовал эту утилиту, работала она крайне говёно и для практических целей (по крайней мере моих) не годилась ни разу. Может расскажете подробнее?

zamazan4ik ★★
()
Ответ на: комментарий от tailgunner

Так расскажи, каким образом «утилизация CPU на кластере даже до 60% не доходила. Выяснилось, что он намудрил что-то с кэшом», потому что промахи кэша и в самом деле не влияют на «утилизацию CPU». Ну разве что под «утилизацией» понимается что-то необычное вроде пропускной способности или производительности.

Я не помню что было конкретно в том случае. Если отвечать на твой вопрос как кэш может повлиять, то достаточно взять mapreduce реализацию в вакууме. Для того, чтобы запустить операцию, нужно откуда-то получить данные, которые ты хочешь редьюсить, например. Перед запуском редьюсера данные бьются на множество чанков и дальше их обход зависит от того, как быстро будет происходить доступ к памяти этих чанков. Пока растут page walk, падает и ipc и тем больше приложение именно бегает по памяти в циклах, а не занимается полезной работой в виде обработки данных. Да, если смотреть top, то там все ядра на 100% могут быть загружены, а когда смотришь strace, то там mmap висит на локах.

xpahos ★★★★★
()
Ответ на: комментарий от xpahos

Если отвечать на твой вопрос как кэш может повлиять, то достаточно взять mapreduce реализацию в вакууме. Для того, чтобы запустить операцию, нужно откуда-то получить данные, которые ты хочешь редьюсить, например. Перед запуском редьюсера данные бьются на множество чанков и дальше их обход зависит от того, как быстро будет происходить доступ к памяти этих чанков. Пока растут page walk

Какое отношение page walk (что бы ты этим не называл) имеет к кэшам CPU?

Да, если смотреть top, то там все ядра на 100% могут быть загружены, а когда смотришь strace, то там mmap висит на локах.

Даже не знаю, что сказать. mmap висит на спинлоках (иначе не было бы 100% загрузки ЦП), и это видно в strace? Даже если так, какое отношение это имеет к кэшам ЦП и вообще архитектурно-специфической оптимизации по мануалам Intel?

tailgunner ★★★★★
()
Последнее исправление: tailgunner (всего исправлений: 1)
Ответ на: комментарий от tailgunner

Так расскажи, каким образом «утилизация CPU на кластере даже до 60% не доходила. Выяснилось, что он намудрил что-то с кэшом», потому что промахи кэша и в самом деле не влияют на «утилизацию CPU». Ну разве что под «утилизацией» понимается что-то необычное вроде пропускной способности или производительности.

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

Правда и 60% это очень хорошее значение.

Crocodoom ★★★★★
()
Ответ на: комментарий от Crocodoom

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

Скорее текущей производительности и производительнрости, достигавшейся ранее, но это предположения, которых мрожно построить много. Хотелось бы просто знать, что в данном случае понимается под «утилизацией» - это «производительность» или что-то еще.

Если с локальность данных проблемы, то FPU простаивает.

ALU тоже. И... какие инструменты замеряют время простоя конкретно FPU?

tailgunner ★★★★★
()
Последнее исправление: tailgunner (всего исправлений: 1)
Ответ на: комментарий от LjubaSherif

Я не тот аноним, но...

Второе, ты можешь показать, что ты не балабол и эту разницу на порядок в более-менее актуальных соседних поколениях.

Есть перевод интересной статьи на хабре https://habr.com/post/415053/

В Skylake длительность инструкции pause возрасла на порядок относительно предыдущих поколений. Из-за этого spin-wait, в котором использовалась эта инструкция начал работать дольше, чем планировалось. Пришлось патчить. В статье есть ссылка на 64-ia-32-architectures-optimization-manual пункт 8.4.7 https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32...

The latency of PAUSE instruction in prior generation microarchitecture is about 10 cycles, whereas on Skylake microarchitecture it has been extended to as many as 140 cycles.

И кто балабол, маня?

ox55ff ★★★★★
()
Ответ на: комментарий от tailgunner

Скорее текущей производительности и производительнрости, достигавшейся ранее

Это вряд ли, там же машина как раз поменялась, а не код.

какие инструменты замеряют время простоя конкретно FPU?

Спеки + анализ численной схемы + тесты, поскольку речь скорее всего идёт о числодробилке, так как были упомянуты кластеры и МФТИ.

Но лучше и правда у xpahos спросить, чем гадать. Что такое 60% утилизации?

Crocodoom ★★★★★
()
Ответ на: комментарий от Crocodoom

Скорее текущей производительности и производительнрости, достигавшейся ранее

Это вряд ли, там же машина как раз поменялась, а не код.

Производительность кода, запущенного на машине.

какие инструменты замеряют время простоя конкретно FPU?

Спеки + анализ численной схемы + тесты,

То есть инструментов таки нет? А я подумал, что в perf вообще волшебства добавили.

tailgunner ★★★★★
()
Последнее исправление: tailgunner (всего исправлений: 1)
Ответ на: комментарий от tailgunner

То есть инструментов таки нет?

Я таких не знаю, ага. Может и есть какие-то утилиты. Как минимум кажется, что через виртуализацию возможно что-то получить. Понятно, что не на живых объёмах данных, но тем не менее.

Crocodoom ★★★★★
()
Ответ на: комментарий от tailgunner

Какое отношение page walk (что бы ты этим не называл) имеет к кэшам CPU?

Да, тут я не прав. page walk приплел зря.

Даже не знаю, что сказать. mmap висит на спинлоках (иначе не было бы 100% загрузки ЦП), и это видно в strace? Даже если так, какое отношение это имеет к кэшам ЦП и вообще архитектурно-специфической оптимизации по мануалам Intel?

mmap видно в strace по continued строчкам. Я думаю ты лучше меня знаешь, что то самое дерево аллоцированных area блокируется при чтении и когда все ридеры уходят, только тогда происходит запись новых нод. Сейчас я ничего придумать не смог, как бы это можно было бы сделать ;) Бенчмарк на переполнение tlb я сделал и он даже не затрагивает l1d кэш, а вот как провязать это с mmap пока не придумал. Может быть завтра будет чуть больше времени и попробую что-нибудь сваять.

xpahos ★★★★★
()
Ответ на: комментарий от Crocodoom

Это не совсем числодробилка. Я в этой штуке, например, расшифровываю SSL сессии собранные с тестов. К МФТИ это отношения не имеет, просто парень, который рассказывал про Haswell(кажется, это было года 4 назад) преподает/преподавал в МФТИ. Он вроде как что-то пытался во ВШЭ такое же сделать, не знаю получилось ли у него.

Утилизация - чистая загрузка исполнения самих задач. Т.е. в моем случае это вот взять tcpdump, посмотреть у пакета все поля, потом выбрать по 5 таплу такие же пакеты, посмотреть время, когда они были получены и отсортировать в правильном порядке, а потом уже сама дешифровка и сверху уже анализ HTTP/HTTP2 параметров. Например, найти с какой ошибкой завершилась определенная сессия в HTTP2.

xpahos ★★★★★
()
Ответ на: комментарий от tailgunner

То есть инструментов таки нет? А я подумал, что в perf вообще волшебства добавили.

Если вообразить что у нас нескончаемое количество денег и нужно что-то больше PMU, то можно к чувакам из Германии обратиться. Я не помню название компании, они занимаются именно хардверным профилированием чипов. Но там совсем какая-то магия, которую я не понимаю. Меня пока хватило только на простенький MIPS подобный CPU на FPGA сваять по книжке :)

xpahos ★★★★★
()
Ответ на: комментарий от xpahos

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

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

Если вообразить что у нас нескончаемое количество денег и нужно что-то больше PMU, то можно к чувакам из Германии обратиться.

Это не все могут (я точно не могу), поэтому мне интересно, умеют ли такое стандартные инструменты вроде perf

tailgunner ★★★★★
()
Ответ на: комментарий от tailgunner

Это не все могут (я точно не могу), поэтому мне интересно, умеют ли такое стандартные инструменты вроде perf

Я глубоко не копал. У нас есть внутренняя лекция в целом по профилированию, но я пока не успеваю ее посмотреть. Приходи к нам работать ;)

xpahos ★★★★★
()
Ответ на: комментарий от tailgunner

Нет, под линухами точно работает и под маком. Также есть вариант установки Vtune на хосте, с какой-то ОС и профилирование не на хостовой машине с другой ОС: https://software.intel.com/en-us/articles/intel-system-studio-2018-system-req...

Vtune может как дёргать perf, так и ставить в систему свой драйвер.

zamazan4ik ★★
()

Я советую прочитать «Совершенный код», там чётко описано что оптимизации не нужны. Сравни:

Intel Pentium II 300 МГц (1997) — 50 Мфлопс
Intel Pentium III 1 ГГц (1999)  — 2 Гфлопс 
Intel(R) Core(TM) i7-7700K      — 89.59 Гфлопс 

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

Так что не трать время на книги по оптимизации =)

AntonyRF ★★★★
()
Ответ на: комментарий от Harald

Угу.

Вот так и теряем лучших людей.

Deleted
()
Ответ на: комментарий от AntonyRF

=)))

Понятно. Ну что ж, есть к чему стремиться.

Deleted
()
Ответ на: комментарий от xpahos

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

nezamudich ★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.