Binaries

Публикувано вторник, 21 март 2017, 12:00

Това е първата статия от серия на тема Модули и структури от данни в Elixir. Ще се запознаем по-задълбочено с двоичните структури в Elixir, как са представени и как и за какво биха могли да са ни полезни.

Конструкция

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

<<>>

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

<< 123, 23, 1 >>

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

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

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

iex> << 280 >>
<<24>>

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

iex> << 280::size(16) >> # Същото като << 280::16 >>
<< 1, 24 >>

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

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

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

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

iex> << 5.5::float >>
<<64, 22, 0, 0, 0, 0, 0, 0>>

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

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

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

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

iex> << 83, 79, 83 >> <> << 24, 4 >>
<<83, 79, 83, 24, 4>>

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

<< 83, 79, 83, << 24, 4 >> >>

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

Размер

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

iex> 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

Разбира се можем да видим и точната дължина в битове:

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

Проверки

Има два метода за проверяване на типа на променлива, свързани с binary структурите.

is_bitstring - Винаги е истина за каквато и да е валидна поредица от данни между << и >>. Няма значение дължината върната от bit_size.
is_binary - Истина е само ако bit_size връща число кратно на 8 - тоест структурата е поредица от байтове.

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

Sub-binaries

С функцията binary_part, можем да боравим с части от дадена binary структура:

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

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

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

Pattern matching

Като всичко друго в Elixir и с binaries можем да съпоставяме:

<< x, y, x >> = << 83, 79, 83 >>

x
83

y
79

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

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

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

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

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

Тук знакът е 1 при отрицателно число и 0, при положително - в случая 0. Пази се в един бит. Цялата част на числото се съдържа в 11 бита, тя се пресмята така: 2^{exponent - 1023}. Цялото число може да се пресметне с (-1)^sign(1 + mantissa/2⁵²)2^{exponent - 1023}:

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

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

iex> << x::5, y::bits >> = << 225 >>
<<225>>
iex> x
28
iex> y
<<1::size(3)>>

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

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

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

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

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

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

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

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

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

Като си говорим за имплементацията е хубаво да обърнем внимание на два вида специални указатели, свързани с binary структурите.

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

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

Отново конкатенация

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

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_zise(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 модула.

Не забравяйте, по горните представяния в паметта и възможни оптимизации са валидни за низовете в Elixir.