Хотя инкрементализм имеет плохую репутацию, если вы пытаетесь произвести революцию в отрасли, это важная характеристика, если вы пытаетесь создать адаптивное приложение.
Большинство приложений имеют модель данных, которая преобразуется в некоторую модель представления, которая затем используется для рисования представления, представляемого пользователю. Так, например, в Word есть структуры данных, которые кодируют ряды стилизованного текста, которые действуют как модель данных, и они форматируются в модель представления строк и структур макета страницы для взаимодействия с пользователем.
Когда пользователь выполняет какое-либо действие в приложении, это действие приводит к изменению модели данных, которое затем проникает в представление и появляется для пользователя за достаточно небольшое количество миллисекунд, чтобы казаться фактически мгновенным (когда все идет хорошо). . То, насколько малой должна быть эта задержка, зависит от типа взаимодействия (например, сенсорным интерфейсам требуются очень маленькие задержки, чтобы обеспечить обратную связь «прилипни к пальцу», в то время как клавиатурные интерфейсы обычно могут обходиться несколько большими задержками). .
По мере увеличения размера модели данных и сложности преобразования этой модели в представление разработчику необходимо все более усложнять структуры данных и алгоритмы, которые он использует. Если у вас есть список в вашей модели данных, который вы собираетесь представить пользователю в отсортированном порядке, вы можете просто пересортировать его целиком, когда он изменится, если в нем всего 10 или около того элементов. Если в нем 100 000 элементов, вам, возможно, придется подумать о чем-то более сложном, например, о самобалансирующемся красно-черном дереве, которое может гарантировать, что стоимость вставки и перераспределения всегда ограничена, поэтому изменение этого списка не остановит ваше приложение. .
На заре приложений продуманный дизайн этих структур данных и алгоритмов, которые манипулировали ими, привели к волшебному опыту использования этих ранних графических приложений. Это были машины, которые были в тысячи раз менее эффективны, чем наши нынешние устройства, поэтому вам нужно было быть очень осторожным, чтобы постоянно обеспечивать быструю интерактивную обратную связь. Приложения были тщательно разработаны таким образом, чтобы небольшие действия пользователя (например, вставка символа в строку текста) включали лишь небольшой объем работы по обновлению структур данных и перерисовке дисплея, чтобы они могли выполняться с небольшой предсказуемой задержкой.
Ранние браузеры (около 1996 г.) имели некоторые функции для поэтапного отображения и компоновки (например, они могли рисовать изображение построчно, когда оно загружалось модемом на 56 КБ, или могли добавлять строки в конец длинной страницы просмотра гранок). Но, за исключением некоторых из этих особых случаев, они, как правило, просто опускали руки и регенерировали весь макет в «пакетном» процессе. Netscape на самом деле повторно анализирует всю страницу из исходного HTML только для макета с новой шириной окна; они в основном не поддерживали модель данных, просто просматривали структуры данных.
Я работал над графическими приложениями (текстовые процессоры, электронные таблицы, программы для рисования) в течение 13 лет к тому времени (конец 1995 года), когда я начал работать над нашим HTML-редактором FrontPage. Я погрузился во все эти проблемы, связанные с разработкой интерактивных приложений. Вот почему меня удивило отсутствие какой-либо поддержки интерактивного макета в этих ранних браузерах.
По мере добавления новых функций HTML они добавлялись без особого внимания к интерактивному поведению. Такие функции, как плавающие таблицы и изображения, были разработаны с упором на простоту использования для HTML-писателя и на «пакетное» поведение макета сверху вниз, но практически не заботились о влиянии на производительность указанного поведения макета для интерактивного приложения. как редактор. Один введенный символ может потребовать полной переразметки и перерисовки всей страницы.
Я был на стороне получателя всего этого, потому что как разработчик HTML-редактора мне нужно было поддерживать функции, которые добавляли производители браузеров. В «традиционном» сценарии разработчик приложения может ограничивать сами функции от начала до конца тем, что может быть эффективно реализовано в рамках интерактивного взаимодействия.
Есть много примеров таких ограничений; Таблицы Microsoft Word были разработаны с возможностями, которые были ограничены желанием обеспечить хорошую интерактивную производительность даже в документах, содержащих таблицы, которые могут занимать тысячи страниц. Фиксированная ширина столбца означала, что ввод текста в одной ячейке имел лишь ограниченное влияние на другой контент. Это контрастирует с таблицами HTML, где один символ может изменить вычисленную ширину каждой ячейки в таблице и потребовать компоновки и перерисовки всего содержимого.
Что касается HTML, мы проделали большую работу, чтобы точно проанализировать, какую информацию можно кэшировать, чтобы ускорить инкрементную компоновку. Например, для макета таблицы вам нужно только удерживать минимально и максимально возможную ширину содержимого ячейки, чтобы знать их влияние на общий макет таблицы. Таким образом, вы можете отбросить всю остальную подробную информацию о макете (для экономии памяти) и по-прежнему иметь возможность быстро реагировать на изменение в другой ячейке. Существует множество других мест (например, с абсолютно позиционированным контентом), где вы можете использовать знания о том, как макет распространяется на другой контент, чтобы кэшировать ограниченный объем информации и ограничивать работу, которую вам нужно выполнять, когда что-то меняется.
По мере того, как в браузеры добавлялись возможности динамических сценариев, разработчикам браузеров в конечном итоге пришлось изучать все эти приемы, которые разрабатывали авторы HTML-редакторов (и столкнулись со всеми теми же трудными проблемами дизайна, с которыми им оставили первые разработчики HTML и CSS). Разработчики, пишущие динамические HTML-страницы, также должны быть осведомлены об этих проблемах с производительностью, чтобы создавать страницы, которые можно было бы быстро повторно отображать. Многие из этих проблем были устранены на всех страницах, кроме самых больших, еще за пару десятилетий аппаратных усовершенствований.
В качестве другого примера я нашел интересным, глядя на устройство для чтения Kindle, что они разработали набор ограничений макета и алгоритмов, которые могут работать как вперед, так и назад. Они делают это для того, чтобы перейти в середину тысячестраничной книги без необходимости компоновки всех предыдущих страниц. Если вы переходите на предыдущие страницы, процесс компоновки выполняется в обратном направлении. Вы видите эффекты только при пролистывании назад и вперед и получении немного разных макетов страниц, как правило, вокруг больших блочных элементов, таких как таблицы и изображения, или явных границ страницы, таких как главы.
Меня затянуло в эту полосу воспоминаний, когда я недавно решал проблему инкрементной обработки в приложении для перераспределения округов, над которым мне приходится работать, DRA2020. Я ранее писал об очень аккуратной работе, связанной с задачей вычисления объединения множества полигонов. Многоугольники представляют участки в избирательном округе. Мы преобразуем набор полигонов в топологию, где полигоны теперь определяются как набор общих ребер. Затем объединение полигонов превращается в гораздо более простую (и более быструю) проблему удаления общих ребер; оставшиеся неразделенные ребра представляют контур нового объединенного полигона.
В простейшем случае мы можем выполнить дорогостоящую операцию вычисления топологии из наших входных полигонов в качестве внутреннего процесса и кэшировать результат для загрузки клиентским приложением. Это также помогает, потому что топология составляет примерно половину размера входных полигонов (поскольку точки, представляющие все, кроме самых внешних краев, являются общими и их нужно сохранить только один раз). Проблема в том, что в некоторых случаях нам нужно объединить отдельные топологии в клиентском приложении.
Это была дорогостоящая операция, потому что она включала распаковку плотно упакованной топологии на составляющие ее полигоны (используя ужасно неэффективное представление JavaScript в виде массива-массива-массива-точек), слияние отдельных списков полигональных объектов, а затем повторный запуск программы. дорогой алгоритм преобразования полигонов в топологию (который раздувает память, поскольку создает несколько хэш-таблиц всех этих точек во время вычислений).
У меня давно был фоновый пункт списка пожеланий, чтобы попытаться найти более быстрое решение этой проблемы, которое в идеале не включало бы полную распаковку и повторный анализ всего набора полигонов. Распространенным сценарием, в котором нам понадобилась эта функциональность, было «разрушение» формы одного участка, чтобы заменить ее формами составляющих блоков переписи, чтобы пользователь мог назначать отдельные блоки переписи округу. Казалось безумием, что нам нужно было запускать весь дорогостоящий алгоритм топологии на всех фигурах для штата (например, CA имеет 25 000 фигур участков с более чем миллионом точек), заменяя только одну из фигур.
Я, наконец, дошел до написания топологической функции splice, которая брала бы несколько упакованных топологий (например, топологию для участков штата и топологию для переписных кварталов одного участка), удаляла некоторый набор функций, а затем объединяла остальные в единую составную упакованную топологию. (вроде функции массива splice в JavaScript). Это работало непосредственно с упакованными топологиями, поэтому экономило много памяти и оттока. Это был сложный код, так как он работает непосредственно с упакованным представлением. Это все в JavaScript, но очень похоже на C++, поскольку все данные хранятся в упакованных массивах ArrayBuffer, а ссылки — это просто индексы в буфере, которые нужно тщательно комбинировать и обновлять, иначе все взорвется.
Трудность в правильном написании этого кода укрепила мой опыт в том, что инкрементальные структуры данных и алгоритмы часто немного сложнее, чем алгоритмы пакетного типа. Вам часто нужно заботиться о хранении дополнительной информации (помимо конечного предполагаемого результата), чтобы сделать инкрементные вычисления быстрыми. Вам также нужно сбалансировать это с желанием не раздувать рабочий набор для вычислений, которых на самом деле не будет. Тип обновлений, которые делает ваше приложение, может быть важным для анализа, поскольку вы смотрите не только на форму входных данных, но и на все способы изменения этих данных.
В нашем случае у нас был очень изолированный случай разрушения участка, но также необходимо было поддержать случай, когда мы объединяли базовые участки с, возможно, тысячей или около того подучастков, которые были разделены на отдельные наборы блоков, разбросанных по штату.
Приложение было хорошо изолировано от изменений топологии, так как оно уже использовало класс, который управлял агрегацией географических данных и занимался созданием и кэшированием различных представлений, которые мы используем внутри. Производительность операции улучшилась на порядок (от сотен до десятков миллисекунд) и значительно улучшилась оперативность пользовательского интерфейса во время операций, когда нам нужно было выполнить эту обработку.
Одна из проблем при использовании высокофункциональных слоев для создания приложения заключается в том, что подобные виды оптимизации, зависящие от сценария, могут быть трудновыполнимы. Ранние авторы приложений сталкивались с трудностями, связанными с необходимостью «сворачивать свои собственные приложения» практически с чистого листа, но это означало, что у них было много возможностей для сквозной оптимизации. Сегодняшним авторам приложений часто гораздо труднее понять, как оптимизировать какой-либо высокофункциональный, но непрозрачный слой для их конкретного сценария. Я уверен, что разработчики, борющиеся с оптимизацией подсказок в чате для API большой языковой модели, могут найти отклик в этом опыте.
В нашем случае я уже разветвил базовую библиотеку топологии, чтобы добавить эффективное упакованное представление, поэтому у меня был прямой доступ ко всем слоям, которые мне нужны для написания функциональности сплайсинга. Это была веселая работа.
