buddy allocator workshop
1.0.0
ที่เก็บนี้มีการใช้งานตัวอย่างเล็ก ๆ น้อย ๆ ของการจัดสรรเพื่อน พวกเขาได้รับการออกแบบมาเพื่อจัดสรรหน่วยความจำทางกายภาพแม้ว่าพวกเขาจะสามารถใช้สำหรับการจัดสรรประเภทอื่น ๆ เช่นกอง ในที่สุดการแสดงที่ดีที่สุดจะถูกรวมเข้ากับดอกไม้
ก่อนอื่นโคลน repo จากนั้น cd ลงไปและทำ cargo +nightly run เพื่อเรียกใช้การจัดสรรตัวอย่างทั้งหมด โดยค่าเริ่มต้นขนาดบล็อกคือ 4Kib และจำนวนบล็อกคือ 100,000 ดังนั้นอาจใช้เวลาสักครู่สำหรับตัวอย่างรายการที่เชื่อมโยง ไม่ต้องกังวลมันจะไม่จัดสรรอะไรเลย - เฉพาะบล็อกหน่วยความจำจำลอง ผ่าน -h หรือ --help เพื่อขอความช่วยเหลือและดูการใช้งาน คุณสามารถแก้ไขซอร์สโค้ดเพื่อเปลี่ยนขนาดบล็อกขั้นต่ำ/สูงสุด ฯลฯ เพื่อเรียกใช้การทดสอบหน่วยเรียกใช้ cargo test น่าเสียดายที่ยังไม่มีเกณฑ์มาตรฐานการขนส่งสินค้า แต่ฉันได้เปรียบเทียบมันค่อนข้างไม่ได้อยู่ในเครื่อง Windows ของฉัน
ฉันทดสอบอัลกอริทึมโดยกำหนดเวลาการใช้งานที่หลากหลายโดยใช้การรายงานในตัวโดยจัดสรร gibibyte ในบล็อก 4Kib (พร้อมการพิมพ์) บนเครื่อง Windows ของฉัน หากคุณมีเกณฑ์มาตรฐานอื่น ๆ ที่จะเพิ่มโปรดดูการสนับสนุน
(MSI CX61-2QF)
| การดำเนินการ | เวลา | ปริมาณงาน |
|---|---|---|
| รายการ - เวกเตอร์ | 2 นาที | ~ 8.33E-3 GIB/S |
| รายการ - รายการที่เชื่อมโยงเป็นสองเท่า | 25 นาที | ~ 6.66E-4 GIB/S |
| ต้น RB - เวกเตอร์ | ~ 0.3s | ~ 3.33 gib/s |
| RB Trees - รายการที่เชื่อมโยงกันเดี่ยว | ~ 0.5s | ~ 2 gib/s |
| ต้นบิตแมป | ~ 0.07s | ~ 14.28 GIB/S |
หมายเหตุ: ปริมาณงานถูกคาดการณ์ตั้งแต่เวลาที่ใช้ในการจัดสรร 1 GIB ในบล็อก 4Kib สำหรับการใช้งานที่มีความซับซ้อน> o (log n) (เช่นการใช้งานตามรายการไร้เดียงสา) สิ่งนี้จะไม่ถูกต้อง - ปริมาณงานจะช้าลงเมื่อมีการจัดสรรบล็อกมากขึ้น สิ่งนี้น่าจะถูกต้องสำหรับคนที่มีความซับซ้อนของ O (log n) หรือน้อยกว่า
การใช้งานนี้ช่วยให้รายการต่อลำดับของบล็อก มันเป็นเรื่องทั่วไปมากกว่ารายการประเภทที่ใช้ ฉันตัดสินใจใช้รายการสองประเภท: เวกเตอร์ ( Vec จาก std ) และรายการที่เชื่อมโยงเป็นสองเท่า ( LinkedList , จาก std ) รายการที่เชื่อมโยงมักจะได้รับผลตอบแทนสำหรับเวลาผลักดันที่คาดการณ์ได้ (ไม่จำเป็นต้องจัดสรรใหม่สำหรับการผลัก) ในขณะที่เวกเตอร์มีพื้นที่แคชที่ดีกว่าเนื่องจากองค์ประกอบถูกจัดสรรในบล็อกหน่วยความจำที่ต่อเนื่องกัน ฉันใช้รายการที่เชื่อมโยงเป็นสองเท่าเนื่องจากเร็วกว่าสำหรับการจัดทำดัชนีกว่ารายการที่เชื่อมโยงกันอย่างเดี่ยวเนื่องจากพวกเขาสามารถวนซ้ำจากด้านหลังหรือด้านหน้าขึ้นอยู่กับว่าดัชนีอยู่ใกล้กับจุดเริ่มต้นหรือจุดสิ้นสุดของรายการ ฉันตัดสินใจที่จะทดสอบทั้งสองเพื่อดูว่าจะทำงานได้ดีกว่าโดยรวม
การดำเนินการเป็นแบบเรียกซ้ำ ในการจัดสรรบล็อกการสั่งซื้อฟรี K ให้ค้นหาบล็อกฟรีใด ๆ ในรายการคำสั่งซื้อบล็อก K ไม่เก็บรายการฟรี หากไม่พบพบมันจะเกิดขึ้นอีกครั้งโดยพยายามจัดสรรบล็อกของคำสั่ง K + 1 ในที่สุดถ้าไม่มีจุดใดบล็อกใด ๆ ที่พบว่ามันยอมแพ้และตื่นตระหนก ทันทีที่มันแยกออกเป็นครึ่งหนึ่งถอดบล็อกดั้งเดิมออกจากรายการคำสั่งซื้อและผลักดันครึ่งหนึ่งไปยังรายการคำสั่งซื้อลดลงทันที จากนั้นจะส่งคืนคำสั่งซื้อและดัชนีของบล็อกแรกในรายการคำสั่งซื้อ คุณสามารถค้นหาอัลกอริทึมนี้ได้ใน find_or_split
เกณฑ์มาตรฐานที่รวดเร็วและไม่เป็นวิทยาศาสตร์บนเครื่อง Windows ของฉันบอกว่าใช้เวลาประมาณสองนาทีในการจัดสรร Gibibyte เต็มรูปแบบ (1024^3 ไบต์) ฉันสังเกตเห็นการหยุดครั้งที่สองแยกเป็นครั้งที่สองเป็นครั้งคราวเมื่อต้องจัดสรรเวกเตอร์ทั้งหมดใหม่เพื่อผลักดันองค์ประกอบ
stdเกณฑ์มาตรฐานที่คล้ายกันบอกว่าใช้เวลา ยี่สิบห้า นาทีในการจัดสรร Gibibyte เต็มรูปแบบ นี่ ช้ากว่าการใช้งานแบบเดียวกันกับเวกเตอร์มากกว่าสิบสองเท่า อย่างไรก็ตามการใช้งานนี้ไม่ได้รับการปรับให้เหมาะสมสำหรับรายการที่เชื่อมโยงดังนั้นจึงไม่ยุติธรรมเล็กน้อย ซึ่งแตกต่างจากการใช้งานกับเวกเตอร์ฉันไม่ได้สังเกตเห็นการหยุดชั่วคราว แต่การจัดสรรค่อยๆช้าลงและช้าลง
เราสามารถสรุปได้ว่าแม้ว่ารายการที่เชื่อมโยงกันสองเท่า ในทางทฤษฎี จะเร็วกว่าการผลักดันมากกว่าเวกเตอร์ แต่ก็ยังช้ากว่าเวกเตอร์ 12 เท่า อาจเป็นเพราะการใช้งานเป็นที่โปรดปรานของเวกเตอร์เล็กน้อย (การจัดทำดัชนีจำนวนมาก) หรือเนื่องจากเวกเตอร์มีพื้นที่แคชที่สูงขึ้นและดังนั้นจึงมีการพลาดแคชน้อยลงในขณะที่รายการที่เชื่อมโยงนั้นมีประสบการณ์แคชสูง
การใช้งานนี้จะช่วยให้ต้นไม้สีแดงดำหนึ่งต้น (จาก intrusive_collections ) สำหรับบล็อกทั้งหมดและรายการฟรีสำหรับแต่ละคำสั่งซื้อ รายการฟรีถูกนำไปใช้สำหรับ Vec ของ STD และ SinglyLinkedList ของ intrusive_collections ฉันเลือกรายการที่เชื่อมโยงกันอย่างเดี่ยวเพราะจะไม่มีประโยชน์จริงในการเชื่อมโยงสองครั้ง - วิธีเดียวที่จะได้รับประโยชน์ (โดยประมาท) คือ FreeList::remove แต่สิ่งนี้เรียกว่ามากที่สุดในองค์ประกอบที่สองในรายการฟรีนี้ดังนั้นจึงไม่มีจุดที่แท้จริงในการเพิ่มประสิทธิภาพสิ่งนี้ ต้นไม้สีแดงดำเป็นรายบุคคลจะจัดสรรแต่ละโหนดซึ่งทำให้ประสิทธิภาพแคชแย่ลง แต่ไม่เหมือนกับ BTreeSet / BTreeMap ของ std การค้นหาของมันคือ O(log n) ในขณะที่ std ใช้การค้นหาเชิงเส้นซึ่งไม่ใช่ O(log n) (คุณสามารถอ่านได้ที่นี่) อย่างไรก็ตามต้นไม้ของ std ไม่ได้จัดสรรโหนดเป็นรายบุคคลดังนั้นพื้นที่แคชจึงดีกว่า ฉันตัดสินใจว่าถึงแม้ว่านี่จะเป็นจริงเนื่องจากผู้จัดสรรเพื่อนต้องจัดการกับบล็อกจำนวนมากอย่างไม่น่าเชื่อ แต่มันสำคัญกว่าที่จะต้องมีอัลกอริทึมการค้นหาที่มีประสิทธิภาพมากขึ้น
การดำเนินการเป็นแบบเรียกซ้ำ ในการจัดสรรบล็อกฟรีของการสั่งซื้อ K ให้ค้นหาบล็อกฟรีใด ๆ ในรายการฟรีรายการสั่งซื้อบล็อก K หากไม่พบพบมันจะเกิดขึ้นอีกครั้งโดยพยายามจัดสรรบล็อกของคำสั่ง K + 1 ในที่สุดถ้าไม่มีจุดใดบล็อกใด ๆ ที่พบว่ามันยอมแพ้และตื่นตระหนก ทันทีที่มันแยกออกเป็นครึ่งหนึ่งถอดบล็อกดั้งเดิมออกจากต้นไม้และแทรกครึ่งหนึ่งผลักที่อยู่ของพวกเขาไปยังรายการฟรีที่เกี่ยวข้อง จากนั้นจะส่งคืนเคอร์เซอร์ที่ชี้ไปที่บล็อกแรก คุณสามารถค้นหาอัลกอริทึมนี้ได้ใน find_or_split ที่ชั้นนอกสุดของการเรียกซ้ำ (ฟังก์ชั่นที่เรียกใช้ฟังก์ชัน find_or_split แบบเรียกซ้ำจริง) บล็อกที่ส่งคืนจะถูกทำเครื่องหมายตามที่ใช้และลบออกจากรายการฟรี
การใช้เวกเตอร์เป็นรายการฟรีใช้เวลา ~ 0.3s ในการจัดสรร GIB เต็มรูปแบบ นี่คือ ~ 0.2s เร็วกว่ารายการที่เชื่อมโยงเป็นเวอร์ชันรายการฟรี นี่อาจเป็นเพราะเวกเตอร์ที่มีพื้นที่แคชที่ดีกว่า
การใช้รายการที่เชื่อมโยงเป็นรายการฟรีใช้เวลา ~ 0.5s ในการจัดสรร GIB เต็มรูปแบบ ดูส่วนของเวกเตอร์เป็นรายการฟรีด้านบน
การใช้งานนี้ เร็วกว่าการใช้งานที่ไร้เดียงสา 400x (อย่างดีที่สุดโดยใช้เวกเตอร์เป็นรายการฟรี) นี่อาจเป็นเพราะต้นไม้สีแดงดำที่มีการดำเนินการ O(log n) ทั่วกระดานเร็วกว่าการค้นหาแทรกและลบเวกเตอร์หรือรายการที่เชื่อมโยง
การใช้งานนี้ไม่ได้เป็นบิตแมปอย่างเคร่งครัด แต่เป็นการปรับเปลี่ยนระบบบิตแมป โดยพื้นฐานแล้วแต่ละบล็อกในต้นไม้จะเก็บคำสั่งซื้อที่ใหญ่ที่สุด (รวมเข้าด้วยกัน) ที่ไหนสักแห่งที่ อยู่ข้างใต้ ตัวอย่างเช่นต้นไม้ที่ฟรีทั้งหมดมี 4 คำสั่งซื้อเช่นนี้:
3
2 2
1 1 1 1
0 0 0 0 0 0 0 0
หากเราจัดสรรหนึ่งคำสั่ง 0 บล็อกดูเหมือนว่า (t คือ t aken):
2
1 2
0 1 1 1
T 0 0 0 0 0 0 0
มันถูกนำไปใช้เป็นอาร์เรย์แบบแบนซึ่งเป็นต้นไม้ที่ชอบ
1
2 3
การเป็นตัวแทนคือ 1; 2; 3 . สิ่งนี้มีคุณสมบัติที่ดีที่ถ้าเราใช้ดัชนีเริ่มต้นที่ 1 (เช่นดัชนีและไม่ใช่ออฟเซ็ต) จากนั้นดัชนีของลูกซ้ายของดัชนีใด ๆ ที่กำหนดคือ 2 * index และเด็กที่เหมาะสมคือเพียง 2 * index + 1 ผู้ปกครองคือ floor(index / 2) เนื่องจากการดำเนินการทั้งหมดเหล่านี้ทำงานกับ 2s เราสามารถใช้ bitshifting ที่มีประสิทธิภาพเพื่อดำเนินการ ( index << 1 , (index << 1) | 1 และ index >> 1 )
เราสามารถทำการค้นหาแบบไบนารีเพื่อค้นหาบล็อก A ที่ไม่มีคำสั่งซื้อที่ต้องการ ก่อนอื่นเราตรวจสอบว่ามีบล็อกใด ๆ ของคำสั่งซื้อที่ต้องการฟรีโดยตรวจสอบบล็อกรูทหรือไม่ หากมีเราตรวจสอบว่าเด็กซ้ายมีฟรีเพียงพอหรือไม่ ถ้าเป็นเช่นนั้นเราก็ตรวจสอบอีกครั้งว่าเป็นลูกที่เหลือ ฯลฯ หากลูกซ้ายของบล็อกไม่มีบล็อกฟรีเพียงพอเราก็ใช้ลูกที่เหมาะสม เรารู้ว่าเด็กที่เหมาะสมจะต้องมีฟรีเพียงพอหรือบล็อกรูทไม่ถูกต้อง
การใช้งานนี้ เร็วมาก ในคอมพิวเตอร์ของฉันใช้เวลา ~ 0.07s ในการจัดสรร 1GIB เท่านั้น ฉันเห็นว่ามันทำงานได้มากถึง 0.04s บนคอมพิวเตอร์ของฉันแม้ว่าประสิทธิภาพจะผันผวนเล็กน้อย ฉันคิดว่านี่คือการโหลด CPU
การใช้งานนี้ไม่ได้มีพื้นที่แคชที่ดีมากเนื่องจากระดับจะถูกเก็บไว้ไกลจากแต่ละคนดังนั้นบล็อกหลักอาจอยู่ไกลจากลูกของมัน อย่างไรก็ตามทุกสิ่งทุกอย่างยังคงเร็วมากดังนั้นจึงถูกสร้างขึ้นมา นอกจากนี้ยังเป็น o (log n) แต่ในทางปฏิบัติแล้วมันเร็วมากจนไม่สำคัญ สำหรับการอ้างอิง: การจัดสรร 8GIB ใช้เวลา 0.6s สำหรับฉัน แต่ฉันได้เห็นว่ามันทำงานได้ดีขึ้นมากที่> 150ms บนแล็ปท็อปของ @Gegy1000
หากคุณมีสิ่งใดที่จะเพิ่ม (เช่นการแก้ไขไปยัง readme หรือการใช้งานหรือเกณฑ์มาตรฐานอื่น) อย่าลังเลที่จะส่งคำขอดึง! คุณยังสามารถสร้างปัญหาได้ หากคุณแค่ต้องการแชทอย่าลังเลที่จะ ping me on the Rust Discord (Restioson#8323)
