Помогите найти самый быстрый алгоритм для выполнения следующей операции.
Дано число типа byte, например 210, которое в двоичной форме выглядит как 11010010. Если считать биты слева на право, а индекс первого бита равен 1, то нужно извлечь из этого числа чётные биты и сформировать из него 4-х битное число.
Например:
210 (dec) -> 11010010 (bin)
Нужно извлечь биты выделенные полужирным и сформировать число 1100 (bin) -> 80 (dec).
2)
Сгенерировать все возможные 256 комбинаций пар ключ/значение, где ключ это искомое число, а значение результат преобразования.
Загрузить их в Hashtable и потом искать по ключу.
Второй способ в 3 раза медленнее первого. Но и первый способ не блещет производительность.
Какие ещё есть варианты.
Здравствуйте, Cynic, Вы писали:
C>Помогите найти самый быстрый алгоритм для выполнения следующей операции. C>Дано число типа byte, например 210, которое в двоичной форме выглядит как 11010010. Если считать биты слева на право, а индекс первого бита равен 1, то нужно извлечь из этого числа чётные биты и сформировать из него 4-х битное число. C>Например: C>210 (dec) -> 11010010 (bin) C>Нужно извлечь биты выделенные полужирным и сформировать число 1100 (bin) -> 80 (dec).
C>Пробовал два алгоритма. C>1) C>
C>2) C>Сгенерировать все возможные 256 комбинаций пар ключ/значение, где ключ это искомое число, а значение результат преобразования. C>Загрузить их в Hashtable и потом искать по ключу.
C>Второй способ в 3 раза медленнее первого. Но и первый способ не блещет производительность. C>Какие ещё есть варианты.
3. Как второй, только загрузить не в хэш, а в обычный массив и индексировать входным числом
MW>3. Как второй, только загрузить не в хэш, а в обычный массив и индексировать входным числом
Вот чё то идея эта пришла только после того как запостил сообщение.
Щас попробовал, примерно в 4-ре раза быстрее первого способа и в 12 раз быстрее второго.
Здравствуйте, Cynic, Вы писали:
MW>>3. Как второй, только загрузить не в хэш, а в обычный массив и индексировать входным числом
C>Вот чё то идея эта пришла только после того как запостил сообщение. C>Щас попробовал, примерно в 4-ре раза быстрее первого способа и в 12 раз быстрее второго.
Немного отклонюсь от темы.
У меня алгоритм работает с массивом byte. По ходу работы программы значения в этом массиве претерпевают разные преобразования с использованием математических операторов (+,-,/,*) и битовых операторов (<, >, |, &, ^). Я так понимаю, что когда программа производит вычисления со значениями типа byte, то она всё время выполняет преобразование из byte в int и наоборот. Если принять во внимание, что расход памяти меня не слишком волнует, а вот производительность критична, не стоит ли мне в этом случае использовать массив int, даже не смотря на то, что будут использоваться только первые 8 бит этого типа?
Здравствуйте, Cynic, Вы писали:
C>2) C>Сгенерировать все возможные 256 комбинаций пар ключ/значение, где ключ это искомое число, а значение результат преобразования. C>Загрузить их в Hashtable и потом искать по ключу.
Надо не в hashtable было загрузить, а в массив. Это же всего лишь 256 байт.
Быстрее этого вряд ли что-то удастся придумать. В принципе, слазить в байтовый массив — это одна машинная команда (ну, если на достаточно низкоуровневом языке писать).
Здравствуйте, Pzz, Вы писали:
Pzz>Надо не в hashtable было загрузить, а в массив. Это же всего лишь 256 байт.
Pzz>Быстрее этого вряд ли что-то удастся придумать. В принципе, слазить в байтовый массив — это одна машинная команда (ну, если на достаточно низкоуровневом языке писать).
Практика показывает что switch на пару процентов может быть быстрее. Стабильно быстрее при конвертации большого массива байт в другой массив.
Здравствуйте, samius, Вы писали: S>Практика показывает что switch на пару процентов может быть быстрее. Стабильно быстрее при конвертации большого массива байт в другой массив.
Здравствуйте, Cynic, Вы писали:
C>Здравствуйте, samius, Вы писали: S>>Практика показывает что switch на пару процентов может быть быстрее. Стабильно быстрее при конвертации большого массива байт в другой массив.
C>И как сюда можно switch прикрутить?
for (int i = 0; i < source.Length; i++)
{
byte result = 0;
switch (i)
{
case 0x00: result = 255; break;
case 0x01: result = 254; break;
case 0x02: result = 253; break;
case 0x03: result = 252; break;
case 0x04: result = 251; break;
case 0x05: result = 250; break;
....
}
dest[i] = result;
}
Быстрее, чем из массива, не получите никак. Но зачем их в этом примере кода преобразуют в инты?
И зачем первоначальная маска с 0x55, если потом всё равно по битам выковыриваем?
А вот что от замены деления на сдвиг что-то ускорилось — это очень странно, компилятор такие вещи обычно делает сам.
У вас вообще оптимизация включена? И чем компилите? А что за тип byte?
Здравствуйте, samius, Вы писали:
S>>>Практика показывает что switch на пару процентов может быть быстрее. Стабильно быстрее при конвертации большого массива байт в другой массив.
нет, это горазщдо медленней обращения в память. этот код загрузит из памяти адрес перехода (уже загрузка по выч. адресу!), затем призведёт непредсказанный переход и затем ещё загрузит константу и ещё раз сделает переход. на С такое было бы на порядок медленней простой загрузки
Здравствуйте, Cynic, Вы писали:
MW>>3. Как второй, только загрузить не в хэш, а в обычный массив и индексировать входным числом C>Щас попробовал, примерно в 4-ре раза быстрее первого способа и в 12 раз быстрее второго.
на С скорость бы была одно преобразование в такт, т.е. 4 млрд на 4 ГГц процессоре. думаю этого должно хватить
ps: если не хватит, то на sse2 будет 4 преобразования в такт, а на avx2 — вдвое больше
Здравствуйте, BulatZiganshin, Вы писали:
BZ>Здравствуйте, samius, Вы писали:
S>>>>Практика показывает что switch на пару процентов может быть быстрее. Стабильно быстрее при конвертации большого массива байт в другой массив.
BZ>нет, это горазщдо медленней обращения в память. этот код загрузит из памяти адрес перехода (уже загрузка по выч. адресу!), затем призведёт непредсказанный переход и затем ещё загрузит константу и ещё раз сделает переход. на С такое было бы на порядок медленней простой загрузки
Что значит "нет"?
У меня тесты. Там где лут трудится 22 сек, свитч 21 сек. Результат повторяется стабильно. Не знаю, как в C, не пробовал.
Здравствуйте, samius, Вы писали:
S>Что значит "нет"? S>У меня тесты. Там где лут трудится 22 сек, свитч 21 сек. Результат повторяется стабильно. Не знаю, как в C, не пробовал.
а ты на случайных данных тестировал или просто нулях? и сколько тактов процессора уходит на обработку олдного байта, а то эти секунды нам ни о чём не говорят?
Здравствуйте, samius, Вы писали:
S>Что значит "нет"? S>У меня тесты. Там где лут трудится 22 сек, свитч 21 сек. Результат повторяется стабильно. Не знаю, как в C, не пробовал.
С таким "тестом" — не удивительно
Там компилятор наверняка преобразовал в result = 255 — i для первых 256 маленьких i, для остальных оставил тупо 0.
Вы попробуйте честно делать switch(source[i]) и в кейсах указать правильные значения результата, а гонять (много раз) на произвольных сорсах, всосанных из входного файла. И даже при этом он скорее всего заменит на табличное присваивание, а 1 секунда из 22 — не показатель, чуть получше уложенный код.
Или полные тесты в студию, с правильными результатами, неконстантным входом и полными ключами сборки.
Здравствуйте, BulatZiganshin, Вы писали:
BZ>на С скорость бы была одно преобразование в такт, т.е. 4 млрд на 4 ГГц процессоре. думаю этого должно хватить
Справедливости ради, вряд ли один такт, надо сформировать адрес (сложение) и вытащить из массива, что даже из L1 чуть больше. Казалось бы, это можно распараллелить, но компилятор не имеет права, ибо source и dest могут перекрываться, надо специально указывать, что это не так, и, скорее всего, руками разворачивать цикл.
BZ>ps: если не хватит, то на sse2 будет 4 преобразования в такт, а на avx2 — вдвое больше
Какая инструкция из sse2 или avx2 умеет делать подстановку из массива для всех элементов? Уж очень неправдоподобно, множественный доступ в память за 1 такт.
Здравствуйте, cures, Вы писали:
BZ>>на С скорость бы была одно преобразование в такт, т.е. 4 млрд на 4 ГГц процессоре. думаю этого должно хватить
C>Справедливости ради, вряд ли один такт, надо сформировать адрес (сложение) и вытащить из массива, что даже из L1 чуть больше. Казалось бы, это можно распараллелить, но компилятор не имеет права, ибо source и dest могут перекрываться, надо специально указывать, что это не так, и, скорее всего, руками разворачивать цикл.
mov al, src[42]
mov al, substititions[al]
mov dst[42], al
вот это на хасвеле выполнится за 1 такт и ещё останется 1 арифметический слот неиспользованным. а дальше ты вероятно не в курсе того как современные out-of-order execution процессоры работают. читай The microarchitecture и Instruction tables отсюда:
www.agner.org/optimize/
BZ>>ps: если не хватит, то на sse2 будет 4 преобразования в такт, а на avx2 — вдвое больше
C>Какая инструкция из sse2 или avx2 умеет делать подстановку из массива для всех элементов? Уж очень неправдоподобно, множественный доступ в память за 1 такт.
3*сдвиг + 4*pand + 3*por — это 10 операций, а поскольку pand/por могут выполняться по 3 за такт, то обработка 16/32 байтного слова займёт 4 такта. ну и загрузка/сохранение в свободные места втиснутся
Здравствуйте, BulatZiganshin, Вы писали:
BZ>Здравствуйте, samius, Вы писали:
S>>Что значит "нет"? S>>У меня тесты. Там где лут трудится 22 сек, свитч 21 сек. Результат повторяется стабильно. Не знаю, как в C, не пробовал.
BZ>а ты на случайных данных тестировал или просто нулях? и сколько тактов процессора уходит на обработку олдного байта, а то эти секунды нам ни о чём не говорят?
На случайных. Мне секунды говорят о том что на конвертации массива из 100000000 байт в такой же массив свитч стабильно работает на 4.5% шустрее. Замеры секунд произведятся на 250 итерациях.
Остальные ответы, полагаю, вы в состоянии получить сами. Причем в той форме, которая вас удовлетворит.
Здравствуйте, cures, Вы писали:
C>Здравствуйте, samius, Вы писали:
S>>Что значит "нет"? S>>У меня тесты. Там где лут трудится 22 сек, свитч 21 сек. Результат повторяется стабильно. Не знаю, как в C, не пробовал.
C>С таким "тестом" — не удивительно
с каким "таким"? Вы телепат?
C>Там компилятор наверняка преобразовал в result = 255 — i для первых 256 маленьких i, для остальных оставил тупо 0. C>Вы попробуйте честно делать switch(source[i]) и в кейсах указать правильные значения результата, а гонять (много раз) на произвольных сорсах, всосанных из входного файла.
Чем по-вашему данные, всосанные из входного файла лучше данных, высосанных из Random? C> И даже при этом он скорее всего заменит на табличное присваивание, а 1 секунда из 22 — не показатель, чуть получше уложенный код. C>Или полные тесты в студию, с правильными результатами, неконстантным входом и полными ключами сборки.
Мне кажется что вам проще получить за минуту любые тесты с любыми результатами и любыми ключами сборки.
Что может быть проще? Вставьте исходную формулу в Console.WriteLine("case {0}: v = {1}; break;", i, f(i)), вставьте результат в код вашего теста.
Здравствуйте, samius, Вы писали:
S>Чем по-вашему данные, всосанные из входного файла лучше данных, высосанных из Random?
скорость работы программы может зависеть от входных данных. так что в идеале надо тестировать на взвешенной смеси реальных вхдных данных, хотя это само по себе проблема. хотя в данном случае случайные данные дадут результат всяко не быстрее любых реальных
Здравствуйте, Pzz, Вы писали:
Pzz>Надо не в hashtable было загрузить, а в массив. Это же всего лишь 256 байт.
Pzz>Быстрее этого вряд ли что-то удастся придумать. В принципе, слазить в байтовый массив — это одна машинная команда (ну, если на достаточно низкоуровневом языке писать).
Команды бывают разные. Одно дело операция с данными из регистра, а другое дело промах мимо кеша.
Если у Вас нет паранойи, то это еще не значит, что они за Вами не следят.
Здравствуйте, samius, Вы писали:
C>>С таким "тестом" — не удивительно S>с каким "таким"? Вы телепат?
Не совсем, только учусь
Но основной цикл Вы привели в коде, там, во-первых, функция берётся от значения индекса, а не от байта из входного массива, а во-вторых, в кейсах стоят присваивания не тем значениям, которые требуются ТС, а последовательным, такие кейсы оптимизируются компилятором в вычитания. Возможно, у Вас уже появились другие тесты, поэтому ниже я и попросил привести их точный текст.
S>Мне кажется что вам проще получить за минуту любые тесты с любыми результатами и любыми ключами сборки. S>Что может быть проще? Вставьте исходную формулу в Console.WriteLine("case {0}: v = {1}; break;", i, f(i)), вставьте результат в код вашего теста.
Получить "любые" тесты можно, только они дадут другие результаты и другое время. Сравнивать времена выполнения разных программ — дело увлекательное, но не слишком продуктивное.
Даже если на минутку забыть, что у меня нет объекта Console (это Java?), Вы правда предлагаете сравнивать времена вычисления функции вместе с распечаткой результатов? Так они действительно будут на порядок больше, чем собственно времена вычисления функции, и где JITу припрёт лучше это разложить — вопрос совершенно отдельный.
Предлагаю мерять именно время вычисления функции от большого количества пусть рандомных входных данных, причём делать это на общедоступной платформе, например — на ideone.com, и на языке топикстартера (Ц или кресты?), так как именно о нём шла речь. Впрочем, можно и на жабе, только в любом случае это надо сделать аккуратно, чтобы, с одной стороны, туда не влезло время распечатки, а с другой — чтобы компилятор не соптимизировал это в пустоту.
И, конечно, руками рисовать 256 правильных кейсов — дело утомительное, если у Вас уже есть такой код, хотелось бы его заюзать.
Вот тут у меня для 2^29 элементов получилось примерно 1.7 секунды для прямого вычисления функции и 1.0 для табличного. А сколько получится со свичом?
Здравствуйте, BulatZiganshin, Вы писали:
BZ>2.5 ГБ за 21 секунду, частота твоего компа пусть 1 ГГц. выходит на порядок медленней программы, написанной на С — она это сделает за 2.5 секунды
Там написано 100 миллионов элементов на 250 итераций, то есть 25 ГБ, итого вполне конкурентоспособный результат, если правильный.
Здравствуйте, BulatZiganshin, Вы писали:
BZ>Здравствуйте, samius, Вы писали:
S>>Остальные ответы, полагаю, вы в состоянии получить сами. Причем в той форме, которая вас удовлетворит.
BZ>2.5 ГБ за 21 секунду, частота твоего компа пусть 1 ГГц. выходит на порядок медленней программы, написанной на С — она это сделает за 2.5 секунды
50ГБ, причем 25 надо прочитать, и 25 записать. Частота моего камня — 3.5 ГГц.
Естественно, это медленее программы на C, никто не утверждал обратного. Хотя бы потому, что C не проверяет диапазоны массива при записи в него. Только я ведь взялся показать способ, который при некоторых условиях работает быстрее ЛУТ-а, реализованного на C#, не на C.
И немного сомневаюсь что аналогичное вычисление даже программа на C сделает за 2.5 секунды на моем компе даже при моей реальной частоте 3.5 ГГц. Задача на грани пропускной способности памяти моего компа.
Здравствуйте, BulatZiganshin, Вы писали:
BZ>Здравствуйте, samius, Вы писали:
S>>Чем по-вашему данные, всосанные из входного файла лучше данных, высосанных из Random?
BZ>скорость работы программы может зависеть от входных данных. так что в идеале надо тестировать на взвешенной смеси реальных вхдных данных, хотя это само по себе проблема. хотя в данном случае случайные данные дадут результат всяко не быстрее любых реальных
Так все-таки, рандомные данные устроят?
Здравствуйте, Arsen.Shnurkov, Вы писали:
S>>Практика показывает что switch на пару процентов может быть быстрее. Стабильно быстрее при конвертации большого массива байт в другой массив.
AS>А за счет чего?
Полагаю что за счет более эффективной прокачки памяти. Ключевое здесь — "большого массива байт". На маленьких массивах свитч сливает в разы.
Здравствуйте, cures, Вы писали:
C>Здравствуйте, samius, Вы писали:
C>>>С таким "тестом" — не удивительно S>>с каким "таким"? Вы телепат?
C>Не совсем, только учусь C>Но основной цикл Вы привели в коде, там, во-первых, функция берётся от значения индекса, а не от байта из входного массива, а во-вторых, в кейсах стоят присваивания не тем значениям, которые требуются ТС, а последовательным, такие кейсы оптимизируются компилятором в вычитания. Возможно, у Вас уже появились другие тесты, поэтому ниже я и попросил привести их точный текст.
Уверен, что понял, что такое функция от значения индекса.
Уверен, что те значения, или не те значения, которые требуются ТС, не играют решительного значения в скорости трансформации. Проверил на тех значениях, что у ТС-а, результаты замеров не изменились.
S>>Мне кажется что вам проще получить за минуту любые тесты с любыми результатами и любыми ключами сборки. S>>Что может быть проще? Вставьте исходную формулу в Console.WriteLine("case {0}: v = {1}; break;", i, f(i)), вставьте результат в код вашего теста.
C>Получить "любые" тесты можно, только они дадут другие результаты и другое время. Сравнивать времена выполнения разных программ — дело увлекательное, но не слишком продуктивное.
Я не предлагаю справнивать результаты выпонения разных программ. Я предлагаю сравнить результаты работы ЛУТ-а и свитча на больших массивах. Условия вы знаете — 25Гб на входе, 25 на выходе. При этом вы сможете подставить именно те значения, которые вас интересуют больше всего.
C>Даже если на минутку забыть, что у меня нет объекта Console (это Java?), Вы правда предлагаете сравнивать времена вычисления функции вместе с распечаткой результатов? Так они действительно будут на порядок больше, чем собственно времена вычисления функции, и где JITу припрёт лучше это разложить — вопрос совершенно отдельный.
Я приводил код на C#. Но может быть у вас есть printf?
Нет, я не предлагал сравнивать времена с распечаткой результатов. Я предлагал дешевый способ нагенерить кода для switch-а. Я подумал, что именно это останавливает вас от написания собственного теста.
C>Предлагаю мерять именно время вычисления функции от большого количества пусть рандомных входных данных, причём делать это на общедоступной платформе, например — на ideone.com, и на языке топикстартера (Ц или кресты?), так как именно о нём шла речь.
Вы так считаете? Почему же ТС создал тему в разделе .NET? Уверен, что речь шла о C#. Тип "byte" в исходном сообщении подтверждает мою смелую догадку.
C>Впрочем, можно и на жабе, только в любом случае это надо сделать аккуратно, чтобы, с одной стороны, туда не влезло время распечатки, а с другой — чтобы компилятор не соптимизировал это в пустоту. C>И, конечно, руками рисовать 256 правильных кейсов — дело утомительное, если у Вас уже есть такой код, хотелось бы его заюзать.
Вот код http://ideone.com/WDTGDo
(250 раз по 1Мб)
C>Вот тут у меня для 2^29 элементов получилось примерно 1.7 секунды для прямого вычисления функции и 1.0 для табличного. А сколько получится со свичом?
Проблема с пуском на ideone в том, что он ограничивает как объем памяти, так и время выполнения.
Здравствуйте, samius, Вы писали:
S>50ГБ, причем 25 надо прочитать, и 25 записать. Частота моего камня — 3.5 ГГц.
Мы меряем (в гигабайтах) не объём работы с памятью, а количество обрабатываемых элементов.
S>Естественно, это медленее программы на C, никто не утверждал обратного. Хотя бы потому, что C не проверяет диапазоны массива при записи в него. Только я ведь взялся показать способ, который при некоторых условиях работает быстрее ЛУТ-а, реализованного на C#, не на C.
Так покажите работающий код, на идиване есть диезы, хотя может быть из моно, и времянка будет немного другая.
Проверка границ занимает не так много, она практически всегда правильно предсказана, и по сравнению с постоянными промахами по кэшам это копейки.
S>И немного сомневаюсь что аналогичное вычисление даже программа на C сделает за 2.5 секунды на моем компе даже при моей реальной частоте 3.5 ГГц. Задача на грани пропускной способности памяти моего компа.
25 миллиардов — вряд ли успеет, разве что на avx2, как предлагали. Но почему не попробовать?
И не меряйте пропускную способность своей памяти, она не особо интересна, меряйте само вычисление, оставаясь внутри L2 и TLB кэшей, как я. И можно результат даже не записывать, например аггрегировать ксором в переменную, ибо ТС спрашивал про алгоритм вычисления, а не про чтение-запись.
Рандомные устроят.
S>Полагаю что за счет более эффективной прокачки памяти. Ключевое здесь — "большого массива байт". На маленьких массивах свитч сливает в разы.
Не надо прокачивать память. Если на маленьких сливает в разы, такой эффект вполне может наблюдаться, просто торможение на свичах позволяет меньше интерферировать с прокачкой, и получается чуть быстрее.
Что там на проценты, у меня на g++ программа начинала вдвое быстрее работать при вставке никогда не выполняющихся условий с распечаткой внутри, без всякой памяти, просто из-за не очень хорошей оптимизации компилятора, причём это удавалось на старых версиях (до 4.6), а на 4.7 в любом случае работала медленно.
Но интересно именно время вычисления функции, без привязки к памяти. А какие времена на маленьких?
Здравствуйте, cures, Вы писали:
C>Здравствуйте, samius, Вы писали:
S>>50ГБ, причем 25 надо прочитать, и 25 записать. Частота моего камня — 3.5 ГГц.
C>Мы меряем (в гигабайтах) не объём работы с памятью, а количество обрабатываемых элементов.
Блин, я ведь не зря оговорился что "для больших массиовов". Если изменить условия и сделать массивы по 250 байт, прогнав их по 100*10^6 раз, то и результаты будут другие. Свитч сольет в 5-8 раз.
S>>Естественно, это медленее программы на C, никто не утверждал обратного. Хотя бы потому, что C не проверяет диапазоны массива при записи в него. Только я ведь взялся показать способ, который при некоторых условиях работает быстрее ЛУТ-а, реализованного на C#, не на C.
C>Так покажите работающий код, на идиване есть диезы, хотя может быть из моно, и времянка будет немного другая.
Ссылка в предыдущем сообщении. Код работает, но времянка сильно другая, ибо для того что бы он вообще запускался на идеуане, пришлось взять размеры массивов по 1Мб. C>Проверка границ занимает не так много, она практически всегда правильно предсказана, и по сравнению с постоянными промахами по кэшам это копейки.
Предсказание работает для того массива, по которому прописан цикл. Второй массив будет с проверкой на допустимый индекс.
S>>И немного сомневаюсь что аналогичное вычисление даже программа на C сделает за 2.5 секунды на моем компе даже при моей реальной частоте 3.5 ГГц. Задача на грани пропускной способности памяти моего компа.
C>25 миллиардов — вряд ли успеет, разве что на avx2, как предлагали. Но почему не попробовать?
Попробуйте C>И не меряйте пропускную способность своей памяти, она не особо интересна, меряйте само вычисление, оставаясь внутри L2 и TLB кэшей, как я. И можно результат даже не записывать, например аггрегировать ксором в переменную, ибо ТС спрашивал про алгоритм вычисления, а не про чтение-запись.
Уже дважды отписал.
ТС не выставлял условия измерения. Я выдумал одни условия, вы настаиваете на других. В тех условиях, на которых вы настаиваете, свитч вовсе не обязан работать быстрее.
C>Рандомные устроят.
S>>Полагаю что за счет более эффективной прокачки памяти. Ключевое здесь — "большого массива байт". На маленьких массивах свитч сливает в разы.
C>Не надо прокачивать память. Если на маленьких сливает в разы, такой эффект вполне может наблюдаться, просто торможение на свичах позволяет меньше интерферировать с прокачкой, и получается чуть быстрее. C>Что там на проценты, у меня на g++ программа начинала вдвое быстрее работать при вставке никогда не выполняющихся условий с распечаткой внутри, без всякой памяти, просто из-за не очень хорошей оптимизации компилятора, причём это удавалось на старых версиях (до 4.6), а на 4.7 в любом случае работала медленно. C>Но интересно именно время вычисления функции, без привязки к памяти. А какие времена на маленьких?
3 секунды LUT, 16 — switch.
Здравствуйте, samius, Вы писали:
S>Ссылка в предыдущем сообщении. Код работает, но времянка сильно другая, ибо для того что бы он вообще запускался на идеуане, пришлось взять размеры массивов по 1Мб.
Да, спасибо, итого у Вас 250М элементов выполняются примерно за секунду, что лутом, что свичом. Не вижу слива в 3-8 раз, не вижу слива вообще, даже если массив сделать размером 10К, чтобы остаться в кэшах.
Очевидно, компилятор соптимизировал этот свич в доступ к своей таблице.
Другая времянка — вполне логично, вряд ли там 3.5 ГГц, да и моно — это не мелкософт.нет.
S>Предсказание работает для того массива, по которому прописан цикл. Второй массив будет с проверкой на допустимый индекс.
По массиву, по которому прописан цикл, даже проверок скорее всего не будет, а по таблице может и будут, но они будут всегда успешны, значит процессор в рантайме тупо их предскажет и много на них не затратит, то есть сбоев конвейера не будет. Если повезёт, может даже заработать быстрее, как я описывал выше
S>ТС не выставлял условия измерения. Я выдумал одни условия, вы настаиваете на других. В тех условиях, на которых вы настаиваете, свитч вовсе не обязан работать быстрее.
А вот теперь самое интересное: на здоровенных массивах он может работать быстрее потому, что в тестах со свичом Вы просто не читаете входную память! Я уже два раза писал: у Вас switch(i), а надо switch(source[i]). И как раз на очень больших массивах тут появляется нехилый performance-gain
Потому я и настаивал на точном коде тестов. И лучше бы тесты делать с выдачей какого-нибудь итогового результата, так и шансов у компилятора всё выкинуть меньше, и такие ошибки быстро находятся.
Попробуйте у себя заменить, глядишь, морок и рассеется, то бишь обгон пропадёт.
S>3 секунды LUT, 16 — switch.
Значит, моно гораздо лучше оптимизирует такие свичи Здесь они идут один к одному.
S>Проблема с пуском на ideone в том, что он ограничивает как объем памяти, так и время выполнения.
Если зарегиться — даёт 15 секунд вроде. По памяти — да, но она обычно не критична.
Здравствуйте, VladFein, Вы писали:
VF>А компилятор как делит на 2, 4, 8, и т. д.?
А как бог на душу положит В смысле implementation defined.
Проблемы с делением могут быть из-за того, что входной тип знаковый, там вроде бы простым сдвигом не обойдёшься, если надо к нулю округлять. И это ещё надо догадаться, что после маски число реально неотрицательное.
Фишка в том, что, например, на ideone действительно ускоряется с 2.86 до 2.16 при замене деления на сдвиги, а сложения на оры. При замене оров на ксоры ускоряется до 2.05. Без функции (если возвращать сам x) работает за 0.56.
Здравствуйте, cures, Вы писали:
C>Здравствуйте, samius, Вы писали:
S>>Ссылка в предыдущем сообщении. Код работает, но времянка сильно другая, ибо для того что бы он вообще запускался на идеуане, пришлось взять размеры массивов по 1Мб.
C>Да, спасибо, итого у Вас 250М элементов выполняются примерно за секунду, что лутом, что свичом. Не вижу слива в 3-8 раз, не вижу слива вообще, даже если массив сделать размером 10К, чтобы остаться в кэшах. C>Очевидно, компилятор соптимизировал этот свич в доступ к своей таблице. C>Другая времянка — вполне логично, вряд ли там 3.5 ГГц, да и моно — это не мелкософт.нет.
Да, видимо в компиляторе моно есть такая оптимизация для свитча.
S>>Предсказание работает для того массива, по которому прописан цикл. Второй массив будет с проверкой на допустимый индекс.
C>По массиву, по которому прописан цикл, даже проверок скорее всего не будет, а по таблице может и будут, но они будут всегда успешны, значит процессор в рантайме тупо их предскажет и много на них не затратит, то есть сбоев конвейера не будет. Если повезёт, может даже заработать быстрее, как я описывал выше
S>>ТС не выставлял условия измерения. Я выдумал одни условия, вы настаиваете на других. В тех условиях, на которых вы настаиваете, свитч вовсе не обязан работать быстрее.
C>А вот теперь самое интересное: на здоровенных массивах он может работать быстрее потому, что в тестах со свичом Вы просто не читаете входную память! Я уже два раза писал: у Вас switch(i), а надо switch(source[i]). И как раз на очень больших массивах тут появляется нехилый performance-gain C>Потому я и настаивал на точном коде тестов. И лучше бы тесты делать с выдачей какого-нибудь итогового результата, так и шансов у компилятора всё выкинуть меньше, и такие ошибки быстро находятся. C>Попробуйте у себя заменить, глядишь, морок и рассеется, то бишь обгон пропадёт.
О, да, благодарю. Все пропало, свитч сливает в 10 раз. На больших объемах неправильный свитч не читал исходный массив, а значит и памяти прогонял вдвое меньше.
S>>3 секунды LUT, 16 — switch.
что странно, эти цифры не изменились после исправления цикла.
C>Значит, моно гораздо лучше оптимизирует такие свичи Здесь они идут один к одному.
Угу
S>>Проблема с пуском на ideone в том, что он ограничивает как объем памяти, так и время выполнения.
C>Если зарегиться — даёт 15 секунд вроде. По памяти — да, но она обычно не критична.
Здравствуйте, samius, Вы писали:
S>О, да, благодарю. Все пропало, свитч сливает в 10 раз. На больших объемах неправильный свитч не читал исходный массив, а значит и памяти прогонял вдвое меньше.
Возможно, не только, оптимизатор .нет мог заметить, что при i > 255 он вообще не попадает ни в один кейс, и для них остаётся старый result. Хотя тогда он выигрывал бы и на гораздо меньших кусках.
S>>>3 секунды LUT, 16 — switch. S>что странно, эти цифры не изменились после исправления цикла.
Не так уж и странно, пока память в кешах, ему, видимо, без разницы, от чего считать.
Немножко извращённый, но вроде бы делает то же самое, но чуть быстрее. Тут 4 сдвига, 3 энда и один ксор. Если они могут выполняться по 3 за такт, то вычисление на sse2 может уложиться в 3 такта, а не в 4
Здравствуйте, Cynic, Вы писали:
C>Вот чё то идея эта пришла только после того как запостил сообщение. C>Щас попробовал, примерно в 4-ре раза быстрее первого способа и в 12 раз быстрее второго.
Первый способ можно легко ускорить в 8 раз, обрабатывая по 8 байт за раз.
long lomg x, y;
y = x & 0x0101010101010101;
x >>= 1;
y = x & 0x0202020202020202:
x >>= 1;
y = x & 0x0404040404040404;
x >>= 1;
y = x & 0x0808080808080808;
x >>= 1;
Здравствуйте, VladFein, Вы писали:
S>>Зачем деление, когда можно просто сдвиг(>>) использовать. Быстрее должно быть.
VF>А компилятор как делит на 2, 4, 8, и т. д.?
Зависит от компилятора. А если он к float'aм еще приведет...
Здравствуйте, VladFein, Вы писали:
VF>А может ну его тогда, такой компилятор?
Ко всему прочему, он ещё в полтора-два раза сливает обычному Ц, даже при табличном доступе.
А мышки плакали, кололись, но продолжали...
Впрочем, это уже похоже на оффтоп и языкосрач
Здравствуйте, cures, Вы писали:
C>Здравствуйте, VladFein, Вы писали:
VF>>А может ну его тогда, такой компилятор?
C>Ко всему прочему, он ещё в полтора-два раза сливает обычному Ц, даже при табличном доступе. C>А мышки плакали, кололись, но продолжали... C>Впрочем, это уже похоже на оффтоп и языкосрач
Здравствуйте, Sharov, Вы писали:
S>А кто в языковом мире не сливает обычному Ц?
Нет таких, даже Ц сам себе сливает
Хотя есть ассемблер, но и на нём надо очень постараться, чтобы обогнать.
Вопрос только в том, насколько сливает. Диез в этом плане не так плох, примерно как жаба, только чуть удобнее, так как есть value-type структуры. Планируется ещё Julia над шлангом, совмещающая скорость и всепрощение к неумеющим работать с памятью, но там индексы с единицы — не взлетит.
C>Немножко извращённый, но вроде бы делает то же самое, но чуть быстрее. Тут 4 сдвига, 3 энда и один ксор.
Пример, конечно, интересный, но почему быстрее? Из-за числа инструкций что-ли? Так скорость не только от их количества зависит. Более длинная программа может значительно обгонять короткую. C>Если они могут выполняться по 3 за такт,
Посмотри на код, тут используется аж два сдвига на переменную, а не на постоянную величину. На intel это традиционный тормоз по меркам побитовых операций.
C> то вычисление на sse2 может уложиться в 3 такта, а не в 4
Ну какое ещё sse2? Нет для этого кода никакого будущего на sse — он крайне плохо подходит для векторизации.
Во-первых, тут сдвигаются большие числа (вроде 0xc84040) для их хранения тебе не хватит ни 8, ни 16 бит, а следовательно в xmm регистр поместятся лишь 4 операнда за раз. Плюс ещё понадобится код для распаковки байтов в эти 32х битные операнды. Хотя есть куда более простой код (см. далее), который прекрасно обрабатывает сразу 16 байтами за раз, полностью используя весь регистр.
Во-вторых, в sse2 нельзя сдвинуть значения xmm регистра на различные величины. Только на константу, либо на переменную, но одинаковую для всего регистра. А произвольный сдвиг ни на sse2, ни на sse3, sse4 или avx сделать нельзя. Только в avx2 впервые появилась инструкция параллельного сдвига (vpsrlvd). Да, довольно поздно для банального побитового сдвига, но так уж есть.
А ещё, если всё же взять процессоры с avx2, то там рядом будет набор набор инструкций bmi2, в котором есть инструкция pext — она вообще решает исходную задачу в одно действие — pext eax, 0x55 (и больше ничего не нужно). На фоне этого связываться с векторизацией вышеприведённой реализации функции — совсем сомнительная затея.
Если уж хочется использовать sse для быстрого преобразования, то делать нужно не так.
Нужно сначала написать обычный код для байта, желательно получше чем в первом сообщении, например, такой:
ui8 dz1(ui8 u) {
u &= 0x55;
u |= u >> 1;
u &= 0x33;
u |= u >> 2;
u &= 0x0f;
return u;
}
И обобщить его на вектор из байт. Можно под вектором подразумевать не обязательно xmm регистр, а даже взять обычный 32/64 битный регистр общего назначения:
ui32 dz4(ui32 u) {
u &= 0x55555555;
u |= u >> 1;
u &= 0x33333333;
u |= u >> 2;
u &= 0x0f0f0f0f;
return u;
}
Либо всё же xmm:
#include"emmintrin.h"
__m128i dz16(__m128i u) {
u = _mm_and_si128(u, _mm_set1_epi8(0x55));
u = _mm_or_si128(u, _mm_srli_epi32(u, 1));
u = _mm_and_si128(u, _mm_set1_epi8(0x33));
u = _mm_or_si128(u, _mm_srli_epi32(u, 2));
u = _mm_and_si128(u, _mm_set1_epi8(0x0f));
return u;
}
Вот так.
При использовании компилятора gcc-4.8 в простеньком тесте на ноутбуке вариант со сдвигом констант 0x321010 и 0xc84040 обрабатывает 0.617*109 элементов в секунду. Вариант с lookup-table работает значительно быстрее и обрабатывает уже 2.593*109 элементов в секунду. А последние два варианта (dz4 и dz16) обрабатывают по 5.970*109 элементов в секунду (разницы между использованием в коде 32 и 128 битных регистров нет из-за того, что у gcc хороший автовекторизатор, и компилятор сам переписал цикл с функцией dz4 на sse2, получив почти аналог dz16).
В общем, получается так, что вариант с sse2 действительно быстрее. И при компиляции в нативный код обгоняет lookup-table где-то в 2.3 раза. Причём для его использования не обязательно даже писать simd код, а достаточно просто взять хороший компилятор и выставить соответствующие настройки оптимизации. Но зато вариант с LUT, хоть и медленнее, но удобнее в использовании — он не требует особой организации данных как вариант с sse2. Да и из C# дергать его сподручнее чем sse2 код.
