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

bitfield 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

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


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

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

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

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

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

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

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

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

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


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