Двоични структури (Binaries)

Публикувано четвъртък, 07 март 2019, 17:00

В тази публикация ще се запознаем по-задълбочено с двоичните структури в Elixir, каква е вътрешната им репрезентация, как и за какво са ни полезни.

Конструкция

Една binary структура представлява поредица от битове (често поредица от байтове). Дефинира се със следната конструкция:

<<>>
#=> <<>>

В тази конструкция слагаме поредица от числа представляващи битове или байтове:

<< 123, 23, 1 >>
#=> << 123, 23, 1 >>

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

<< 0b01111011, 0b00010111, 0b00000001 >> == << 123, 23, 1 >>
#=> true

Числата винаги представляват един байт. Ако числото е по-голямо от 255, то е “отрязано” до един байт.

<< 280 >>
#=> <<24>>

Разбира се има начин числата да представляват повече от един байт. Това става с помощта на модификатора size.

<< 280::size(16) >>
#=> << 1, 24 >>

# или

<< 280::16 >>
#=> << 1, 24 >>

<< 0b00000001, 0b00011000 >> == << 280::16 >>
#=> true

С този модификатор можем да представим число в 7 бита:

<< 129::7 >>
#=> <<1::size(7)>> # Всъщност е отрязано от 10000001 - взимат се десните 7 бита - 0000001

Интересно е съхранението на числа с плаваща запетая като binaries. Винаги се представят като двоична структура от 8 байта:

<< 5.5::float >>
#=> <<64, 22, 0, 0, 0, 0, 0, 0>>

Това е така, защото числата с плаваща запетая в Elixir са с double прецизност или 64 битови.

<<sign::1, exponent::11, mantissa::52>> = <<5.5::float>>
#=> <<64, 22, 0, 0, 0, 0, 0, 0>>
{sign, exponent, mantissa}
#=> {0, 1025, 1688849860263936}

Функции и операции свързани с binaries

Конкатенация

Възможно е да конкатенираме binary структури с оператора <>.

<< 83, 79, 83 >> <> << 24, 4 >>
#=> <<83, 79, 83, 24, 4>>

Друг начин за конкатенация е:

<< 83, 79, 83, << 24, 4 >> >>
#=> <<83, 79, 83, 24, 4>>

Този код е аналогичен на примера с оператора <>.

Размер

В паметта, за binary структурите, има мета-информация, която съхранява дължината им. Това значи, че пресмятането на дължината на binary структура е операция с константа сложност. Поради това и функцията за намиране на дължината на двоична структура има в името си size:

byte_size(<< 83, 79, 83 >>)
#=> 3

Когато боравим с битове, чийто брой не е кратен на 8, ще се закръгли нагоре:

byte_size(<< 34::5, 23::2, 12::2 >>)
#=> 2

# Между другото:
<< 34::5, 23::2, 12::2 >> == << 22, 0::1 >>
#=> true

Разбира се можем да видим и точната дължина в битове, което е отново O(1) операция:

bit_size(<< 34::5, 23::2, 12::2 >>)
#=> 9

Проверки

Има два начина за проверяване дали типа на дадена променлива е поредица от битове.

Kernel.is_bitstring/1 - Истина за всяка валидна binary структура.
Kernel.is_binary/1 - Истина е само ако bit_size/1 връща число кратно на 8 - тоест структурата е поредица от байтове.

В повечето случаи ще използваме Kernel.is_binary/1.

Sub-binaries

С функцията Kernel.binary_part/3 можем да боравим с части от дадена binary стойност:

binary_part(<< 83, 79, 83, 23, 21, 12 >>, 1, 3)
#=> <<79, 83, 23>>

Взима под-структура от индекс - втория аргумент с брой елементи - третия. Очаквайте ArgumentError, ако тези аргументи са невалидни индекс и/или дължина за дадената структура.

Важното тук е, че това е бърза операция - нищо не се копира, просто получавате указател от дадено място в паметта, с дадена дължина.

Pattern matching

В Elixir можем да съпоставяме и binaries:

<< x, y, x >> = << 83, 79, 83 >>
#=> "SOS"

x
#=> 83

y
#=> 79

Друга интересна възможност е да съпоставим променлива към повече от един байт.

<< x, y, z::binary >> = << 83, 79, 83, 43, 156 >>
#=> <<83, 79, 83, 43, 156>>
z
#=> << 83, 43, 156 >>

# Ако не добавим `::binary` автоматично съпоставя променлива на 1 байт:
<< x, y, z >> = << 83, 79, 83, 43, 156 >>
#=> ** (MatchError) no match of right hand side value: <<83, 79, 83, 43, 156>>

Ето пример за разделяне и изваждане на частите на число с плаваща запетая, така както е представено:

<< sign::size(1), exponent::size(11), mantissa::size(52) >> = << 4815.162342::float >>
#=> <<64, 178, 207, 41, 143, 62, 204, 196>>

sign
#=> 0

Тук знакът е 1 при отрицателно число и 0 при положително - в случая е 0. Пази се в един бит.

Цялото число може да се пресметне с (-1)^sign(1 + mantissa/2⁵²)2^{exponent - 1023}:

:math.pow(-1, sign) * (1 + mantissa / :math.pow(2, 52)) * :math.pow(2, exponent - 1023)
#=> 4815.162342

Освен float и binary модификаторите, има integer модификатор, който се прилага автоматично ако никой друг не е използван. Модификаторът bytes е аналогичен на binary. Модификаторите bits и bitstrig се използват за съпоставяне на битстринг съдържание - поредица от битове с неопределена дължина.

<< x::5, y::bits >> = << 225 >>
#=> <<225>>

x
#=> 28

y
#=> <<1::size(3)>>

Модификаторите bitstrig и binary без дължина могат да се използват само в края на binary структурата.

Останалите възможни модификатори са utf8, utf16 и utf32, които са свързани с unicode. Ще се върнем към utf8, когато си говорим за низове в следващата публикация.

Интересно нещо, свързано с модификаторите, е, че size работи с тях. size задава дължина в битове, когато работим с integer, но ако работим с binary модификатор, size е в байтове:

<< x::binary-size(4), _::binary >> = << 83, 222, 0, 345, 143, 87 >>
#=> <<83, 222, 0, 89, 143, 87>>

x # 4 байта
#=> <<83, 222, 0, 89>>

Имплементация

Всеки процес в Elixir има собствен heap. В тази памет се съхраняват различни структури от данни и стойности. Когато два процеса си комуникират, съобщенията, които се изпращат между тях, се копират в heap-овете им.

Когато си говорим за binaries, обаче, има една голяма разлика с този модел. Ако binary-то е 64 байта или по-малко, то се съхранява в heap-a на процеса си и се копира при размяна с друг процес, както е описано по-горе. Такива binary структури наричаме heap binaries.

Когато структурата ни е по-голяма от 64 байта, тя не се пази в process heap-a. Пази се в обща памет за всички процеси на даден node (Erlang виртуална машина). В process heap-a се пази малък обект, наречен ProcBin, който е указател към даденото binary, съхранено в общия heap. В този общ heap, binary структура може да бъде сочена от множество такива ProcBin указатели от множество процеси. Има reference counter за всеки от тези указатели. Когато той стане 0, Garbage Collector-ът ще може да изчисти binary-то от общия heap. Такива binary структури наричаме refc binaries.

Защо това е хубаво? Защото при по-големи двоични структури няма постоянно копиране между процесите и съществуват различни оптимизации. Разбира се, трябва да се внимава с тези refc binaries.

Говорейки си за имплементацията е хубаво да обърнем внимание на два вида специални указатели, свързани с двоичните структури.

По-горе споменахме sub binary стойностите, получен чрез Kernel.binary_part/3, която вътрешно ползва :erlang.split_binary/2. Това е специален указател който сочи към част от дадено binary. Няма копиране (защото всичко е immutable). Създаването на sub binary е евтина операция, но ако става въпрос за refc binary, reference counter-a се увеличава.

Друг специален обект е match context-ът. Той е подобен на sub binary, но оптимизиран заbinary pattern matching. Държи указател към двоичните данни в паметта, и когато нещо е match-нато, указателят се придвижва напред. Компилаторът отлага създаването на sub binary за всяка match-ната променлива, ако е възможно, и преизползва един и същ match context.

Оптимизации при конкатенация

Да видим как работи конкатенацията, когато сме запознати с модела на пазене на двоичните структури в паметта. Имаме следния код:

x = << 83, 222, 0, 89 >>
y = << x, 225, 21 >>
z = << y, 125, 156 >>
a = << y, 15, 16, 19 >>

Нека обясним всеки ред в този пример.

На първия ред виждаме, че x сочи към ново binary, което е 4 байта, следователно се създава в heap-a на текущия процес.

Вторият ред представлява конкатенация. Към x се добавят още 2 байта и това ново binary се присвоява на y. Какво става с паметта? Операцията за добавяне всъщност създава ново refc binary. Така е имплементирана. В общата памет се заделя място с големина max(2 * byte_size(x), 256), в случая - 256 байта:

[4] -> |83|222|0|89| | | | |...| -> 256 байта

Този указател е създаден в heap-a на текущия процес, също heap binary-то за x, което беше създадено на първия ред, сега може да бъде изчистено от Garbage Collector-a на процеса си. Байтовете, които трябва да се добавят са добавени в свободното пространство:

[4] -> |83|222|0|89|225|21| | |...| -> 256 байта
[6] -^

Какво става на 3-ти ред? Искаме да добавим към y още 2 байта и да присвоим на z резултата. Тъй като след байтовете на y има свободно място, те се преизползват за z. Няма копиране, защото всичко е immutable, от което следва че може да се преизползва всичко, когато е възможно:

[4] -> |83|222|0|89|225|21|125|156| | | |...| -> 256 байта
[6] -^
[8] -^

Сега става интересно. На 4-ти ред искаме да добавим към y 3 байта и да присвоим резултата към a. Сега след стойността на y, в паметта има данни и не можем да преизползваме пространството. Затова run-time системата, копира стойността на y на ново място в паметта (използва формулата по-горе) и добавя 3-те нови байта там:

[4] -> |83|222|0|89|225|21|125|156| | | |...| -> 256 байта
[6] -^
[8] -^

[9] -> |83|222|0|89|225|21|15|16|19| | |...| -> 256 байта

Тази оптимизация е възможна в доста малко случаи. Има операции, които карат паметта да стане компактна и да освободи неизползваните байтове, от което следва че подобна оптимизация при добавяне ще е невъзможна. Такива операции са пращането на binary-то като съобщение между процеси, както и създаването на match context при pattern matching.

С този последен пример завършваме тази публикация. Показахме ви binary структурите в по-голяма дълбочина преди да говорим за низове. Почти всичко казано не е специфично за Elixir и идва от Erlang. Следващата статия ще разгледа низовете в дълбочина - ще си говорим за unicode и utf8 и ще споменем някои от функциите в String модула.