Re[9]: Самый быстрый алгоритм
От: BulatZiganshin  
Дата: 25.01.15 11:07
Оценка:
Здравствуйте, samius, Вы писали:

S>Остальные ответы, полагаю, вы в состоянии получить сами. Причем в той форме, которая вас удовлетворит.


2.5 ГБ за 21 секунду, частота твоего компа пусть 1 ГГц. выходит на порядок медленней программы, написанной на С — она это сделает за 2.5 секунды
Люди, я люблю вас! Будьте бдительны!!!
Re[9]: Самый быстрый алгоритм
От: BulatZiganshin  
Дата: 25.01.15 11:10
Оценка:
Здравствуйте, samius, Вы писали:

S>Чем по-вашему данные, всосанные из входного файла лучше данных, высосанных из Random?


скорость работы программы может зависеть от входных данных. так что в идеале надо тестировать на взвешенной смеси реальных вхдных данных, хотя это само по себе проблема. хотя в данном случае случайные данные дадут результат всяко не быстрее любых реальных
Люди, я люблю вас! Будьте бдительны!!!
Re[3]: Самый быстрый алгоритм
От: Arsen.Shnurkov  
Дата: 25.01.15 14:49
Оценка:
S>Практика показывает что switch на пару процентов может быть быстрее. Стабильно быстрее при конвертации большого массива байт в другой массив.

А за счет чего?
Re[2]: Самый быстрый алгоритм
От: TK Лес кывт.рф
Дата: 25.01.15 16:30
Оценка:
Здравствуйте, Pzz, Вы писали:

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


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


Команды бывают разные. Одно дело операция с данными из регистра, а другое дело промах мимо кеша.
Если у Вас нет паранойи, то это еще не значит, что они за Вами не следят.
Re[9]: Самый быстрый алгоритм
От: cures Россия cures.narod.ru
Дата: 25.01.15 22:31
Оценка: -1
Здравствуйте, 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 для табличного. А сколько получится со свичом?
Re[10]: Самый быстрый алгоритм
От: cures Россия cures.narod.ru
Дата: 25.01.15 22:34
Оценка:
Здравствуйте, BulatZiganshin, Вы писали:

BZ>2.5 ГБ за 21 секунду, частота твоего компа пусть 1 ГГц. выходит на порядок медленней программы, написанной на С — она это сделает за 2.5 секунды


Там написано 100 миллионов элементов на 250 итераций, то есть 25 ГБ, итого вполне конкурентоспособный результат, если правильный.
Re[10]: Самый быстрый алгоритм
От: samius Россия http://sams-tricks.blogspot.com
Дата: 25.01.15 23:19
Оценка:
Здравствуйте, 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 ГГц. Задача на грани пропускной способности памяти моего компа.
Re[10]: Самый быстрый алгоритм
От: samius Россия http://sams-tricks.blogspot.com
Дата: 25.01.15 23:20
Оценка:
Здравствуйте, BulatZiganshin, Вы писали:

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


S>>Чем по-вашему данные, всосанные из входного файла лучше данных, высосанных из Random?


BZ>скорость работы программы может зависеть от входных данных. так что в идеале надо тестировать на взвешенной смеси реальных вхдных данных, хотя это само по себе проблема. хотя в данном случае случайные данные дадут результат всяко не быстрее любых реальных

Так все-таки, рандомные данные устроят?
Re[4]: Самый быстрый алгоритм
От: samius Россия http://sams-tricks.blogspot.com
Дата: 25.01.15 23:25
Оценка:
Здравствуйте, Arsen.Shnurkov, Вы писали:

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


AS>А за счет чего?

Полагаю что за счет более эффективной прокачки памяти. Ключевое здесь — "большого массива байт". На маленьких массивах свитч сливает в разы.
Re[10]: Самый быстрый алгоритм
От: samius Россия http://sams-tricks.blogspot.com
Дата: 25.01.15 23:49
Оценка:
Здравствуйте, 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 в том, что он ограничивает как объем памяти, так и время выполнения.
Re[11]: Самый быстрый алгоритм
От: cures Россия cures.narod.ru
Дата: 25.01.15 23:57
Оценка:
Здравствуйте, 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 в любом случае работала медленно.
Но интересно именно время вычисления функции, без привязки к памяти. А какие времена на маленьких?
Re[12]: Самый быстрый алгоритм
От: samius Россия http://sams-tricks.blogspot.com
Дата: 26.01.15 00:07
Оценка:
Здравствуйте, 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.
Re[13]: Самый быстрый алгоритм
От: cures Россия cures.narod.ru
Дата: 26.01.15 00:32
Оценка: 10 (1)
Здравствуйте, 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 секунд вроде. По памяти — да, но она обычно не критична.
Re[2]: Самый быстрый алгоритм
От: VladFein США www.FeinSoftware.com
Дата: 26.01.15 01:21
Оценка:
Здравствуйте, Sharov, Вы писали:

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


S>Зачем деление, когда можно просто сдвиг(>>) использовать. Быстрее должно быть.


А компилятор как делит на 2, 4, 8, и т. д.?
Re[3]: Самый быстрый алгоритм
От: cures Россия cures.narod.ru
Дата: 26.01.15 01:37
Оценка:
Здравствуйте, VladFein, Вы писали:

VF>А компилятор как делит на 2, 4, 8, и т. д.?


А как бог на душу положит В смысле implementation defined.
Проблемы с делением могут быть из-за того, что входной тип знаковый, там вроде бы простым сдвигом не обойдёшься, если надо к нулю округлять. И это ещё надо догадаться, что после маски число реально неотрицательное.
Фишка в том, что, например, на ideone действительно ускоряется с 2.86 до 2.16 при замене деления на сдвиги, а сложения на оры. При замене оров на ксоры ускоряется до 2.05. Без функции (если возвращать сам x) работает за 0.56.
Re[14]: Самый быстрый алгоритм
От: samius Россия http://sams-tricks.blogspot.com
Дата: 26.01.15 02:05
Оценка:
Здравствуйте, 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 секунд вроде. По памяти — да, но она обычно не критична.
Re[15]: Самый быстрый алгоритм
От: cures Россия cures.narod.ru
Дата: 26.01.15 02:29
Оценка:
Здравствуйте, samius, Вы писали:

S>О, да, благодарю. Все пропало, свитч сливает в 10 раз. На больших объемах неправильный свитч не читал исходный массив, а значит и памяти прогонял вдвое меньше.


Возможно, не только, оптимизатор .нет мог заметить, что при i > 255 он вообще не попадает ни в один кейс, и для них остаётся старый result. Хотя тогда он выигрывал бы и на гораздо меньших кусках.

S>>>3 секунды LUT, 16 — switch.

S>что странно, эти цифры не изменились после исправления цикла.

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

Кстати, вот ещё один варант функции F:
return (byte) (((0x321010 >> ((i << 2) & 20)) ^ (0xc84040 >> ((i >> 2) & 20))) & 0xf);

Немножко извращённый, но вроде бы делает то же самое, но чуть быстрее. Тут 4 сдвига, 3 энда и один ксор. Если они могут выполняться по 3 за такт, то вычисление на sse2 может уложиться в 3 такта, а не в 4
Re[3]: Самый быстрый алгоритм
От: VladFein США www.FeinSoftware.com
Дата: 26.01.15 03:19
Оценка:
Здравствуйте, 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;
Re[3]: Самый быстрый алгоритм
От: Sharov Россия  
Дата: 26.01.15 10:32
Оценка:
Здравствуйте, VladFein, Вы писали:

S>>Зачем деление, когда можно просто сдвиг(>>) использовать. Быстрее должно быть.


VF>А компилятор как делит на 2, 4, 8, и т. д.?


Зависит от компилятора. А если он к float'aм еще приведет...
Кодом людям нужно помогать!
Re[4]: Самый быстрый алгоритм
От: VladFein США www.FeinSoftware.com
Дата: 26.01.15 14:17
Оценка:
Здравствуйте, Sharov, Вы писали:

VF>>А компилятор как делит на 2, 4, 8, и т. д.?


S>Зависит от компилятора. А если он к float'aм еще приведет...


А может ну его тогда, такой компилятор?
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.