У Льоні сьогодні

Пʼятничний пост про GTD. Те, що варто не тримати все в голові, а краще записувати, це зрозуміло. Але… може хоч памʼятати “що зробити” це корисно? Цього тижня зловив розуміння, що як раз ні, навпаки.

Задача була така: “зателефонувати виконробу”. Ходив я з нею декілька днів. Скільки не згадував, так і не знайшов нагоди зателефонувати. Можна було б пояснити це прокрастинацією, тобто простими словами, лінню.

Проте от що я помітив: перед тим, як робити дзвінок, раптом виявлялося, що взагалі-то, ще не знаю, про що говорити. Задача не була хибною: дзвінок дійсно мав відбутися. Але вона не була наступною дією. Наступна дія, при ближчому розгляді, знайшлася на кшталт “уточнити з дружиною вибір фарби”. А це зовсім інший контекст. Та поки цього не усвідомиш, виглядало так, ніби я прокрастиную, та треба було лише “зібрати волю”. А причина була зовсім не у волі, а в браку осмислення.

Та іронія в тому, що саме такі задачі й застряють в голові. Ті, що прості, зробиш та забудеш. Тому коли в голові крутиться те що треба зробити, та ще й не один день крутиться, то це вірний знак що пора його записати та обміркувати за схемою.

Це і є те, про що йдеться в GTD: не тримай справи в голові, записуй. Навіть якщо справа не велика — зовсім не обовʼязково її можна “взяти та зробити”.

Роздивлявся формат серіалізації Cap’n Proto. Його особливістю є відсутність копіювання даних. Це значить, що коли у вас є буфер даних (та схема до нього), то значення можна забирати прямо з буфера. Фактично Cap’n Proto не стільки серіалізатор, скільки формат організації даних у масиві памʼяті.

Схожих рішень не так багато. Можу відзначити flatbuffers від Google як справжню альтернативу. Тут треба обовʼязково роздивлятися, як воно підтримує вашу платформу (в моєму випадку - Go.) Взагалі я б сказав, що рідко трапляються обставини, щоб саме серіалізація була вузьким місцем.

Проте мені подобається те, що з масивом даних можна працювати по шматочках. Наприклад, якщо у вас є JSON в 1 Гб, то доведеться весь його завантажити та розібрати — навіть коли з нього потрібне одне значення. А якщо Cap’n Proto, то можна прицільно забирати конкретні записи та значення. Це гарно працює з mmap.

Також за моїми вимірами масив даних Cap’n Proto займає суттєво менше памʼяті, ніж еквівалентні структури Go. Особливо по витратах на керування памʼяттю. Там, де у звичайних структур спостерігаю надлишок майже в 100%, у Cap’n Proto його практично немає. Та й не дивно, бо в памʼяті утримується єдиний звичайнісінький масив байтів.

З незручного: Cap’n Proto не підтримує зміну довжини масивів (без перестворення). Також відсутній тип-словник. Словників взагалі в zero-copy не бачу — ймовірно, тому, що для ефективної роботи їх доведеться пересортовувати. Але словник завжди можна замінити пошуком за відсортованим списком.

Наразі автор Cap’n Proto працює у Cloudflare, а сам формат широко використовується у Cloudflare Workers, зокрема для зберігання даних.

Коли потрібно надати двійкові дані в стислій текстовій формі, варто спочатку їх стиснути, а потім кодувати у Base64. Або, як наслідок, навіть якщо на сервері є автоматичне стискання на виході, краще все одно стиснути вхідні дані.

Чому так? Бо суть алгоритму Gzip - побудова словника з повторюваних послідовностей. (Алгоритмів взагалі є декілька, але зазвичай береться Лемпель-Зів-Велч, про нього й мова.) Повторювана послідовність залишиться такою в Base64 тільки тоді, коли вона вирівняна відносно “сітки” по три байти: Base64 кожні три байти перетворює в чотири символи. Ба більше, кожний випадок послідовності мусить бути вирівняний однаково: бо той самий байт на 1, 2, 3 місці в трійці буде представлений в Base64 абсолютно по-різному:

"foo" => Zm9v
" foo" => IGZvbw==
"  foo" => ICBmb28=
"   foo" => ICAgZm9v

Бачите, як послідовність Zm9v зʼявляється знову тільки там, де перед нею три пробіли? На практиці Gzip зможе замінити лише ту частину повторів, якій пощастило збігтися з сіткою. Та ще й обрізаних під неї.

А Base64 навпаки, все одно, що кодувати. Ефективність тут стала: хоч сирі дані, хоч стиснуті, хоч білий шум — все збільшиться в розмірі на 33%.

🤯 Мав нагоду попрактикуватись з конфігурацією AWS ElastiCache через Terraform. ElastiCache - то керований AWS сервіс для Memcached та Redis. Напевно, найгірша абстракція, яку я бачив у AWS, та Terraform нічого не спрощує.

Видно, що спочатку в ElastiCache був Memcached, а потім додали Redis. Бо те, що в них називається “кластер”, з Memcached містить декілька вузлів, а з Redis - тільки один. Але потім в Redis теж зʼявилася підтримка кластерів, її додали в ElastiCache та назвали “cluster mode cluster”. Гарно, так?

Окрім того, в Redis ще є реплікація. Кластери — то коли дані розбиті на декілька вузлів, а реплікація — коли кожен вузол містить копію. Звісно реплікацію теж можна увімкнути в ElastiCache, та зовсім все заплутати.

В Terraform є два ресурси для “кластерів” ElastiCache. aws_elasticache_cluster - це один вузол Redis, а aws_elasticache_replication_group - це декілька вузлів… серед яких можуть бути як репліковані вузли, так і ті, що складають кластер. Я вже не кажу, що це ще один шар незрозумілих назв, але також виникає проблема, що коли в Terraform хочемо перейти від одного вузла до декількох, доведеться замінити один ресурс іншим.

Причому в AWS це не складає складнощів, та увімкнення реплікації навіть не зупиняє базу. Єдине, що для використання репліки в застосунку доведеться замінити адресу вузла на адресу групи, але це можна зробити коли зручно — стара адреса вузла продовжує працювати. Взагалі Terraform бачить старий вузол, а реплікацію — ні, що непогано, бо нам залишається спокійно змінити конфігурацію — задача переходить повністю в площину Terraform.

Як її розвʼязати? Редагувати стан. На превелику радість, за останні роки в Terraform зʼявилися повні можливості редагування стану через конфігурацію. Раніше для того треба було робити консольні команди — що було складно, якщо стан зберігається на CI. А тепер замінити один ресурс на інший можна одним блоком removed (щоб прибрати aws_elasticache_cluster зі стану, але не видалити сам вузол) та import (щоб внести всю групу як aws_elasticache_repication_group).

…Ще з позитивного — те, що міграції та оновлення в ElastiCache відбуваються без відключень та без втрати даних. Коли сервіс вже працює, то працює гарно.

Нам не обовʼязково обмежуватись кодуваннями, де розмір словника є ступенем двійки. Це, звісно, суттєво спрощує операції та дозволяє робити декодування таким псевдокодом (для Base64):

three_bytes = lookup[c0] + lookup[c1] << 6 + lookup[c2] << 12 + lookup[c3] << 18

Але ж будь-який інший розмір словника також технічно можливий. Фактично ми впроваджуємо систему числення з основою, що дорівнює розміру словника, та переводимо наші двійкові дані в та з неї. Єдине, що відрізняє цей процес від шкільної програми: вхідна послідовність розбивається на фрагменти такого розміру, щоб вони влазили в 64-бітне число. (А ще краще — у 48-бітне, що не втратить точності в типі Double та не створить сюрпризів, наприклад, у JavaScript.)

Як тривіальний приклад, розглянемо Base10. Тут кожний символ має одне з 10 значень. Два символи: 100 значень. Три: 1000 значень. Це більше за 256 - значить, трьома символами Base10 можна закодувати один байт. Надлишок такого кодування аж 300%. Хоча насправді за 3 байти можна впоратись й у Base7 (де 343 можливих значень.) А з Base10 надлишок буде менше, якщо кодувати 2 байти (65536 значень) у 5 символів: тільки 250%.

…Якщо це узагальнити, можна прийти до ілюстрації вище. Вона показує надлишок для всіх основ від 2 до 256, але тільки тих, де він зменшується (що в Base64, що в Base65 3 байти даних кодуються в 4 символи.)

Що ми бачимо? Краще за Base64 буде тільки Base85 - який, як згадали в коментарях, використовує Git, а до того ж ще й PostScript та PDF. Як я розумію, тут вирішили, що розмір файлу важливіший за швидкість обробки. Наприклад, в Git у Base85 кодуються патчі - операції з патчами не такі часті, отже можна й почекати.

Наступне покращення наступає на Base102 - для такого вже доведеться відкусити декілька системних символів. Що робить наше “текстове кодування” не таким вже й текстовим. Гадаю, це пояснює, чому окрім Base64 та Base85 інших кодувань немає. (Ну як, немає… Base16 ми теж скрізь використовуємо!)

Прочитав сьогодні в блозі Євгенія Гизили статтю про збірку WASM в складі пакета для браузера. Йшлося проміж іншим про кодування WASM у Base64 для включення у вихідний код JavaScript. (Бо WASM надає нам фактично обʼєктний модуль, який в JavaScript просто так не запакуєш.)

Виникла думка: ну, мабуть, Base64, стандартизований ще у 1996 році, в наш час Unicode та емодзі — не найкомпактніший спосіб кодувати двійкові дані в текст? Думка виявилась хибною: ось чому.

По-перше, стандарт Unicode, та конкретно UTF-8, випереджає Base64, бо зʼявився ще у 1992. Але то таке, історична дрібниця. По-друге, кодування символів у UTF-8 менш ефективне за Base64: символ довжиною у 2 байти кодується у 3, тобто з 50% надлишку замість 33%. (Пояснення тут в тому, що UTF-8 повинен бути сумісним з ASCII, тож всі байти символів Unicode містять виставлений верхній біт, а до того ще й маркери довжини символу).

Отже, як би ми не намагалися використати символи Unicode для кодування, нічого краще за Base64 не отримаємо.

(До речі, рядки в JavaScript мають кодування UTF-16 - єдине з кодувань Unicode, яке не сумісне з ASCII, тобто технічно можна було б досягти кращої ефективності. Але це тільки в памʼяті - а файл, який ми хочемо зменшити, все одно майже напевно буде в UTF-8.)

В ASCII7 128 символів. Не всі можна використовувати: символи 0-31 є системними. До того, важливо, щоб кількість символів в кодуванні була ступенем двійки: це дозволяє кодувати та декодувати з використанням побітових операцій та швидкої таблиці-словника. Виходить, 64 символи — це найкраща кількість, а Base64 - це математично найкраще кодування. Ось так.

🦀 Грав сьогодні в Another Crab’s Treasure - до речі, рекомендую як рідкісно життєрадісний, а все-таки дуже складний соулслайк. Та намагався зрозуміти, в чому ж та складність складається.

🚥 Кожний супротивник у Dark Souls має чітко визначений набір ударів та комбінацій - moveset. Критично важливо (для самої гри), що всякий удар починається з підказки (tell), за яким його можна відрізнити. А всяка дія гравця починається із затримки (замаху, наприклад), та не може бути зупинена.

🩰 Це й складає особливий характер гри, де взаємодія гравця з супротивником не зводиться до того, хто кого швидше лупить. Натомість від гравця очікується вивчення рухів (як власних, так і вражих) та участь в бою практично як у танцю. Противник веде — ми відповідаємо.

⏲️ Тому найпряміший шлях до подолання наступного випробування у Dark Souls (або Another Crab’s Treasure) - це звернути увагу на рухи та підказки противника та шукати, як з ними “танцювати”. А шлях “в лоб” - тобто бити скоріше та захищатися від ударів — значно складніший та не такий приємний (тому багато людей вважають soulslike занадто складними.)

🥋 Все це мені нагадало кати у бойових мистецтвах: гра — як послідовність вправ, які ми маємо вивчити. Та задоволення від неї особливе: задоволення отриманих знань.

Я люблю генерацію коду як аналог метапрограмування на Go. Навіть більше, ніж метапрограмування як у Ruby, оскільки згенерований код можна переглянути, а не тільки уявити.

Дженерики частково прибрали потребу в кодогенерації: а саме, більше не потрібно генерувати код “з підставлянням типів”. Це чудово та, звісно, в нашому коді є місце дженерикам. (Хоча я поки не брався за впровадження суто функціональних підходів, як, наприклад робить модуль github.com/samber/lo.)

Але все ж навіть з дженериками залишається багато шаблонного коду, який неможливо узагальнити. Уявимо, що у нас є структура Database, в якій 10 різних полів Table[Key, Record]. Всі ці поля доведеться оголосити, ініціалізувати, та виконати різне обслуговування. Щоб не копіювати десять разів однакові рядки для кожної таблиці, нам і допоможе кодогенерація.

Раніше я передавав параметри генератора в рядку //go:generate, але нещодавно знайшов інший підхід. Можна почати з конфігурації у JSON чи TOML, а у генераторі зчитувати ту конфігурацію та генерувати весь код. Наприклад, в конфігурації може бути список таблиць, за яким ми генеруємо і структуру Database, і функцію Database.SaveTables(), і все інше.

Можливості практично необмежені! Але все ж я б радив зводити генерований код до мінімуму, бо код в шаблоні точно важче сприймати та редагувати. Наприклад, замість генерації всієї Database можна згенерувати структуру tables та вбудувати її: type Database struct { tables }. Тоді цей тип можна розширювати без вдавання до шаблону.

В продовження вчорашньої ситуації: ділюся декількома знахідками.

• З динамічних мов як Ruby чи JavaScript можна звикнути, що обʼєкти та “словники” працюють хоч приблизно однаково. В Golang це абсолютно не так. Структура фундаментально економніша. Особливо це стосується маленьких структур. Наприклад, бачив словники з двох ключів-констант; можу припустити, що так їх простіше було завантажити чи побудувати. Але “словник зі сталими ключами” в Go - це структура.

• Звісно, ще гірше, коли такий словник не один, а повторюється тисячі разів. Взагалі виходить так, що краще розташовувати словники на найвищому рівні ієрархії. Це може потребувати деякої “інверсії адресації”; наприклад, не масив словників, а словник масивів.

• Як вже писав вчора, з боку оптимізації памʼяті вибір між структурою та вказівником набирає новий сенс: бо дозволяє уникнути фрагментації. Наприклад, масив з 1000 структур буде одним блоком пам’яті: структури зберігатимуться послідовно. Масив з 1000 вказівників - 1001 блоками: вказівники будуть в масиві послідовно, а структури — кожна окремо.

• Хоч рядки в Go є константами, але це ніяк не значить, що дві змінні-рядки з однаковим значенням зберігатимуться в памʼяті лише один раз. Так станеться тільки якщо ми призначимо одну змінну іншої. Це особливо стосується завантаження з JSON: якщо у вас рядок повторюється мільйон разів, кожний зберігатиметься окремо. Поки найкраще, що я можу тут придумати — це власний Unmarshal, який буде заміняти прочитане значення на глобальну константу. (Причому тоді зовсім не обовʼязково робити ту константу рядком.)

Намагаюся знизити розмір величезної структури даних на Golang. (Назвемо її “базою даних в памʼяті.”) Вона більше не влазить в памʼять, відповідно, є сенс знизити витрати, а не просто палити гроші на неоптимально використані ресурси.

Колись я вже дивився на це питання, але тоді питання було більше академічне. На практиці все дуже складно. Звісно, в Go немає способу дізнатися розмір складеної змінної в памʼяті. Майже будь-яка складена змінна буде містити вказівники, тобто складатися з багатьох ділянок памʼяті. Навіть якщо припустити, що всередині немає ані дублікатів, ані циклів вказівників, все одно доведеться рекурсивно збирати все по шматочку.

До того, всі складені типи займають деяку кількість зайвого місця. Структури містять вирівнювальні байти. Масиви мають резервну місткість. З типом map все взагалі погано, бо його нутрощі нам недоступні, та ми практично не можемо дізнатись, яка в словника резервна місткість. Але вона є: дуже грубо кажучи, Go резервує місце під кількість елементів, кратну ступеням двійки.

А зверху того, памʼять виділяється на купі ділянками. Якщо ділянки великі — в них буде багато зайвого місця. Якщо маленькі — каталог ділянок буде сам собою займати забагато. В будь-якому разі реальне використання памʼяті буде ще більше, ніж ми можемо підрахувати за змістом, причому чим більше маленьких обʼєктів — тим гірше. Це ще одна причина уникати зайвих вказівників: кожний вказівник в програмі збільшує фрагментацію памʼяті.

Пишу маленький аналізатор витрат. Поки що мені вдалося “пояснити” десь 60% тих витрат, що повідомляє ReadMemStats. Чи є 40% надлишком на керування памʼяттю? Хочеться, щоб ні.