Перейти к содержимому
Zer0Galaxy

Оптимизация округления в Lua

Рекомендуемые сообщения

Вы запускаете один и тот же код?

Я вижу, что у @Zer0Galaxy используется local uptime=require("computer").uptime, наверное @ECS скопировал его.

А @eu_tomat использует local uptime=os.clock

В чем их различие, кстати?

Изменено пользователем hohserg

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
7 часов назад, hohserg сказал:

@Zer0Galaxy используется local uptime=require("computer").uptime, наверное @ECS скопировал его.

Мы тут все слегка изменяем код Zer0Galaxy.

7 часов назад, hohserg сказал:

@eu_tomat использует local uptime=os.clock

Это фрагмент варианта ECS. Ему, похоже, было лень менять название на другое. И я тоже не стал переделывать.
Название вводит в заблуждение, но логика кода верная.

 

computer.uptime() возвращает округлённое до целых тиков время работы компьютера с момента его включения.
os.clock() возвращает время, в течение которого компьютер был занят вычислениями, не округляя его до тиков.

 

Конкретно в этом случае для измерения уместнее использовать именно os.clock.

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Lua не перестаёт удивлять.

$ lua5.3 -e 't0=os.clock()local v for i=1,1e9 do v=i//1.0 end print(os.clock()-t0)'
11.848781
$ lua5.3 -e 't0=os.clock()local v for i=1,1e9 do v=i//1 end print(os.clock()-t0)'
16.08497

Операция целочисленного деления на целочисленную константу работает медленнее, нежели на константу с плавающей точкой.

Соответственно, округление (val+0.5)//1.0 также будет выполняться быстрее, чем (val+0.5)//1.

  • Нравится 2
  • Спасибо 1
  • Ха-ха 3

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
В 02.10.2021 в 23:37, eu_tomat сказал:

Операция целочисленного деления на целочисленную константу работает медленнее, нежели на константу с плавающей точкой

Неожиданно

Это небось всякие оптимизации под SSE влияют

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Прикол в том, что целочисленное деление на целое число должно быть быстрее целочисленного деления на дробное

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
1 минуту назад, hohserg сказал:

Прикол в том, что целочисленное деление на целое число должно быть быстрее целочисленного деления на дробное

О том и речь. Делимое-то тоже целочисленное. Всё целочисленное: и операция деления, и делимое, и делитель, и частное. Но есть нюанс.

 

Для понимания сути происходящего пришлось погрузиться в чтение исходников Lua. Пересказывать всю цепочку поисков слишком долго. Поэтому кратко изложу принципы. Сначала ищем по всем файлам фрагмент "idiv", затем сопоставляем, что откуда вызывается, а для завершения картины запрашиваем построение ассемблерного листинга нужных файлов с использованием опций из makefile.

 

В сухом остатке имеем:

  • Есть две разные операции целочисленного деления: для целых и для дробных чисел, как бы странно это не звучало.
  • Операция целочисленного деления реализована гораздо более сложным кодом, нежели деление дробных чисел.

Целочисленное деление дробных чисел:

# lobject.c:81:     case LUA_OPIDIV: return luai_numidiv(L, v1, v2);
        vdivsd  %xmm1, %xmm0, %xmm0     # v2, v1, tmp101
        vroundsd        $9, %xmm0, %xmm0, %xmm0 #, tmp101, <retval>
        ret

Целочисленное деление целых чисел:

# lobject.c:60:     case LUA_OPIDIV: return luaV_idiv(L, v1, v2);
        movq    %rcx, %rdx      # v2,
        movq    %rax, %rsi      # v1,
        jmp     luaV_idiv       #
...
luaV_idiv:
        leaq    1(%rdx), %rax
        movq    %rdx, %rcx
        cmpq    $1, %rax
        jbe     .L350
        movq    %rsi, %rax
        cqto
        idivq   %rcx
        xorq    %rsi, %rcx
        js      .L351
        ret
...

Часть кода вырезана, там обрабатываются проверки деления на ноль и работы с отрицательными числами. Но и в этом куске кода почти все операции выполняют эти самые проверки.

 

Необходимыми же операциями являются лишь idivq, да ret. Возможно, там нужны ещё какие-то операции перемещения из регистра в регистр, но они быстрые в сравнении с названными выше.

 

8 часов назад, man_cubus сказал:

Это небось всякие оптимизации под SSE влияют

Влияют. Тем не менее я рискну предположить, что на чистом Си без вспомогательных проверок целочисленное деление выполнится быстрее нежели дробное. Даже с SSE-оптимизациями. Возможно, кто-то проверит.

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

// сначала конвертирует всё в инт, поэтому и повидло.
http://www.inf.puc-rio.br/~roberto/talks/ws2014.pdf

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
42 минуты назад, prop сказал:

// сначала конвертирует всё в инт

Во-первых, эта гипотеза не подтверждается исходниками Lua. Во-вторых, не подтверждается экспериментально. Усечённый листинг исходников я уже продемонстрировал, теперь настало время демонстрации.

 

1. Этот эксперимент показывает явную зависимость типа возвращаемого результата от типов операндов:

> return 7//3
2
> return 7.0//3
2.0

В первом случае результат целочисленный, а во втором – дробный. Если операнды предварительно округляются, то зачем приводится к дробному типу результат операции? Да и и если бы эта гипотеза была верна, то операция с целочисленными операндами выполнялась бы быстрее, нежели с дробными. А ситуация явно противоположная.

 

2. Этот эксперимент демонстрирует, что округляется лишь результат, но не операнды:

> 3 // 1
3

> return 3.1//1.1
2.0

> 3.9 // 1.9
2.0

 

Теперь почитаем приведённый выше учебник Роберту – наше всё – Иерузалимски:

Цитата

Integer division converts operands to integers and does an integer division

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Эксперименты - это хорошо, когда нет более надежных источников.

По поводу скорости целочисленного деления.

Идем в сорсы.
 

Видим, что при OP_IDIV, если оба операнда int, то используется intarith, а затем luaV_idiv
тык

Если же нет, то numarith и luai_numidiv
тык

Соответственно получаем, что самое медленное - это целочисленное деление двух int,
затем целочисленное деление float и int(в любом порядке)

и наконец самое быстрое - простое деление.
image.png.1c8d965796d5acda80091a0830f1c840.png
 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
Скрытый текст
1 час назад, prop сказал:


image.png.1c8d965796d5acda80091a0830f1c840.png

 

Предлагаю переоформить этот эксперимент, т.к. совершенно невозможно понять, что именно этот эксперимент демонстрирует, или перепроверить результаты. Тут запускаются какие-то файлы с неизвестным кодом. В этом осуждении уже приведён более читаемый и воспроизводимый пример:

В 02.10.2021 в 23:37, eu_tomat сказал:

$ lua5.3 -e 't0=os.clock()local v for i=1,1e9 do v=i//1.0 end print(os.clock()-t0)'
11.848781
$ lua5.3 -e 't0=os.clock()local v for i=1,1e9 do v=i//1 end print(os.clock()-t0)'
16.08497

 

Такое оформление позволяет сразу увидеть и версию Lua, и код, и полученный результат. А кроме этого позволяет легко скопировать код для перепроверки результата. Приведённый же скриншот позволяет лишь увидеть не привязанный ни к чему результат.

 

 

И, кстати, чем обосновано это противопоставление?

55 минут назад, prop сказал:

Эксперименты - это хорошо, когда нет более надежных источников.
...

Идем в сорсы.

Оба подхода дополняют друг друга.

 

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

 

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

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Код взят из этой темы:

t0=os.clock()
local v 
for i=1,1e9 do 
v=i//1.0 
end 
print(os.clock()-t0)

Разница только в 

int_idiv:     i // 1

float_idiv:  i // 1.0

div:            i / 1.0

 

Цитата

Но тебя этот пост не убедил, т.к. полученный результат противоречит учебнику.


Я поделился информацией, остальное кто-то додумал сам.

tl;dr
В итоге я провел свое исследование потому что ты нечетко обозначил результаты своего, кроме краткого

Цитата

Операция целочисленного деления реализована гораздо более сложным кодом, нежели деление дробных чисел

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

Сама по себе находка интересная, хоть и получилась из-за преждевременной оптимизации.
Для лучшего представления результатов думаю лучше сделать отдельную тему, объединив материал.
 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Мы ж программисты. Давай рассуждать логически.

 

49 минут назад, prop сказал:

Я поделился информацией, остальное кто-то додумал сам.

Да, додумал. Благо, вариантов не так много. Например, ты согласен с источником, и в случае его ошибочности заблуждаешься вместе с ним. Либо, отдавая себе отчёт в некорректности утверждения, намеренно вводишь читателей в заблуждение. Я предпочёл первый вариант. Додумал. Какие ещё существуют причины для вброса ложного утверждения?

 

1 час назад, prop сказал:

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

Смотрим выше и видим конкретные места в исходниках (с кусками ассемблерного кода и описанием причин):

В 08.10.2021 в 20:35, eu_tomat сказал:

# lobject.c:81: case LUA_OPIDIV: return luai_numidiv(L, v1, v2);

...

# lobject.c:60: case LUA_OPIDIV: return luaV_idiv(L, v1, v2);

Выше есть и результаты замера пар int/float и int/int:

В 02.10.2021 в 23:37, eu_tomat сказал:

$ lua5.3 -e 't0=os.clock()local v for i=1,1e9 do v=i//1.0 end print(os.clock()-t0)'
11.848781
$ lua5.3 -e 't0=os.clock()local v for i=1,1e9 do v=i//1 end print(os.clock()-t0)'
16.08497

 

В сухом остатке в твоём посте новой информацией оказались лишь результаты замера для пары float/float. Да и то, для операции обычного деления, а не целочисленного. А это разные операции: в случае обычного деления не требуется округление результата.

 

Начинался же пост претенциозной фразой:

6 часов назад, prop сказал:

Эксперименты - это хорошо, когда нет более надежных источников.

Мораль: обесценивая сообщения предыдущих участников и претендуя на новизну, будь готов к тому, что любой высказанный тобой тезис также будет подвергнут оценке и, возможно обесценен.

 

Полагаю, вопрос ценности и новизны исчерпан. Возвращаемся к исходному вопросу.

1 час назад, prop сказал:

Для лучшего представления результатов думаю лучше сделать отдельную тему, объединив материал.

Что именно ты предлагаешь? Как эту тему назвать? О чём она? Об оптимальном способе округления? Об оптимизации кода? О целочисленном делении? Какие посты предлагаешь перенести из этой темы в новую? Или ничего переносить не надо, а просто процитировать в новой теме?


И о объединении каких материалов идёт речь? Что, с чем и как предлагаешь объединять? И как предлагаешь систематизировать наработанный материал, учитывая, что на результат измерений влияет не только оборудование, но и другое ПО, разделяющие общие с Lua ресурсы?

 

Была когда-то тема с похожей идеей. Но там тоже всё сложно.

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Тем временем начинающий криптодиггер использовал функцию, которую ему оптимизировали всем форумом, только в комментах.
Потом вообще убрал её.
image.thumb.png.0ba6eb00496bbc759e2369a1291a50be.png

 

Изменено пользователем prop

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
2 минуты назад, prop сказал:

Потом вообще убрал её.

Он внимательно читал сообщения и применил полученные знания на практике.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
12 часа назад, prop сказал:

Тем временем начинающий криптодиггер использовал функцию, которую ему оптимизировали всем форумом, только в комментах.
Потом вообще убрал её.
image.thumb.png.0ba6eb00496bbc759e2369a1291a50be.png

 

Она просто не нужна была. Я ее вырезал на 2 день.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
18 часов назад, OpenReactor сказал:

Она просто не нужна была. Я ее вырезал на 2 день.

Я о том же, зато оптимизировали.
Если представить себя мыжпрограммистами и провести аналогию с реальностью,
то команда просто так потратила время на преждевременную оптимизацию.

Обязательно к прочтению

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
2 часа назад, prop сказал:

Если представить себя мыжпрограммистами и провести аналогию с реальностью,
то команда просто так потратила время на преждевременную оптимизацию.

Если провести аналогию с реальностью, то дети в песочнице строили домики и лепили куличики.

 

Один из них построил домик. Спрашивает других: можно ли сделать лучше. Другие оценивают. Кто-то спрашивает: а это зачем, оно же тут лишнее. Другой говорит, нет, не лишнее, и наоборот, так даже лучше. Другие тоже заинтересовались. Обсудили, нашли лучший вариант, какой смогли, и довольные разошлись по домам.

 

Через два дня домик смыло дождём. Но дети с радостью вспоминали опыт коллективного творчества: они обязательно применят его в своих взрослых проектах. И только вечно недовольная старуха Шапокляк злобно шептала: всё тлен, всё тлен...

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
15 часов назад, eu_tomat сказал:

Если провести аналогию с реальностью, то дети в песочнице строили домики и лепили куличики.

 

Один из них построил домик. Спрашивает других: можно ли сделать лучше. Другие оценивают. Кто-то спрашивает: а это зачем, оно же тут лишнее. Другой говорит, нет, не лишнее, и наоборот, так даже лучше. Другие тоже заинтересовались. Обсудили, нашли лучший вариант, какой смогли, и довольные разошлись по домам.

 

Через два дня домик смыло дождём. Но дети с радостью вспоминали опыт коллективного творчества: они обязательно применят его в своих взрослых проектах. И только вечно недовольная старуха Шапокляк злобно шептала: всё тлен, всё тлен...

Есть основательные предположения что лучший домик или куличик всего навсего сломают те у кого не получилось. Ожидаема реакция на твоё стремление к улучшению.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
8 часов назад, NEO сказал:

Есть основательные предположения что лучший домик или куличик всего навсего сломают те у кого не получилось.

Да и пусть ломают. Важен не домик, а полученный опыт строительства. Я, например, считаю свой опыт активности в этой теме позитивным.

 

Раньше я вычислял длительность времени в целых тактах Майнкрафта таким кодом: dt = ((t2-t1)/0.05+0.5)//1

Теперь же я могу сделать то же самое кодом более простым и при этом более эффективным: dt = (t2-t1+0.025)//0.05

Разве это не прекрасно?

 

Также теперь я знаю, что Lua предварительно вычисляет выражения, являющиеся константами. А до этого момента я думал, что это работает только в более "взрослых" языках программирования.

 

Меньше заблуждений. Больше знаний. А домик из песка разрушится в любом случае.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Сделаю уточнение.

В 08.10.2021 в 20:35, eu_tomat сказал:

Операция целочисленного деления реализована гораздо более сложным кодом, нежели деление дробных чисел.

Дело оказалось вообще не в этом. Все эти вспомогательные операции слишком мелкие, чтобы принимать их в расчёт. Главная причина в том, что сама по себе операция деления целых чисел в моей модели процессора выполняется медленнее, чем операция деления вещественных чисел в регистре SSE. Время деления на константу со значением 5 отличается примерно в два раза.

В 08.10.2021 в 20:35, eu_tomat сказал:

Тем не менее я рискну предположить, что на чистом Си без вспомогательных проверок целочисленное деление выполнится быстрее нежели дробное. Даже с SSE-оптимизациями. Возможно, кто-то проверит.

Я сам решил проверить эту гипотезу, и она также не подтвердилась. Сама проверка оказалась не такой простой, как мне казалось на первый взгляд. Компилятор довольно хорошо оптимизирует код, заменяя операцию деления на константу операциями умножения и сдвига. В результате возникает иллюзия, будто бы целочисленное деление выполняется в три-четыре раза быстрее вещественного. Но это не так. Проверить это можно построением ассемблерного листинга. Мне пришлось постараться, чтобы компилятор перестал воспринимать содержимое переменной как константу, и наконец-то использовал операцию деления.

 

Также умный компилятор вообще отказывался создавать код, если его результат не использовался в дальнейшем. Поэтому, в отличие от Lua, недостаточно просто сохранять результат в какую-то переменную. Этот результат надо где-то использовать.

 

Также я пробовал отказаться от оптимизаций на этапе компиляции. Но в этом случае результат получается менее точным. В зависимости от выбранного способа записи результат может измениться не только количественно, но и качественно. Оптимизированный код обеспечивает более повторяемый результат.

 

Эксперимент получился недостаточно чистым. Поэтому его полезно было бы повторить в кодах ассемблера, чтобы не продираться сквозь особенности компилятора. Но я пока не до конца осилил синтаксис ассемблера AT&T. Поэтому рабочая гипотеза такова: операция vdivsd процесcора Intel выполняется быстрее idivq.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Присоединяйтесь к обсуждению

Вы можете написать сейчас и зарегистрироваться позже. Если у вас есть аккаунт, авторизуйтесь, чтобы опубликовать от имени своего аккаунта.

Гость
Ответить в тему...

×   Вы вставили отформатированное содержимое.   Удалить форматирование

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отобразить как ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.


×
×
  • Создать...