หน้าแรก>การเขียนโปรแกรมที่เกี่ยวข้อง>ซี/ซี++
ดาวน์โหลด

ซีเนียม

xenium เป็นไลบรารีส่วนหัวเท่านั้นที่ให้คอลเลกชันของโครงสร้างข้อมูลที่เกิดขึ้นพร้อมกันและอัลกอริธึมการเรียกคืนหน่วยความจำ โครงสร้างข้อมูลได้รับการกำหนดพารามิเตอร์เพื่อให้สามารถใช้กับแผนการบุกเบิกต่างๆ ได้ (คล้ายกับวิธีที่ STL อนุญาตให้ปรับแต่งตัวจัดสรร)

  • ส่วนหัวเท่านั้น
  • ปรับแต่งได้สูง
  • ไม่จำเป็นต้องมีรหัสเริ่มต้น
  • รองรับจำนวนเธรดแบบไดนามิก (ไม่มีข้อกำหนดเวลาคอมไพล์คงที่)

เอกสารประกอบให้รายละเอียดเพิ่มเติม

โครงการนี้อิงจากงานก่อนหน้าของฉันใน https://github.com/mpoeter/emr

ตัวอย่างการใช้งาน 

# include < xenium/ramalhete_queue.hpp >
# include < xenium/reclamation/epoch_based.hpp >

struct msg { ... };

xenium::ramalhete_queue<
  std::unique_ptr<msg>,
  xenium::policy::reclaimer<xenium::reclamation::epoch_based<>>,
  xenium::policy::entries_per_node< 2048 >
> queue;

queue.push(std::make_unique<msg>());

std::unique_ptr<msg> data;
if (queue.try_pop(data)) {
    // do something with data
}

โครงสร้างข้อมูล

ในขณะนี้ จำนวนโครงสร้างข้อมูลที่ให้ไว้ค่อนข้างน้อย เนื่องจากจนถึงขณะนี้มุ่งเน้นไปที่แผนการบุกเบิก อย่างไรก็ตาม มีแผนจะเพิ่มโครงสร้างข้อมูลอีกหลายรายการในอนาคตอันใกล้นี้

  • michael_scott_queue - คิวผู้ผลิตหลายราย/ผู้บริโภคหลายรายที่ไม่มีการล็อคแบบไม่มีขอบเขต เสนอโดย Michael และ Scott [MS96]
  • ramalhete_queue - คิว multi-producer/multi-consumer ที่รวดเร็วไร้ขอบเขตที่เสนอโดย Ramalhete [Ram16]
  • vyukov_bounded_queue - คิว FIFO ของผู้ผลิตหลายราย/ผู้บริโภคหลายรายที่มีขอบเขตตามเวอร์ชันที่เสนอโดย Vyukov [Vyu10 ]
  • kirsch_kfifo_queue - คิว k-FIFO ของผู้ผลิตหลายราย/ผู้บริโภคหลายรายที่ไม่มีขอบเขต เสนอโดย Kirsch และคณะ [KLP13].
  • kirsch_bounded_kfifo_queue - คิว k-FIFO ของผู้ผลิตหลายราย/ผู้บริโภคหลายรายแบบมีขอบเขตที่เสนอโดย Kirsch และคณะ [KLP13].
  • nikolaev_queue - คิวผู้ผลิตหลายราย/ผู้บริโภคหลายรายที่ไม่มีขอบเขต เสนอโดย Nikolaev [Nik19]
  • nikolaev_bounded_queue - คิวที่มีผู้ผลิตหลายราย/ผู้บริโภคหลายรายแบบมีขอบเขตที่เสนอโดย Nikolaev [Nik19]
  • harris_michael_list_based_set - คอนเทนเนอร์ที่ไม่มีการล็อคซึ่งมีชุดวัตถุที่ไม่ซ้ำกันที่เรียงลำดับแล้ว โครงสร้างข้อมูลนี้อิงตามโซลูชันที่เสนอโดย Michael [Mic02] ซึ่งต่อยอดจากข้อเสนอดั้งเดิมโดย Harris [Har01]
  • harris_michael_hash_map - แผนที่แฮชที่ไม่มีการล็อคตามโซลูชันที่เสนอโดย Michael [Mic02] ซึ่งต่อยอดจากข้อเสนอดั้งเดิมโดย Harris [Har01]
  • chase_work_stealing_deque - งานขโมย deque ตามข้อเสนอของ Chase และ Lev [CL05]
  • vyukov_hash_map - แฮชแมปที่เกิดขึ้นพร้อมกันซึ่งใช้การล็อคแบบละเอียดสำหรับการดำเนินการอัปเดต การใช้งานนี้ได้รับแรงบันดาลใจอย่างมากจากเวอร์ชันที่เสนอโดย Vyukov [Vyu08]
  • left_right - การใช้งานทั่วไปของอัลกอริทึม LeftRight ที่เสนอโดย Ramalhete และ Correia [RC15]
  • seqlock - การใช้งานการล็อกลำดับ (หรือมักเรียกว่า "การล็อกตามลำดับ")

แผนการบุกเบิก

การดำเนินการตามแผนการบุกเบิกจะขึ้นอยู่กับเวอร์ชันที่ดัดแปลงของอินเทอร์เฟซที่เสนอโดย Robison [Rob13]

มีการนำแผนการบุกเบิกต่อไปนี้ไปใช้:

  • lock_free_ref_count [Val95, MS95]
  • hazard_pointer [Mic04]
  • hazard_eras [RC17]
  • quiescent_state_based
  • generic_epoch_based - นี่คือการเรียกคืนตามยุคทั่วไปที่สามารถกำหนดค่าได้หลายวิธี เพื่อความง่าย จึงมีการกำหนดนามแฝงต่อไปนี้ไว้ล่วงหน้าสำหรับการกำหนดค่าที่เกี่ยวข้อง
    • epoch_based [Fra04]
    • new_epoch_based [HMBW07]
    • debra [Bro15]
  • stamp_it [PT18a, PT18b]

อาคาร

xenium เป็นไลบรารีส่วนหัวเท่านั้น ดังนั้นเพื่อใช้งาน ก็เพียงพอแล้วที่จะรวมโฟลเดอร์ xenium ไว้ในรายการไดเร็กทอรีรวมของคุณ ไม่จำเป็นต้องมีไลบรารีของบุคคลที่สามอื่น ๆ อย่างไรก็ตาม การใช้งานนั้นใช้คุณสมบัติ C++17 ดังนั้นจึงจำเป็นต้องมีคอมไพลเลอร์ที่รองรับ C++17 ที่เพียงพอ คอมไพเลอร์ต่อไปนี้ถูกใช้ใน CI build และด้วยเหตุนี้จึงทราบว่าได้รับการสนับสนุน:

  • gcc9
  • เสียงดังกราว10
  • วิชวลสตูดิโอ 2019

การทดสอบหน่วยต้องใช้ googletest และการวัดประสิทธิภาพต้องใช้ taocpp/json และ taocpp/config การขึ้นต่อกันเหล่านี้รวมอยู่ในโมดูลย่อย ดังนั้นการทดสอบหน่วยและ/หรือเกณฑ์มาตรฐานจึงสามารถสร้างได้ดังนี้: 

 git clone https://github.com/mpoeter/xenium.git && cd xenium
git submodule update --init --recursive
mkdir build && cd build
cmake ..
make gtest
make benchmark

อ้างอิง

[Bro15] เทรเวอร์ อเล็กซานเดอร์ บราวน์. การเรียกคืนหน่วยความจำสำหรับโครงสร้างข้อมูลที่ไม่มีการล็อค: จะต้องมีวิธีที่ดีกว่านี้ ใน Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC) หน้า 261–270 พลอากาศเอก, 2558.
[CL05] เดวิด เชส และ ยอสซี เลฟ deque ขโมยงานแบบวงกลมแบบไดนามิก ใน การดำเนินการของการประชุม ACM Symposium ประจำปีครั้งที่ 17 เรื่องความเท่าเทียมในอัลกอริทึมและสถาปัตยกรรม (SPAA) หน้า 21–28 พลอากาศเอก, 2548.
[ฟรา04] เคียร์ เฟรเซอร์. เสรีภาพในการล็อคในทางปฏิบัติ วิทยานิพนธ์ระดับปริญญาเอก ห้องปฏิบัติการคอมพิวเตอร์แห่งมหาวิทยาลัยเคมบริดจ์, 2547
[ฮาร์01] ทิโมธี แอล. แฮร์ริส. การใช้งานจริงของรายการเชื่อมโยงที่ไม่ปิดกั้น ใน รายงานการประชุมนานาชาติเรื่องคอมพิวเตอร์แบบกระจาย (DISC) ครั้งที่ 15 หน้า 300–314 สปริงเกอร์-แวร์แลก, 2544.
[HMBW07] โธมัส อี. ฮาร์ต, พอล อี. แม็คเคนนีย์, แองเจลา เดมเก้ บราวน์ และโจนาธาน วอลโพล ประสิทธิภาพของการเรียกคืนหน่วยความจำสำหรับการซิงโครไนซ์แบบไม่มีล็อค วารสารคอมพิวเตอร์แบบขนานและแบบกระจาย, 67(12):1270–1285, 2007.
[KLP13] คริสตอฟ เคิร์สช์, ไมเคิล ลิปเพาทซ์ และฮันเนส พาเยอร์ คิว k-FIFO ที่รวดเร็วและปรับขนาดได้ ไม่มีการล็อค ใน การดำเนินการประชุมนานาชาติเรื่องเทคโนโลยีคอมพิวเตอร์แบบขนาน (PaCT) หน้า 208–223, Springer-Verlag, 2013
[ไมค์02] มาเก็ด เอ็ม. ไมเคิล. ตารางแฮชที่ไม่มีการล็อคไดนามิกประสิทธิภาพสูงและชุดตามรายการ ใน การดำเนินการของการประชุม ACM Symposium ประจำปีครั้งที่ 14 เกี่ยวกับอัลกอริทึมและสถาปัตยกรรมแบบขนาน (SPAA) หน้า 73–82 พลอากาศเอก, 2545.
[ไมค์04] มาเก็ด เอ็ม. ไมเคิล. ตัวชี้อันตราย: เรียกคืนหน่วยความจำที่ปลอดภัยสำหรับวัตถุที่ไม่มีการล็อค ธุรกรรม IEEE บนระบบขนานและแบบกระจาย 15(6):491–504, 2004
[MS95] Maged M. Michael และ Michael L. Scott การแก้ไขวิธีการจัดการหน่วยความจำสำหรับโครงสร้างข้อมูลที่ไม่มีการล็อค รายงานทางเทคนิค มหาวิทยาลัย Rochester, 1995
[MS96] Maged M. Michael และ Michael L. Scott ง่าย รวดเร็ว และใช้งานได้จริงโดยไม่ปิดกั้นและปิดกั้นอัลกอริธึมคิวที่ทำงานพร้อมกัน ใน รายงานการประชุม ACM Symposium ประจำปีครั้งที่ 15 เรื่องหลักการคอมพิวเตอร์แบบกระจาย (PODC) หน้า 267–275 พลอากาศเอก, 1996.
[นิค19] Ruslan Nikolaev คิว fifo ที่ไม่มีการล็อคที่ปรับขนาดได้ พกพาสะดวก และมีประสิทธิภาพ ใน การประชุมวิชาการนานาชาติเรื่องคอมพิวเตอร์แบบกระจาย (DISC) ครั้งที่ 33 ปี 2019
[PT18a] มานูเอล โปเตอร์ และเจสเปอร์ ลาร์สสัน แทรฟฟ์ ประกาศโดยย่อ: Stamp-it ซึ่งเป็นรูปแบบการเรียกคืนหน่วยความจำที่ทำงานพร้อมกันและมีประสิทธิภาพมากขึ้นในรูปแบบหน่วยความจำ C ++ ใน การดำเนินการของการประชุม ACM Symposium ประจำปีครั้งที่ 30 เรื่องความเท่าเทียมในอัลกอริทึมและสถาปัตยกรรม (SPAA) หน้า 355–358 พลอากาศเอก, 2018.
[PT18b] มานูเอล โปเตอร์ และเจสเปอร์ ลาร์สสัน แทรฟฟ์ Stamp-it ซึ่งเป็นรูปแบบการเรียกคืนหน่วยความจำพร้อมกันที่มีประสิทธิภาพมากกว่าเธรดในโมเดลหน่วยความจำ C++ รายงานทางเทคนิค ปี 2561
[ราม16] เปโดร รามาลเฮเต้. FAAArrayQueue - คิวที่ไม่มีการล็อค MPMC (ตอนที่ 4 จาก 4) บล็อก พฤศจิกายน 2559
[RC15] เปโดร รามาลเฮเต และอันเดรีย คอร์เรอา ซ้าย-ขวา - เทคนิคการควบคุมการทำงานพร้อมกันพร้อมการอ่านแบบลืมเลือนของประชากรโดยไม่ต้องรอ ตุลาคม 2558
[RC17] เปโดร รามาลเฮเต และอันเดรีย คอร์เรอา ประกาศโดยย่อ: ยุคอันตราย - การฟื้นฟูหน่วยความจำแบบไม่ปิดกั้น ใน การดำเนินการของการประชุม ACM Symposium ประจำปีครั้งที่ 29 เรื่องความเท่าเทียมในอัลกอริทึมและสถาปัตยกรรม (SPAA) หน้า 367–369 พลอากาศเอก, 2017.
[ร็อบ13] อาร์ช ดี. โรบิสัน การออกแบบตามนโยบายเพื่อการทำลายอย่างปลอดภัยในคอนเทนเนอร์ที่เกิดขึ้นพร้อมกัน เอกสารคณะกรรมการมาตรฐาน C++ ปี 2013
[วาล95] จอห์น ดี. วาลัวส์. โครงสร้างข้อมูลที่ไม่มีการล็อค วิทยานิพนธ์ระดับปริญญาเอก สถาบันสารพัดช่าง Rensselaer, 2538
[วียู08] มิทรี วยูคอฟ แผนที่แฮชที่ปรับขนาดได้ การโพสต์ของ Google Groups, 2008
[Vyu10] มิทรี วยูคอฟ คิว MPMC ที่มีขอบเขตเรียบง่ายและมีประสิทธิภาพ การโพสต์ของ Google Groups, 2010
ขยาย
ข้อมูลเพิ่มเติม
แอปที่เกี่ยวข้อง
แนะนำสำหรับคุณ
ข้อมูลที่เกี่ยวข้อง ทั้งหมด