#meme #bio

Простите

Блеск и нищета #rust:
https://twitter.com/frankmcsherry/status/954062968903405573

Хотел написать что-то по поводу сегодняшней даты, но... Серьёзно, вы же умные люди, вы и так знаете, какой сегодня день. Будет хорошо, если вы поздравите сегодня кого надо. Спасибо.

Попытался сделать через GAT-ы, но фиг вам:
error: type-generic associated types are not yet implemented

#prog #rust #rustlib

Замечательная библиотека для разбора значений на уровне битов. Как ни странно, не от dtolnay.

https://github.com/porglezomp/bitmatch

В питоне удобно сделали, совместили параллелизм зелёных потоков и накладные расходы нативных тредов.

#prog #моё

Сегодня я хотел бы рассказать о возможных способах реализации полиморфизма в языках программирования и о том, какие выгоды и издержки они имеют. Disclaimer: я не особо шарю, так что могу наговорить глупостей.

Полиморфизм — это свойство кода обрабатывать данные разных типов единым образом. Замечательная вещь, не так ли? К сожалению, истинно полиморфного кода мало: если полиморфная функция делает что-то помимо тасовки аргументов, рано или поздно нужно будет выполнить операцию, специфичную для конкретного типа. Для того, чтобы исполнить полиморфный код, нужно каким-то образом передать в него эти функции для конкретного типа. О том, как это можно сделать и на какие компромиссы при этом приходится идти, я сегодня и расскажу.

1. ad hoc полиморфизм (aka полиморфизм для бедных). В этом варианте мы не прилагаем никаких специальных усилий к обеспечению полиморфизма: достаточно разрешить иметь в языке перегрузку функций. При подстановке конкретного типа в обобщённый код компилятор ищет перегрузки с соответствующими типами и вставляет нужные вызовы.

Достоинства:
* Легко реализовать.

Недостатки:
* Наличие перегрузки сразу ставит вопрос о том, какая перегрузка более специфичная, что усложняет рассуждения о коде.
* Требует наличия в языке механизма написания кода с отложенной проверкой типов (макросы в C и шаблоны в C++ под это определение в данном контексте подходят).
* Непосредственное следствие из предыдущего пункта: ошибки несоответствия типов ловятся по месту использования, а не по месту определения, что затрудняет отладку кода и написание высокообобщённого кода ("У меня не сошлись типы потому, что я неправильно вызвал функцию или потому. что сама функция определена ошибочно?").
* Сам факт обобщённости затруднительно переносить между границами отдельных единиц компиляции (читай, фиг вам, а не динамическая линковка).

Резюмируя: использовать имеет смысл тогда, когда нет других альтернатив.

2. Если нам нужно иметь таблицу функций для каждого значения некоего типа, наиболее прямолинейный способ достичь этого — это включить эту таблицу в каждое значение. Так поступают компиляторы всех мейнстримных объектно-ориентированных языков программирования (Java, C#, C++ при использовании классов).

Достоинства:
* Обобщённая функция в скомпилированном коде всего одна для каждой комбинации типов, поэтому итоговый бинарник остаётся достаточно маленьким.
* Если в языке есть интерфейсы, которые могут расширять друг друга, то можно организовать таблицы функций (vtable) таким образом, чтобы vtable для интерфейса Bar, расширяющего интерфейс Foo, начиналась с vtable интерфейса Foo. Таким образом можно получить повышающее преобразование (upcast), которое ничего не стоит в рантайме.
* Нормальная проверка типов: ошибки ловятся в определении обобщённой функции, если функция неправильна определена, и на месте использования при вызове с неправильными типами аргументов.
* Нормально работает с динамической линковкой.

К сожалению, в этом бочонке мёда есть ковш дёгтя:
* (Этот пункт относится главным образом к вышеупомянутым мейнстримным ООП ЯП, которые смешивают наследование интерфейса и наследование данных) Так как размер конкретного типа вызываемой функции неизвестен, аргументы приходится передавать по указателю (это можно обойти, но с весьма нетривиальными ухищрениями), то есть как минимум первое обращение к аргументу косвенное (последующие могут быть напрямую, если данные остались в кеше процессора). Если созданный аргумент выходит за пределы функции, в которой был создан, то его приходится выделять в куче.
* Если мы хотим иметь в языке расширяемые интерфейсы (а мы хотим, чтобы не копипастить всё руками), то мы не можем напрямую включать vtable в само значение, потому что мы не знаем размера этой vtable наперёд. Поэтому обращение к функциям проходит через ещё один указатель. Конечно, если мы знаем, что интерфейс нерасширяем, то мы можем включить эти функции напрямую, но: а) в этом случае upcast сломается; б) vtable будет занимать в кеше место, оставляя меньше места под поля аргумента.
* Если мы хотим иметь возможность реализовывать несколько интерфейсов для типов (а мы хотим), то придётся держать несколько таблиц, и так как их число наперёд неизвестно, то их придётся держать в динамическом списке (+1 индирекция) и при апкасте к разным интерфейсам либо при каждом обращении искать нужную таблицу, либо менять порядок таблиц в рантайме, так что по факту бесплатный upcast мы теряем.
* Так как у каждого отдельного аргумента потенциально своя vtable, мы не можем толком иметь функции вида fn<T>(arg1 T, arg T) -> T, что очень — нет, не так — ОЧЕНЬ сильно ограничивает выразительность системы типов.
* Получить доступ к vtable можно только в том случае, если у нас есть на руках значение нужного типа, поэтому мы не можем иметь функции вида fn default<T>() -> T и fn from_str<T>(string s) -> T.

3. А что, если мы не будем в лоб включать vtable в каждое значение, а передавать указатель на неё рядом со значением? Так происходит в Rust при использовании dyn Trait и в Haskell при использовании экзистенциальной типизации. Компромиссы при этом схожи с предыдущим решением, поэтому я сконцентрируюсь на отличиях.

Достоинства:
* Использование функций в vtable требует одного косвенного доступа вместо двух.
* Апкаст к разным интерфейсам требует лишь замены указателя на vtable, сам аргумент трогать не надо. Для каждой конкретной комбинации интерфейсов можно составить свою vtable, поэтому тут нет проблем с vtable неизвестного размера.
* Так как само значение не включает в себя vtable, компилятор в состоянии в тех случаях, когда конкретный нижележащий тип известен, может передавать его по значению и, таким образом, избежать выделения памяти в куче, даже если значение уходит из функции, в которой было порождено. Также в этом случае компилятор может заинлайнить функции из vtable.

Недостатки:
* Фактически, в этом случае мы передаём по два указателя на аргумент, что в некоторых случаях может оказаться расточительно (кеш процессора всё же не очень большой).
* Вместо того, чтобы иметь по одной vtable в бинарнике на реализацию интерфейса типом, при использовании статической схемы распределения vtable для апкастов мы вынуждены хранить в бинарнике каждую комбинацию интерфейсов для каждого типа, которая используется в программе. В этом случае мы занимаем место в бинарнике дублирующимся определениями. В принципе, это можно решить, передавая отдельно указатели на каждую vtable, но лично мне неизвестен ни один язык, в котором это реально использовалось бы (если вы вдруг знаете — напишите в личку или в чат @decltype_chat_ptr_t). Подобное предлагалось к реализации в Rust, но дальше обсуждений дело так и не зашло (нет, ссылку на RFC я сейчас найти не могу).

4. Максимальной гибкости мы достигаем, передавая vtable отдельно для каждого типа аргумента вместо того, чтобы привызывать к отдельным аргументам. В этом случае vtable могут передаваться в рантайме (Scala), на этапе компиляции (Rust) или тогда, когда решит компилятор (Haskell, но там, как правило, передаётся в итоге на этапе компиляции).

Достоинства:
* Мы можем спокойно мономорфизировать обобщённые функции и инлайнить функции из vtable.
* Тот факт, что vtable одинаковая для обоих аргументов, позволяет использовать описывать обобщённые функции вида fn add<T>(a T, b T) -> T
* Тот факт, что мы можем передавать vtable, не передавая самого аргумента этого типа, позволяет писать обобщённые функции вида fn default<T>() ->T (и, что немаловажно, строить на их базе новые, вроде fn default_pair() -> (T, T)).

Недостатки:
* Мономорфизованные функции увеличивают итоговый размер бинарника.
* Динамическая линковка сильно затруднена (хотя и возможна).
* vtable нужно как-то передавать в обобщённые функции. Передавать их явно слишком неудобно, поэтому в тех языках, где подобные механизмы есть (Rust, Haskell, Scala), нужно каким-то образом определять, какую именно реализацию интерфейса для данного типа надо передавать. Это — отдельная сложная проблема, и то, как её решают — тема, достойная отдельного поста.

Чёрт возьми, как же в телеге неудобно лонгриды писать

Каждый раз, когда ты принимаешь Vec<T> по ссылке, где-то в мире ругается один Клиппи

#prog #rust #article #rustlib

О том, как писать быстрый код на Rust, вкупе с советами по профилированию кода. Рассказывается на примере библиотеки fasteval, по настоящему быстрой библиотеки для подсчёта арифметических выражений.

likebike.com/posts/How_To_Write_Fast_Rust_Code.html

#prog #rust #article

Как сделать API, оперирующее глобальным состоянием, которое не даёт возможности использовать себя некорректно. Rust особенно хорош в части предотвращения неправильного использования на этапе компиляции: единственная проверка в рантайме — создание токена доступа к библиотеке, который должен существовать в единственном экземпляре. Как пишет автор, этот подход можно применить и в других языках программирования, но это может потребовать больше проверок в рантайме.

adventures.michaelfbryan.com/posts/pragmatic-global-state/

#prog #rust #article #rustlib

От этого же человека: библиотека для трансформации неструктурированного текста в формате markdown. Очень элегантное, на мой взгляд, API для потокового изменения документа.

adventures.michaelfbryan.com/posts/markedit/

#prog #rust #rustlib

Кому-то в расточате требовались параметризованные тесты. Так вот, такая библиотека есть.

crates.io/crates/test-case

#prog #rust #rustlib #amazingopensource

Библиотека, которая возвращает Cow вместо String для трансформированных строк, если это возможно. Всегда знал, что кто-то напишет нечто подобное, на мой взгляд, очень полезная вещь.

https://github.com/RReverser/cow-utils-rs

#prog #rust #article

Продолжая тему строк в Rust: развёрнутая статья, которая достаточно доходчиво объясняет, почему в Rust два типа строк. Да и написано так, что читать легко и приятно.

https://fasterthanli.me/blog/2020/working-with-strings-in-rust/