ฉันจะจัดระเบียบสมาชิกในโครงสร้างให้เปลืองพื้นที่น้อยที่สุดในการจัดตำแหน่งได้อย่างไร

[ไม่ซ้ำกับ การขยายและการบรรจุโครงสร้าง คำถามนั้นเกี่ยวกับวิธีการและเวลาที่ช่องว่างภายในจะเกิดขึ้น อันนี้เกี่ยวกับวิธีการจัดการกับมัน]

ฉันเพิ่งรู้ว่าหน่วยความจำสิ้นเปลืองไปเท่าใดอันเป็นผลมาจากการจัดตำแหน่งใน C ++ ลองพิจารณาตัวอย่างง่ายๆ ต่อไปนี้:

struct X
{
    int a;
    double b;
    int c;
};

int main()
{
    cout << "sizeof(int) = "                      << sizeof(int)                      << '\n';
    cout << "sizeof(double) = "                   << sizeof(double)                   << '\n';
    cout << "2 * sizeof(int) + sizeof(double) = " << 2 * sizeof(int) + sizeof(double) << '\n';
    cout << "but sizeof(X) = "                    << sizeof(X)                        << '\n';
}

เมื่อใช้ g++ โปรแกรมจะให้ผลลัพธ์ดังต่อไปนี้:

sizeof(int) = 4
sizeof(double) = 8
2 * sizeof(int) + sizeof(double) = 16
but sizeof(X) = 24

นั่นคือค่าใช้จ่ายหน่วยความจำ 50%! ในอาเรย์ขนาด 3 กิกะไบต์ขนาด 134'217'728 Xs 1 กิกะไบต์จะเป็นการเติมเต็มอย่างแท้จริง

โชคดีที่วิธีแก้ปัญหานั้นง่ายมาก - เราเพียงแค่ต้องสลับ double b และ int c รอบ:

struct X
{
    int a;
    int c;
    double b;
};

ตอนนี้ผลลัพธ์น่าพึงพอใจมากขึ้น:

sizeof(int) = 4
sizeof(double) = 8
2 * sizeof(int) + sizeof(double) = 16
but sizeof(X) = 16

อย่างไรก็ตาม มีปัญหา: สิ่งนี้เข้ากันไม่ได้ ใช่ ภายใต้ g++ int คือ 4 ไบต์และ double คือ 8 ไบต์ แต่นั่นไม่จำเป็นต้องเป็นจริงเสมอไป (การจัดตำแหน่งไม่จำเป็นต้องเหมือนกัน) ดังนั้นภายใต้สภาพแวดล้อมที่แตกต่างกัน การแก้ไขนี้ไม่เพียงแต่จะไร้ประโยชน์เท่านั้น แต่ มันอาจทำให้สิ่งต่าง ๆ แย่ลงด้วยการเพิ่มจำนวนช่องว่างภายในที่จำเป็น

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

ชี้แจง

เนื่องจากความเข้าใจผิดและความสับสน ฉันขอเน้นย้ำว่า ฉันไม่ต้องการแพ็ค struct ของฉัน นั่นคือฉันไม่ต้องการให้สมาชิกไม่อยู่ในแนวเดียวกันและทำให้เข้าถึงได้ช้ากว่า แต่ฉันยังคงต้องการให้สมาชิกทุกคนปรับตัวได้ด้วยตนเอง แต่ในลักษณะที่ใช้หน่วยความจำน้อยที่สุดในการเสริม ซึ่งสามารถแก้ไขได้โดยใช้ เช่น การจัดเรียงใหม่ด้วยตนเองตามที่อธิบายไว้ที่นี่และใน ศิลปะที่สูญหายของการบรรจุ โดย เอริค เรย์มอนด์ ฉันกำลังมองหาวิธีอัตโนมัติและข้ามแพลตฟอร์มมากที่สุดเท่าที่จะเป็นไปได้ในการทำเช่นนี้ ซึ่งคล้ายกับที่อธิบายไว้ใน ข้อเสนอ P1112 สำหรับมาตรฐาน C++20 ที่กำลังจะมาถึง


c++ optimization struct-member-alignment memory-alignment memory-layout
person Community    schedule 25.06.2019    source แหล่งที่มา
comment
หากคุณต้องการอาร์เรย์ที่มีองค์ประกอบหลายร้อยล้านรายการ บางทีอาร์เรย์อาจไม่ใช่โครงสร้างข้อมูลที่ถูกต้องตั้งแต่แรกเลย อย่างน้อยก็ไม่ใช่อาร์เรย์ในหน่วยความจำ (ลองนึกถึงไฟล์ที่แมปหน่วยความจำหรืออาจเป็นฐานข้อมูลบางประเภท)   -  person Some programmer dude    schedule 25.06.2019
comment
และจริงๆ แล้ว คำตอบเดียวที่เป็นไปได้สำหรับคำถาม [i] มีวิธีข้ามแพลตฟอร์มที่เชื่อถือได้ในการแก้ปัญหานี้ (ลดจำนวนช่องว่างภายในที่ต้องการให้เหลือน้อยที่สุดโดยไม่ต้องทนทุกข์กับประสิทธิภาพที่ลดลงที่เกิดจากการวางแนวที่ไม่ตรง) อาจเป็นเพียงแค่ไม่ธรรมดาเท่านั้น อาจมีวิธีแก้ไขเฉพาะของคอมไพเลอร์และระบบ แต่ไม่มีอุปกรณ์พกพาหรือคอมไพเลอร์/แพลตฟอร์ม/ระบบที่ไม่เชื่อเรื่องพระเจ้า   -  person Some programmer dude    schedule 25.06.2019
comment
อาจเป็นประโยชน์บางประการในการพกพาจากการใช้ จำนวนเต็มความกว้างคงที่ จึงไม่เปลี่ยนแปลง ขนาดกับคุณ   -  person user4581301    schedule 25.06.2019
comment
และเกี่ยวกับ [w]hy คอมไพเลอร์ไม่ทำการเพิ่มประสิทธิภาพดังกล่าว (สลับสมาชิกโครงสร้าง / คลาสไปรอบ ๆ เพื่อลดช่องว่างภายใน) คอมไพเลอร์จะทำอย่างนั้นได้อย่างไรในเมื่อไม่สามารถบอกได้ว่าโครงสร้างนั้นใช้ทำอะไร? บางทีมันอาจถูกจัดเก็บไว้ในไฟล์ไบนารี่หรือส่งผ่านโปรโตคอลการสื่อสารแบบอนุกรม (ซึ่งในกรณีนี้โครงสร้างที่คลายการแพ็ก (ด้วยตนเองหรือโดยคอมไพเลอร์ pragma) เป็นความคิดที่ไม่ดีจริงๆ แต่มันก็ยังคงเกิดขึ้น)   -  person Some programmer dude    schedule 25.06.2019
comment
ข้อกำหนดการจัดตำแหน่งที่ใหญ่ที่สุด อันดับแรก หากไม่มี แสดงว่าเป็นสมาชิกที่ใหญ่ที่สุดอันดับแรก สำหรับคำถาม จริง ของคุณ ใช่ มีวิธีการที่เข้ากันได้ข้ามกันในการทำเช่นนี้ เรียกว่า string นอกเหนือจากนั้น ประเภทที่ใช้ความกว้างบิตที่ระบุสามารถช่วยได้มาก แต่ยังต้องมีการจัดการแบบ endian หากคุณจริงๆ จริงจังกับข้ามแพลตฟอร์ม กล่าวโดยย่อ โปรโตคอล มีอยู่โดยเฉพาะเพื่อแก้ไขปัญหาดังกล่าวและเชื่อมความแตกต่างที่สำคัญระหว่างแพลตฟอร์ม สิ่งเหล่านี้เป็นหนึ่งใน หลายประการ ว่าทำไมจึงมีอยู่ ข้อแม้: โอกาสที่ดีที่ฉันเข้าใจผิดโดยสิ้นเชิงเกี่ยวกับคำถามนี้   -  person WhozCraig    schedule 25.06.2019
comment
สุดท้ายนี้ รู้สึกเหมือนเป็นปัญหา XY สำหรับฉันมาก การจัดเรียงโครงสร้างใหม่เป็นวิธีการแก้ปัญหา แต่อะไรคือปัญหา ของจริง ที่อยู่เบื้องหลังการแก้ปัญหานี้ คุณ จริงๆ พยายามทำอะไรให้สำเร็จ? ทำไมคุณถึงต้องการอาร์เรย์นับล้านโครงสร้าง? บางทีอาจมีวิธีแก้ปัญหาอื่นที่เป็นไปได้สำหรับปัญหาดั้งเดิมนั้น ปัญหาที่ไม่เกี่ยวข้องกับอาร์เรย์หรือซึ่งทำให้การเติมที่เป็นไปได้ไม่เกี่ยวข้อง   -  person Some programmer dude    schedule 25.06.2019
comment
ด้วยเหตุผลทั้งหมดข้างต้น ไม่มีสิ่งใดที่รับประกันพื้นที่จัดเก็บขั้นต่ำสำหรับขนาดโครงสร้าง แต่ @WhozCraig ให้คำอธิบายที่แม่นยำของกฎที่เรียบง่ายเกินไป ใหญ่ที่สุดก่อนเล็กที่สุดสุดท้าย ในการลดลำดับของขนาดพื้นที่จัดเก็บที่ต้องการ . นั่นเป็นแนวทางที่สมเหตุสมผลซึ่งมีแนวโน้มที่จะลดพื้นที่เก็บข้อมูลระหว่างคอมไพเลอร์และฮาร์ดแวร์ให้เหลือน้อยที่สุด แต่ไม่มีการรับประกันใด ๆ สองโครงสร้างจะได้รับการจัดสรรพื้นที่เก็บข้อมูลจำนวนเท่ากันระหว่างคอมไพเลอร์ (นอกเหนือจากตัวอย่างเล็กน้อย (เช่น struct foo { int a, b; };)   -  person David C. Rankin    schedule 26.06.2019
comment
@Someprogrammerdude ทำไมคุณถึงต้องการอาร์เรย์หลายล้านโครงสร้าง ฉันเชื่อว่าใน HPC มันค่อนข้างธรรมดา ตัวอย่างเช่น เราทำงานกับเมทริกซ์กระจัดกระจายที่มีขนาดใหญ่มาก ขั้นตอนการทำงานโดยทั่วไปของเราคือการสร้างองค์ประกอบเมทริกซ์ จากนั้นแปลงเป็นรูปแบบพื้นที่จัดเก็บข้อมูลที่มีประสิทธิภาพสำหรับการประมวลผลต่อไป โดยทั่วไปการแปลงนี้เกี่ยวข้องกับการเรียงลำดับ ขออภัย C++ ไม่รองรับการเรียงลำดับอาร์เรย์หลายรายการพร้อมกัน ดังนั้นเราจึงจัดเรียงอาร์เรย์เหล่านั้นในรูปแบบของอาร์เรย์ของโครงสร้าง โดยแต่ละรายการมีดัชนีแถว/คอลัมน์และค่า เราสามารถทำงานได้แม้จะมีองค์ประกอบเมทริกซ์นับพันล้านองค์ประกอบในกระบวนการ MPI เดียว   -  person Daniel Langr    schedule 26.06.2019
comment
คำอธิบายของคุณเกี่ยวกับการไม่บรรจุโครงสร้างนั้นฟังดูเหมือนกับการบรรจุโครงสร้างทุกประการ   -  person chrylis -cautiouslyoptimistic-    schedule 26.06.2019
comment
ภายใต้ g++ int คือ 4 ไบต์ และ double คือ 8 ไบต์ บน Arduino (คอมไพเลอร์พื้นฐานคือ GCC ซึ่งใช้เป็นคอมไพเลอร์ C ++) double จะเหมือนกับ float (4 ไบต์) ซึ่งอาจเป็นเรื่องแปลกใจสำหรับบางคน (โดยเฉพาะถ้ามีเลขนัยสำคัญมากกว่า 7-8 หลัก) จำเป็นสำหรับตัวนับความถี่...)   -  person Peter Mortensen    schedule 26.06.2019
comment
การเติมและการบรรจุโครงสร้างที่เป็นไปได้ซ้ำกัน   -  person John Bollinger    schedule 26.06.2019
comment
@chrylis ไม่ได้บรรจุโครงสร้างที่นำมาซึ่งการเข้าถึงที่ไม่สอดคล้องกันใช่ไหม มีวิธีกลางที่คุณจัดลำดับองค์ประกอบใหม่   -  person RonJohn    schedule 27.06.2019
comment
@RonJohn ไม่จำเป็น โดยเฉพาะอย่างยิ่ง เป็นเรื่องปกติที่การจัดตำแหน่งจะเป็นสิ่งที่อยู่ในบรรทัดที่มีขนาดคำหรือตัวถูกดำเนินการใหญ่กว่า ซึ่งหมายความว่า (int, int, double) จะถูกจัดเรียงตามธรรมชาติโดยไม่มีช่องว่างภายใน   -  person chrylis -cautiouslyoptimistic-    schedule 27.06.2019
comment
หากคุณพบว่าคำถามนี้มีประโยชน์ ที่นี่ เป็นวิธีอื่นๆ ที่คุณสามารถเพิ่มประสิทธิภาพโค้ดของคุณในระดับต่ำได้   -  person    schedule 27.06.2019
comment
@DanielLangr ฉันถามเพราะฉันต้องการให้ OP อธิบายรายละเอียดเกี่ยวกับปัญหา ของจริง แทนที่จะแก้ไขปัญหาที่ไม่รู้จัก (สำหรับเรา)   -  person Some programmer dude    schedule 01.07.2019

คำตอบ (7)


arrow_upward
36
arrow_downward

(อย่าใช้กฎเหล่านี้โดยไม่คิด ดูประเด็นของ ESR เกี่ยวกับตำแหน่งแคชสำหรับสมาชิกที่คุณใช้ร่วมกัน และในโปรแกรมแบบมัลติเธรด ระวังการแบ่งปันสมาชิกที่เขียนโดยเธรดที่แตกต่างกันในทางที่ผิด โดยทั่วไปคุณไม่ต้องการข้อมูลต่อเธรดใน โครงสร้างเดียวเลยด้วยเหตุผลนี้ เว้นแต่ว่าคุณกำลังทำเพื่อควบคุมการแยกด้วย alignas(128) ขนาดใหญ่ สิ่งนี้ใช้กับ atomic และ vars ที่ไม่ใช่อะตอมมิก สิ่งที่สำคัญคือเธรดที่เขียนไปยังบรรทัดแคชไม่ว่าพวกมันจะทำเช่นไรก็ตาม)

หลักทั่วไป: ใหญ่ที่สุดไปเล็กที่สุด alignof() คุณไม่สามารถทำอะไรได้สมบูรณ์แบบทุกที่ แต่กรณีที่พบบ่อยที่สุดในทุกวันนี้คือการใช้งาน C++ ปกติอย่างสมเหตุสมผลสำหรับ CPU 32 หรือ 64 บิตปกติ ประเภทดั้งเดิมทั้งหมดมีขนาดยกกำลัง 2

ประเภทส่วนใหญ่จะมี alignof(T) = sizeof(T) หรือ alignof(T) ต่อยอดที่ความกว้างรีจิสเตอร์ของการนำไปใช้งาน ประเภทที่ใหญ่กว่ามักจะมีความสอดคล้องมากกว่าประเภทที่เล็กกว่า

กฎการบรรจุโครงสร้างใน ABI ส่วนใหญ่จะทำให้สมาชิก struct มีการจัดตำแหน่ง alignof(T) แบบสัมบูรณ์โดยสัมพันธ์กับจุดเริ่มต้นของ struct และตัว struct เองจะสืบทอด alignof() ที่ใหญ่ที่สุดจากสมาชิกใดๆ ก็ตาม

  • ใส่สมาชิกแบบ 64 บิตเสมอก่อน (เช่น double, long long และ int64_t) แน่นอนว่า ISO C++ ไม่ได้แก้ไขประเภทเหล่านี้ที่ 64 บิต / 8 ไบต์ แต่ในทางปฏิบัติกับ CPU ทั้งหมดที่คุณสนใจ บุคคลที่ย้ายโค้ดของคุณไปยัง CPU แปลกใหม่สามารถปรับแต่งเค้าโครงโครงสร้างเพื่อปรับให้เหมาะสมได้หากจำเป็น

  • ตามด้วยตัวชี้ และจำนวนเต็มความกว้างของตัวชี้: size_t, intptr_t และ ptrdiff_t (ซึ่งอาจเป็น 32 หรือ 64 บิต) สิ่งเหล่านี้ล้วนมีความกว้างเท่ากันในการใช้งาน C ++ สมัยใหม่ตามปกติสำหรับ CPU ที่มีรุ่นหน่วยความจำแบบแบน

    พิจารณาใส่รายการลิงค์และตัวชี้ซ้าย/ขวาของต้นไม้ก่อนหากคุณสนใจซีพียู x86 และ Intel การไล่ตัวชี้ผ่านโหนดในแผนผังหรือรายการลิงก์ มีบทลงโทษเมื่อที่อยู่เริ่มต้นของ struct อยู่ในหน้า 4k ที่แตกต่างจากสมาชิกที่คุณกำลังเข้าถึง ทำให้พวกเขาเป็นหลักประกันที่ไม่สามารถเป็นเช่นนั้นได้

  • จากนั้น long (ซึ่งบางครั้งจะเป็น 32 บิตแม้ว่าตัวชี้จะเป็น 64 บิตใน LLP64 ABI เช่น Windows x64) แต่รับประกันว่ากว้างอย่างน้อยเท่ากับ int

  • จากนั้น 32 บิต int32_t, int, float, enum (แยก int32_t และ float นำหน้า int ก็ได้ หากคุณสนใจระบบ 8/16 บิตที่เป็นไปได้ที่ยังคงแพดประเภทเหล่านั้นเป็น 32 บิต หรือทำงานได้ดีกว่าหากระบบจัดเรียงตามธรรมชาติ ระบบดังกล่าวส่วนใหญ่ไม่มีโหลดที่กว้างกว่า (FPU หรือ SIMD) ดังนั้นจึงต้องจัดการประเภทที่กว้างกว่าเป็นหลายชิ้นแยกกันตลอดเวลา)

    ISO C++ อนุญาตให้ int แคบได้ถึง 16 บิตหรือกว้างโดยพลการ แต่ในทางปฏิบัติมันเป็นประเภท 32 บิตแม้แต่บน CPU 64 บิตก็ตาม นักออกแบบ ABI พบว่าโปรแกรมที่ออกแบบมาเพื่อทำงานกับ int แบบ 32 บิต จะทำให้หน่วยความจำสิ้นเปลือง (และขนาดแคช) หาก int กว้างกว่า อย่าตั้งสมมติฐานที่อาจก่อให้เกิดปัญหาเรื่องความถูกต้อง แต่สำหรับประสิทธิภาพแบบพกพา คุณเพียงแค่ต้องถูกต้องในกรณีปกติ

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

  • แล้วก็ short / int16_t

  • แล้วก็ char / int8_t / bool

  • (สำหรับแฟล็ก bool หลายรายการ โดยเฉพาะอย่างยิ่งหากเป็นแบบอ่านส่วนใหญ่หรือหากแฟล็กทั้งหมดมีการแก้ไขร่วมกัน ให้พิจารณารวมแฟล็กเหล่านั้นด้วยบิตฟิลด์ 1 บิต)

(สำหรับประเภทจำนวนเต็มที่ไม่ได้ลงนาม ให้ค้นหาประเภทการลงนามที่เกี่ยวข้องในรายการของฉัน)

อาร์เรย์ แบบหลายไบต์จาก 8 ไบต์ที่มีประเภทแคบกว่าสามารถไปเร็วกว่านี้ได้หากต้องการ แต่หากคุณไม่ทราบขนาดที่แน่นอนของประเภท คุณไม่สามารถรับประกันได้ว่า int i + char buf[4] จะเติมเต็มช่องที่จัดแนวขนาด 8 ไบต์ระหว่าง doubles สองอัน แต่มันไม่ใช่สมมติฐานที่ไม่ดี ดังนั้นฉันจะทำต่อไปหากมีเหตุผลบางอย่าง (เช่น พื้นที่เชิงพื้นที่ของสมาชิกที่เข้าถึงร่วมกัน) เพื่อรวมพวกเขาเข้าด้วยกันแทนที่จะรวมไว้ตอนท้าย

ประเภทแปลกใหม่: x86-64 System V มี alignof(long double) = 16 แต่ i386 System V มีเพียง alignof(long double) = 4, sizeof(long double) = 12 เป็นประเภท x87 80 บิต ซึ่งจริงๆ แล้วมีขนาด 10 ไบต์ แต่เสริมเป็น 12 หรือ 16 ดังนั้นจึงเป็นผลคูณของการจัดตำแหน่ง ทำให้อาร์เรย์เป็นไปได้โดยไม่ละเมิดการรับประกันการจัดตำแหน่ง

และโดยทั่วไป จะยุ่งยากมากขึ้นเมื่อสมาชิก struct ของคุณรวมเข้าด้วยกัน (struct หรือ union) ด้วย sizeof(x) != alignof(x)

สิ่งที่บิดเบี้ยวอีกอย่างคือใน ABI บางตัว (เช่น Windows 32 บิตถ้าฉันจำได้ถูกต้อง) สมาชิก struct จะถูกจัดแนวตามขนาด (สูงสุด 8 ไบต์) สัมพันธ์กับจุดเริ่มต้นของ struct แม้ว่า alignof(T) จะเป็น ยังคงมีเพียง 4 สำหรับ double และ int64_t
นี่เป็นการปรับให้เหมาะสมสำหรับกรณีทั่วไปของการจัดสรรหน่วยความจำที่จัดแนว 8 ไบต์แยกกันสำหรับโครงสร้างเดียว โดยไม่ต้องให้ การรับประกัน การจัดตำแหน่ง i386 System V ยังมี alignof(T) = 4 เหมือนกันสำหรับประเภทดั้งเดิมส่วนใหญ่ (แต่ malloc ยังคงให้หน่วยความจำที่จัดแนว 8 ไบต์เพราะ alignof(maxalign_t) = 8) แต่อย่างไรก็ตาม i386 System V ไม่มีกฎการบรรจุโครงสร้างนั้น ดังนั้น (ถ้าคุณไม่จัดเรียงโครงสร้างของคุณจากใหญ่ที่สุดไปเล็กที่สุด) คุณสามารถจบลงด้วยสมาชิก 8 ไบต์ที่อยู่ต่ำกว่าแนวสัมพันธ์กับจุดเริ่มต้นของโครงสร้าง .

CPU ส่วนใหญ่มีโหมดการกำหนดแอดเดรสที่อนุญาตให้เข้าถึงออฟเซ็ตไบต์ใดๆ เมื่อมีตัวชี้ในรีจิสเตอร์ โดยทั่วไปออฟเซ็ตสูงสุดจะมีขนาดใหญ่มาก แต่ใน x86 จะบันทึกขนาดโค้ดหากออฟเซ็ตไบต์พอดีกับไบต์ที่เซ็นชื่อ ([-128 .. +127]) ดังนั้นหากคุณมี อาร์เรย์ประเภทใดๆ จำนวนมาก แนะนำให้วางไว้ภายหลังในโครงสร้าง หลังสมาชิกที่ใช้บ่อย แม้ว่าจะต้องเสียค่ารองพื้นสักหน่อยก็ตาม

คอมไพเลอร์ของคุณมักจะสร้างโค้ดที่มีที่อยู่ struct ในรีจิสเตอร์เสมอ ไม่ใช่ที่อยู่ตรงกลางของ struct เพื่อใช้ประโยชน์จากการแทนที่เชิงลบระยะสั้น

Eric S. Raymond เขียนบทความ The Lost Art of Structure Packing โดยเฉพาะส่วนที่เกี่ยวกับการเรียงลำดับโครงสร้างใหม่นั้นเป็นคำตอบสำหรับคำถามนี้

เขายังกล่าวถึงประเด็นสำคัญอีกประการหนึ่ง:

9. ความสามารถในการอ่านและตำแหน่งแคช

แม้ว่าการจัดเรียงใหม่ตามขนาดเป็นวิธีที่ง่ายที่สุดในการกำจัดสิ่งที่เลอะเทอะ นั่นไม่ใช่สิ่งที่ถูกต้องเสมอไป ยังมีอีกสองประเด็น: ความสามารถในการอ่านและตำแหน่งแคช

ในโครงสร้าง ขนาดใหญ่ ที่สามารถแยกข้ามขอบเขตแคชไลน์ได้อย่างง่ายดาย มันสมเหตุสมผลที่จะวาง 2 สิ่งไว้ใกล้กันหากใช้ร่วมกันเสมอ หรือแม้กระทั่งต่อเนื่องกันเพื่อให้สามารถบรรทุก/จัดเก็บรวมกันได้ เช่น คัดลอก 8 หรือ 16 ไบต์ด้วยจำนวนเต็มหนึ่ง (ไม่มีเครื่องหมาย) หรือโหลด/จัดเก็บ SIMD แทนที่จะแยกโหลดสมาชิกที่มีขนาดเล็กกว่า

โดยทั่วไปบรรทัดแคชจะมีขนาด 32 หรือ 64 ไบต์บน CPU สมัยใหม่ (บน x86 สมัยใหม่จะมีขนาด 64 ไบต์เสมอ และตระกูล Sandybridge มีตัวดึงข้อมูลเชิงพื้นที่บรรทัดที่อยู่ติดกันในแคช L2 ที่พยายามทำให้คู่บรรทัดขนาด 128 ไบต์สมบูรณ์ แยกจากตัวตรวจจับรูปแบบการดึงข้อมูลล่วงหน้า HW ลำแสงหลัก L2 และการดึงข้อมูลล่วงหน้า L1d)

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

(@alexis โพสต์คำตอบเฉพาะลิงก์ที่ลิงก์ไปยังบทความของ ESR ดังนั้นขอบคุณสำหรับจุดเริ่มต้นนั้น)

person Peter Cordes    schedule 26.06.2019
comment
แม้ว่านี่จะไม่ใช่โซลูชันข้ามแพลตฟอร์ม สมบูรณ์ จริงๆ และไม่ใช่โซลูชันแบบอัตโนมัติ แต่ก็มีข้อมูลที่แท้จริงที่สุดเกี่ยวกับวิธีแก้ปัญหานี้ ดังนั้นฉันจะยอมรับ บางทีฉันอาจจะสร้างวิกิชุมชนที่นี่ในภายหลังแทน - person ; 26.06.2019
comment
@YanB: ฉันไม่ได้อ่านคำถามทั้งหมดก่อนที่จะตอบ ฉันไม่ทราบว่าส่วนใหญ่คุณกำลังมองหาโซลูชันอัตโนมัติ แทนที่จะเป็นหลักการทั่วไป แต่โชคดีที่ CPU กระแสหลัก 32 และ 64 บิตสมัยใหม่มีความคล้ายคลึงกันมากพอ ซึ่งจริงๆ แล้วเราใส่ใจว่าเราสามารถให้คำแนะนำที่เป็นประโยชน์ได้ แม้ว่า ISO C++ จะไม่รับประกันโดยพื้นฐานแล้วก็ตาม มีข้อสันนิษฐานมากมายเกี่ยวกับสิ่งที่เป็นเรื่องปกติซึ่งเกิดขึ้นกับ C++ (และ CPU สมัยใหม่) แยกจากมาตรฐาน ISO C++ สิ่งเหล่านี้เกือบจำเป็นสำหรับการนำ C++ ไปใช้เพื่อให้เป็นประโยชน์กับทุกสิ่งในทางปฏิบัติ! - person Peter Cordes; 26.06.2019
comment
การเรียงลำดับจากเล็กไปหาใหญ่อาจจะดีกว่าโดยรวม: ส่งผลให้เข้าถึงสมาชิกส่วนใหญ่ได้อย่างมีประสิทธิภาพมากขึ้น (เช่น เนื่องจากออฟเซ็ตมีขนาดเล็กลงตามที่คุณชี้ให้เห็น แต่ยังเป็นเพราะสมาชิกของโครงสร้างมีแนวโน้มที่จะอยู่ในบรรทัดแคช) การลดขนาดหลักๆ คือการที่ช่องว่างภายในมีแนวโน้มที่จะปรากฏขึ้นตรงกลางของโครงสร้างมากกว่าส่วนท้าย ดังนั้นการคัดลอกอาจมีประสิทธิภาพน้อยลงในบางกรณีที่ผิดปกติ - person BeeOnRope; 27.06.2019
comment
@BeeOnRope: โดยเฉพาะอย่างยิ่งกับการเพิ่มประสิทธิภาพที่ไม่ได้รับ gcc การรวมร้านค้าของ GCC8 สำหรับการสร้างศูนย์ของโครงสร้างปฏิเสธที่จะเขียนทับช่องว่างภายใน: gcc.gnu.org/bugzilla /show_bug.cgi?id=82142 - person Peter Cordes; 27.06.2019
comment
ดูเหมือนจะไม่ใช่ปัญหาสากล ดูการทดสอบด่วนของฉัน - person BeeOnRope; 27.06.2019

arrow_upward
31
arrow_downward

gcc มีคำเตือน -Wpadded ที่เตือนเมื่อมีการเพิ่มช่องว่างภายในในโครงสร้าง:

https://godbolt.org/z/iwO5Q3:

<source>:4:12: warning: padding struct to align 'X::b' [-Wpadded]
    4 |     double b;
      |            ^

<source>:1:8: warning: padding struct size to alignment boundary [-Wpadded]
    1 | struct X
      |        ^

และคุณสามารถจัดเรียงสมาชิกใหม่ด้วยตนเองเพื่อให้มีช่องว่างภายในน้อยลง/ไม่มีเลย แต่นี่ไม่ใช่โซลูชันข้ามแพลตฟอร์ม เนื่องจากประเภทต่างๆ สามารถมีขนาด/การจัดตำแหน่งที่แตกต่างกันบนระบบที่แตกต่างกัน (ตัวชี้ที่โดดเด่นที่สุดคือ 4 หรือ 8 ไบต์บนสถาปัตยกรรมที่แตกต่างกัน) กฎทั่วไปคือเปลี่ยนจากการจัดตำแหน่งที่ใหญ่ที่สุดไปหาน้อยที่สุดเมื่อประกาศสมาชิก และหากคุณยังกังวลอยู่ ให้คอมไพล์โค้ดของคุณด้วย -Wpadded หนึ่งครั้ง (แต่ฉันจะไม่เก็บมันไว้โดยทั่วไป เพราะบางครั้งจำเป็นต้องมีการเติมช่องว่าง)

ส่วนสาเหตุที่คอมไพเลอร์ไม่สามารถทำได้โดยอัตโนมัติก็เนื่องมาจากมาตรฐาน ([ class.mem]/19) รับประกันได้ว่า เนื่องจากนี่เป็นโครงสร้างที่เรียบง่ายที่มีเฉพาะสมาชิกสาธารณะเท่านั้น &x.a < &x.c (สำหรับบาง X x;) ดังนั้นจึงไม่สามารถจัดเรียงใหม่ได้

person Artyer    schedule 25.06.2019
comment
ฉันไม่คิดว่าจะเห็นสิ่งที่มีประโยชน์ออกมาจากคำถามนี้โดยสุจริต ไม่ทราบตัวเลือก gcc นั้น (และตอนนี้ฉันก็มีเสียงดังกราวด้วยเช่นกัน) ขอบคุณที่สอนบางอย่างให้ฉัน ติ๊ก - person WhozCraig; 25.06.2019
comment
@WhozCraig ใช่ clang ก็มีตัวเลือกนี้ด้วย (มันยังมีชื่อเดียวกันด้วยซ้ำ) มันมีประโยชน์มาก (อย่างน้อยสำหรับฉัน) เมื่อจัดการกับปัญหาการจัดเรียงใหม่ เป็นเรื่องน่าเสียดายที่ (อย่างน้อยตอนนี้) ฉันยังไม่พบวิธีแก้ปัญหาแบบอัตโนมัติ - person ; 26.06.2019
comment
มีแพลตฟอร์มสมัยใหม่จากระยะไกลที่ประเภทการวางตามลำดับ double, [ไม่ได้ลงนาม] long long, [i]int64_t, int64_t, พอยน์เตอร์, long, float, int32_t, int, int16_t, short, char จะไม่ให้การจัดตำแหน่งที่เหมาะสมที่สุดหรือไม่ - person supercat; 29.06.2019

arrow_upward
14
arrow_downward

ไม่มีโซลูชันแบบพกพาในกรณีทั่วไป เมื่อแยกข้อกำหนดขั้นต่ำตามที่มาตรฐานกำหนด ประเภทต่างๆ อาจมีขนาดใดก็ได้ตามที่การใช้งานต้องการ

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

คุณสามารถใช้ประเภทความกว้างคงที่เช่น

struct foo
{
    int64_t a;
    int16_t b;
    int8_t c;
    int8_t d;
};

และจะเหมือนกันในทุกแพลตฟอร์ม หากระบุประเภทเหล่านั้น แต่จะใช้ได้กับประเภทจำนวนเต็มเท่านั้น ไม่มีประเภทจุดทศนิยมที่มีความกว้างคงที่ และออบเจ็กต์/คอนเทนเนอร์มาตรฐานจำนวนมากสามารถมีขนาดแตกต่างกันได้บนแพลตฟอร์มที่ต่างกัน

person NathanOliver    schedule 25.06.2019
comment
การเติมเกลือลงบนแผล ประเภทจุดลอยตัวมักจะไวต่อตำแหน่งการจัดตำแหน่งบัส ดังนั้นจึงเป็นการเสริมมนต์ที่ไม่มีกระสุนเงิน อย่างไรก็ตาม สิ่งนี้มีประโยชน์มากเมื่อโหลดโครงสร้างด้วยสิ่งอื่นนอกเหนือจากจุดลอยตัวและตัวชี้ที่อาจเกิดขึ้น ฉันใช้มันบ่อยๆ - person WhozCraig; 25.06.2019
comment
เหตุใดจึงไม่อนุญาตให้มีการจัดเรียงสมาชิกใหม่ คุณช่วยชี้แจงได้ไหม? - person ; 26.06.2019
comment
หากคุณใช้ความสามารถในการพกพาข้ามแพลตฟอร์มถึงขีดจำกัด โปรดทราบว่าประเภทความกว้างที่แน่นอนเหล่านี้เป็น ทางเลือก ทุกแพลตฟอร์มต้องมี int_least16_t และ int_fast16_t แต่ (เช่น หาก CHAR_BIT != 8) ไม่จำเป็นต้องมี int16_t บนแพลตฟอร์มที่กำหนด - person DevSolar; 26.06.2019
comment
@DevSolar แม้ว่าพวกเขาจะเป็นทางเลือก แต่โค้ดจะไม่สามารถคอมไพล์ได้หากไม่มีอยู่ดังนั้นอย่างน้อยคุณก็จะไม่ได้รับไบนารีที่ระเบิดใส่คุณ - person NathanOliver; 26.06.2019
comment
คุณสามารถจัดเก็บ float ในรูปแบบ 4 ไบต์ แค่อ่านเขียนก็น่าเกลียดแล้ว - person Oblivion; 26.06.2019
comment
@ยันบี. เพราะมาตรฐานบอกอย่างนั้น ดูเพิ่มเติมที่ stackoverflow.com/questions/118068/. สำหรับเหตุผลนั้น มีหลายสิ่งหลายอย่างที่จะเสียหายหากคอมไพเลอร์มีอิสระที่จะทำสิ่งนั้น (เหนือสิ่งอื่นใด ลองนึกภาพโปรแกรมที่เขียน structs โดยตรงไปยังไฟล์ด้วย fwrite และอ่านกลับด้วย fread การเปลี่ยนแปลงในคอมไพเลอร์อาจทำให้รูปแบบไฟล์เสียหายกะทันหัน ความเข้ากันได้สำหรับโปรแกรมที่คอมไพล์) - person jamesdlin; 26.06.2019

arrow_upward
4
arrow_downward

นี่เป็นปัญหาระหว่างหน่วยความจำกับความเร็วในตำราเรียน ช่องว่างภายในคือการแลกเปลี่ยนหน่วยความจำกับความเร็ว คุณไม่สามารถพูดได้:

ฉันไม่ต้องการ "แพ็ค" โครงสร้างของฉัน

เพราะ pragma pack เป็นเครื่องมือที่คิดค้นขึ้นเพื่อทำให้การแลกเปลี่ยนนี้แตกต่างออกไป นั่นคือ ความเร็วสำหรับหน่วยความจำ

มีวิธีข้ามแพลตฟอร์มที่เชื่อถือได้หรือไม่

ไม่ ไม่สามารถมีได้ การจัดตำแหน่งเป็นปัญหาที่ขึ้นอยู่กับแพลตฟอร์มอย่างเคร่งครัด ขนาดของประเภทต่างๆ เป็นปัญหาที่ขึ้นอยู่กับแพลตฟอร์ม การหลีกเลี่ยงการเติมโดยการจัดระเบียบใหม่จะขึ้นอยู่กับแพลตฟอร์มที่กำลังสอง

ความเร็ว หน่วยความจำ และข้ามแพลตฟอร์ม - คุณสามารถมีได้เพียงสองเท่านั้น

เหตุใดคอมไพเลอร์จึงไม่ทำการเพิ่มประสิทธิภาพดังกล่าว (สลับสมาชิกโครงสร้าง/คลาสไปรอบๆ เพื่อลดช่องว่างภายใน)

เนื่องจากข้อกำหนดเฉพาะของ C++ รับประกันโดยเฉพาะว่าคอมไพเลอร์จะไม่ทำให้โครงสร้างที่จัดระเบียบอย่างพิถีพิถันของคุณยุ่งเหยิง ลองนึกภาพคุณมีทุ่นสี่อันติดต่อกัน บางครั้งคุณใช้มันตามชื่อ และบางครั้งคุณส่งต่อมันไปยังเมธอดที่รับพารามิเตอร์ float[3]

คุณกำลังเสนอว่าคอมไพเลอร์ควรสับเปลี่ยนพวกมัน อาจทำให้โค้ดทั้งหมดเสียหายนับตั้งแต่ปี 1970 และเพราะเหตุใด? คุณรับประกันได้ไหมว่าโปรแกรมเมอร์ทุกคนจะต้องการบันทึก 8 ไบต์ต่อโครงสร้างจริง ๆ ประการหนึ่งฉันแน่ใจว่าถ้าฉันมีอาร์เรย์ 3 GB ฉันจะประสบปัญหาใหญ่กว่า GB ไม่มากก็น้อย

person Agent_L    schedule 26.06.2019
comment
ฉันขอยืนยันว่าปัญหาเดียวที่นี่คือ "บางครั้งคุณส่งต่อไปยังวิธีการที่ใช้ float[3] พารามิเตอร์" นั่นเป็นกรณีการใช้งานที่ค่อนข้างพิเศษ อันที่จริง ฉันจะบอกว่ามันเป็นปัญหาหลักที่นี่ที่ C++ รองรับการเล่นกลพอยน์เตอร์ประเภทนี้ หากไม่ทำเช่นนั้นและอนุญาตให้คอมไพเลอร์เรียงลำดับใหม่เพื่อการเพิ่มประสิทธิภาพเสมอ โค้ดจำนวนมากก็จะทำงานเร็วขึ้น ในขณะที่โปรแกรมที่จะต้องเขียนใหม่เพื่อล้อม float[3] ไว้อย่างชัดเจนในอาร์เรย์จะมีโทษด้านประสิทธิภาพที่ละเลย - person leftaroundabout; 26.06.2019
comment
ฉันค่อนข้างแน่ใจว่าตัวแปรสมาชิกจุดลอยตัวสี่ตัวที่พิมพ์ด้วยการพิมพ์เพื่อส่งผ่านพวกมันในฐานะ float[3] ทำให้เกิดพฤติกรรมที่ไม่ได้กำหนดไว้ - person Jeremy Friesner; 26.06.2019
comment
@JeremyFriesner: โปรดทราบว่าพฤติกรรมที่ไม่ได้กำหนดนั้นมีจุดประสงค์เพื่อให้การใช้งานที่สามารถเสนอความหมายที่มีประโยชน์มากขึ้นให้ทำเช่นนั้นเมื่อใช้งานได้จริง ก่อนที่ผู้ทำลายล้างภาษาจะเข้ามาแทนที่และเริ่มใช้เป็นข้อแก้ตัวที่จะไม่เสนอความหมายที่มีประโยชน์แม้ในกรณีที่พวกเขาจะไม่มีค่าใช้จ่ายใด ๆ . - person supercat; 26.06.2019
comment
@supercat โดยไม่คำนึงถึงเจตนาในอดีต การเรียกใช้พฤติกรรมที่ไม่ได้กำหนดไม่ใช่สิ่งที่เราต้องการทำ (เว้นแต่คุณจะสนุกกับการค้นพบและวินิจฉัยพฤติกรรมที่ไม่เหมาะสมของรันไทม์ที่คลุมเครือ) - person Jeremy Friesner; 26.06.2019
comment
@JeremyFriesner: Standard ไม่เคยต้องการให้การใช้งานสนับสนุนความหมายทั้งหมดที่จำเป็นสำหรับวัตถุประสงค์เฉพาะใด ๆ บนแพลตฟอร์มเป้าหมายจำนวนมาก I/O คงเป็นไปไม่ได้หากไม่มีการใช้พอยน์เตอร์เพื่อแสดงที่อยู่ที่ไม่ได้ระบุอ็อบเจ็กต์ตามที่มาตรฐานกำหนด หากไม่ได้รับอนุญาตให้ดำเนินการตามที่มาตรฐานไม่ได้กำหนดข้อกำหนดไว้ เราจะไม่สามารถอะไรก็ตามบนแพลตฟอร์มดังกล่าวได้ - person supercat; 26.06.2019
comment
@JeremyFriesner: แน่นอนว่าคงมีคนถามถึงปัญหาหากใครพยายามใช้เทคนิคการเขียนโปรแกรมระดับต่ำในการใช้งาน ที่ไม่ได้รับการออกแบบหรือกำหนดค่าให้เหมาะสมกับวัตถุประสงค์ดังกล่าว แต่ใช้ การใช้งานที่ไม่เหมาะสมสำหรับงาน ใดๆ ที่พยายามทำอยู่ อาจเป็นการถามถึงปัญหา - person supercat; 26.06.2019
comment
@supercat จริงๆ แล้วมันไม่ใช่ภาษาที่ทำลายล้าง แต่เป็นผู้เขียนคอมไพเลอร์ที่สามารถบีบโอกาสในการเพิ่มประสิทธิภาพเพิ่มเติมโดยการใช้พฤติกรรมที่ไม่ได้กำหนดอย่างแท้จริง โดยพื้นฐานแล้ว คุณหวังว่าคอมไพลเลอร์จะทำสิ่งที่สมเหตุสมผล ในขณะที่ผู้เขียนคอมไพเลอร์ชอบทำอะไรที่รวดเร็ว (เพราะนั่นช่วยปรับปรุงเกณฑ์มาตรฐาน ซึ่งจะช่วยปรับปรุงยอดขาย/ส่วนแบ่งความคิด และปรับปรุงความเร็วรันไทม์ได้จริงแม้ในโปรแกรมที่ค่อนข้างปกติ) - person toolforger; 26.06.2019
comment
@toolforger: คุณเคยอ่านเหตุผลที่เผยแพร่แล้วหรือยัง? ตามที่คณะกรรมการระบุ ลักษณะพื้นฐานที่สุดของ Spirit of C คือความไว้วางใจต่อโปรแกรมเมอร์ และอย่าขัดขวางโปรแกรมเมอร์จากการทำสิ่งที่ต้องทำ พวกเขายังตระหนักอย่างชัดเจนว่าหนึ่งในจุดแข็งของ C คือความสามารถในการใช้โปรแกรมที่ไม่สามารถพกพาได้เพื่อทำสิ่งต่าง ๆ ที่โปรแกรมพกพาไม่สามารถทำได้ (เพราะว่า Standard ไม่ได้เตรียมไว้ให้) หากงานบางอย่างไม่สามารถทำได้โดยไม่ดำเนินการใดๆ การใช้งานทั้งหมดที่เหมาะสมกับงานจะสนับสนุนการดำเนินการนั้น ไม่ว่ามาตรฐานจะกำหนดหรือไม่ก็ตาม - person supercat; 26.06.2019
comment
@toolforger: ผู้เขียนคอมไพเลอร์แนะนำการแบ่งขั้วที่ผิดพลาดระหว่างความเร็วและความหมาย สำหรับคอมไพเลอร์ที่บางครั้งถือว่าการคำนวณจำนวนเต็มแบบเซ็นชื่อเหมือนกับว่าดำเนินการกับประเภทที่กว้างกว่าจะช่วยให้เพิ่มประสิทธิภาพที่มีประโยชน์ได้มากกว่า 90% ที่เกี่ยวข้องกับการกระโดดรางเมื่อล้น หากคอมไพลเลอร์ดังกล่าวได้รับซอร์สโค้ดที่ใช้ประโยชน์จากข้อเท็จจริงที่ว่า ทั้งหมด ที่จะทำได้ คอมไพเลอร์สามารถบรรลุการปรับให้เหมาะสมที่ไม่สามารถทำได้ด้วยซอร์สโค้ดที่เขียนขึ้นสำหรับการโอเวอร์โฟลว์ จะต้องหลีกเลี่ยงในทุกรูปแบบต้นทุน - person supercat; 26.06.2019
comment
@toolforger: โดยทั่วไปแล้ว การเพิ่มประสิทธิภาพที่ถือว่าโปรแกรมเมอร์ไม่จำเป็นต้องทำ X อาจมีประโยชน์สำหรับโปรแกรมที่ต้องทำ X แต่จะต่อต้านประสิทธิผลในกรณีที่พฤติกรรมที่ต้องการนั้นเป็นสิ่งที่จะเกิดขึ้นได้อย่างแม่นยำ เพียงทำ X หากจำเป็นต้องมีการกระทำ X สำหรับงานบางอย่าง แต่ไม่ใช่งานอื่น และหากค่าใช้จ่ายในการสนับสนุน X ในการใช้งานที่แตกต่างกันจะแตกต่างกันไป X ควรได้รับการสนับสนุนในการใช้งานหรือการกำหนดค่าที่ใช้สำหรับงานที่ต้องการ แต่ไม่ใช่ในส่วนที่ต้องการ กำหนดรายจ่ายโดยไม่จำเป็น นั่นควรจะชัดเจนในตัวเอง แต่ดูเหมือนจะไม่ใช่ - person supercat; 26.06.2019
comment
@supercat ประเด็นที่คุณยกนั้นเกี่ยวกับมาตรฐานภาษา ไม่ใช่เกี่ยวกับผู้เขียนคอมไพเลอร์ นอกจากนี้ การแบ่งขั้วไม่ได้เป็นเท็จ ความสามารถในการเพิกเฉยต่อกรณีที่ไม่ได้กำหนดไว้ (แทนที่จะทำในสิ่งที่คุณต้องการให้พวกเขาทำ) สามารถเร่งความเร็วได้ถึง 50% มันเป็นปัญหาเรื่องความเร็วจริงๆ ที่ทำให้มาตรฐาน C กลายเป็นสิ่งที่เต็มไปด้วยพฤติกรรมที่ไม่ได้กำหนด ไม่ใช่การก่อกวนภาษา - person toolforger; 27.06.2019
comment
BTW สิ่งนี้กลายเป็นการอภิปรายเพิ่มเติมเกี่ยวกับรายละเอียดความเป็นมา ซึ่งไม่ใช่ความคิดเห็นที่มีไว้เพื่ออะไร - person toolforger; 27.06.2019
comment
@toolforger: หนึ่งคำถามสั้น ๆ ที่แยกจากกัน: คุณเชื่อว่าผู้เขียนมาตรฐานมีจุดประสงค์เพื่อขัดขวางการใช้ภาษาเป็นรูปแบบหนึ่งของแอสเซมเบลอร์ระดับสูงหรือไม่? - person supercat; 27.06.2019
comment
@supercat แอสเซมเบลอร์ระดับสูงนั้นอยู่ในรายการลำดับความสำคัญสูงอย่างแน่นอน แต่ก็มีอย่างอื่นอีกแน่นอน เนื่องจากการตัดสินใจในการออกแบบภาษาทุกครั้งถือเป็นการแลกเปลี่ยน จึงไม่มีแม้แต่ภาษา X ที่ชัดเจนที่มุ่งเน้นไปที่คุณลักษณะ A เลยด้วยซ้ำ มันเป็นสิ่งที่ค่อยเป็นค่อยไปเสมอ - person toolforger; 27.06.2019
comment
ให้เราสนทนาต่อในการแชท - person supercat; 27.06.2019

arrow_upward
4
arrow_downward

Mate ในกรณีที่คุณมีข้อมูล 3GB คุณควรแก้ไขปัญหาด้วยวิธีอื่นแล้วสลับสมาชิกข้อมูล

แทนที่จะใช้ 'array of struct' สามารถใช้ 'struct of arrays' ได้ ดังนั้นพูด

struct X
{
    int a;
    double b;
    int c;
};

constexpr size_t ArraySize = 1'000'000;
X my_data[ArraySize];

กำลังจะกลายเป็น

constexpr size_t ArraySize = 1'000'000;
struct X
{
    int    a[ArraySize];
    double b[ArraySize];
    int    c[ArraySize];
};

X my_data;

แต่ละองค์ประกอบยังคงเข้าถึงได้ง่าย mydata.a[i] = 5; mydata.b[i] = 1.5f;...
ไม่มีช่องว่างภายใน (ยกเว้นสองสามไบต์ระหว่างอาร์เรย์) เค้าโครงหน่วยความจำเป็นมิตรกับแคช Prefetcher จัดการการอ่านบล็อกหน่วยความจำตามลำดับจากขอบเขตหน่วยความจำที่แยกจากกันบางส่วน

นั่นไม่ใช่เรื่องแปลกอย่างที่คิดเมื่อมองแวบแรก วิธีการดังกล่าวใช้กันอย่างแพร่หลายสำหรับการเขียนโปรแกรม SIMD และ GPU


อาร์เรย์ของโครงสร้าง (AoS) โครงสร้างของอาร์เรย์

person user3124812    schedule 28.06.2019
comment
สิ่งนี้จะดีกว่ามากเมื่อสามารถใช้ SIMD ได้ แต่เมื่อคุณต้องการการเข้าถึงโครงสร้างแบบกระจาย / แบบสุ่ม (และต้องการสมาชิกหลายคนในโครงสร้างเดียวกัน แต่ ไม่ใช่ สิ่งใดจากโครงสร้างใกล้เคียง) SoA จะทำให้คุณเสียค่าใช้จ่าย 3 เท่าของแคชที่พลาดไป นอกจากนี้ ยังทำให้คุณเสียค่าใช้จ่ายในการใช้พอยน์เตอร์/รีจิสเตอร์เพิ่มขึ้น โดยเฉพาะสำหรับการจัดสรรที่ไม่ใช่ CISC และ/หรือการจัดสรรแบบไม่คงที่ แต่ถ้า SIMD เป็นตัวเลือกสำหรับลูปใดๆ ของคุณ ก็มักจะมากที่จะมี SoA - person Peter Cordes; 16.07.2019

arrow_upward
2
arrow_downward

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

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

คนอวดรู้บางคนจะบ่นว่าโค้ดที่ใช้ประโยชน์จากพฤติกรรมนั้นคือ "ไม่สามารถพกพาได้" ฉันจะตอบพวกเขา

รหัส C ไม่สามารถพกพาได้ แม้ว่าจะพยายามให้โปรแกรมเมอร์มีโอกาสเขียนโปรแกรมพกพาได้อย่างแท้จริง แต่คณะกรรมการ C89 ไม่ต้องการบังคับให้โปรแกรมเมอร์เขียนแบบพกพา เพื่อขัดขวางการใช้ C ในฐานะ "แอสเซมเบลอร์ระดับสูง": ความสามารถในการเขียนโค้ดเฉพาะเครื่องคือ หนึ่งในจุดแข็งของซี

จากการขยายหลักการดังกล่าวเล็กน้อย ความสามารถของโค้ดซึ่งจำเป็นต้องรันบนเครื่อง 90% เท่านั้น เพื่อใช้ประโยชน์จากคุณสมบัติทั่วไปของ 90% ของเครื่องนั้น แม้ว่าโค้ดดังกล่าวจะไม่ใช่ "เฉพาะเครื่อง" อย่างแน่นอนก็ตาม จุดแข็งประการหนึ่งของ C แนวคิดที่ว่าโปรแกรมเมอร์ภาษา C ไม่ควรถูกคาดหวังให้ก้มตัวไปข้างหลังเพื่อรองรับข้อจำกัดของสถาปัตยกรรมซึ่งใช้เฉพาะในพิพิธภัณฑ์มานานหลายทศวรรษควรเป็นสิ่งที่ชัดเจนในตัวเอง แต่ดูเหมือนจะไม่เป็นเช่นนั้น

person supercat    schedule 26.06.2019

arrow_upward
1
arrow_downward

คุณสามารถใช้ #pragma pack(1) ได้ แต่สาเหตุที่แท้จริงก็คือคอมไพลเลอร์ได้ปรับให้เหมาะสม การเข้าถึงตัวแปรผ่านรีจิสเตอร์แบบเต็มนั้นเร็วกว่าการเข้าถึงตัวแปรเพียงเล็กน้อย

การแพ็กเฉพาะมีประโยชน์สำหรับซีเรียลไลซ์และความเข้ากันได้ของอินเตอร์คอมไพเลอร์เท่านั้น ฯลฯ

เนื่องจาก NathanOliver เพิ่มอย่างถูกต้อง สิ่งนี้อาจล้มเหลวในบางแพลตฟอร์ม .

person Michael Chourdakis    schedule 25.06.2019
comment
อาจต้องการทราบว่าสิ่งนี้มีปัญหาด้านประสิทธิภาพที่อาจเกิดขึ้นหรืออาจทำให้โค้ดใช้งานไม่ได้ในบางแพลตฟอร์ม: stackoverflow.com/questions/7793511/ - person NathanOliver; 25.06.2019
comment
ตามความรู้ของฉัน การใช้ #pragma pack ทำให้เกิดปัญหาด้านประสิทธิภาพที่อาจเกิดขึ้น และด้วยเหตุนี้จึงไม่ใช่วิธีแก้ปัญหาที่ต้องการ - person ; 25.06.2019