Инкрементные вычисления

Инкрементные вычисления , также известные как инкрементальные вычисления , — это функция программного обеспечения , которая при каждом изменении фрагмента данных пытается сэкономить время , пересчитывая только те выходные данные, которые зависят от измененных данных. ^[1]^[2]^[3] Когда инкрементные вычисления успешны, они могут быть значительно быстрее, чем наивное вычисление новых результатов. Например, пакет программного обеспечения для работы с электронными таблицами может использовать дополнительные вычисления в своих функциях пересчета, чтобы обновлять только те ячейки, содержащие формулы, которые зависят (прямо или косвенно) от измененных ячеек.

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

Статический и динамический

Методы дополнительных вычислений можно условно разделить на два типа подходов:

Статические подходы пытаются получить инкрементальную программу из обычной программы P, используя, например, либо ручное проектирование и рефакторинг, либо автоматические преобразования программы. Эти преобразования программы происходят до того, как будут предоставлены какие-либо входные данные или изменения входных данных.

Динамические подходы записывают информацию о выполнении программы P на конкретном входе (I1) и используют эту информацию, когда вход изменяется (на I2), чтобы обновить выход (с O1 на O2). На рисунке показана взаимосвязь между программой P, функцией расчета изменений ΔP, которая составляет ядро инкрементальной программы, и парой входов и выходов I1, O1 и I2, O2.

Специализированные и универсальные подходы

Некоторые подходы к инкрементальным вычислениям являются специализированными, а другие — общего назначения.Специализированные подходы требуют от программиста явного указания алгоритмов и структур данных, которые будут использоваться для сохранения неизмененных подрасчетов. С другой стороны, подходы общего назначения используют язык, компилятор или алгоритмические методы для придания инкрементального поведения программам, которые в противном случае не были бы инкрементальными. ^[4]

Статические методы

Производные программы

Учитывая вычисление $C=f(x_{1},x_{2},\dots x_{n})$ и потенциальное изменение $x_{j}:=\Delta _{x_{j}}$ мы можем вставить код до того, как произойдет изменение (предварительная производная), и после изменения (постпроизводная), чтобы обновить значение $C$ быстрее, чем повторный запуск $f$ . Пейдж записала список правил формального разграничения программ в SUBSETL. ^[5]

Посмотреть техническое обслуживание

В системах баз данных, таких как DBToaster, представления определяются с помощью реляционной алгебры. Инкрементное обслуживание представлений статически анализирует реляционную алгебру для создания правил обновления, которые быстро поддерживают представление при наличии небольших обновлений, таких как вставка строки. ^[6]

Динамические методы

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

Захвата зависимостей между всеми возможными значениями можно избежать, определив подмножество важных значений (например, результаты агрегирования), по которым можно отслеживать зависимости, и постепенно пересчитывая другие зависимые переменные, тем самым балансируя объем информации о зависимостях, которую нужно отслеживать, с объемом пересчета. выполняться при изменении ввода. ^[7]

Частичную оценку можно рассматривать как метод автоматизации простейшего случая инкрементных вычислений, в котором делается попытка разделить данные программы на две категории: те, которые могут меняться в зависимости от входных данных программы, и те, которые не могут (и наименьшие единица изменения — это просто «все данные, которые могут меняться»). Частичная оценка может сочетаться с другими методами дополнительных вычислений.

При использовании циклов в графе зависимостей одного прохода по графу может оказаться недостаточно для достижения фиксированной точки. В некоторых случаях полная переоценка системы семантически эквивалентна поэтапной оценке и может быть более эффективной на практике, если не в теории. ^[8]

Существующие системы

Компилятор и языковая поддержка

Автоматическая инкрементализация (также называемая «самонастраивающимися вычислениями» и «адаптивным функциональным программированием»), ^[9] Дельта ML , Адаптивный Haskell
Корнеллский синтезатор-генератор ^[10]
IceDust — собственный предметно-ориентированный язык.

Фреймворки и библиотеки

приспособление ^[11] - с реализациями на нескольких языках
Односторонние ограничения потока данных (реактивные вычисления в C++)
Дифференциальный поток данных
Джейн Стрит, постепенно
Инкрементальный журнал данных ( LogicBlox )
Инкрементальный Пролог (XSB) ^[12]
Специализированные для предметной области подходы:
- Инкрементальная проверка типов

Приложения

Базы данных (просмотр обслуживания)
Системы сборки
Таблицы ^[13]
Среды разработки
Финансовые расчеты
Оценка грамматики атрибутов
Графические вычисления и запросы
Графические интерфейсы (например, различия React и DOM)
Научные применения

См. также

Ссылки

^ Карлссон, Магнус (2002). «Монады для инкрементных вычислений». Материалы седьмой международной конференции ACM SIGPLAN по функциональному программированию . Нью-Йорк: ACM . стр. 26–35. дои : 10.1145/581478.581482 . ISBN 1-58113-487-8 .
^ Умут А. Ачар (2005). Саморегулирующиеся вычисления (PDF) (кандидатская диссертация).
^ Камил Деметреску; Ирен Финокки; Андреа Рибикини (2011). «Реактивное императивное программирование с ограничениями потока данных» . Материалы 26-й Международной конференции ACM по языкам и приложениям объектно-ориентированных систем программирования (OOPSLA 2011) . АКМ . стр. 407–426. arXiv : 1104.2293 . дои : 10.1145/2048066.2048100 . ISBN 978-1-4503-0940-0 .
^ Ян Чен; Джошуа Данфилд; Мэтью А. Хаммер; Умут А. Ачар. Неявные самонастраивающиеся вычисления для чисто функциональных программ . ИКФП '11. стр. 129–141. Архивировано из оригинала 30 октября 2016 г. Проверено 12 марта 2018 г.
^ Пейдж, Роберт (1981). Формальное дифференцирование: метод синтеза программ . UMI Research Press. ISBN 978-0-8357-1213-2 .
^ Ахмад, Яниф; Кеннеди, Оливер; Кох, Кристоф; Николич, Милош (1 июня 2012 г.). «DBToaster: дельта-обработка высшего порядка для динамических, часто свежих просмотров». Учеб. ВЛДБ Эндоу . 5 (10): 968–979. arXiv : 1207.0137 . дои : 10.14778/2336664.2336670 . ISSN 2150-8097 .
^ Мугилан Мариаппан; Кеваль Вора (2019). «GraphBolt: синхронная обработка потоковых графов на основе зависимостей». На Европейской конференции по компьютерным системам (EuroSys'19) . стр. 25:1–25:16. дои : 10.1145/3302424.3303974 .
^ Кимберли Берчетт; Грегори Х. Купер; Шрирам Кришнамурти (2007). «Понижение: метод статической оптимизации для прозрачной функциональной реактивности». На симпозиуме ACM SIGPLAN по частичной оценке и манипулированию программами на основе семантики . стр. 71–80. CiteSeerX 10.1.1.90.5866 . ISBN 978-1-59593-620-2 .
^ Хаммер, Мэтью А.; Ачар, Умут А.; Чен, Ян (2009). «ЦЕЛ». Материалы конференции ACM SIGPLAN 2009 г. по проектированию и реализации языков программирования — PLDI '09 . п. 25. дои : 10.1145/1542476.1542480 . ISBN 9781605583921 . S2CID 11058228 .
^ Репс, Томас; Тейтельбаум, Тим (1984). «Синтезатор-генератор». Материалы первого симпозиума по разработке программного обеспечения ACM SIGSOFT/SIGPLAN «Практические среды разработки программного обеспечения» - SDE 1 . стр. 42–48. дои : 10.1145/800020.808247 . ISBN 978-0897911313 .
^ «Адаптон: абстракции языка программирования для дополнительных вычислений» . сайт Adapton.org . Проверено 7 октября 2016 г.
^ Саха, Диптикалян; Рамакришнан, ЧР (2005). «Поэтапная оценка табличного Пролога: за пределами программ чистой логики». Практические аспекты декларативных языков . Конспекты лекций по информатике. Том. 3819. стр. 215–229. CiteSeerX 10.1.1.111.7484 . дои : 10.1007/11603023_15 . ISBN 978-3-540-30947-5 . ISSN 0302-9743 .
^ Хаммер, Мэтью; Пханг, Ху; Хикс, Майкл; Фостер, Джеффри (2014). АДАПТОН: составные дополнительные вычисления по требованию (PDF) . ПЛДИ.

[monads-for-incremental-1] Карлссон, Магнус (2002). «Монады для инкрементных вычислений». Материалы седьмой международной конференции ACM SIGPLAN по функциональному программированию . Нью-Йорк: ACM . стр. 26–35. дои : 10.1145/581478.581482 . ISBN 1-58113-487-8 .

[2] Умут А. Ачар (2005). Саморегулирующиеся вычисления (PDF) (кандидатская диссертация).

[3] Камил Деметреску; Ирен Финокки; Андреа Рибикини (2011). «Реактивное императивное программирование с ограничениями потока данных» . Материалы 26-й Международной конференции ACM по языкам и приложениям объектно-ориентированных систем программирования (OOPSLA 2011) . АКМ . стр. 407–426. arXiv : 1104.2293 . дои : 10.1145/2048066.2048100 . ISBN 978-1-4503-0940-0 .

[4] Ян Чен; Джошуа Данфилд; Мэтью А. Хаммер; Умут А. Ачар. Неявные самонастраивающиеся вычисления для чисто функциональных программ . ИКФП '11. стр. 129–141. Архивировано из оригинала 30 октября 2016 г. Проверено 12 марта 2018 г.

[5] Пейдж, Роберт (1981). Формальное дифференцирование: метод синтеза программ . UMI Research Press. ISBN 978-0-8357-1213-2 .

[6] Ахмад, Яниф; Кеннеди, Оливер; Кох, Кристоф; Николич, Милош (1 июня 2012 г.). «DBToaster: дельта-обработка высшего порядка для динамических, часто свежих просмотров». Учеб. ВЛДБ Эндоу . 5 (10): 968–979. arXiv : 1207.0137 . дои : 10.14778/2336664.2336670 . ISSN 2150-8097 .

[7] Мугилан Мариаппан; Кеваль Вора (2019). «GraphBolt: синхронная обработка потоковых графов на основе зависимостей». На Европейской конференции по компьютерным системам (EuroSys'19) . стр. 25:1–25:16. дои : 10.1145/3302424.3303974 .

[8] Кимберли Берчетт; Грегори Х. Купер; Шрирам Кришнамурти (2007). «Понижение: метод статической оптимизации для прозрачной функциональной реактивности». На симпозиуме ACM SIGPLAN по частичной оценке и манипулированию программами на основе семантики . стр. 71–80. CiteSeerX 10.1.1.90.5866 . ISBN 978-1-59593-620-2 .

[HammerAcar2009-9] Хаммер, Мэтью А.; Ачар, Умут А.; Чен, Ян (2009). «ЦЕЛ». Материалы конференции ACM SIGPLAN 2009 г. по проектированию и реализации языков программирования — PLDI '09 . п. 25. дои : 10.1145/1542476.1542480 . ISBN 9781605583921 . S2CID 11058228 .

[RepsTeitelbaum1984-10] Репс, Томас; Тейтельбаум, Тим (1984). «Синтезатор-генератор». Материалы первого симпозиума по разработке программного обеспечения ACM SIGSOFT/SIGPLAN «Практические среды разработки программного обеспечения» - SDE 1 . стр. 42–48. дои : 10.1145/800020.808247 . ISBN 978-0897911313 .

[11] «Адаптон: абстракции языка программирования для дополнительных вычислений» . сайт Adapton.org . Проверено 7 октября 2016 г.

[SahaRamakrishnan2005-12] Саха, Диптикалян; Рамакришнан, ЧР (2005). «Поэтапная оценка табличного Пролога: за пределами программ чистой логики». Практические аспекты декларативных языков . Конспекты лекций по информатике. Том. 3819. стр. 215–229. CiteSeerX 10.1.1.111.7484 . дои : 10.1007/11603023_15 . ISBN 978-3-540-30947-5 . ISSN 0302-9743 .

[adapton-pldi2014-13] Хаммер, Мэтью; Пханг, Ху; Хикс, Майкл; Фостер, Джеффри (2014). АДАПТОН: составные дополнительные вычисления по требованию (PDF) . ПЛДИ.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]