Incremental - ไลบรารีสำหรับการคำนวณแบบเพิ่มทีละส่วน

 (github.com/janestreet)
1 คะแนน โดย GN⁺ 3 시간 전 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • Incremental เป็นไลบรารีที่ช่วยให้อัปเดตการคำนวณที่ซับซ้อนได้อย่างมีประสิทธิภาพเมื่ออินพุตเปลี่ยนแปลง
  • ได้แรงบันดาลใจจากงานวิจัยด้าน การคำนวณแบบปรับตัวเอง (self-adjusting computation) ของ Umut Acar และคณะ
  • สามารถจัดโครงสร้างให้การคำนวณขนาดใหญ่ เช่น สเปรดชีต ตอบสนองต่อการเปลี่ยนแปลงของข้อมูลได้อย่างมีประสิทธิภาพ
  • สามารถสะท้อนข้อมูลใหม่ลงในมุมมองของแอปพลิเคชัน GUI ได้อย่างมีประสิทธิภาพ
  • ช่วยรับประกันว่า ข้อมูลที่ได้จากการคำนวณต่อยอด เช่น การแปลงย้อนกลับของการกรองหรือการแมป จะซิงค์กับข้อมูลต้นฉบับอยู่เสมอ

กรณีการใช้งาน

  • อัปเดต การคำนวณที่ซับซ้อน ได้อย่างมีประสิทธิภาพเพื่อตอบสนองต่ออินพุตที่เปลี่ยนแปลง
  • สามารถจัดโครงสร้างให้การคำนวณขนาดใหญ่ในรูปแบบสเปรดชีตตอบสนองต่อการเปลี่ยนแปลงของข้อมูลได้
  • สามารถผสานข้อมูลใหม่เข้ากับมุมมอง GUI ได้อย่างมีประสิทธิภาพ
  • ซิงค์ข้อมูลที่ได้จากการคำนวณจากต้นฉบับอย่างต่อเนื่อง
    • การกรองข้อมูล
    • การแปลงย้อนกลับของการแมป

ภูมิหลังการออกแบบและเอกสาร

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 3 시간 전
ความคิดเห็นจาก Hacker News

  • การเขียนโปรแกรมแบบ reactive ลักษณะนี้ในปัจจุบันถูกใช้กันอย่างแพร่หลายใน JavaScript UI framework ภายใต้ชื่อ signals และกำลังมีข้อเสนอเพื่อกำหนดเป็นมาตรฐาน
    Vue, SolidJS, Svelte, Ember, Angular ใช้อยู่ และใน React ก็มี implementation อย่าง MobX และ Jotai อยู่ด้วย อัลกอริทึมสำหรับการแพร่กระจายการเปลี่ยนแปลงและการประเมินกราฟมีทิศทางแบบไม่มีวงวน (DAG) ก็มีหลายแบบ และเท่าที่รู้ SolidJS 2 ใช้อัลกอริทึมแบบอิงความสูงที่คล้ายกับ Incremental
    ผมกำลังทดลองการ implement ที่จัดสรร node ลงใน arena แบบ Int32Array แล้วเชื่อมด้วย linked list เพื่อหลีกเลี่ยง ภาระ GC ที่แปรผันตามจำนวน dependency edge
    ใน Rust ก็มีหลาย implementation เช่นกัน โดย UI framework มี Leptos และระบบคำนวณแบบ incremental ทั่วไปที่ rust-analyzer ใช้คือ Salsa เราอาจมองสิ่งนี้เป็น build system ที่ติดตาม dependency อัตโนมัติได้ด้วย โดย tup จะ instrument งาน build เพื่อตรวจจับว่าอ่านไฟล์ใดบ้างแล้วตั้งความสัมพันธ์ dependency ขึ้นมา บทความของผู้เขียนและงานคลาสสิกอย่าง Build Systems à la Carte ก็น่าอ่าน

    • สามารถสร้าง dependency graph แบบเบาที่ล้างทิ้งได้อย่างรวดเร็ว ไม่จำเป็นต้องอธิบายถึงขั้นว่า signal เปลี่ยนอย่างไร แค่ทำเครื่องหมายว่าอาจมีการเปลี่ยนแปลง แล้วเมื่อมีการเปลี่ยนแปลงก็ล้างสิ่งที่พึ่งพาออก จากนั้นค่อยลงทะเบียนใหม่เมื่อมีการร้องขอข้อมูลชุดใหม่ ในกระบวนการนี้ subscriber บางรายอาจได้รับแจ้งการเปลี่ยนแปลงที่ไม่ได้สนใจอีกต่อไปแล้ว
      อย่างไรก็ตาม การคำนวณแบบ incremental กับ functional reactive programming (FRP) เป็นคนละขอบเขตกันจริง ๆ การคำนวณแบบ incremental จะ derive ฟังก์ชันที่ทำงานกับ delta อย่างชัดเจน แต่ FRP อาจใช้แค่วิธีค้นหาส่วนที่เสียหายแล้วกู้คืนก็ได้
    • อีกตัวอย่างสำคัญคือ JetBrains Noria แก่นของ Noria ไม่ใช่ UI framework แต่เป็น แพลตฟอร์มการคำนวณแบบ incremental ทว่าปัจจุบันถูกใช้เพื่อปรับการ render GUI ของ JetBrains Air IDE ให้มีประสิทธิภาพขึ้น
    • ดูเหมือนจะมีความแตกต่างค่อนข้างมากใน การจัดการการอัปเดตของ object ที่ซับซ้อน และ scheduling ก็มีแนวโน้มจะแตกต่างกันมากด้วย

  • ไลบรารี Incremental ดูเหมือนพยายามแก้ปัญหาการ re-materialize บางส่วน ของกราฟการคำนวณเมื่อข้อมูลต้นทางเปลี่ยน คล้ายกับ build system ที่ออกแบบมาดี และเป็นแนวทางที่มีประโยชน์ซึ่งพบได้บ่อยใน functional programming
    ในสาขาการคำนวณแบบ incremental ยังมี Differential Dataflow รวมถึงเทคโนโลยีใกล้เคียงอย่าง Timely Dataflow และ DBSP ด้วย Feldera อิง DBSP ส่วน Materialize นำโดยคนที่เกี่ยวข้องกับ Differential Dataflow
    ผมกำลังพัฒนา modolap ซึ่งเป็นแนวทางอีกแบบที่เจาะจงกับข้อมูลและ workload ด้านการเงิน มีปัญหาใหญ่และสำคัญมากมายที่ต้องแก้ ในเรื่องที่เกี่ยวข้องกัน ตอนbuild systemของ Signals and Threads ก็น่าอ้างอิง

    • การกดปุ่มหลักของ modolap แล้วถูกพาไปหน้า จ่ายเงิน Stripe 2,000 ดอลลาร์ โดยไม่มีคำอธิบายใด ๆ นี่ถือว่ากล้ามาก
    • openivm เป็น SQL-to-SQL compiler ที่ implement การคำนวณ aggregate หลากหลายแบบให้เป็นการคำนวณ incremental และยังมี DuckDB extension สำหรับดูแล materialized view โดยอัตโนมัติด้วย

  • Goldman ก็ใช้แนวทางเดียวกันในการตั้งราคาผลิตภัณฑ์ทางการเงินเมื่อราว 30 ปีก่อน ระหว่างที่ทำงานที่นั่นประมาณ 13 ปี ผมจำการถกเถียงยาว ๆ เรื่อง Node Purpling ได้
    วิทยาการคอมพิวเตอร์ก้าวหน้าขึ้นแล้ว และในมุมมองของผม นี่ไม่ใช่แนวทางแบบกราฟ แต่การคำนวณอย่างเช่นอนุพันธ์มีต้นทุนสูง จึงต้องลดจำนวนครั้งที่รันให้เข้าใกล้ค่าต่ำสุดเชิงทฤษฎีให้มากที่สุด มีการสนทนาใน HNที่เกี่ยวข้องด้วย

    • สิ่งนี้นำไปสู่สภาพแวดล้อมที่เรียกกันไม่เป็นทางการว่า bank python และบทความนี้อธิบายไว้ได้ดี
      ประเด็นที่บรรยายปัญหาได้ดีที่สุดคือ แม้คุณจะเห็น IDE ภายในองค์กรโดยเฉพาะแล้วไม่โมโหจนลาออก แต่พนักงานใหม่ก็ยังใช้เวลาปรับตัวนานผิดปกติ และแม้ผ่านไปหลายเดือนก็ยังต้องเรียนรู้องค์ประกอบที่แตกต่างโดยพื้นฐานอยู่เรื่อย ๆ ตัวผมเองใช้เวลาประมาณ 2 ปีครึ่งกว่าจะเข้าใจงานที่ทำอย่างสมบูรณ์
      แทบไม่มีการฝึกอบรมสมัยใหม่เลย จนกระทั่งตระหนักว่าจำเป็นต้องสอนใหม่ ส่วนที่แย่ที่สุดคือการเขียนโค้ดเพื่อสร้าง UI และไม่ได้รับอนุมัติให้ใช้กับโปรเจกต์ใหม่

  • หนึ่งในงานนำเสนอเชิงเทคนิคที่ชอบที่สุดคือ Seven Implementations of Incremental: https://www.janestreet.com/tech-talks/seven-implementations-of-incremental/

  • เมื่อไม่กี่ปีก่อน ผมสนใจ dataflow programming มาก และดูเหมือนว่าหลายคนเข้าหาปัญหานี้จากหลายทิศทาง พอเห็นไลบรารีนี้ก็นึกถึง Javelin ของ Clojure ทันที

  • ถ้าสนใจ ก็น่าดู UI library Bonsai ที่สร้างบน Incremental ด้วย
    ไลบรารีอย่าง React ข้ามงานที่ไม่จำเป็นได้อย่างมีประสิทธิภาพด้วย virtual DOM แต่การสร้าง virtual DOM เองก็ใช้เวลา Bonsai ทำให้ แม้แต่ virtual DOM ก็เป็น incremental และใช้งานแล้วก็สนุกด้วย
    ผมเคยสร้างไลบรารี desktop UI สำหรับ Revery ที่ตอนนี้ไม่ได้ดูแลแล้ว แต่ใช้ Bonsai เวอร์ชันค่อนข้างเก่า

  • ผมยังไม่เข้าใจทั้งหมดว่าสิ่งนี้ต่างจาก แพตเทิร์น Observable อย่างไร ซึ่งเป็นการส่งค่าใหม่เข้าอินพุต ผ่านการคำนวณ แล้วส่งผลลัพธ์ใหม่ให้ผู้สมัครรับข้อมูล
    น่าจะมีการตรวจจับการเปลี่ยนแปลงและการปรับให้เหมาะสมที่หยุดเผยแพร่ต่อเมื่อค่ายังเหมือนเดิม แต่ Observable ก็ทำได้เช่นกัน ส่วนที่ใช้ stabilize เพื่อรวมการเปลี่ยนแปลงเป็นชุดก่อนคำนวณใหม่ก็น่าสนใจ แต่ก็ยังน่าจะทำด้วย Observable ได้เหมือนกัน
    สงสัยว่าความแตกต่างหลักอยู่ที่การสร้างกราฟการคำนวณโดยอัตโนมัติผ่านการสำรวจภายใน หรือมีปัจจัยที่พื้นฐานกว่านั้น

    • ขึ้นอยู่กับว่านิยามแพตเทิร์น Observable อย่างไร ปัจจัยพื้นฐานตรงนี้คือ การประเมินผลแบบหน่วงเวลาและการเชื่อมโยงแบบหลวมระหว่างโหนดของกราฟ ค่าของโหนดจะถูกทำให้เป็นรูปธรรมก็ต่อเมื่อถูกสังเกต และยังจัดการการเปลี่ยนโครงสร้างกราฟระหว่างรันได้อย่างยืดหยุ่น
      เมื่อสังเกตเพียงบางโหนด ก็ไม่จำเป็นต้องทำให้ทั้งกราฟเป็นรูปธรรม สามารถหยุดการคำนวณเมื่อใดก็ได้ ปล่อยให้กราฟอยู่ในสถานะที่อัปเดตเพียงบางส่วน แล้วเปลี่ยนอินพุตเพิ่มเติม จากนั้นค่อยทำให้โหนดที่สนใจเป็นรูปธรรมต่อได้ และอัลกอริทึมจะจัดการการเปลี่ยนแปลงทั้งหมดให้เรียบร้อย
      การคำนวณแบบเพิ่มทีละส่วนโดยเนื้อแท้เป็นคำที่ครอบคลุมคุณสมบัติเหล่านี้ และระบบแบบเดียวกันก็อาจจัดโครงสร้างด้วยโมเดลผู้สังเกตการณ์และผู้สมัครรับข้อมูลได้เช่นกัน สเปรดชีต Excel แบบคลาสสิกเป็นตัวอย่างที่ดี และ คำอธิบายอัลกอริทึม Salsa ก็น่าอ่านประกอบ
    • คร่าว ๆ Observable คือวิธีสมัครรับเป้าหมายแล้วฟังค่า ส่วน Incremental ใกล้เคียงกับ แคชที่ครอบคลุมทั้ง DAG ของการคำนวณและสถานะ มากกว่า จึงปรับให้เหมาะสมได้โดยคำนวณใหม่เฉพาะส่วนที่จำเป็น
      งานนำเสนอ ของ Ron Minsky ดีมาก
    • บทความนี้ ช่วยให้เข้าใจ ภูมิทัศน์ของระบบแบบเพิ่มทีละส่วนและสตรีมมิง ได้
    • ผมก็คิดคล้ายกัน ตอนแรกที่เห็น ดูใกล้เคียงกับ reactive programming ที่มีการติดตาม dependency มาก สงสัยว่าข้อดีจริง ๆ คือ ความใช้งานง่ายของ API หรือเป็นการปรับให้เหมาะสมภายในที่ทำได้ยากในทางปฏิบัติด้วยการใช้งาน Observable ทั่วไป
    • โดยพื้นฐานแล้วเป็นกราฟจริง ๆ แต่เป็นวิธีคำนวณการเปลี่ยนแปลงใน กราฟขนาดใหญ่และเปลี่ยนแบบไดนามิก ได้อย่างถูกต้องและมีประสิทธิภาพ
      ลองนึกถึงกราฟย่อยรูปเพชรที่แตกออกเป็นโหนดกลางหลายร้อยโหนด แล้วกลับมารวมกันผ่านเส้นทางที่มีความยาวต่างกัน บางเส้นทางอาจมี min(A, B) และมีกรณีที่เปลี่ยนเฉพาะฝั่งค่ามากสุด
      วิธีแบบ observer ธรรมดามีโอกาสทำให้ปริมาณการคำนวณพุ่งแบบเอ็กซ์โปเนนเชียล และยังอาจก่อปัญหา concurrency ได้ง่าย ไลบรารีนี้แม้โครงสร้างกราฟจะเปลี่ยนแบบไดนามิก ก็ยังใกล้เคียงที่สุดในเชิงประสิทธิภาพและถูกต้อง การใช้ observer หรืออย่างอื่นก็อาจให้ผลลัพธ์เดียวกันได้ แต่การทำให้ถูกต้องพร้อมหลีกเลี่ยงหน้าผาด้านประสิทธิภาพนั้นยากกว่ามาก

  • จุดแข็งของโปรเจกต์จาก Jane Street คือการนำไอเดียที่เคยอยู่ในงานวิจัยหรือระบบเฉพาะกลุ่มมา ห่อหุ้มให้อยู่ในรูปแบบที่นักพัฒนาใช้งานได้จริง แม้จะไม่ได้นำไลบรารีไปใช้ เอกสารออกแบบก็มักคุ้มค่าแก่การอ่าน

  • Electric Clojure ให้ การเรนเดอร์แบบเพิ่มทีละส่วนข้ามขอบเขตไคลเอนต์·เซิร์ฟเวอร์ สิ่งที่คล้ายที่สุดน่าจะเป็น SolidJS แต่ SolidJS ใช้เฉพาะฝั่งฟรอนต์เอนด์

  • เคยทำของคล้ายกันมาก่อน แต่แทบไม่พบกรณีอ้างอิงเลย พอวัตถุประสงค์การใช้งานหายไปก็ปิดโปรเจกต์ไป แต่ยังอยากกลับไปดูอีกครั้ง และยังคงอยู่บน npm ในชื่อ data-rambler
    แนวคิดคือการป้อนสตรีมข้อมูลให้กับ ภาษาเฉพาะโดเมน (DSL) ที่โหลดเข้า JavaScript runtime ได้ โมดูลจะแปลงข้อมูลเป็นสตรีมเอาต์พุตหลายรายการ แล้วส่งต่อไปยังไลบรารีรายงานแยกต่างหากเพื่อสร้างรายงานไดนามิกแบบใช้เทมเพลต
    ตั้งแต่เวอร์ชันแรกก็ค่อนข้างทรงพลังแล้ว แต่ก็เคยมีแผนใหญ่ที่จะปรับปรุงให้เป็นไวยากรณ์แบบ JavaScript มากขึ้นเพื่อลดความซับซ้อน