?

Log in

No account? Create an account
nyaload

Журнал Пушыстого

Журнал Пушыстого

Previous Entry Share Next Entry
memory latency
nyaload
_winnie
Сегодня столкнулся с тем, что прочитать один байт по смещению, взятому из хеш-функции - это 100 тактов процессора, и ничего тут не сделаешь (ну кроме как завести сотню компьютеров). У меня генерируется 16-байтовый murmur-хеш, и он используется для чтения 4-х байтов из 4-х рандомных точек полугигабайта. Эти чтения происходят дольше, чем подсчет хеша, и все остальное в программе ( разбиение строки на подстроки по границам utf-8 символов, чтение std::string из файла и тп).

Профайлер VS2012 - приятный, разобрался за пять минут. Плохо, что он не показывает hot-spot на уровне асм-команд - показал в release режиме на строчку «b = (b & ~(0xf << ofs)) + (val << ofs);», и я её полчаса оптимизировал. Хотя на самом деле тормоза были именно в movzx при чтении байта.


скриншот профайлера:
код реализует MinCount Sketch с 4-битовыми счетчиками.



  • 1
И что? Известная ж тема.

Я в незапамятные времена перешёл с компа на Celeron 300A (разогнанном до 450MHz) на ноут на P4-1800 - и не ощутил ожидаемого прироста производительности в эмуляторе супернинтендо =). От офигения написал свой бенчмарк: на арифметике скорость пропорциональна тактовой (разница в 4 раза), на последовательном доступе к памяти разница уже в два раза, на произвольном её нет вообще. Протестил компы на работе - ситуация аналогичная, выше скорость была только на компе с дорогущей RIMM (кажется) памятью. Тогда я и разочаровался в прогрессе настольных компов =).

А нельзя ли алгоритм переписать? Может, реально при заполнении этого самого полугигабайта разбить его на блоки и посчитать плотности распределения в этих блоках - чтобы не искать конкретный байт, а прикидывать, каким он мог бы быть? Ну или ещё как-то обрабатывать последовательно при заполнении...

Edited at 2013-08-02 12:51 pm (UTC)

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

Если задача состоит в том, чтобы взять рандомных 4 байта из полугига, но всегда одних и тех же для любого заданного полугига, то, очевидно, адаптируется.

ага, я эту проблему у себя в жж подымал некоторое время тому назад, когда писал что процы говно и на самом деле у нас 160 000 "нетривиальных операций" (кеш миссов) на фрейм при 60 кадрах в секунду

http://www.programmersheaven.com/download/15515/1/ZipView.aspx - та же проблема (с решением для частного случая) 18 лет назад.

Ещё известная тема - умножение матриц. Если одну матрицу сразу повернуть - умножение резко ускоряется.

Этот алгоритм - это Min-Count Sketch, просто так "повернуть" вряд ли выйдет.

Можно попробовать всякие трюки (попробовать как-нибудь читать параллельно из памяти, от prefetch на низком уровне до mapreduce на высшем или изменить требования к алгоритму "давайте делить по словам, а не по буквам"). Можно попробовать трюк "давайте для однобуквенных строк считать, что их хеш равен самой букве". Тогда можно расположить меняющиеся байты рядом.

Мне пока что не надо выворачиваться наизнанку для оптимизации в этом месте, я ещё целиком всю программу не написал.

Перечитал про него... Мда... Полгига статистики с произвольным доступом - это всё-таки жёстко.
Единственная идея по оптимизации - апдейтить статистику не на каждый чих, а кучей, как-то накапливая данные.

Можно попробовать вручную префетчи повставлять. Для хотспотов на уровне ассемблера порекомендую Intel VTune, коим ваш покорный слуга занимается.

Да, VTune годная штука, после него описанные тут ограничения профайлера VS2013 выглядят дико.

Зато прочитать 10 байт по разным смещениям - уже 10 тактов (в среднем). Больше 10, правда, не получится, потому как Интеловские процессоры имеют только 10 Line Fill Buffers.

Попробовал позвать на вычисленные адреса _mm_prefetch(, _MM_HINT_T0), _MM_HINT_NTA), _m_prefetch.
Попробовал разбить цикл на две части - записать в локальную переменную ui64 localStorage[T] прочитанные байты. И во втором цикле использовать прочитанное.

Оба варианта дают ускорение на 10%, не в 4-ре раза :]

А процессор какой?

Нужен Ivy Bridge или Haswell, на более старых процессорах TLB miss блокирует выполнение.

профайлить дебаг изза кончености профайлера все таки стыд позор. лучше найти нормальный профайлер.
читать лучше гранулами по 64 =) так что константы многих O(1) такие что проигрывают логарифмам легко.

Дебаг - ради красивого скриншота всё-таки :)


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

Edited at 2013-08-02 09:46 pm (UTC)

(Deleted comment)
Спасибо за анализ и за разные варианты!

> Алсо, цикл на заполнение buf выглядит слишком брутально. Во-первых, можно дешевле читать по 28 бит из потока.
Экспериментировал с разными K, это самый быстрый способ который я знаю, чтобы прочитать много раз по К бит...

> Во-вторых, кажется, что проще писать хэш в четыре инта, и отгрызать 28 бит от 32 одной маской. Всё равно же мурмур кучу лишнего генерит, и у нас 16 бит неизрасходованного хэша остаётся.
Ага, так и сделал. +5% к скорости.

> Алсо, не очень понятно, почему бы в изначальном алгоритме не посчитать сразу махом все T адресов и сделать T префетчей, чтобы ждать их не по одному, а сразу пачкой. Тут же нет зависимостей следующего адреса от предыдущего, как бы можно не париться (и забить на всё то, что я написал выше).

Я попробовал пару вариантов (сначала прочитать четыре значения в локальный массив, и только потом использовать), _(m)m_prefetch(, NTA/T0), ускорилось на 10%.
То ли я криво пробовал, то ли процессор и так уже параллельно читает и я не сильно помог.


Edited at 2013-08-04 05:40 pm (UTC)

ну да, нужно улучшать локальность памяти. может можно на меньшей таблице примерно посчитать, а потом на полной уточнить.

  • 1