Compose Hackathon: День 2.5

Ну вот, так много для ведения блога каждый день. Лучше поздно, чем никогда, верно? В любом случае, у меня есть хорошее оправдание: я был очень занят написанием кода и тестов, и все идет не очень хорошо. Я называю этот день 2.5, так как я не спал большую часть ночи, а сегодня еще ничего не сделал.

Прогресс

Время встать. Вот что я сделал на данный момент:

• Создал абстрактный класс, который:

  • Добавляет мутирующий метод к CharSequence:

      fun replace(start: Int, end: Int, text: CharSequence)
    

    • Добавляет метод для эффективного копирования частей буфера в другие символьные массивы:

      fun getChars(start: Int, end: Int, dest: CharArray, destOffset: Int)
    

  • Реализует остальную часть CharSequence поверх свойства length и метода getChars, так что реализаторам нужно реализовать только 3 вещи.

  • Возвращает изменяемый экземпляр того же самого из CharSequence.subSequence, так что он может действовать как своего рода мутирующая линза в исходную последовательность, а не просто дешевое представление только для чтения.

  • Поддерживает специфические для платформы GetChars-подобные интерфейсы через пустой общий expect interface, а на Android использует его для расширения GetChars.

• Построил три конкретные реализации этого абстрактного класса:

  • Базовая таблица, которая не поддерживает снимки, как в качестве способа выяснить, как на самом деле это сделать, так и в качестве контроля для сравнения с реализациями, поддерживающими снимки.
  • Кусочная таблица, поддерживающая моментальные снимки очень простым и наивным способом, который не пытается быть эффективным, но был очень быстро создан и проще для рассуждений, а также выступает в качестве верхней границы контроля для более оптимизированной реализации. У него нет фактического буфера добавления, он просто хранит вставленные тексты непосредственно в их фрагментах. Спасибо Алексу Ваньо за предложение этой реализации!
  • Таблица фрагментов с поддержкой снапшотов, которая использует трюки, описанные в моем первом сообщении. Она намного сложнее, но благодаря обширному набору юнит-тестов, общим с другими реализациями (см. ниже), я уверен, что она действительно работает.

• Взял обширный набор модульных тестов для существующей реализации GapBuffer, добавил кучу тестов для дополнительных контрактов CharSequence, добавил больше тестов для изоляции моментальных снимков и параметризировал набор тестов для запуска на всех трех конкретных реализациях.

• Также скопировал эталоны GapBuffer и параметризировал их для выполнения всех трех реализаций.

Обучение

GetChars

Очень жаль, что ни в Java, ни в Kotlin нет стандартного интерфейса, позволяющего типу объявить, что он поддерживает эффективное многосимвольное копирование. Метод getChars в моем абстрактном классе таблиц позволяет эффективно копировать фрагмент CharSequence в любую часть CharArray. Это намного эффективнее для копирования больших строк, чем просто вызов CharSequence.get() для каждого отдельного символа. Он берет свою сигнатуру из того, что, похоже, стало стандартом де-факто для такого метода, появляющегося в String, StringBuilder и интерфейсе Android GetChars. К сожалению, кроме этого специфичного для Android интерфейса, не существует стандартного интерфейса Kotlin или JVM, который можно реализовать, чтобы объявить, что он поддерживает эту функциональность. Чтобы использовать ее для CharSequence неизвестных типов, вам придется вручную проверять набор известных типов и потенциально возвращаться к итерации с помощью get. Класс TextUtils в Android имеет статический метод, который делает это для типов, перечисленных выше, но этот метод недоступен на других платформах или в модульных тестах на стороне хоста. Если бы только Kotlin поддерживал типовые классы…

Буфер разрыва в сравнении с таблицей фрагментов

Библиотека Jetpack Microbenchmark действительно хороша. Compose активно использует ее, и там уже были бенчмарки для реализации буфера разрыва, поэтому было легко сравнить мои реализации.

В большинстве бенчмарков производительность таблицы фрагментов без снимков на самом деле довольно близка к буферу разрыва. Она лучше в некоторых случаях (сброс буфера в String и случайные вставки в больших буферах), но хуже в других (операции смежной замены, любые операции замены в маленьких буферах). Это имеет смысл, поскольку перемещение пробела в большом буфере может означать сдвиг вплоть до всего символьного буфера, в то время как в таблице фрагментов требуется только сдвиг списка фрагментов. Копии массивов в маленьких буферах выполняются очень быстро, но таблица фрагментов все равно должна нести накладные расходы на управление фрагментами, поэтому я думаю, что гибридный подход, когда таблица фрагментов использует другую структуру данных для маленьких буферов, может помочь во многих распространенных случаях.

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

Распределение намного хуже для таблиц фрагментов во всех случаях записи, что логично, поскольку им необходимо выделять объекты для фрагментов, чего не нужно делать буферу разрыва.

Накладные расходы на моментальные снимки

Наивная таблица фрагментов с поддержкой моментальных снимков и таблица, более близкая к реализации без моментальных снимков, гораздо ближе по производительности, чем я ожидал до сих пор. Они также обе намного хуже, чем таблица без снимков, что меня меньше удивляет, так как я еще не сделал много оптимизаций. Я планирую покопаться в этом сегодня и, надеюсь, сделать некоторые значительные улучшения.

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

Постоянные коллекции KotlinX

Я знал, что Compose использует библиотеку kotlinx.collections.immutable под капотом для реализации SnapshotStateList и друзей, но я не знал, что мы на самом деле встраиваем исходники этой библиотеки. Причина, которая кажется очевидной, если подумать, заключается в том, что публичная библиотека все еще не стабильна, поэтому Compose не может иметь зависимость от нее из своих стабильных релизов. Это отстой, потому что Compose не хочет раскрывать свой форк этой библиотеки, поэтому она является внутренней в модуле runtime:runtime. А все эти текстовые вещи, которые я делаю, находятся в модуле ui:ui-text, поэтому мне пришлось сделать вторую копию библиотеки коллекций. Если мы когда-нибудь выпустим ее в продажу, мы могли бы выделить наш форк в отдельный модуль Gradle и пометить все специальной аннотацией @OptIn, чтобы сторонний код случайно не использовал ее. Но постоянные коллекции — это действительно полезный инструмент, и я очень надеюсь, что kotlinx.collections.immutable скоро выйдет в версии 1.0.

Далее

Вот что я планирую сделать сегодня:

• Добавить стресс-тест для борьбы с соперничеством между несколькими писателями в разных потоках. Тесты изоляции моментальных снимков, которые я уже написал, покрывают большинство моделей поведения при обработке параллелизма, но я понял, что они не гарантируют, что трюк прямого изменения последнего сегмента в буфере добавления синхронизируется правильно.
• Улучшить управление фактическими фрагментами: есть много возможностей для «правильной» реализации, но при этом накапливается много ненужной фрагментации в таблице фрагментов. Фрагментированные таблицы фрагментов будут медленнее обрабатываться как при чтении, так и при записи, поскольку и то, и другое требует итерации, в худшем случае, по всей таблице.
  • Также добавьте модульные тесты для этого.
• Покопайтесь в трассировках Perfetto, сгенерированных в бенчмарках (опять же, Jetpack Microbenchmark — потрясающая вещь), чтобы попытаться оптимизировать все еще больше и приблизиться к существующей производительности буфера разрывов.
• Исследовать возможность использования гибридного подхода, при котором маленькие буферы сложения (меньше размера полного сегмента буфера сложения) хранятся в более простой структуре данных, возможно, даже просто в массиве или неизменяемом буфере разрыва, который мы копируем при каждой мутации.
  • Небольшие буферы, вероятно, являются наиболее распространенным случаем, поскольку большинство текстовых полей в мобильных приложениях в конечном итоге не содержат так много текста.
  • Копирование небольших массивов на самом деле очень быстро, поэтому мне интересно, будет ли это быстрее, чем накладные расходы на управление частями и сложными постоянными структурами данных.
  • Это также может быть более эффективным с точки зрения пространства, поскольку текстовые поля, содержащие только почтовые индексы, не должны занимать более нескольких десятков байт.
  • Рассмотрите возможность использования связанного списка для таблицы фрагментов вместо PersistentList, поскольку список нужно просматривать только в порядке, последовательно, с самого начала (текущая реализация использует индексы, но это несложно изменить).