Самый быстрый алгоритм
От: Cynic Россия  
Дата: 24.01.15 16:28
Оценка: :)
Помогите найти самый быстрый алгоритм для выполнения следующей операции.
Дано число типа byte, например 210, которое в двоичной форме выглядит как 11010010. Если считать биты слева на право, а индекс первого бита равен 1, то нужно извлечь из этого числа чётные биты и сформировать из него 4-х битное число.
Например:
210 (dec) -> 11010010 (bin)
Нужно извлечь биты выделенные полужирным и сформировать число 1100 (bin) -> 80 (dec).

Пробовал два алгоритма.
1)
    byte byteNum = 210;
    int num = (int)(byteNum) & 0x55;
        int num2 = (num & 64) / 8 + (num & 16) / 4 + (num & 4) / 2 + (num & 1);


2)
Сгенерировать все возможные 256 комбинаций пар ключ/значение, где ключ это искомое число, а значение результат преобразования.
Загрузить их в Hashtable и потом искать по ключу.

Второй способ в 3 раза медленнее первого. Но и первый способ не блещет производительность.
Какие ещё есть варианты.
:)
Re: Самый быстрый алгоритм
От: MT-Wizard Украина  
Дата: 24.01.15 16:34
Оценка: 1 (1) +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>    byte byteNum = 210;
C>    int num = (int)(byteNum) & 0x55;
C>        int num2 = (num & 64) / 8 + (num & 16) / 4 + (num & 4) / 2 + (num & 1);
C>


C>2)

C>Сгенерировать все возможные 256 комбинаций пар ключ/значение, где ключ это искомое число, а значение результат преобразования.
C>Загрузить их в Hashtable и потом искать по ключу.

C>Второй способ в 3 раза медленнее первого. Но и первый способ не блещет производительность.

C>Какие ещё есть варианты.

3. Как второй, только загрузить не в хэш, а в обычный массив и индексировать входным числом
А ти, москалику, вже приїхав (с)
Re[2]: Самый быстрый алгоритм
От: Cynic Россия  
Дата: 24.01.15 16:37
Оценка:
MW>3. Как второй, только загрузить не в хэш, а в обычный массив и индексировать входным числом

Вот чё то идея эта пришла только после того как запостил сообщение.
Щас попробовал, примерно в 4-ре раза быстрее первого способа и в 12 раз быстрее второго.
:)
Re[3]: Самый быстрый алгоритм
От: Cynic Россия  
Дата: 24.01.15 16:57
Оценка:
Здравствуйте, Cynic, Вы писали:

MW>>3. Как второй, только загрузить не в хэш, а в обычный массив и индексировать входным числом


C>Вот чё то идея эта пришла только после того как запостил сообщение.

C>Щас попробовал, примерно в 4-ре раза быстрее первого способа и в 12 раз быстрее второго.

Немного отклонюсь от темы.
У меня алгоритм работает с массивом byte. По ходу работы программы значения в этом массиве претерпевают разные преобразования с использованием математических операторов (+,-,/,*) и битовых операторов (<, >, |, &, ^). Я так понимаю, что когда программа производит вычисления со значениями типа byte, то она всё время выполняет преобразование из byte в int и наоборот. Если принять во внимание, что расход памяти меня не слишком волнует, а вот производительность критична, не стоит ли мне в этом случае использовать массив int, даже не смотря на то, что будут использоваться только первые 8 бит этого типа?
:)
Re: Самый быстрый алгоритм
От: Pzz Россия https://github.com/alexpevzner
Дата: 24.01.15 16:59
Оценка:
Здравствуйте, Cynic, Вы писали:

C>2)

C>Сгенерировать все возможные 256 комбинаций пар ключ/значение, где ключ это искомое число, а значение результат преобразования.
C>Загрузить их в Hashtable и потом искать по ключу.

Надо не в hashtable было загрузить, а в массив. Это же всего лишь 256 байт.

Быстрее этого вряд ли что-то удастся придумать. В принципе, слазить в байтовый массив — это одна машинная команда (ну, если на достаточно низкоуровневом языке писать).
Re: Самый быстрый алгоритм
От: Sharov Россия  
Дата: 24.01.15 18:06
Оценка: +2 -2
Здравствуйте, Cynic, Вы писали:

C>Пробовал два алгоритма.

C>1)
C>
C>    byte byteNum = 210;
C>    int num = (int)(byteNum) & 0x55;
C>        int num2 = (num & 64) / 8 + (num & 16) / 4 + (num & 4) / 2 + (num & 1);
C>


Зачем деление, когда можно просто сдвиг(>>) использовать. Быстрее должно быть.
Кодом людям нужно помогать!
Re[2]: Самый быстрый алгоритм
От: Cynic Россия  
Дата: 24.01.15 18:24
Оценка:
Здравствуйте, Sharov, Вы писали:
S>Зачем деление, когда можно просто сдвиг(>>) использовать. Быстрее должно быть.

Согласен, на 15% быстрее. Но всё равно в разы медленнее чем в алгоритме с массивом byte.
:)
Re[2]: Самый быстрый алгоритм
От: samius Россия http://sams-tricks.blogspot.com
Дата: 24.01.15 18:56
Оценка:
Здравствуйте, Pzz, Вы писали:

Pzz>Надо не в hashtable было загрузить, а в массив. Это же всего лишь 256 байт.


Pzz>Быстрее этого вряд ли что-то удастся придумать. В принципе, слазить в байтовый массив — это одна машинная команда (ну, если на достаточно низкоуровневом языке писать).


Практика показывает что switch на пару процентов может быть быстрее. Стабильно быстрее при конвертации большого массива байт в другой массив.
Re[3]: Самый быстрый алгоритм
От: Cynic Россия  
Дата: 24.01.15 18:59
Оценка:
Здравствуйте, samius, Вы писали:
S>Практика показывает что switch на пару процентов может быть быстрее. Стабильно быстрее при конвертации большого массива байт в другой массив.

И как сюда можно switch прикрутить?
:)
Re[4]: Самый быстрый алгоритм
От: samius Россия http://sams-tricks.blogspot.com
Дата: 24.01.15 19:03
Оценка:
Здравствуйте, 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;
            }
Re: Самый быстрый алгоритм
От: cures Россия cures.narod.ru
Дата: 24.01.15 22:23
Оценка: +1
Здравствуйте, Cynic, Вы писали:

Быстрее, чем из массива, не получите никак. Но зачем их в этом примере кода преобразуют в инты?
И зачем первоначальная маска с 0x55, если потом всё равно по битам выковыриваем?
А вот что от замены деления на сдвиг что-то ускорилось — это очень странно, компилятор такие вещи обычно делает сам.
У вас вообще оптимизация включена? И чем компилите? А что за тип byte?
Re[5]: Самый быстрый алгоритм
От: BulatZiganshin  
Дата: 24.01.15 22:56
Оценка:
Здравствуйте, samius, Вы писали:

S>>>Практика показывает что switch на пару процентов может быть быстрее. Стабильно быстрее при конвертации большого массива байт в другой массив.


нет, это горазщдо медленней обращения в память. этот код загрузит из памяти адрес перехода (уже загрузка по выч. адресу!), затем призведёт непредсказанный переход и затем ещё загрузит константу и ещё раз сделает переход. на С такое было бы на порядок медленней простой загрузки
Люди, я люблю вас! Будьте бдительны!!!
Re[3]: Самый быстрый алгоритм
От: BulatZiganshin  
Дата: 24.01.15 22:58
Оценка:
Здравствуйте, Cynic, Вы писали:

MW>>3. Как второй, только загрузить не в хэш, а в обычный массив и индексировать входным числом

C>Щас попробовал, примерно в 4-ре раза быстрее первого способа и в 12 раз быстрее второго.

на С скорость бы была одно преобразование в такт, т.е. 4 млрд на 4 ГГц процессоре. думаю этого должно хватить

ps: если не хватит, то на sse2 будет 4 преобразования в такт, а на avx2 — вдвое больше
Люди, я люблю вас! Будьте бдительны!!!
Отредактировано 24.01.2015 23:56 BulatZiganshin . Предыдущая версия .
Re[6]: Самый быстрый алгоритм
От: samius Россия http://sams-tricks.blogspot.com
Дата: 24.01.15 23:04
Оценка: +1
Здравствуйте, BulatZiganshin, Вы писали:

BZ>Здравствуйте, samius, Вы писали:


S>>>>Практика показывает что switch на пару процентов может быть быстрее. Стабильно быстрее при конвертации большого массива байт в другой массив.


BZ>нет, это горазщдо медленней обращения в память. этот код загрузит из памяти адрес перехода (уже загрузка по выч. адресу!), затем призведёт непредсказанный переход и затем ещё загрузит константу и ещё раз сделает переход. на С такое было бы на порядок медленней простой загрузки


Что значит "нет"?
У меня тесты. Там где лут трудится 22 сек, свитч 21 сек. Результат повторяется стабильно. Не знаю, как в C, не пробовал.
Re[7]: Самый быстрый алгоритм
От: BulatZiganshin  
Дата: 24.01.15 23:51
Оценка:
Здравствуйте, samius, Вы писали:

S>Что значит "нет"?

S>У меня тесты. Там где лут трудится 22 сек, свитч 21 сек. Результат повторяется стабильно. Не знаю, как в C, не пробовал.

а ты на случайных данных тестировал или просто нулях? и сколько тактов процессора уходит на обработку олдного байта, а то эти секунды нам ни о чём не говорят?
Люди, я люблю вас! Будьте бдительны!!!
Re[7]: Самый быстрый алгоритм
От: cures Россия cures.narod.ru
Дата: 24.01.15 23:53
Оценка:
Здравствуйте, samius, Вы писали:

S>Что значит "нет"?

S>У меня тесты. Там где лут трудится 22 сек, свитч 21 сек. Результат повторяется стабильно. Не знаю, как в C, не пробовал.

С таким "тестом" — не удивительно
Там компилятор наверняка преобразовал в result = 255 — i для первых 256 маленьких i, для остальных оставил тупо 0.
Вы попробуйте честно делать switch(source[i]) и в кейсах указать правильные значения результата, а гонять (много раз) на произвольных сорсах, всосанных из входного файла. И даже при этом он скорее всего заменит на табличное присваивание, а 1 секунда из 22 — не показатель, чуть получше уложенный код.
Или полные тесты в студию, с правильными результатами, неконстантным входом и полными ключами сборки.
Re[4]: Самый быстрый алгоритм
От: cures Россия cures.narod.ru
Дата: 25.01.15 00:05
Оценка:
Здравствуйте, BulatZiganshin, Вы писали:

BZ>на С скорость бы была одно преобразование в такт, т.е. 4 млрд на 4 ГГц процессоре. думаю этого должно хватить


Справедливости ради, вряд ли один такт, надо сформировать адрес (сложение) и вытащить из массива, что даже из L1 чуть больше. Казалось бы, это можно распараллелить, но компилятор не имеет права, ибо source и dest могут перекрываться, надо специально указывать, что это не так, и, скорее всего, руками разворачивать цикл.

BZ>ps: если не хватит, то на sse2 будет 4 преобразования в такт, а на avx2 — вдвое больше


Какая инструкция из sse2 или avx2 умеет делать подстановку из массива для всех элементов? Уж очень неправдоподобно, множественный доступ в память за 1 такт.
Re[5]: Самый быстрый алгоритм
От: BulatZiganshin  
Дата: 25.01.15 00:15
Оценка:
Здравствуйте, 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 такта. ну и загрузка/сохранение в свободные места втиснутся
Люди, я люблю вас! Будьте бдительны!!!
Re[8]: Самый быстрый алгоритм
От: samius Россия http://sams-tricks.blogspot.com
Дата: 25.01.15 06:54
Оценка:
Здравствуйте, BulatZiganshin, Вы писали:

BZ>Здравствуйте, samius, Вы писали:


S>>Что значит "нет"?

S>>У меня тесты. Там где лут трудится 22 сек, свитч 21 сек. Результат повторяется стабильно. Не знаю, как в C, не пробовал.

BZ>а ты на случайных данных тестировал или просто нулях? и сколько тактов процессора уходит на обработку олдного байта, а то эти секунды нам ни о чём не говорят?

На случайных. Мне секунды говорят о том что на конвертации массива из 100000000 байт в такой же массив свитч стабильно работает на 4.5% шустрее. Замеры секунд произведятся на 250 итерациях.
Остальные ответы, полагаю, вы в состоянии получить сами. Причем в той форме, которая вас удовлетворит.
Re[8]: Самый быстрый алгоритм
От: samius Россия http://sams-tricks.blogspot.com
Дата: 25.01.15 07:02
Оценка:
Здравствуйте, 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)), вставьте результат в код вашего теста.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.