Перейти к публикации
Jakowlew

barr - битовые поля и бинарные массивы

  

6 пользователей проголосовало

У вас нет прав на голосование в этом опросе, или на просмотр результатов опроса. Пожалуйста, войдите или зарегистрируйтесь для голосования в опросе.

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

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

Основная цель - сэкономить память при хранении данных в небольшом диапазоне. Как известно, в Lua целое число занимает 64 бита и может принимать значения от -2^32 до 2^32-1. Такой огромный диапазон практически никогда не нужен и память расходуется впустую. Что если мы попробуем упаковать несколько маленьких чисел в одно большое?

 

Скачать библиотеку можно здесь: https://pastebin.com/WLmJ19QJ

Возможны изменения и доработка, так что проверяйте время от времени пастебин на наличие новой версии

Текущая версия: 1.1
1.0:
Первая версия, добавлены все основные методы

1.1: Добавлены методы barr:writeArray(array:table) и barr:readArray(pos:number, n:number):number
 

Пример:

 

У нас есть некий массив байт. Например, это координаты пикселя на экране, цвет фона, цвет символа и сам символ в ASCII кодировке (занимает 1 байт). В стандартном представлении один пиксель будет занимать в памяти 5 * 8 = 40 байт, хотя используются только 8.

-- Каждое число занимает в памяти 64 бита, т.е. 8 байт
-- Хотя наши значения лежат в диапазоне 0..255 и занимают 1 байт
-- Таким образом, в каждом числе 7 байт простаивают впустую!
local pixel = {
  x = 3,
  y = 4,
  bgColor = 42,
  fgColor = 0,
  char = 18
}

-- 8 - кол-во бит под одну порцию данных
arr = barr:new(8)
-- Записываем наши данные в barr
for i = 1, #pixel do
  arr:write(pixel[i])
end

-- Получаем первый байт, в нашем случае pixel.x
print(arr:read(0)[0]) -- 3
-- Занимаемая память
print(#arr.data * 8) -- 8 байт 

А что если использовать эти 7 байт? Ведь мы можем сделать это! barr позволяет упаковать весь наш пиксель в одно число. Да еще 2 байта останется!

 

 

Пример 2:

 

А если нужна более сложная структура? Например, так:

-- Занимает 24 байта, хотя может всего 1
local struct = {
  flag = 1, -- 0..1, 1 бит
  mode = 3, -- 0..3, 2 бита
  data = 32, -- 0..32, 5 бит
}

arr = barr:new({1, 2, 5})
arr:write(struct) -- 1 байт
arr:write({0, 2, 18}) -- еще 1 байт

local t = arr:read(0)
print(t[1], " ", t[2], " ", t[3]) -- 1, 3, 32
print(#arr.data * 8) -- 8 байт, из них 6 - пустые

Таким образом barr может уменьшить объем потребляемой для хранения данных памяти в 64 раза ( если упаковывать значения в диапазоне 0..1)

 

 

Если вы еще не устали, то вот подробная документация для задротов:

 

barr - binary array, состоит из ячеек - cell, каждая из которых может хранить в себе несколько порций данных - chunk-ов.

-- Здесь и дальше arr - экземпляр barr

-- Количество ячеек (cell)
#arr.data
-- Структура порции (chunk)
-- Каждый элемент таблицы - кол-во бит, отведенных под данные
arr.chunk
-- Количество бит, занимемых порцией
-- Является суммой элементов arr.chunk
arr.chunkSize
-- Максимальный размер порции.
--Попытка создать порцию больше данного значения является ошибкой
arr.maxChunkSize
-- Количество порций в массиве
arr.size
-- Максимальное оличество порций в одной ячейке
arr.cellCapacity

-- Создание нового массива.
-- Входной параметр - таблица с данными о структуре порции
arr = barr:new({1, 2, 3, 4, 5})
-- Может быть числом, если порция состоит из одного элемента
arr = barr:new(8)
-- Если входной параметр не число или таблица, то arr == nil
-- Если входной параметр таблица, но ее элементы не числа,
-- или их сумма больше maxChunkSize, то arr == nil
arr = barr:new({1, {}, 3}) -- ошибка, не все элементы таблицы числа
arr = barr:new("2") -- все в порядке, "2" преобразуется в 2
arr = barr:new({10500, 10500}) -- ошибка, размер порции больше maxChunkSize

-- Запись порции в массив
-- Дописывает биты порции в ячейку
-- Если ячейки не хватает, то создается новая, и порция сохраняется в ней
-- Поэтому при однородных данных
-- barr:new(8) лучше, чем barr:new({8, 8, 8})
-- Входной параметр - таблица с данными порции
-- Если значение поля табилцы больше диапазона соответсвующего поля чанка,
-- то оно переполнятся в соответстви с правилами переполнения и ошибка не возникает
-- Если входной параметр == nil, то вовзращется nil
arr = barr:new({1, 3, 5})
arr:write({1, 3, 18})

arr = barr:new(8)
arr:write({257}) -- 257 станет 1, т.к. 257 % 2^8 == 1

-- Чтение порции из массива
-- Входной параметр - порядковый номер порции, нумерация начинается с 0
-- Если входной параметр == nil, < 0 или > size, то вовзращется nil
-- Вовзращает таблицу с данными порции
arr = barr:new(8)
arr:write(42)
t = arr:read(0) -- читает первую порцию, t = {42}
print(t[1]) -- 42
print(arr:read(0)[1]) -- 42, так тоже можно

-- Запись массива порций
chunks = {3, 14, 15, 92, 65, 35, 89}
arr:write(chunks)

-- Чтение в массив порций
-- Читает n порций с позиции pos (нумерация от 0)
-- Возвращает массив с порциями 
chunks = {}
pos, n = 0, 3
arr:read(pos, n)
print("Pi = ", chunks[1], ".", chunks[2]) -- Pi = 3.14

-- Вспомогательные ф-ии
-- Возведение целого числа x в степень y, где y целое и y >= 0
arr:pow(3, 3) -- 27
-- Возведение 2 в степень y, где y целое и y >= 0
arr:pow2(10) -- 1024
-- Возведение в степень работает с целыми числами
-- Необходимость в низ появилась тогда, когда
-- math.pow(2, 55) == math.pow(2, 55) - 1
-- оказалось true из-за погрешности в операциях с плавающей точкой

 

Когда использовать barr? Каждый пустой экземпляр barr занимает как минимум 48 байт и 544 как максимум (если порция состоит из 64 1-битовых полей, в таком случае лучше использовать порцию из 1 1-битового поля, тогда размер barr будет 48 байт).

Таким образом barr помогает при достаточно большом объеме данных, выигрыш от экономии которых нивелирует затраты на размер пустого экземпляра и 8 байт на каждую новую порцию. Как и писалось выше, можно максимальная экономия памяти составляет практически 64 раза.

 

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

 

Тесты:

Тесты проводились на чистом Lua 5.3

Код самого теста:

 

 
local b = require("barr")

local lim = 100000
print("Элементов таблицы: ", lim)

collectgarbage(collect)
mem1 = collectgarbage("count")
time1 = os.clock()
local t1 = {}
for i = 1, lim do
  t1[i] = 42
end
time2 = os.clock()
mem2 = collectgarbage("count")
tpic = (mem2 - mem1) * 1024
print("Пиковая память таблицы: ", tpic)

collectgarbage(collect)
mem2 = collectgarbage("count")
tnorm = (mem2 - mem1) * 1024
print("Нормальная память таблицы: ", tnorm)
ttable = time2 - time1
print("Время таблицы: ", ttable)
print("======")

collectgarbage(collect)
mem1 = collectgarbage("count")
time1 = os.clock()
t2 = b:new(8)
for i = 1, lim do
  t2:write({1})
end
time2 = os.clock()
mem2 = collectgarbage("count")
bpic = (mem2 - mem1) * 1024
print("Пиковая память barr: ", bpic)

collectgarbage(collect)
mem2 = collectgarbage("count")
bnorm = (mem2 - mem1) * 1024
print("Нормальная память barr: ", bnorm)
tbarr = time2 - time1
print("Время barr: ", tbarr)
print("======")

if tpic > bpic then print("Выигрыш в пиковом потреблении, раз: ", tpic / bpic)
else print("Проигрыш в пиковом потреблении, раз: ", bpic / tpic) end

if tnorm > bnorm then print("Выигрыш в нормальном потреблении, раз: ", tnorm / bnorm)
else print("Проигрыш в нормальном потреблении, раз: ", bnorm / tnorm) end

if ttable > tbarr then print("Выигрыш во времени, раз: ", ttable / tbarr)
else print("Проигрыш во времени, раз: ", tbarr / ttable) end
 

 

Результаты тестов:

 

chunk = {1}
Элементов таблицы: 10
Пиковая память таблицы: 288.0
Нормальная память таблицы: 288.0
Время таблицы: 0.0
======
Пиковая память barr: 864.0
Нормальная память barr: 384.0
Время barr: 0.0
======
Проигрыш в пиковом потреблении, раз: 3.0
Проигрыш в нормальном потреблении, раз: 1.3333333333333
Проигрыш во времени, раз: 0.0

Элементов таблицы: 100
Пиковая память таблицы: 2080.0
Нормальная память таблицы: 2080.0
Время таблицы: 0.0
======
Пиковая память barr: 5200.0
Нормальная память barr: 400.0
Время barr: 0.0
======
Проигрыш в пиковом потреблении, раз: 2.5
Выигрыш в нормальном потреблении, раз: 5.2
Проигрыш во времени, раз: 0.0

Элементов таблицы: 1000
Пиковая память таблицы: 16416.0
Нормальная память таблицы: 16416.0
Время таблицы: 0.0
======
Пиковая память barr: 48624.0
Нормальная память barr: 624.0
Время barr: 0.0
======
Проигрыш в пиковом потреблении, раз: 2.9619883040936
Выигрыш в нормальном потреблении, раз: 26.307692307692
Проигрыш во времени, раз: 0.0

Элементов таблицы: 10000
Пиковая память таблицы: 262124.0
Нормальная память таблицы: 262160.0
Время таблицы: 0.0
======
Пиковая память barr: 484464.0
Нормальная память barr: 4464.0
Время barr: 0.046
======
Проигрыш в пиковом потреблении, раз: 1.848224504433
Выигрыш в нормальном потреблении, раз: 58.727598566308
Проигрыш во времени, раз: 0.0

Элементов таблицы: 100000
Пиковая память таблицы: 2097132.0
Нормальная память таблицы: 2097168.0
Время таблицы: 0.031
======
Пиковая память barr: 603040.0
Нормальная память barr: 33136.0
Время barr: 0.425
======
Выигрыш в пиковом потреблении, раз: 3.4776001591934
Выигрыш в нормальном потреблении, раз: 63.289715113472
Проигрыш во времени, раз: 13.709677419355

chunk = {8}
Элементов таблицы: 10
Пиковая память таблицы: 288.0
Нормальная память таблицы: 288.0
Время таблицы: 0.0
======
Пиковая память barr: 880.0
Нормальная память barr: 400.0
Время barr: 0.0
======
Проигрыш в пиковом потреблении, раз: 3.0555555555556
Проигрыш в нормальном потреблении, раз: 1.3888888888889
Проигрыш во времени, раз: 0.0

Элементов таблицы: 100
Пиковая память таблицы: 2080.0
Нормальная память таблицы: 2080.0
Время таблицы: 0.0
======
Пиковая память barr: 5424.0
Нормальная память barr: 624.0
Время barr: 0.001
======
Проигрыш в пиковом потреблении, раз: 2.6076923076923
Выигрыш в нормальном потреблении, раз: 3.3333333333333
Проигрыш во времени, раз: 0.0

Элементов таблицы: 1000
Пиковая память таблицы: 16416.0
Нормальная память таблицы: 16416.0
Время таблицы: 0.0
======
Пиковая память barr: 50416.0
Нормальная память barr: 2416.0
Время barr: 0.005
======
Проигрыш в пиковом потреблении, раз: 3.0711500974659
Выигрыш в нормальном потреблении, раз: 6.794701986755
Проигрыш во времени, раз: 0.0

Элементов таблицы: 10000
Пиковая память таблицы: 262124.0
Нормальная память таблицы: 262160.0
Время таблицы: 0.002
======
Пиковая память barr: 513136.0
Нормальная память barr: 33136.0
Время barr: 0.044
======
Проигрыш в пиковом потреблении, раз: 1.95760784972
Выигрыш в нормальном потреблении, раз: 7.9116368903911
Проигрыш во времени, раз: 22.0

Элементов таблицы: 100000
Пиковая память таблицы: 2097132.0
Нормальная память таблицы: 2097168.0
Время таблицы: 0.016
======
Пиковая память barr: 947088.0
Нормальная память barr: 262512.0
Время barr: 0.468
======
Выигрыш в пиковом потреблении, раз: 2.2142947645836
Выигрыш в нормальном потреблении, раз: 7.9888462241726
Проигрыш во времени, раз: 29.25

 

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

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


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

Ой! А зачем же так код упакован? И Lua beautifier не хочет приводить его в порядок.

В общем, код я посмотреть пока не смог, а запускать не буду.

 

В связи с этим возникает вопрос: не приводит ли интенсивное использование этой библиотеки к обратному эффекту, о котором рассказывал @ECS, когда сборщик мусора не успевает чистить интенсивно создаваемые и уничтожаемые объекты, от чего фактическое потребление памяти начинает расти?

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


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

@@eu_tomat, плюсую, хотелось бы глянуть и потестировать исходник без минификации. Еще интересует возможность практического применении подобной методики: безусловно, упор на экономию памяти - дело благородное, однако, к примеру, для отрисовки изображений и буферизации экрана идея не сгодится ввиду необходимости постоянной распаковки/упаковки чисел, что катастрофически снизит производительность. Это не претензия к либе, а вопрос о ее применении "не на бумажке"

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


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

@eu_tomat@ECS
Упаковал минифайером, чтобы скрипт меньше места занимал. Залил полную версию.

 

Судя по тестам, при кол-ве элементов около 1000 все происходит буквально мнгновенно, при кол-ве около 10000 - за сотые доли секунды. Тестил все не в опенкомпах, а на своем стареньком ноутбуке, Pentium dual-core, 1.3Ггц на ядро. Но в целом, упаковка/распаковка происходят в ~20-25 раз медленнее, чем при работе с обычными таблицами, причем время вроде как должно линейно расти при увеличении элементов чанка. Но, думаю, даже опенкомпы разницы при размере в 1000-2000 не заметят.

 

Касаемо памяти, тут все не однозначно. В пиковом потреблении памяти тратится больше примерно в 2-3 раза при небольшой длине массива. При n = 100000 память даже в пике тратится в 2.2 раза меньше, при n = 23000-24000 затраты одинаковы. В нормальном состоянии при записи 8-битных данных выигрыш начинается уже при n = 20-25

 

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

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

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


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

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

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

×   Вставлено в виде отформатированного текста.   Вставить в виде обычного текста

  Разрешено не более 75 эмодзи.

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

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

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


×