Каморка

У нас на фирме соревнование проводится. Кто напишет функцию, которая сработает быстрее.
Задание:
Процессор Intel Xeon.
Функция void WhateverName( int64_t* array ) должна заполнить массив всеми возможными 64 битными значениями, у которых установлены четыре бита. Ну, то есть: 15, 23, 27, 29, 30, 39 и так далее. Порядок не важен, повторения не позволяются, подразумевается, что в массиве достаточно памяти.

Сразу даю хинт. Можно написать быстрее, чем копирование хардкодированного массива. Почему и как - догадайтесь сами

common Ща я побежал читать архитектуру ксенона. Ты у нас значит крутой, ну на тебе крутому встречную задачу, что такое Луна знаешь? От ан ней кратеры есть - они типа круглые. Тебе дают фотку луны надо на ней определить кратеры - то есть центры и радиусы. АФТАМАТИТЕСКИ. Что ценно, никаких сакральных знаний о внетренней архитектуре процессора и работы кешей и шин знать не обязательно.

Публика в волнение ждеть =)

Публика подождет.
Ибо про луну - это не задачка, а фигня полная. На решение нужно не меньше недели потратить, тем более, фотографий ты не дал.

А в моем случае, простейшую функцию написать - 10 минут хватит. А вот как разогнать - это интересный вопрос.

Старина Зотин писал(а):Публика подождет.
Ибо про луну - это не задачка, а фигня полная. На решение нужно не меньше недели потратить, тем более, фотографий ты не дал.

А в моем случае, простейшую функцию написать - 10 минут хватит. А вот как разогнать - это интересный вопрос.

Да ничего особо интересного. Генерить в регистрах, потом лить в память. Ибо memcpy() естественно будет медленнее. Вопрос всего лишь в том как генерить, но это уже дело техники. Так как требуется 64 бита то наверное будет иметь смысл юзать регистры FPU.

Алгоритм который будет генерить неповторающуюся последовательность чисел с выставлеными 4-мя битами без обращений к памяти наверняка придумать не так сложно.

-Maxim

Да вот, не фига.

Я могу сразу оптимальнее придумать. Ну, например, высчитываешь неиспользованный размер дата-кеша в последней итерации и на него перед генерацией делаешь memcpy - потому что, все равно, кешу пропадать, а значит можно часть скопировать без потерь.

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

Уже быстрее.

Старина Зотин писал(а):Да вот, не фига.

Я могу сразу оптимальнее придумать. Ну, например, высчитываешь неиспользованный размер дата-кеша в последней итерации и на него перед генерацией делаешь memcpy - потому что, все равно, кешу пропадать, а значит можно часть скопировать без потерь.

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

Уже быстрее.

Размер массива получится 15MB, так что затык все равно будет на стороне записи в оперативную память, а каждый следующий элемент в этой последовательности можно генерить всего несколькими машинными инструкциями. Не поможет тут ни хардкодирование ни копирование. Тупая генерация в регистрах и копирование в память в цикле. Объем кода тоже будет всего сотня-другая байтов и цикл будет попадать в предсказатель ветвлений в 99.9999% случаев так что никаких особых извратов не надо.

Как вариант небольшой оптимизации использовать SSE для заливки в память сразу по 128 бит - в этом случае последний кусок быстрее "зайдет" в L2 кеш и теоретически время исполнения функции будет немного меньше. Но все равно - основной bottleneck будет в том что размер генерируемого массива существенно больше размера L2 кеша, поэтому "голосуй не голосуй все равно получиш шайбу." Будеш сидеть и ждать пока предыдущая порция данных смоется в оперативку.

-Maxim

Вообще-то, размер массива не 15, а чуть меньше 5 мегабайт. То есть, почти мегабайт кеша в конце подсчета будет оставаться неиспользованным - 20%, однако.

И хардкодирование и копирование, конечно, помогут.
Копирование плохо только потерями кеша данных, а хардкодирование - кеша инструкций. Если их делать в объемах, которые не трогают кешей, то будет быстрее, тут даже спорить не о чем.

При этом, надо еще помнить, что копирование и хардкодирование не так просто работать будут - в параллель можно еще и префетч запустить.

И это мы еще не обсуждали векторные инструкции.

Зачем те брат фотографии? Ьерешь листок бымаги, рисуешь кружки, мона левой рукой, под сканер и вперед. Сильно я удивлен оценкой неделя - с чем связан такой прогноз? Почему не 5 минут и не месяц?

Старина Зотин писал(а):Вообще-то, размер массива не 15, а чуть меньше 5 мегабайт. То есть, почти мегабайт кеша в конце подсчета будет оставаться неиспользованным - 20%, однако.

И хардкодирование и копирование, конечно, помогут.
Копирование плохо только потерями кеша данных, а хардкодирование - кеша инструкций. Если их делать в объемах, которые не трогают кешей, то будет быстрее, тут даже спорить не о чем.

При этом, надо еще помнить, что копирование и хардкодирование не так просто работать будут - в параллель можно еще и префетч запустить.

По поводу 5 мегабайт таки согласен - попутал с задачкой на комбинирование где все шарики разные.

По поводу всего остального: ну ну, дерзайте. В "объемах, которые не трогают кешей" я хотел бы посмотреть как это вы так откусите кусочек кеша размером ровно в 1MB и заюзаете его для префетча. Успехов в борьбе с ассоциативностью.

Хардкодирование вообще бесперспективно ввиду того что оно будет нагружать и так нагруженую FSB, замедляя операции записи результата.

В общем задача очень близка к написанию оптимизированной процедуры bzero(), пока ничего более хорошего в этом вопросе наука не придумала как использовать SSE при больших размерах буфера.

-Maxim

OMFG, это-ж что вы там такое пишете, что за такую экономию боретесь?
Т.е. я понимаю что игрульки, но что бы вот так...

Старина,

а с какой целью у вас в конторе проводят такие соревнования ? ... делать нечего (извените за грубость) ?

Старина Зотин писал(а):У нас на фирме соревнование проводится. Кто напишет функцию, которая сработает быстрее.
Задание:
Процессор Intel Xeon.
Функция void WhateverName( int64_t* array ) должна заполнить массив всеми возможными 64 битными значениями, у которых установлены четыре бита. Ну, то есть: 15, 23, 27, 29, 30, 39 и так далее. Порядок не важен, повторения не позволяются, подразумевается, что в массиве достаточно памяти.

Сразу даю хинт. Можно написать быстрее, чем копирование хардкодированного массива. Почему и как - догадайтесь сами

ну так какое время надо побить ?

sobomax писал(а):По поводу всего остального: ну ну, дерзайте. В "объемах, которые не трогают кешей" я хотел бы посмотреть как это вы так откусите кусочек кеша размером ровно в 1MB и заюзаете его для префетча. Успехов в борьбе с ассоциативностью.

А в чем проблема? Префетч, вообще-то не сразу на весь кеш работает, а только на одну line.

sobomax писал(а):Хардкодирование вообще бесперспективно ввиду того что оно будет нагружать и так нагруженую FSB, замедляя операции записи результата.

А при чем тут FSB? Я же сказал, дохардкодировать до размеров i-cache. Инструкции из памяти читать не надо - все в кеше.

sobomax писал(а):В общем задача очень близка к написанию оптимизированной процедуры bzero(), пока ничего более хорошего в этом вопросе наука не придумала как использовать SSE при больших размерах буфера.

Согласен. SSE использовать нужно.

Marmot писал(а):OMFG, это-ж что вы там такое пишете, что за такую экономию боретесь?
Т.е. я понимаю что игрульки, но что бы вот так...

Ну а представь себе, например, 30 персонажей на экране, у каждого около 200 движущихся частей. Нужно рассчитать позу, проверить, легальна ли она с точки зрения humanIK, легальна ли с точки зрения физики, а потом еще наложить текстуры и отрисовать, не говоря уже о том, что еще и логика игры должна когда-то исполняться. И все это при ограниченном бюджете времени - ну примерно 30-40 миллисекунд.

Тут за каждый такт приходится бороться.

dima писал(а):а с какой целью у вас в конторе проводят такие соревнования ? ... делать нечего (извените за грубость) ?

Исключительно для развлечения. Ну а кроме того, интересно посмотеть, кто какие приемчики применяет. В реальном коде не всегда легко разобраться, а тут простая задачка - можно быстро прочитать и взять на вооружение.