Incremental - Library untuk komputasi inkremental

 (github.com/janestreet)
1 poin oleh GN⁺ 3 jam lalu | 1 komentar | Bagikan ke WhatsApp
  • Incremental adalah library yang membantu memperbarui komputasi kompleks secara efisien ketika input berubah
  • Terinspirasi oleh riset self-adjusting computation dari Umut Acar dan lainnya
  • Dapat digunakan untuk menyusun komputasi skala besar seperti spreadsheet agar merespons perubahan data secara efisien
  • Dapat merefleksikan data baru secara efisien ke view pada aplikasi GUI
  • Dapat memastikan data turunan tetap tersinkronisasi dengan data sumber, seperti pada filtering atau transformasi balik mapping

Bidang penggunaan

  • Memperbarui komputasi kompleks secara efisien sebagai respons terhadap input yang berubah
  • Dapat menyusun komputasi skala besar berbentuk spreadsheet agar merespons perubahan data
  • Dapat mengintegrasikan data baru secara efisien ke view GUI
  • Menyinkronkan secara berkelanjutan data turunan yang dihitung dari sumber
    • Filtering data
    • Transformasi balik mapping

Latar belakang desain dan dokumentasi

Bacaan terkait

1 komentar

 
GN⁺ 3 jam lalu
Komentar Hacker News

  • Pemrograman reaktif seperti ini kini banyak digunakan di framework UI JavaScript dengan nama signals, dan usulan standardisasi juga sedang berjalan.
    Vue, SolidJS, Svelte, Ember, dan Angular menggunakannya, sementara di React ada implementasi seperti MobX dan Jotai. Ada berbagai algoritma untuk propagasi perubahan dan evaluasi graf asiklik berarah (DAG); setahu saya SolidJS 2 menggunakan algoritma berbasis tinggi yang mirip dengan Incremental.
    Saya sedang bereksperimen dengan implementasi yang mengalokasikan node di arena Int32Array dan menghubungkannya dengan linked list untuk menghindari beban GC yang sebanding dengan jumlah edge dependensi.
    Di Rust juga ada beberapa implementasi; sebagai framework UI ada Leptos, dan sebagai sistem komputasi inkremental umum yang digunakan rust-analyzer ada Salsa. Ini juga bisa dilihat sebagai sistem build yang melacak dependensi secara otomatis: tup menginstrumentasi pekerjaan build untuk mendeteksi file apa saja yang dibaca lalu menetapkan relasi dependensinya. Tulisan penulisnya di sini dan karya klasik Build Systems à la Carte juga layak dibaca.

    • Kita bisa membuat graf dependensi ringan yang dapat dikosongkan dengan cepat. Tidak perlu mendeskripsikan bagaimana sebuah signal berubah; cukup tandai bahwa ia mungkin telah berubah, lalu saat terjadi perubahan kosongkan dependennya dan daftarkan ulang ketika data baru diminta. Dalam proses ini, sebagian subscriber mungkin menerima notifikasi untuk perubahan yang sebenarnya sudah tidak mereka pedulikan.
      Namun komputasi inkremental dan functional reactive programming (FRP) sebenarnya merupakan ranah yang berbeda. Komputasi inkremental secara eksplisit menurunkan fungsi yang bekerja pada delta, sedangkan FRP bisa saja hanya memakai pendekatan menemukan bagian yang rusak lalu memperbaikinya.
    • Contoh besar lainnya adalah JetBrains Noria. Inti Noria bukanlah framework UI, melainkan platform komputasi inkremental, tetapi saat ini digunakan untuk mengoptimalkan rendering GUI di JetBrains Air IDE.
    • Tampaknya ada perbedaan cukup besar dalam penanganan pembaruan objek kompleks, dan kemungkinan scheduling-nya juga berbeda.

  • Library Incremental tampaknya mencoba menyelesaikan masalah merealisasikan ulang sebagian graf komputasi ketika data sumber berubah. Ini mirip dengan sistem build yang dirancang dengan baik, dan merupakan pendekatan berguna yang juga sering dipakai dalam pemrograman fungsional.
    Di bidang komputasi inkremental juga ada Differential Dataflow, teknologi berdekatan Timely Dataflow, dan DBSP. Feldera berbasis DBSP, sementara Materialize dipimpin oleh orang-orang yang terkait dengan Differential Dataflow.
    Saya sedang mengembangkan modolap, pendekatan terpisah yang dikhususkan untuk data dan workload finansial. Ada banyak masalah besar dan penting yang perlu diselesaikan. Terkait hal ini, episode tentang sistem build dari Signals and Threads juga layak dirujuk.

    • Menekan tombol utama di modolap lalu langsung diarahkan ke pembayaran Stripe sebesar 2.000 dolar tanpa penjelasan apa pun itu cukup berani.
    • openivm adalah compiler SQL-to-SQL yang mengimplementasikan berbagai operasi agregasi sebagai operasi inkremental, dan juga menyediakan ekstensi DuckDB yang memelihara materialized view secara otomatis.

  • Goldman juga menggunakan pendekatan yang sama untuk penentuan harga produk keuangan sekitar 30 tahun lalu. Selama kurang lebih 13 tahun bekerja di sana, saya ingat diskusi panjang tentang Node Purpling.
    Ilmu komputer sudah berkembang, dan menurut saya ini bukan pendekatan berbasis graf, tetapi komputasi seperti diferensiasi mahal biayanya, jadi jumlah eksekusinya harus ditekan sedekat mungkin ke minimum teoretis. Ada juga diskusi HN terkait.

    • Hal ini melahirkan lingkungan yang secara informal disebut bank python, dan tulisan ini membahasnya dengan baik.
      Bagian yang paling tepat menggambarkan masalahnya adalah bahwa, bahkan jika seseorang tidak langsung marah dan resign saat melihat IDE internal khusus, pegawai baru butuh waktu luar biasa lama untuk beradaptasi, dan setelah berbulan-bulan pun masih harus terus mempelajari elemen-elemen yang pada dasarnya berbeda. Saya sendiri butuh sekitar dua setengah tahun untuk benar-benar memahami pekerjaan saya.
      Hampir tidak ada pelatihan modern sampai mereka sadar bahwa orang perlu dilatih ulang. Bagian terburuknya adalah coding untuk membuat UI, dan untuk proyek baru penggunaannya tidak disetujui.

  • Salah satu presentasi teknis favorit saya adalah Seven Implementations of Incremental: https://www.janestreet.com/tech-talks/seven-implementations-of-incremental/

  • Beberapa tahun lalu saya sangat tertarik pada pemrograman dataflow, dan tampaknya banyak orang mendekati masalah ini dari berbagai arah. Saat melihat library ini, saya langsung teringat Javelin dari Clojure.

  • Jika tertarik, library UI Bonsai yang dibangun di atas Incremental juga layak dilihat.
    Library seperti React secara efisien melewati pekerjaan yang tidak perlu dengan virtual DOM, tetapi membuat virtual DOM itu sendiri juga memakan waktu. Bonsai bahkan menginkrementalkan virtual DOM, dan juga menyenangkan untuk dikerjakan.
    Saya pernah membuat library UI desktop untuk Revery yang kini tidak lagi dipelihara, tetapi itu menggunakan versi Bonsai yang cukup lama.

  • Saya belum sepenuhnya memahami bagaimana ini berbeda dari pola Observable, yang menerbitkan nilai baru ke input, menjalankan komputasi, lalu menyampaikan hasil baru ke pelanggan
    Memang ada optimasi seperti deteksi perubahan dan menghentikan propagasi ketika nilainya tetap sama, tetapi Observable juga bisa melakukannya. Bagian yang memproses perubahan secara batch sebelum rekalkulasi dengan stabilize juga menarik, tetapi itu pun bisa diimplementasikan dengan Observable
    Saya penasaran apakah perbedaan utamanya ada pada penyusunan graf komputasi secara otomatis melalui inspeksi internal, atau ada aspek yang lebih mendasar

    • Tergantung bagaimana Anda mendefinisikan pola Observable. Di sini aspek mendasarnya adalah evaluasi malas dan koneksi lemah antar-node graf. Nilai node hanya diwujudkan saat diamati, dan perubahan struktur graf saat eksekusi juga ditangani secara fleksibel
      Ketika hanya sebagian node yang diamati, tidak perlu mewujudkan seluruh graf. Komputasi bisa dihentikan kapan saja sehingga graf dibiarkan dalam keadaan hanya sebagian diperbarui, lalu input diubah lagi, kemudian pewujudan node yang diminati dapat dilanjutkan; algoritmanya akan merapikan semua perubahan
      Komputasi inkremental pada dasarnya adalah istilah yang mencakup karakteristik seperti ini, dan sistem yang sama juga bisa disusun dengan model observer dan subscriber. Spreadsheet Excel klasik adalah contoh yang baik, dan penjelasan algoritma Salsa juga layak dirujuk
    • Secara garis besar, Observable adalah cara berlangganan ke suatu target dan mendengarkan nilainya, sedangkan Incremental lebih dekat ke cache di seluruh DAG komputasi dan state. Ia bisa mengoptimalkan dengan menghitung ulang hanya bagian yang diperlukan
      Presentasi Ron Minsky sangat bagus
    • Tulisan ini membantu memahami lanskap sistem inkremental dan streaming
    • Saya juga berpikir mirip. Sekilas, ini tampak sangat dekat dengan pemrograman reaktif yang memiliki pelacakan dependensi. Saya penasaran apakah keunggulan sebenarnya ada pada kemudahan penggunaan API, atau pada optimasi internal yang secara realistis sulit dilakukan dengan implementasi Observable umum
    • Pada dasarnya ini memang graf, tetapi caranya adalah menghitung perubahan secara akurat dan efisien pada graf yang sangat besar dan berubah secara dinamis
      Bayangkan subgraf berbentuk berlian yang bercabang menjadi ratusan node perantara lalu bergabung kembali melalui jalur dengan panjang berbeda-beda. Bisa juga ada min(A, B) di beberapa jalur, dan hanya sisi dengan nilai maksimum yang berubah
      Pendekatan observer sederhana berpotensi membuat jumlah komputasi meledak secara eksponensial dan besar kemungkinan menimbulkan masalah konkurensi. Library ini tetap mendekati optimal dan benar meskipun struktur graf diubah secara dinamis. Hasil yang sama memang bisa dicapai dengan observer dan semacamnya, tetapi mengimplementasikannya dengan benar sambil menghindari jurang performa jauh lebih sulit

  • Keunggulan proyek Jane Street adalah mengemas gagasan yang sebelumnya ada di ranah riset atau sistem niche menjadi bentuk yang benar-benar bisa dipakai developer. Sekalipun tidak mengadopsi library-nya, dokumen desainnya umumnya layak dibaca

  • Electric Clojure menyediakan rendering inkremental yang melintasi batas klien-server. Menurut saya yang paling mirip adalah SolidJS, tetapi SolidJS hanya berlaku untuk frontend

  • Dulu saya pernah membuat sesuatu yang mirip dan hampir tidak menemukan preseden. Karena tujuan penggunaannya hilang, proyek itu saya hentikan, tetapi saya ingin melihatnya lagi; masih ada di npm dengan nama data-rambler
    Gagasannya adalah memasok stream data ke domain-specific language (DSL) yang dapat dimuat ke runtime JavaScript. Modul mengubah data menjadi beberapa stream keluaran, lalu meneruskannya ke library laporan terpisah untuk menghasilkan laporan dinamis berbasis template
    Sejak versi pertama, kemampuannya sudah cukup kuat, tetapi ada juga rencana besar untuk memperbaikinya dengan sintaks yang lebih JavaScript-idiomatik demi mengurangi kompleksitas