Помогите найти самый быстрый алгоритм для выполнения следующей операции.
Дано число типа 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)), вставьте результат в код вашего теста.
