การสร้าง JSON Parser ประสิทธิภาพสูง

 (dave.cheney.net)
1 คะแนน โดย GN⁺ 2023-11-06 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • การบรรยาย GopherCon Singapore 2023 ของ Dave Cheney กล่าวถึงกระบวนการออกแบบการสร้าง สตรีมมิง JSON parser ใน Go โดยยังคง API ที่คล้ายกับ encoding/json แต่เพิ่ม throughput และลดการ allocate
  • JSON ไม่มีตัวบอกความยาว จึงต้องอ่านอินพุตจนจบ และขีดล่างของประสิทธิภาพอย่างน้อยคือ read(N)+parse(N) ดังนั้นข้อจำกัดหลักคือการลดการย้อนกลับไปเยี่ยมชมไบต์และโทเค็นเดิม การคัดลอก การ allocate และการเรียกฟังก์ชันใน hot path
  • encoding/json.Decoder.Token คืนค่าโทเค็นเป็น interface{} ซึ่งสะดวก แต่ค่ารูปธรรมจะ escape ไปอยู่บน heap ทำให้เกิด การ allocate ตามสัดส่วนจำนวนโทเค็น และแม้แต่โทเค็น "hello" เพียงตัวเดียวก็เกิด 3 allocs/op
  • pkg/json ลด ต้นทุน hot path ด้วย NextToken ที่คืน subslice ของ []byte จากอินพุต, sliding window ของ byteReader, การ inline ด้วยมือ, การเรียกเมธอดสถานะโดยตรง และการกำจัด bounds check
  • สุดท้าย pkg/json.Scanner สามารถ tokenize แบบไม่ allocate เมื่อมีบัฟเฟอร์ให้, Decoder.Token เร็วกว่า encoding/json.Decoder.Token 2~3 เท่า และ Decoder.NextToken ที่ allocate น้อยกว่าแสดงประสิทธิภาพเร็วกว่า 8~10 เท่า

เป้าหมายและข้อจำกัดพื้นฐาน

  • เป้าหมายคือการสร้าง JSON parser ประสิทธิภาพสูง ในฐานะกรณีศึกษาการออกแบบแพ็กเกจ Go
  • เป้าหมายการออกแบบมีสามข้อ
    • รองรับ การประมวลผลแบบสตรีมมิง ที่ไม่โหลดอินพุตทั้งหมดขึ้นหน่วยความจำ
    • ให้ throughput สูงขึ้นและ allocate น้อยลง ขณะยังเข้ากันได้อย่างสมเหตุสมผลกับ API ระดับสูง json.Decoder ของ encoding/json
    • นอกจาก API ของ encoding/json แล้ว ยังให้ API ที่มีประสิทธิภาพกว่าแบบไม่ allocate หรือมีขอบเขตจำกัด
  • หาก buffer อินพุตทั้งหมดไว้ในหน่วยความจำก่อน จะเกิดความเสี่ยงด้านความพร้อมใช้งานเมื่อไม่รู้ขนาดอินพุตหรืออินพุตไม่มีที่สิ้นสุด และยังเพิ่มเวลารอก่อนเริ่มประมวลผล
  • การอ่านแบบสตรีมมิงประมวลผลได้ทันทีเมื่อข้อมูลมาถึง และสามารถซ้อนทับการอ่านกับการประมวลผลได้

ความซับซ้อนเชิงเวลาของการ parse JSON

  • JSON ไม่มี ตัวบอกความยาว จึงต้องอ่านอินพุตทั้งหมดเพื่อให้รู้ว่าต้องอ่านเท่าไร
  • หากต้อง parse องค์ประกอบลำดับที่ 1,000 ของ JSON array ก็ต้องอ่านและประมวลผลองค์ประกอบ 999 ตัวก่อนหน้า จึงไม่สามารถข้ามการประมวลผลอินพุตได้
  • ขีดล่างของประสิทธิภาพแปรตามขนาดอินพุต และไม่ใช่แค่อ่านอย่างเดียว แต่ต้องผ่าน state machine ของ JSON เพื่อหาจุดเริ่มและจุดจบของโทเค็น จึงอย่างน้อยเป็น read(N)+parse(N)
  • เกณฑ์ในการลดต้นทุนเพิ่มเติมมีดังนี้
    • หากอ่าน N ไบต์แล้ว แต่ละไบต์ควรถูกประมวลผลเพียงครั้งเดียวเท่าที่เป็นไปได้
    • โทเค็นเดียวกันก็ควรถูกประมวลผลเพียงครั้งเดียว
    • จำกัดจำนวนการเรียกฟังก์ชันใน hot path ของ Scanner หรือ Decoder ให้เป็น O(tokens) ไม่ใช่ O(bytes)
    • ลดการคัดลอกเพื่อลดจำนวนครั้งที่ต้องกลับไปเยี่ยมชมไบต์เดิม
    • ลดการ allocate เพื่อลดต้นทุน heap allocation, การเข้าถึงโครงสร้างข้อมูลที่ใช้ร่วมกัน, lock, cache contention และ GC

การ tokenize และการออกแบบ API

  • JSON decoder แบ่งกว้าง ๆ เป็นสองขั้นตอน
    • scanner หรือ tokenizer ที่แปลง byte stream เป็น JSON token stream
    • unmarshaller ที่นำ JSON token stream ไปใช้กับอ็อบเจกต์ Go
  • encoding/json.Decoder.Token คืนค่าโทเค็นเป็น interface{}
    • สตริงแทนด้วย string, ตัวเลขด้วย float64, boolean ด้วย bool, null ด้วย nil, delimiter ด้วย json.Delim
    • วิธีนี้สะดวกต่อการใช้งาน เพราะแสดงทั้งค่าและชนิดของโทเค็นพร้อมกัน
  • ความสะดวกมีต้นทุนตามมา
    • Brad Fitzpatrick เรียก Token API ว่า garbage factory
    • ตามการออกแบบ API Decoder.Token ค่ารูปธรรมที่ allocate ให้แต่ละโทเค็นจะ escape ไปอยู่บน heap
    • จำนวนการ allocate ถูกผูกกับจำนวนโทเค็นของอินพุต
  • ใน benchmark โทเค็น "hello" เพียงตัวเดียว encoding/json แสดงผล 355ns/op, 19.7MB/s, 37.0B/op, 3.00 allocs/op
  • การออกแบบ API เป็นตัวกำหนดการ allocate และการ allocate อาจส่งผลโดยตรงต่อประสิทธิภาพ

โทเค็น []byte และข้อมูลชนิดแบบโดยนัย

  • โทเค็น JSON รู้ชนิดได้จากตัวอักษรแรกเท่านั้น
    • {, }: จุดเริ่มและจุดจบของอ็อบเจกต์
    • [, ]: จุดเริ่มและจุดจบของ array
    • t: true
    • f: false
    • n: null
    • ": สตริง
    • -, 0~9: ตัวเลข
  • API Decoder.NextToken ของ pkg/json ไม่แปลง []byte อินพุตเป็นค่า Go แต่คืนไบต์ที่แทนโทเค็นเป็น subslice จากอินพุตโดยตรง
  • ไบต์แรกของ []byte ที่คืนมาบอกชนิดของโทเค็น
  • API นี้มีข้อจำกัด
    • เอาต์พุตไม่ใช่สำเนา แต่เป็น subslice ของอินพุต จึงมีข้อจำกัดเรื่องอายุการใช้งาน
    • ลักษณะนี้คล้ายกับ API ของ bufio.Scanner
    • หากต้องการจัดการชนิดโทเค็นหรือค่าสตริง/ตัวเลขจริงให้สะดวกขึ้น ต้องมี abstraction ระดับสูงกว่า

การอ่านอย่างมีประสิทธิภาพ: byteReader

  • วิธีดั้งเดิมแบบ io.Reader.Read คัดลอก ข้อมูลจาก reader ไปยังบัฟเฟอร์ และการคัดลอกนี้เองก็มีต้นทุน
  • io.Reader.Read ปล่อยให้ผู้เรียกจัดการบัฟเฟอร์
    • หากอ่านทีละไบต์ อาจต้องมีพื้นที่เก็บไบต์ที่ผ่านมา หรือพื้นที่สำหรับย้อนกลับ
    • วิธีอ่านใส่บัฟเฟอร์ขนาดใหญ่แล้วหาจุดเริ่มและจุดจบของโทเค็น จะต้องมีงานจัดการจำนวนมาก การคัดลอก และการขยายบัฟเฟอร์เมื่อจุดจบของโทเค็นไม่ได้อยู่ในบัฟเฟอร์
  • ทางเลือกคือใช้ byteReader ซึ่งได้รับแรงบันดาลใจจาก iopipe ของ Steven Schveighoffer และแนวคิดของ Phil Pearl
  • byteReader ให้ sliding window บน io.Reader และคล้ายกับ bufio.Reader แต่มี API ที่มีประสิทธิภาพกว่า
    • window() คืนหน้าต่างข้อมูลปัจจุบันที่ยังไม่ได้อ่าน
    • release(n) ทิ้ง n ไบต์ด้านหน้าของหน้าต่าง
    • extend() อ่านข้อมูลเพิ่มจาก reader ชั้นล่างเพื่อขยายหน้าต่าง
  • benchmark การค้นหา whitespace เป็น baseline ที่เยี่ยมชมแต่ละอักขระเพื่อตรวจว่าเป็น whitespace หรือไม่ และแสดงผลประมาณ 2.04~2.07GB/s ในหลายอินพุต
  • โค้ดตัวอย่างตัวนับ whitespace อยู่ที่ github.com/davecheney/whitespace

การปรับแต่ง scanner

  • Scanner.Next ข้าม whitespace ระหว่างกลาง ตรวจชนิดโทเค็นจากอักขระตัวแรกของหน้าต่าง แล้วอ่านจนถึงจุดจบของโทเค็น
  • ประสิทธิภาพช่วงต้นของ Scanner.Next อยู่ที่ประมาณ 1/4~2/5 ของ baseline whitespace
    • เช่น Scanner/canada 510MB/s, citm_catalog 677MB/s, sample 837MB/s
  • การปรับแต่งแรกคือเปลี่ยนการอัปเดตฟิลด์ s.offset ไปใช้ตัวแปร local offset
    • s.offset เป็น 0 ตอนเข้าและออกจากฟังก์ชัน ดังนั้นการเปลี่ยนแปลงภายในจึงไม่ปรากฏต่อภายนอก
    • การใช้ตัวแปร local ทำให้คอมไพเลอร์หลีกเลี่ยงการเขียนหน่วยความจำชั่วคราวได้
    • citm_catalog ลดจาก 2.52ms เป็น 1.80ms หรือลดลง 28.46%, sample ลดจาก 828µs เป็น 528µs หรือลดลง 36.24%
  • เหตุผลที่ผลลัพธ์ต่างกันตามอินพุตคือ จำนวน whitespace แตกต่างกัน
    • canada มี whitespace เพียง 33 ตัว
    • citm มี whitespace 1,227,563 ตัว
  • การปรับแต่งที่สองคือ inline ด้วยมือ Scanner.token เข้าไปใน Scanner.Next
    • คอมไพเลอร์ Go ไม่สามารถ inline Scanner.token, parseString, parseNumber, Scanner.Next ฯลฯ โดยอัตโนมัติได้ เนื่องจาก for loop และความซับซ้อนของฟังก์ชัน
    • Scanner.Next และ Scanner.token ถูกเรียกต่อหนึ่งโทเค็นอินพุต จึงเกิดต้นทุนการเรียกฟังก์ชันสองครั้งต่อโทเค็น
  • หลัง inline ด้วยมือ throughput ดีขึ้น 9~24%
    • canada เพิ่มจาก 512MB/s เป็น 642MB/s หรือเพิ่มขึ้น 24.50%
    • citm_catalog เพิ่มจาก 960MB/s เป็น 1105MB/s หรือเพิ่มขึ้น 15.16%
    • sample เพิ่มจาก 1.33GB/s เป็น 1.46GB/s หรือเพิ่มขึ้น 9.11%
  • ผลของการปรับแต่งสรุปได้สองข้อ
    • ลดการอัปเดต s.offset จาก 1 ครั้งต่อไบต์เป็น 1 ครั้งต่อโทเค็น
    • การหลีกเลี่ยงการเรียกฟังก์ชันใน hot path อาจช่วยปรับปรุงประสิทธิภาพได้

การตรวจสอบความถูกต้องและ Decoder.NextToken

  • scanner เพียงอย่างเดียวสามารถแบ่งโทเค็นได้ แต่การประมวลผล JSON ที่สมบูรณ์ต้องมี การตรวจสอบสถานะ
  • JSON เป็น state machine และโทเค็นถัดไปที่มาได้จะถูกจำกัดตามโทเค็นปัจจุบัน
    • ตัวอย่างเช่น หลังจากอ่าน {, "username" แล้ว มีเพียง : เท่านั้นที่ถูกต้อง
  • Decoder.NextToken เพิ่ม state logic บน Scanner.Next เพื่อตรวจสอบว่าลำดับโทเค็นถูกต้องหรือไม่
  • สถานะแบ่งเป็น value, object key string, object colon, object value, object comma, array value, array comma, end state เป็นต้น
  • แม้ในการตรวจสอบความถูกต้องรุ่นแรก pkg/json ก็แสดงผลเร็วกว่า encoding/json 8~10 เท่า
    • canada: pkg/json 399MB/s, encoding/json 34.6MB/s
    • citm_catalog: pkg/json 713MB/s, encoding/json 87.1MB/s
    • sample: pkg/json 1.23GB/s, encoding/json 216MB/s

การปรับแต่ง state transition

  • แกนกลางของ Decoder.NextToken คือคำสั่ง switch
  • switch ทั่วไปอาจถูก implement เหมือนชุดคำสั่ง if ต่อเนื่อง ทำให้ branch ยาว ๆ แบ่ง instruction stream และเพิ่มภาระให้ branch predictor ของ CPU
  • มีวิธีใช้ตารางเพื่อหาเมธอดสถานะจากค่าสถานะ แต่ตัวอย่าง implementation คอมไพล์ไม่ผ่านเพราะมีลูป initialization
  • แทนที่จะทำเช่นนั้น ใช้ method expression ของ Go เพื่อเก็บเมธอดไว้ใน d.state โดยตรง แทนการเก็บค่าสถานะแบบ enum
    • Decoder.NextToken เรียกเมธอดสถานะปัจจุบันโดยตรง เช่น return d.state(d, tok)
  • วิธี computed goto นี้เพียงอย่างเดียวไม่ได้ปรับปรุงประสิทธิภาพมากนัก
    • บางอินพุตแทบไม่เปลี่ยน และใน twitter, code, example ช้าลงเล็กน้อย
    • sample เร็วขึ้น 1.15%
  • การเปลี่ยนแปลงนี้ทำให้การปรับแต่งถัดไป คือ outlining เป็นไปได้

Outlining และการกำจัด bounds check

  • หลัง outlining แล้ว Decoder.NextToken ทำเพียง return d.state(d) และเมธอดสถานะแต่ละตัวเรียก d.scanner.Next() โดยตรง
  • เนื่องจากไม่ส่ง tok เป็นอาร์กิวเมนต์ให้เมธอดสถานะ จึงลด call stack ได้ 3 words
  • เมื่อการตรวจ len(tok) < 1 และ switch tok[0] อยู่ในฟังก์ชันเดียวกัน จึงสามารถ กำจัด bounds check ได้
    • ก่อนหน้านี้การตรวจ len(tok) อยู่ใน Decoder.NextToken และเมธอดสถานะถูกเรียกผ่าน method expression จึงไม่ถูก inline
    • ดังนั้น tok[0] ในเมธอดสถานะจึงยังต้องมี bounds check
    • เมื่อทำการตรวจความยาวในฟังก์ชันเดียวกัน คอมไพเลอร์สามารถพิสูจน์ได้ว่า tok มีความยาวอย่างน้อย 1
  • Decoder.NextToken เองก็เรียบง่ายขึ้นจน inline ได้
    • ผู้เรียกเห็นแทบจะเป็นการเรียกเมธอดสถานะปัจจุบันโดยตรง แทน dec.NextToken()
    • ต้นทุนการเรียกฟังก์ชันจึงถูกกำจัด

ผล benchmark สุดท้าย

  • pkg/json.Scanner ชั้นล่างสุดทำ streaming tokenization แบบไม่ allocate ได้เมื่อมีบัฟเฟอร์ไม่กี่ KB ให้
    • canada: 638.78MB/s, 0 B/op, 0 allocs/op
    • citm_catalog: 1110.51MB/s, 0 B/op, 0 allocs/op
    • sample: 1471.01MB/s, 0 B/op, 0 allocs/op
  • pkg/json.Decoder.Token เร็วกว่า encoding/json.Decoder.Token 2~3 เท่า
    • canada: 101.98MB/s vs 33.19MB/s
    • citm_catalog: 333.23MB/s vs 82.71MB/s
    • sample: 788.59MB/s vs 209.12MB/s
  • pkg/json.Decoder.NextToken allocate น้อยกว่ามากและเร็วกว่า 8~10 เท่า
    • canada: 466.52MB/s, 136 B/op, 3 allocs/op vs 34.42MB/s, 17,740,399 B/op, 889,106 allocs/op
    • citm_catalog: 798.58MB/s, 136 B/op, 3 allocs/op vs 86.08MB/s, 5,661,597 B/op, 324,692 allocs/op
    • sample: 1346.85MB/s, 1144 B/op, 9 allocs/op vs 217.44MB/s, 723,781 B/op, 26,095 allocs/op
  • ที่ API ระดับสูงสุด pkg/json สามารถ unmarshal เป็นอ็อบเจกต์ Go ได้ในลักษณะเดียวกับ encoding/json
    • canada: 82.08MB/s vs 58.70MB/s
    • citm_catalog: 215.66MB/s vs 104.00MB/s
    • sample: 615.99MB/s vs 128.04MB/s
  • ลิงก์การบรรยายอยู่ที่ dave.cheney.net/paste/gophercon-sg-2023.html, โค้ดอยู่ที่ github.com/pkg/json

ประเด็นที่ได้จากการออกแบบ

  • การ allocate ส่งผลต่อประสิทธิภาพ

    • แม้ GC จะ allocate ได้เร็วและเก็บกวาดได้มีประสิทธิภาพ แต่การไม่ allocate ย่อมเร็วกว่าเสมอ
    • การออกแบบ API สามารถทำให้ไม่ต้อง allocate ได้
    • ความเร็วที่เพิ่มขึ้นส่วนใหญ่ของแพ็กเกจนี้มาจากการลดการ allocate
    • เวลาที่ไม่ถูกใช้ไปกับเส้นทาง heap allocation และรอบ GC ถูกนำไปใช้กับการ scan
    • API encoding/json.Decoder ต้อง allocate เพราะคืนค่า primitive เป็น interface{}
    • ค่า escape ไปอยู่บน heap และโดยพฤตินัยกลายเป็น pointer ไปยังค่านั้น
    • ในการประมวลผลข้อมูล การ allocate อาจเป็นต้นทุนประสิทธิภาพที่ใหญ่ที่สุดของอัลกอริทึม
    • การลดต้นทุนต่อไบต์และต่อโทเค็นอย่างระมัดระวังเป็นปัจจัยใหญ่อันดับสองของการปรับปรุงประสิทธิภาพ
    • ทิศทางสำคัญคือเปลี่ยนการเรียกฟังก์ชันต่อไบต์ให้เป็นการเรียกฟังก์ชันต่อโทเค็น
    • เริ่มจากสมมติฐานว่า encoding/json อาจช้ากว่าเพราะ API และหากยอมรับ API แบบอื่นได้ ก็สามารถได้ประสิทธิภาพเพิ่มขึ้น 2~3 เท่าในบางเส้นทาง unmarshal และ 8~10 เท่าในการ tokenize

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

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

 
GN⁺ 2023-11-06
ความคิดเห็นจาก Hacker News

  • ดูดีทีเดียว ตลอดเส้นทางอาชีพ ผมทำ JSON parser มามากเกินไปแล้ว แต่การมีเอกสารอ้างอิงที่แสดงทีละขั้นว่าควรออกแบบ JSON parser ที่สมเหตุสมผลและรวดเร็วอย่างไรนี่ดีมากจริง ๆ
    อย่างไรก็ดี JSON ไม่จำเป็นต้องมี tokenizer แยกชัดเจน แนวคิดเรื่อง token สามารถตัดออก แล้วรวมการ parse กับการ tokenize เข้าด้วยกันทั้งหมดได้ ปกติก็ทำกันแบบนี้ และโดยรวมจะเรียบง่ายกว่า
    ในภาษาอย่าง ECMAScript จะยากกว่ามาก เพราะมีกรณีที่ตอนแรกดูเหมือนเป็น subset ของไวยากรณ์นิพจน์ในวงเล็บ เช่น arrow function แล้วค่อยตัดสินได้เมื่อเห็น => ทำให้อาจต้องมองล่วงหน้าได้ยาวแบบไม่จำกัด

    • อยากรู้จริง ๆ ว่าต้องทำงานแบบไหนถึงพูดได้ว่า “ทำ JSON parser มามากเกินไป” ตลอดอาชีพ

  • เป็นบทความที่อ่านตามได้ดี และวาง flow ชัดว่าถ้าจะ implement เองควรทำแบบนี้
    ถ้าใน production ต้องการ performance ล้วน ๆ ก็น่าดู https://github.com/simdjson/simdjson ของ Daniel Lemire ด้วย มี Go port ของ MinIO ที่ https://github.com/minio/simdjson-go เช่นกัน

    • ถ้ารูปแบบ JSON เหมือนเดิมเสมอ ก็อาจทำได้ดีกว่า JSON parser แบบทั่วไป
    • ก่อนหน้านี้ตอนเปรียบเทียบ performance ของ JSON parser หลายตัว parser ที่ใช้ SIMD ช้าจนน่าผิดหวังกว่าที่คาด
    • ไลบรารี JSON ที่เร็วที่สุดใน Go มาจาก บริษัทที่อยู่เบื้องหลัง TikTok
    • simdjson ไม่ได้ครองตำแหน่งเร็วที่สุดมานานมากแล้ว

  • สิ่งที่ได้เรียนรู้จากการทำ JSON parser ที่เร็ว ๆ คือมันปนรายละเอียดเฉพาะของแต่ละภาษาอยู่มาก แต่ถ้าสรุปให้ทั่วไปคือแบบนี้
    ในขั้น tokenize ควรหลีกเลี่ยง heap allocation tokenizer ควรคืน struct ที่ allocate บน stack หรือทำเป็นฟังก์ชันที่คืน token แบบ int64 ซึ่ง pack ตำแหน่งเริ่มต้น ความยาว และ type offset ของ token ไว้
    ในขั้น parse ก็ควรหลีกเลี่ยง heap allocation เช่นกัน และอาจรองรับ interface อย่าง getString(key String) สำหรับ client ที่ต้องการ slice จาก buffer มาใช้
    ตอน deserialize เป็น object ที่รู้ field ได้ตั้งแต่ compile time โดยปกติจะ generate switch ตามความยาวของ key ก่อนจะเปรียบเทียบค่า string
    ใน data pipeline ที่ประมวลผล JSON จำนวนมาก แค่เลือก JSON library ก็ทำให้ performance ต่างกันได้ 3~10 เท่า และ parser หลัก ๆ ส่วนใหญ่มักพยายาม allocate object
    ถ้า class ที่จะ serialize/deserialize รู้ได้ตั้งแต่ compile time Java Jackson ก็ทำได้ค่อนข้างดี แต่ด้วยการเขียนโค้ดอย่างระมัดระวังและ profiling ก็สามารถรีดเพิ่มได้อีกราว 2 เท่า
    ในทางกลับกัน ถ้าต้องประมวลผล JSON ใด ๆ parser กระแสหลักมักจะ allocate เยอะ ดังนั้น parser ที่เขียนเองและ intrusive กว่าสามารถหลีกเลี่ยงสิ่งนี้ได้ และเมื่อประมวลผลวัตถุตั้งแต่หลายพันถึงหลายล้านรายการต่อวินาที ผลได้ด้าน performance จะใหญ่มาก

  • ผมทำ GraphQL tokenizer และ parser ด้วยแนวทางคล้ายกัน และอันนี้ก็ไม่มี memory allocation แถมเร็วพอสมควร ถ้าสนใจโค้ดดูได้ที่ https://github.com/wundergraph/graphql-go-tools

    • งานประหลาดของผมก็น่าดูเหมือนกัน: https://github.com/graph-guard/gqlscan
      เคยพูดในหัวข้อนี้ด้วย แต่น่าเสียดายที่ไม่ได้อัดวิดีโอไว้ พยายามรีด Go ให้ได้มากที่สุดจนแทบจะเสียสติ :D
    • สำหรับ GQL server แบบ allowlist-based ที่รู้ query ทั้งหมดไว้ล่วงหน้า อยากรู้ว่านี่เป็นปัญหาใหญ่แค่ไหน เพราะสามารถ cache หรือจดจำผลการ parse AST ไว้ได้ น่าจะเป็นปัญหา performance แค่ไม่กี่นาทีหลัง container เริ่มทำงานหรือเปล่า
      หรือมันมีผลกระทบในทางอื่นด้วยหรือไม่

  • ใน n2[1] ต้องการ tokenizer ที่เร็ว และเจอปัญหา ตัวสร้างขยะ แบบเดียวกัน โดยพื้นฐานคือปัญหาที่มีชุด token คงที่อย่าง json.Delim ปนกับ string ที่ก่อให้เกิด allocation
    วิธีแก้ที่ผมคิดว่าค่อนข้างดีคือทำ tokenizer ให้เป็น generic สำหรับ T ใด ๆ แล้วรับฟังก์ชันที่แปลง byte slice เป็น T จากนั้นใช้ T แทน string
    แบบนี้ caller สามารถส่ง representation ที่มีประสิทธิภาพกว่า เช่น representation ที่ allocation น้อยกว่า เข้ามาได้ และในขณะเดียวกันในการ unit test ก็ใช้ identity function เพื่อทดสอบ tokenizer ได้สะดวก
    ในความหมายหนึ่ง มันคล้ายกับการ fuse tokenizer กับ parser ตอน build time แต่ด้วย generic ทำให้ tokenizer ไม่ต้องรู้ representation ของ parser ก็ยังรักษาการแบ่งชั้นไว้ได้
    [1] https://github.com/evmar/n2

  • การปรับปรุงเหนือ standard library ด้วย การออกแบบ API ที่ดีกว่านั้นเป็นไปได้ แต่การทำ parser แบบ streaming เต็มรูปแบบโดยไม่เติม struct ไปครึ่งหนึ่งแล้วออกกลางคันก่อนจะพบ error นั้นแทบจะยากในทางปฏิบัติ ดูเหมือน standard library กำหนดเรื่องนี้ไว้เป็นข้อจำกัดเชิงออกแบบอย่างชัดเจนด้วย

  • ผมอาจพลาดอะไรไป แต่ผู้เขียนพูดซ้ำ ๆ ว่าสร้าง parser แบบ “streaming” โดยไม่ได้อธิบายว่ามันหมายถึงอะไรจริง ๆ
    โดยเฉพาะในส่วน “hash table” ไม่มีคำอธิบายว่าจัดการ key ซ้ำอย่างไร อยากรู้ว่าถ้าเจอ key ซ้ำจะเรียก sink code สองครั้ง หรือรอจนอ่าน “hash table” ทั้งหมดเสร็จก่อนแล้วค่อยเรียก sink code
    ในความเห็นผม JSON เป็นโครงสร้างแบบลำดับชั้น ไม่รู้ความยาวล่วงหน้า และที่สำคัญที่สุดคือมี key ซ้ำ จึงไม่เหมาะกับ streaming โดยธรรมชาติ
    อาจทำ subset บางส่วนของ JSON ให้เป็นมิตรกับ streaming มากขึ้นได้ แต่ถ้าจะทำอย่างนั้นก็ไม่มีเหตุผลต้องไปแก้ JSON ถ้าทางแก้คือการเปลี่ยน JSON ผมคิดว่าใช้ format อื่นที่ไม่ใช่ JSON ไปเลยดีกว่า

  • ดีใจที่มีการกล่าวถึง Phil Pearl
    https://github.com/bytedance/sonic ก็น่าดูเช่นกัน

  • น่าแปลกที่ไม่มีวิธีบอกว่า “ให้ inline ฟังก์ชันนี้จริง ๆ” สำหรับฟังก์ชันที่ใหญ่เกินไปจนไม่ได้ inline
    งานพื้นฐานอย่างการนับ/ค้นหา whitespace น่าจะเร็วขึ้นมากถ้า vectorize ด้วย SIMD แต่ก็เข้าใจว่าอยู่นอกขอบเขตของผู้เขียน

    • แน่นอนว่า force inline ได้

  • ประโยคที่ว่า “การคาดหวังว่าจะเก็บ input ทั้งหมดไว้ใน memory ได้เป็นเรื่องไม่สมจริง” นั้นผิดสำหรับแอปพลิเคชันส่วนใหญ่

    • แอปพลิเคชันส่วนใหญ่อ่าน JSON จากเครือข่าย และนั่นคือ stream แม้ JSON จะค่อนข้างเล็ก แต่ถ้า buffer request ทั้งหมดไว้ใน memory แล้วค่อยจัดการ จะเพิ่ม latency อย่างมาก
    • ถูก แต่สำหรับแอปพลิเคชันที่ต้องทำ การแปลงแบบ ETL กับ dataset ขนาดใหญ่ streaming เป็นกลยุทธ์ที่มีประโยชน์มหาศาล
      อาจบอกได้ว่า Go ไม่ใช่เครื่องมือที่เหมาะกับงานนั้น แต่ถ้า optimize แบบนี้ ผมก็ไม่เห็นเหตุผลว่าทำไมจะทำไม่ได้
    • ถ้าทำ library ก็ต้องระบุข้อจำกัดให้ชัดเจน หรือไม่ก็รองรับ streaming
      ผมเคยยัดข้อมูล JSON ระดับกิกะไบต์เข้าไป ดังนั้น streaming parser จึงน่าขอบคุณมาก แถมการรองรับ streaming ยังเป็นสัญญาณว่าผู้เขียนรู้ use case หลายแบบและทำ engineering ได้ดีกว่า
      memory นั้นถูกและเกือบฟรีเฉพาะในทฤษฎี แต่ในโลกจริงไม่ใช่แบบนั้น
    • ถ้าพอใจกับระดับว่า “ใส่ลงดิสก์ได้” mmap() ก็เป็นตัวเลือกได้ไม่ใช่หรือ กรณีที่ต้องการ streaming จริง ๆ เช่นต้องประมวลผลข้อมูลช่วงต้นให้เร็วจากไฟล์ JSON เดี่ยว เหมือน stream ของธุรกรรมหรืองาน นั่นเป็นอีกเรื่อง
    • HTTP request body ถือเป็นส่วนหนึ่งของ input ด้วยหรือเปล่า?