Здравствуйте, 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м еще приведет...
