เหตุผลที่ฟอร์ก rand เพื่อสร้าง API สุ่มที่เล็กกว่าและสม่ำเสมอกว่า

 (casualhacks.net)
1 คะแนน โดย GN⁺ 2 시간 전 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • rand ซึ่งเป็น crate สุ่มหลักของ Rust มีการกระจายโอเปอเรชันที่ใช้บ่อยไว้ตาม trait หลายตัว จึงพัฒนา urandom ขึ้นมาให้มี public/implementation surface ที่เล็กกว่าและประสบการณ์ใช้งานที่สม่ำเสมอกว่า
  • รวบรวมโอเปอเรชันระดับสูงไว้ในโครงสร้าง Random ตัวเดียว และซีล trait Rng เพื่อให้ความสำคัญกับ การค้นหา API ได้ง่าย และการปรับแต่งภายใน มากกว่าการรองรับตัวสร้างสุ่มแบบใดก็ได้
  • โดยไม่ได้นำอัลกอริทึมสุ่มใหม่มาใช้ แต่เลือกฟังก์ชันเอาต์พุตของ Xoshiro256 ตามการใช้งาน ทำให้ในการทดสอบสร้าง f64 จำนวน 1,000 ค่า มี throughput สูงกว่า rand 0.10.2 ราว 31%
  • การสุ่มจำนวนเต็มแบบสม่ำเสมอถูกรวมเส้นทาง reuse/one-shot ด้วย implementation แบบไม่ลำเอียง เพียงชุดเดียวที่คำนวณ threshold แบบ lazy และในการทดสอบช่วง 500..20_000 ก็เร็วกว่าสองเส้นทางของ rand
  • เอาต์พุตดิบจาก seed แบบชัดเจนรองรับการทำซ้ำได้ข้ามสถาปัตยกรรมที่รองรับและรีลีสที่เข้ากันได้ตาม SemVer แต่ต้องแลกกับการ เสียความสามารถเชื่อมต่อกับตัวสร้างสุ่มใดก็ได้ และ ecosystem ด้าน distribution/third-party integration ขนาดใหญ่ของ rand

API Random ที่รวมไว้เป็นหนึ่งเดียว

  • โอเปอเรชันที่มีประโยชน์ของ rand กระจายอยู่ตาม trait หลายตัว
    • การสุ่มค่าในช่วงต้องใช้ RngExt, การเลือกจากลำดับต้องใช้ IndexedRandom, การสับต้องใช้ SliceRandom
    • rand 0.10 มี helper ระดับรากอย่าง rand::random_range สำหรับการเรียกแบบครั้งเดียว
    • แต่ถ้าต้องการเก็บ RNG handle หรือใช้โอเปอเรชันกับลำดับอย่างการเลือก/สับ ก็ยังต้องหาเมธอดตาม trait หลายตัวอยู่ดี
  • แม้จะลด import ด้วย prelude ก็ยังต้องรู้ว่า extension method ใช้กับ type ไหนระหว่าง RNG, slice หรือ iterator จึงหาได้ไม่ง่ายจาก IDE autocomplete อย่างเดียว
  • urandom วาง consumer API ระดับสูงไว้ใน โครงสร้าง wrapper Random ตัวเดียว
    • สร้าง Random<urandom::rng::Xoshiro256Rng> ได้ด้วย urandom::new()
    • เรียก uniform, choose, shuffle ได้จากออบเจ็กต์เดียวกัน
    • ดู random, uniform, chance, choose, shuffle, sample และอื่น ๆ ได้จาก autocomplete
    • ทั้งหมดเป็นเมธอดเฉพาะตัว จึงไม่ต้องหาหรือ import high-level extension trait

Rng แบบซีลที่เลือกการปรับแต่งแทน extensibility

  • rand มอง low-level RNG trait เป็น public extension point แต่ใน urandom นั้น trait Rng ถูกซีล เพื่อให้เลือกและ implement ตัวสร้างที่รองรับจากภายใน crate
    • ไม่สามารถนำตัวสร้างสุ่มใด ๆ มาต่อเข้ากับ Random ได้
    • หากจะเพิ่มตัวสร้างใหม่ ต้องแก้ urandom เอง
  • หากเป้าหมายคืออัลกอริทึมที่ดีกว่า ตอนนี้ Xoshiro256 และ ChaCha ก็เป็นตัวเลือกตั้งต้นที่ใช้กันอยู่แล้วตามบทบาท และคำแนะนำก็เปลี่ยนช้า
    • หากมีตัวเลือกที่ดีกว่า ก็สามารถนำมาใช้ใน major release ถัดไปได้
  • หากต้องการให้เข้ากันได้กับโปรเจ็กต์อื่น ภาษาโปรแกรมอื่น อัลกอริทึมแบบ legacy ฮาร์ดแวร์เฉพาะทาง หรือตัวสร้างสำหรับงาน simulation โดยเฉพาะ การใช้ตัวสร้างเดียวกันอย่างเดียวไม่พอ
    • ต้องใช้อัลกอริทึมที่เกี่ยวข้องอย่างการสุ่มแบบสม่ำเสมอและการสับให้เหมือนกันด้วย จึงเหมาะกว่าที่จะมี implementation เฉพาะซึ่งทำสัญญาทั้งชุดนั้น
  • ด้วย trait แบบซีล จึงสามารถเพิ่มโอเปอเรชันดิบที่ urandom ต้องใช้ได้โดยไม่ต้องออกแบบหรือเขียนเอกสารสัญญาการ implement สำหรับตัวสร้างที่ไม่รู้จักและกรณียกเว้นต่าง ๆ
    • สามารถจับคู่ตัวสร้างกับอัลกอริทึมให้เหมาะกันเพื่อทำ specialization บางอย่างได้ ซึ่ง rand ทำไม่ได้
  • สำหรับแอปส่วนใหญ่ การเลือก entropy มีประโยชน์กว่าการเพิ่ม implementation PRNG ใหม่
    • ตัวสร้างแต่ละตัวเปิดคอนสตรักเตอร์ from_seed แบบเนทีฟไว้
    • สร้าง Random ที่ใช้ seed แบบชัดเจนได้ เช่น ChaCha12Rng::from_seed(seed)
    • แม้จะไม่รับ implementation RNG ใดก็ได้ แต่ก็ยังคง extension point ที่คาดว่าผู้ใช้ขั้นสูงจะต้องการไว้

ประสิทธิภาพที่ดีขึ้นจากอัลกอริทึมชุดเดิม

  • urandom ไม่ได้ใช้อัลกอริทึมสร้างเลขสุ่มแบบใหม่
    • สำหรับงานที่ไม่เกี่ยวกับคริปโตบนระบบ 64 บิต urandom::new() และ rand::rngs::SmallRng ใช้ตระกูล Xoshiro256 เดียวกัน
    • สำหรับงานด้านคริปโต urandom::csprng() และ rand::rngs::StdRng ใช้ ChaCha12
    • ตัวสร้างภายในของ convenience function rand::rng() ก็เป็น ChaCha12 เช่นกัน
  • อินเทอร์เฟซของตัวสร้างใน rand ให้ทั้ง integer word และการเติมไบต์ ดังนั้น distribution ที่ต้องการ f64 ก็ยังต้องขอจาก u64 เต็มคำก่อน
  • urandom::Rng ไม่ได้มีแค่ next_u32, next_u64 แต่ยังมี next_f32 และ next_f64 ด้วย
    • เลขสุ่มแบบ floating-point ต้องใช้บิตสุ่มน้อยกว่า word เต็ม
    • ตัวสร้างสามารถ override เมธอดเหล่านี้ด้วยเส้นทางเอาต์พุตที่ต้นทุนต่ำกว่าได้
  • implementation ของ Xoshiro แยกเส้นทางเอาต์พุตโดยใช้ state transition ร่วมกัน
    • สำหรับ u64 ยังคงใช้ Xoshiro256++
    • สำหรับ u32 และ floating-point ใช้ Xoshiro256+ ที่เร็วกว่า โดยบิตบนถูกออกแบบมาให้เหมาะกับงานประเภทนี้
  • ผลไมโครบेंช์มาร์กที่สร้างเลขสุ่ม 1,000 ค่า ด้วย urandom 1.0 และ rand 0.10.2 มีดังนี้
    • Xoshiro u64: ทั้งสองฝั่ง 814ns
    • Xoshiro u32: rand 836ns, urandom 788ns
    • Xoshiro f64: rand 1,033ns, urandom 788ns
    • ChaCha12 f64: rand 2,199ns, urandom 2,011ns
  • throughput แบบ end-to-end ของ Xoshiro f64 สูงขึ้นราว 31% และใช้เวลารันสั้นลง 24% แต่เส้นทาง u64 ที่ทำงานเดียวกันแทบไม่ต่างกัน
  • ChaCha12 ไม่ได้ override next_f64 จึงมีประสิทธิภาพใกล้เคียงกันโดยรวม
  • เวลาแน่นอนอาจต่างกันตามเครื่องและคอมไพเลอร์ และดูเงื่อนไขเพิ่มเติมได้ใน บันทึกเบนช์มาร์กฉบับเต็ม

เส้นทางการสุ่มแบบสม่ำเสมอที่รวมเป็นหนึ่งเดียว

  • หากสุ่มจำนวนเต็มด้วยการหาเศษจากความยาวช่วงตรง ๆ จะเกิด อคติ ดังนั้นการสุ่มจำนวนเต็มแบบสม่ำเสมอที่ถูกต้องต้องปฏิเสธผลลัพธ์บางส่วนจากเอาต์พุตของตัวสร้าง
  • การคำนวณ rejection threshold ที่ถูกต้องต้องใช้การหาเศษซึ่งมีต้นทุนสูง
    • ถ้าใช้ sampler ซ้ำหลายครั้ง ก็ยอมรับต้นทุนตอนตั้งค่าเริ่มต้นได้
    • แต่ถ้าสร้างค่าเดียว ต้นทุนนี้จะสูงเมื่อเทียบกัน
  • rand เปิดเผยความต่างนี้ผ่าน trait UniformSampler
    • UniformInt ที่สร้างไว้จะคำนวณ threshold ล่วงหน้าเพื่อสุ่มแบบไม่ลำเอียง
    • Rng::random_range ใช้ hook sample_single หรือ sample_single_inclusive แยกต่างหากเพื่อเลี่ยงค่าใช้จ่ายตอนตั้งค่า
    • ในฟีเจอร์พื้นฐาน เส้นทางลัดแบบครั้งเดียวใช้อัลกอริทึมตัวที่สองที่มีอคติเล็กน้อย
    • ฟีเจอร์เสริม unbiased จะเปลี่ยนเป็นเวอร์ชันวนซ้ำที่ซับซ้อนกว่า
  • urandom คำนวณ threshold แบบ lazy และใช้ implementation คูณ-ปฏิเสธแบบไม่ลำเอียงเพียงชุดเดียว ทั้งสำหรับช่วงที่ใช้ซ้ำและช่วงแบบครั้งเดียว
    • ใช้วิธีที่อธิบายไว้ในงานปี 2018 ของ Daniel Lemire Fast Random Integer Generation in an Interval
    • สำหรับช่วงที่ใช้จริงส่วนใหญ่ candidate แรกจะถูกส่งคืนก่อนถึงขั้นหาร
    • หาก candidate แรกใช้ไม่ได้ จึงค่อยคำนวณ threshold ที่ถูกต้องแล้ววนซ้ำแบบไม่ลำเอียง
    • รองรับกรณียกเว้น range == 0 ที่หมายถึงขอทั้งช่วงเต็มด้วย
  • จัดการทั้ง distribution แบบใช้ซ้ำและช่วงแบบครั้งเดียวด้วย implementation เดียวกัน โดยไม่ต้องมีเมธอดแยก อัลกอริทึมตัวที่สอง ค่าใช้จ่ายตั้งต้น หรือ fast path ที่มีอคติ
  • ผลเบนช์มาร์กการสุ่ม 1,000 ค่าในช่วง 500..20_000 มีดังนี้
    • UniformInt แบบใช้ซ้ำ: rand 1,098ns, urandom 950ns
    • ช่วงแบบครั้งเดียว: rand 1,079ns, urandom 942ns
  • ผลของ rand อ้างอิงจากฟีเจอร์พื้นฐาน ดังนั้นแถว one-shot ที่เร็วกว่าเล็กน้อยยังเป็นเส้นทางที่มีอคติเล็กน้อย ขณะที่ urandom เร็วกว่าทั้งสองเส้นทางในสภาพไม่ลำเอียง

การทำซ้ำได้ข้ามรีลีสและสถาปัตยกรรม

  • urandom ถือว่า การทำซ้ำได้ เป็นส่วนหนึ่งของสัญญาสาธารณะ
    • หากใช้ seed แบบชัดเจนเดียวกันและลำดับการเรียก low-level RNG เหมือนกัน เอาต์พุตดิบของตัวสร้างแบบกำหนดได้จะคงเดิม
    • รับประกันความเสถียรข้ามสถาปัตยกรรมที่รองรับและรีลีสที่เข้ากันได้ตาม SemVer
    • เซิร์ฟเวอร์ 64 บิตและไคลเอนต์ WebAssembly 32 บิตสามารถใช้ฐานตัวสร้างเดียวกันเพื่อการ replay ได้
  • เพื่อรักษาความเข้ากันได้นี้ จึงยอมแลกประสิทธิภาพบนสถาปัตยกรรม 32 บิต
  • เป็นการรับประกันที่แรงกว่า นโยบายการทำซ้ำได้ของ rand
    • ตัวสร้างและอัลกอริทึมการสุ่มแบบพกพาได้ของ rand อาจให้เอาต์พุตต่างกันใน minor release
    • SmallRng และ StdRng ก็ไม่ได้พกพาได้โดยชัดแจ้ง และอาจเปลี่ยนไปตามแพลตฟอร์มหรือรีลีสของไลบรารีด้วย

ต้นทุนของทางเลือกและเกณฑ์การนำไปใช้

  • urandom รวบรวมโอเปอเรชันทั่วไปไว้ใน Random เพื่อให้ค้นหาได้ง่ายโดยไม่ต้องพึ่ง extension trait
  • ออกแบบตัวสร้างและ distribution ร่วมกันเพื่อทำเส้นทางเอาต์พุต Xoshiro ที่เบากว่า และเส้นทางสุ่มแบบสม่ำเสมอที่ไม่ลำเอียงเพียงชุดเดียว
  • สตรีมดิบที่เสถียรจากตัวสร้างที่กำหนด seed แบบชัดเจนสามารถใช้กับ เกมและการจำลองแบบกำหนดได้
  • แต่ก็ไม่สามารถนำตัวสร้างสุ่มใดก็ได้มาใช้ และไม่มีทั้งรายการ distribution ที่ใหญ่กว่าและ ecosystem การเชื่อมต่อ third-party แบบที่ rand มี
  • หากต้องการ ecosystem ที่กว้าง rand เหมาะกว่า แต่หากชอบ API surface ที่เล็กกว่า การค้นหาที่ง่าย การปรับแต่งแบบบูรณาการ และนโยบายการทำซ้ำได้ที่เข้มแข็งกว่า ก็สามารถเลือก urandom ได้
  • ดูแพ็กเกจได้ที่ crates.io, เอกสาร API, และ ซอร์สบน GitHub

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

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

 
GN⁺ 2 시간 전
ความคิดเห็นบน Lobste.rs

  • มีเหตุผลมากพอที่จะฟอร์ก rand แต่ ชื่อ urandom ฟังดูเหมือนเป็นไลบรารีที่เกี่ยวข้องกับ /dev/urandom

    • ดูเหมือนมีประโยชน์ แต่ชื่ออาจทำให้สับสนได้ ถ้าดูแค่ชื่อโดยไม่ได้อ่านบทความ ก็คงคิดว่า พึ่งพาไฟล์ I/O และคงไม่เข้าไปดู

  • เห็นด้วยกับประเด็นปัญหา แต่ไม่ค่อยชอบ pub fn new() -> Random<impl Rng + Clone>
    ถ้าทำให้ทั้งแอปพลิเคชันเป็นพารามิเตอร์ด้วย Random<T> where T: Rng จะเพิ่มงานจุกจิก และทำให้ปัญหาเรื่อง เวลา compile กับ dyn หนักขึ้นมาก สู้ให้ struct Random มีชนิดข้อมูลแบบเจาะจงไปเลย หรืออย่างรองก็เลือก struct Random<T = rng::Xoshiro256Rng> ดีกว่า

  • เพราะความอึดอัดคล้าย ๆ กัน เคยลองทำเองแล้วเหมือนกัน แต่ไม่ใช่ฟอร์ก และ มีฟีเจอร์น้อยกว่า rand มาก

  • ดีใจที่มีคนที่รู้สึกถึงปัญหาแบบเดียวกับฉันลงมือแก้จริง ๆ ดูเหมือนว่า Rust จะมีแนวโน้มแปลก ๆ ที่ทำให้คนสร้างไลบรารีแบบ trait soup
    ชนิดข้อมูลหลักของฐานข้อมูลที่ใช้ในงานต้อง implement trait อย่างน้อย 15 ตัว ทำให้ autocomplete เละเทะและเอกสารก็สับสน แม้จะลดจำนวน trait ลงไปบ้างแล้ว แต่ก็มักติดปัญหา dependency แบบวนรอบ หรือทำให้เขียนเทสต์หลักไม่ได้

    • นี่เป็นปรากฏการณ์ที่ architecture astronauts จากสาย Java นำสไตล์ object-oriented แบบเดิมมาใช้กับ Rust dependency แบบวนรอบเป็นสัญญาณว่าเราไปฝืนแยกสิ่งเดียวที่ยังแยกไม่ได้ออกจากกัน หรือแยกวัตถุสามอย่างออกจากกันไม่ถูกต้อง ถ้าควบคุมโค้ดทั้งหมดได้ ก็ใช้ enum แทน trait ได้
    • ใน ecosystem ด้าน cryptography ของ Rust ปัญหา trait soup รุนแรงเป็นพิเศษจนแทบคลั่ง

  • ไลบรารีนี้ทำให้นึกถึงทั้ง deep interface ของ APOSD และงานด้าน cryptography ของ Filippo ที่ออกแบบให้ทำพลาดได้ยาก ซึ่งทั้งสองอย่างเป็นคำชมอย่างมาก

    • แต่ urandom::new() ไม่ได้คืนค่า ตัวสร้างเลขสุ่มที่ปลอดภัยเชิง cryptography ดังนั้นจึงยังไม่ใช่การออกแบบที่พลาดไม่ได้จริง ๆ โดยเฉพาะอย่างยิ่ง /dev/urandom บน Linux นั้นปลอดภัย จึงยิ่งทำให้สับสน

  • อีกทางเลือกหนึ่งแทน rand คือ fastrand ซึ่งเป็นตัวสร้างเลขสุ่มที่เรียบง่ายและเร็ว เรียบง่ายกว่า rand และ urandom แต่ก็มีฟีเจอร์น้อยกว่าด้วย