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

Сегодня я озаботится малым быстродействием заказанного мне скрипта на 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'))')

проверим:

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

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

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

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