Germany | Finland | Saint Petersburg | Drive

О пользе inline-кода или библиотека bit

Опубликовано в QLua

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

 

 

Конечно, была использована функция band, находящаяся в библиотеке 

Например, проверка наличия младшего бита в этой маске с использованием этой библиотеки выглядит так:

bit.band(number,1)

Поскольку толкового профайлера для lua нет (или я о нем не в курсе) пришлось некоторое время поэкспериментировать. Подозрение пало именно на эту функцию, как наиболее часто вызываемую. Я решил проверить.

Вот так выглядел мой тест (в варианте исполнения в среде виртуальной машины терминала quik

local n
s1 = os.clock()
for i = 1,100000000 do
n = bit.band(i,1)
end
s1 = os.clock() - s1
s2 = os.clock()
for i = 1,100000000 do
n = i % 2
end
s2 = os.clock() - s2
message(tostring(s1) .. " " .. tostring(s2))

Проверял на двухпроцессорном ноутбуке. Результаты интересные и стабильно повторяемые:

Вариант с использованием bit.band занимал 31-33 секунды. А вариант с получением остатка от деления на 2 - примерно 9 секунд. На вашем компьютере цифры могут отличаться, но соотношение должно быть таким же.

То есть в 3 с лишним раза быстрее.

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

 

local m,n
for i = 1,10000000 do
   n = bit.band(i,1)
   m = i % 2

   if n ~= m then
       message("" .. n .. " " .. m)
   end
end

Запускаем, ждем некоторое время. Все нормально.

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

Вывод. Библиотека bit при использовании целочисленной арифметики не нужна - inline проверки с использованием остатка от целочисленного деления значительно быстрее при прочих равных.

 


 Update 27.04.2017

Один из разработчиков торгового комплекса Quik попросил раскрыть фразу "Эксперименты на разрядах, отличных от младшего, дали аналогичный результат". Перефразируя, задача ставится как "проверить биты, отличные от младшего". Не вопрос, проверим.

К примеру, проверим предпоследний бит. Его можно проверить так:

x % 4 > 1

В случае если бит установлен, результатом выражения будет true. Если бит не установлен, то, очевидно, false.

Сравним быстродействие со встроенной bit.band. Для чистоты эксперимента функцию bit.band локализуем:

local n
local band = bit.band s1 = os.clock()
for i = 1,100000000 do n = band(i,2) ~= 2 end s1 = os.clock() - s1 s2 = os.clock() for i = 1,100000000 do n = i % 4 > 1 end s2 = os.clock() - s2 message(tostring(s1) .. " " .. tostring(s2))

Результат аналогичный:

30.837     15.741

Теперь перейдем к общему случаю.

Если использовать препроцессор M4 при построении текстов на lua (я его использую), то можно упростить себе жизнь. Чтобы не вычислять каждый раз значения битовых масок, можно написать простейший макрос, который будет разворачиваться в проверку нужного бита:

define(`m4_bit1',`(`$1' % eval(2 * 2**`$2') >= eval(2**`$2'))')

проверим:

Число Двоичный код Номер бита Выражение Результат
0 0 0 (0 % 2 >= 1) false
1 1 0 (1 % 2 >= 1) true
1 1 1 (1 % 4 >= 2) false
1 1 5 (1 % 64 >= 32) false
7 111 0 (7 % 2 >= 1) true
7 111 2 (7 % 8 >= 4) true
8 1000 3 (8 % 16 >= 8) true
8 1000 0 (8 % 2 >= 1) false
16 10000 4 (16 % 32 >= 16) true
16 10000 5 (16 % 64 >= 32) false
17 10001 0 (17 % 2 >= 1) true
17 10001 1 (17 % 4 >= 2) false
55 110111 3 (55 % 16 >= 8) false
55 110111 4 (55 % 32 >= 16) true
55 110111 5 (55 % 64 >= 32) true
55 110111 6 (55 % 128 >= 64) false

Все правильно. Итого в сухом остатке. Чтобы проверить нужный бит в маске, можно вызвать функцию bit.band(x,n) - в этом случае будет вызвана функция библиотеки, либо применить в тексте скрипта макрос m4_bit1(x,n) - в этом случае проверка будет inline и в 2-3 раза быстрее.

Соответственно, макрос, который будет проверять бит на равенство нулю, будет выглядеть аналогично:

define(`m4_bit0',`(`$1' % eval(2 * 2**`$2') < eval(2**`$2'))')

 


См также Округление до шага цены

Комментарии   
# swerg 28.04.2017 06:58
Код проверки не младшего бита - ошибочный. Он возвращает верный результат лишь для ограниченного набора параметров.
Ответить | Ответить с цитатой | Цитировать
# admin 28.04.2017 19:09
Буду признателен, если сможете привести пример.
Ответить | Ответить с цитатой | Цитировать
Добавить комментарий


Архив QLua

Майнинг в браузере