Стендап Сьогодні

Що я зробив, що я хочу зробити, і що це все значить.
Повсякденні здобутки в форматі стендапу.
Детальніше в статті

06.09.2023

Про те, як я колись переписував код на асемблері

В продовження теми про оптимізацію низького рівня, колись мені довелось переписати пару функцій на асемблері, щоб досягнути суттєвого прискорення.

Мова йде знову про бітові мапи. Одна з ключових операцій з ними — підрахунок кількості “одиничних” бітів в числі (а точніше, в масиві чисел довжиною в мегабайт або більше.) Окрім очевидного підходу “в циклі зсувати число та перевіряти нижній біт” є набагато більш ефективна формула ваги Гемінга. Але максимально ефективно буде використати інструкцію процесора, яка робить саме те, що нам потрібно: POPCNT.

На той момент (2016 рік) готового рішення для використання її з Go не було (А зараз є, наприклад, модуль go-popcount.) Проте інструкція була настільки смачна, а операція настільки важлива для нашого проєкту, що я вирішив власноруч її інтегрувати.

Go підтримує код на асемблері без додаткових засобів. До модуля можна просто додати файл .s з реалізацією однієї або декількох функцій. Звісно, такий файл буде обмежений однією з архітектур, тому можна також написати реалізацію за замовчуванням - на Go.

Не потрібно навіть знати в досконалості структуру цього файлу. Командою objdump можна декомпілювати програму або модуль в код на асемблері. Тобто послідовність дій така: пишемо першу версію функції на Go, компілюємо, декомпілюємо, після чого можна переписати тіло функції, як хочемо. Звісно, розуміння асемблера все одно необхідно — знати регістри, моделі адресації та таке інше.

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

Не знаю, чи буде в житті ще один такий випадок, але принаймні можу в резюме написати, “професійний асемблерист”.

05.09.2023

Вирівнювання структур в Go

На роботі поділилися цікавою статтею. У двох словах: Golang вирівнює кожний елемент структури так, що він розташовується в памʼяті на межі, кратній його розміру (наприклад, int64 - на адресі, що кратна 8 байтам.) Таким чином, якщо в структурі перемішані поля byte та int64, можна витратити набагато більше памʼяті, ніж очікуєш (а byte використовують, щоб заощадити памʼять, чи не так?)

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

Та, мова Go достатньо абстрагована, щоб робити вирівнювання автоматично. Для порівняння, на C структура є буквально відображенням області памʼяті на набір полів, тому ніякого вирівнювання не відбувається та ми вільні власноруч обирати, де розташовується кожне поле — навіть якщо це означає стріляти собі в ногу.

Залишається питання — чому тоді Go не оптимізує порядок полів також для економії пам’яті? Я знайшов відповідь — це просто складно. Є пара обговорень конкретно про це. Поки що навіть з автоматичним вирівнюванням є багато нюансів.

Зате існують напівавтоматичні інструменти: правило fieldalignment для govet - його треба явно увімкнути в golangci-lint. Та оптимізатор gopium. Я спробував fieldalignment на нашому проєкті — він знайшов купу “покращень” - але в більшості випадків я б віддав перевагу осмисленій послідовності полів, а не перемішаній заради оптимізації. Хіба що якщо це структура для внутрішньої бази даних, що зберігатиме тисячі записів.

04.09.2023

Пригоди з живленням через USB-C

Напередодні випуску iPhone 15, який, за всією логікою, буде мати порт USB-C, хотілося б проговорити пару нюансів з використанням USB-C для зарядки. ʼ

Бо в USB-C не тільки безліч протоколів та режимів для даних, але й з живленням теж не все просто. Якщо коротко, то в кабелі USB-C є пара жил, по якій пристрій повідомляє зарядці, яку напругу він очікує.

Нещодавно дізнався, що зарядки USB-C взагалі відмовлять в струмі, якщо пристрій не комунікує про свої можливості. Я це виявив з ретро-консоллю Anbernic RG353M. Хоч вона й має для зарядки розʼєм USB-C, але зарядити її можна тільки кабелем “USB-A - USB-C”. Кумедно, що якщо такий кабель доповнити перехідником USB-C-USB-A, щоб знов з обох кінців стало USB-C, то такий франкенкабель працює з усіма зарядними пристроями. (Через те, що на переході в USB-A втрачається функція “розумного живлення”.) Так само тільки через франкенкабель заряджається моя лампа з гільзи - в ній, напевно, надто простий контур живлення. Тобто мрія про єдиний кабель USB-C, яким можна заряджати всі пристрої, поки не здійсниться.
З позитивного: оскільки зарядні пристрої USB-C здатні видавати струм з напругою 5, 9, 12, 15 та навіть 20V (в залежності від потужності зарядки), то технічно вони підходять для живлення всяких побутових пристроїв. Наприклад, роутеру. Для цього є перехідники “USB-C to barrel plug” - вони містять мікросхему, яка перемкне зарядний пристрій на потрібну напругу. Так можна заживити роутер від павербанка, що може невдовзі статися до нагоди. А ще є універсальні блоки-“клієнти” USB-C - наприклад, fpx.

03.09.2023

Для чого гарний ElasticSearch?

Нарешті, з цими новими знаннями, можу відповісти на питання — що (окрім повнотекстового пошуку) доцільно робити на ElasticSearch.

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

02.09.2023

Чим пошук в ElasticSearch відрізняється від PostgreSQL

Наступне для мене питання — в PostgreSQL теж є індекси. Чим тоді ElasticSearch краще?

Взагалі, якщо почитати документацію про PostgreSQL, або подивитись це гарне відео, то можна помітити, що аналоги індексам ElasticSearch тут теж є. Індекси GIN то є інвертований словник, який теж зберігає групу документів, в яких є те чи інше слово. Індекси GiST то більш-менш те саме дерево пошуку, як ElasticSearch використовує для чисел та геолокацій.

Щоправда, я не бачив, щоб GIN/GiST використовували для простих значень — рядків або чисел — так, як це робить ElasticSearch. Ну, може я чогось не знаю. Але річ не в тім. Як я розумію, справжня перевага ElasticSearch у швидкому поєднанні багатьох індексів.

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

Бітові мапи настільки ефективні, що PostgreSQL їх теж використовує. Мабуть, доводилось в EXPLAIN бачити назву bitmap scan? Щоб поєднати два індекси (а точніше, дві умови, що їх використають), PostgreSQL будує бітові мапи для рядків, які відповідають кожній умові та поєднує їх бітовими операціями.

Тільки різниця в тому, що в ElasticSearch бітові мапи завжди готові до використання, а PostgreSQL ще має їх побудувати з індексу. Та також, в PostgreSQL дані нормалізовані, тому їх доведеться зводити до купи з різних таблиць, де будуть використані різні індекси, які вже так просто не поєднаєш.

До того ж PostgreSQL підтримує транзакції, а це значить, що для кожного рядка він має також перевірити, чи рядок видимий поточній транзакції (в тому числі чи не видалений він.) В ElasticSearch такий крок не потрібний, а перевірка на видалення робиться ще одною бітовою мапою. (До речі, в обох базах оновлення запису відбувається через видалення старої та додавання нової версії.)

Отже, зорієнтованість на швидкий пошук за багатьма умовами, денормалізація та відсутність транзакцій робить ElasticSearch швидше за PostgreSQL.

01.09.2023

Як OpenSearch індексує числа

Вчора я написав трохи застарілу інформацію: насправді десь з 2016 року Lucene вже не зберігає числа у вигляді рядків. Тобто, така можливість залишилась, але тепер є інший спосіб індексування: k-d дерево. Я не пишу “кращий”, бо все залежить від того, що з ним робити.

K-d дерево це дерево множин точок у K-вимірному просторі. Кожен рівень дерева ділить множину навпіл за одним з вимірів. Таким чином, дерево є збалансованим, тобто має рівну кількість точок в кожній гілці — а значить, мінімальну кількість розгалужень.

Але ми хотіли індексувати числа. До чого тут якісь простори? Так, технічно число задає точку в 1-вимірному просторі, а узагальнення на багато вимірів дозволяє використати ту саму структуру даних також для географічних координат, діапазонів та інших застосувань, де важливо порівнювати одночасно декілька показників. У випадку чисел, дерево просто ділить діапазон навпіл, поки не досягне зазначеного розміру множини, що залишається.

В Lucene K-d дерева зберігаються окремо від інвертованого індексу (словника, про який я писав вчора.) Тобто заради ефективності пошуку архітектори впровадили цілу нову структуру даних та формат файлу. З цього боку зрозуміло, чому обрали саме k-d дерева, які покривають багато потреб, а не тільки пошук чисел.

Пошук в K-d дереві відбувається завжди за діапазоном. Кожний вузол дерева визначає діапазон значень всередині. Він може бути або цілком всередині, або цілком ззовні, або перетинати діапазон пошуку. Ті вузли, що всередині, додаються до результату, ззовні — відкидаються, та тільки в ті, що перетинають, доведеться спускатись на наступний рівень та дивитись на менші підмножини. Таким чином ми маємо справу з найбільшими можливими множинами, та відповідно — з найменшою їх кількістю.

Тепер, про доцільність такого індексу в контексті чисел. Якщо вам потрібно шукати числа за діапазоном, то він ефективний, питань нема. А якщо числа — це ідентифікатори, а шукати потрібно тільки по рівності, то алгоритм залишиться такий самий — хоч для діапазону з одного значення. Ба більше, оскільки множини в k-d дереві не доходять до такої деталізації, то наприкінці пошуку відбувається перебір — не дуже великий, але все ж зайвий.

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

31.08.2023

Основа архітектури ElasticSearch, або: чому він такий спритний?

Вирішив для себе зрозуміти, в чому ж така перевага ElasticSearch (та OpenSearch, який є його відгалуженням) по швидкості індексування та пошуку. Розповім про головне.

ElasticSearch побудований на рушії пошуку Lucene. Дуже цікаво, що базова можливість в Lucene вузька: це словник документів за ключовими словами. Як пишуть в цій статті, інші типи пошуку реалізовані через той самий словник — через пошук ключових слів або їх префіксів. (Тут хотілося б ще дорозслідувати.)

Ну, добре, пошук в словнику — операція добре вивчена, двійковий пошук в університеті проходять. Але типовий запит потребує пошуку не за одним, а за декількома словами. Тобто множини документів від кожного слова ще потрібно буде поєднати. Щоб робити це ефективно, Lucene, як пишуть тут використовує для множин… добре мені знайомі бітові мапи. Ось він, секрет швидкості!

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

30.08.2023

Ruby - не найкраща скриптова мова, якщо працюєш з великими файлами

Невеликий сюжет з сьогоднішньої практики. Потрібно було загнати близько 5 мільйонів рядків JSON з файлу в OpenSearch… тільки не по одному — бо зовсім довго — а пачками. Файл займає 2 ГБ, відповідно рядки десь по 400 байтів кожний, але довжина змінна (в кожному рядку — обʼєкт JSON.) До речі, в GZip цей же ж файл займає тільки 70 МБ. Стискайте ваш JSON!

Почав робити це на Ruby - бо простіше за все. Відкрив файл, читаєш собі методом each_line, збираєш пакет та відправляєш. От тільки чомусь працювало це дуже повільно. Пакет з 10 Мб збирався близько хвилини.

Подумав, що може each_line повільно читає, бо йому треба шукати на перенесення рядка. Спробував прочитати весь файл — методом readlines, а потім вже спокійно їх обробляти. Це ситуацію не покращило. Моя підозра лягла на виділення памʼяті при наборі пакета.

Тоді, думаю, скрипт дуже простий — перепишу його на Go. Тут теж є bufio#ReadLine. А головне, що в Go можна виділити памʼять для всього буфера одноразово, а потім потроху його наповнювати. Для цього є третій аргумент функції make: зарезервована місткість.

Далі все пішло добре та після декількох експериментів документи були імпортовані. Для мене висновком стало те, що, якщо вже потрібно обробити такий великий файл, то можна відразу писати скрипт на Go та уникнути проблем з памʼяттю.

(До речі. На Ruby моєю помилкою було те, що я відразу збирав пакет в один рядок. Це й призводить до зайвого виділення памʼяті. Вирішити можна так: збирати рядки в масив, а потім єднати операцією join. Але, на мою думку, урок залишається.)

29.08.2023

Типи клавіш механічних клавіатур

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

Cherry або OEM - мають циліндричну увігнуту поверхню (округляються до боків). Такі можна знайти на клавіатурах великих брендів - Razer, ASUS, та й на різних немеханічних клавіатурах теж. Тобто, напевно, вони нікого не здивують. До того ж по висоті вони всі більш-менш однакові.
SA - мають сферично увігнуту поверхню. Мої улюблені — подобається, коли пальці лягають в клавіші. Профілів SA багато, відрізняються вони висотою клавіш. Наприклад, DSA - дуже низькі, а KSA - фірмовий профіль Keychron - просто височенні. Доведеться перевіряти та, можливо, все одно вчитись на помилках.
XDA - Пласкі клавіші низького профілю. По пласких клавішах зручніше пересувати пальці, тому, за моїм досвідом, вони краще підходять до ігор.

Особливо важливо дивитись на профіль, коли хочеш замінити клавіші частково — наприклад, встановити модні стрілочки. Незлагода не буде ані зручною, ані красивою.

Також, коли шукаєш заміну на свою клавіатуру, вкрай важливо знати, що “широкі” кнопки (наприклад, Shift) можуть бути різної ширини, та перевіряти, що набір на заміну міститиме ті, що потрібні. З останньою заміною я вже перевіряв-перевіряв, і все одно проґавив правий Cmd, який на Keychron Q1 має одинарну ширину, а в наборі такого не було. Але це ще не так погано, як відсутній Shift чи Backspace.

28.08.2023

Модифікація Markdown зі збереженням оригінального синтаксису

Окрім того, щоб парсити, мені ж ще потрібно вносити в документ зміни. Плани поки прості: коли задача створюється, додати їй поточну дату як дату початку: ➕ 2023-08-28. Коли задача є завершеною (має маркер), то дату завершення: ✅ 2023-08-28. Логіка зрозуміла, але як це реалізувати на практиці?

Швидко зрозумів, що підхід “розібрати текст на AST, поміняти та зібрати наново” не працює. Парсер Remark не зберігає повну інформацію про розмітку: як приклад, заголовки можна вказувати або # решітками, або рядком === під заголовком. І те, і те стає в AST просто “заголовком”. Потім при відтворенні Markdown отримуємо заголовки в форматі, який було задано опціями. Одним словом, користувач отримає стандартизований варіант свого файлу. Що буде дивно, бо ми тільки хотіли додати дату в єдиний рядок з задачею.

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

Таке рішення дуже нагадує віртуальну DOM, знайому по React та інших бібліотеках. Там ми теж хочемо зберігати якнайбільше документу без змін.

Раніше

Пізніше