กลับไปหน้าบทความ

อ่าน 5 นาที

อุปกรณ์ของดัฟฟ์

C (ภาษาโปรแกรม)/นิทานพื้นบ้านการเขียนโปรแกรมคอมพิวเตอร์/ภาษาเขียนโปรแกรมชาวบ้าน/ซอร์สโค้ด

ในภาษาการเขียนโปรแกรมC อุปกรณ์ของดัฟฟ์เป็นวิธีการคลายลูป ด้วยตนเอง โดยการสลับโครงสร้างทางไวยากรณ์สองอย่างของภาษา C ได้แก่ ลูป do - whileและคำสั่ง...

อุปกรณ์ของดัฟฟ์

ในภาษาการเขียนโปรแกรมC อุปกรณ์ของดัฟฟ์เป็นวิธีการคลายลูป ด้วยตนเอง โดยการสลับโครงสร้างทางไวยากรณ์สองอย่างของภาษา C ได้แก่ ลูป do - whileและคำสั่ง switchการค้นพบนี้ได้รับการยกย่องให้แก่ทอม ดัฟฟ์ในเดือนพฤศจิกายนปี 1983 ขณะที่ดัฟฟ์ทำงานให้กับลูคัสฟิล์มและใช้มันเพื่อเร่งความเร็วโปรแกรมแอนิเมชั่นแบบเรียลไทม์

การคลายลูป (Loop unrolling) พยายามลดภาระของการแยกเงื่อนไขที่จำเป็นในการตรวจสอบว่าลูปเสร็จสิ้นแล้วหรือไม่ โดยการเรียกใช้กลุ่มของเนื้อหาลูปต่อรอบ เพื่อจัดการกับกรณีที่จำนวนรอบไม่สามารถหารลงตัวด้วยค่าเพิ่มขึ้นของลูปที่คลายแล้ว เทคนิคทั่วไปในหมู่ นักเขียนโปรแกรม ภาษาแอสเซมบลีคือการกระโดดเข้าไปตรงกลางของเนื้อหาลูปที่คลายแล้วโดยตรงเพื่อจัดการกับส่วนที่เหลือ[ 1 ] Duff ได้นำเทคนิคนี้ไปใช้ในภาษา C โดยใช้คุณสมบัติการกระโดด ผ่านป้ายกำกับกรณี (case label fall-through ) ของภาษา C เพื่อกระโดดเข้าไปในเนื้อหาที่คลายแล้ว[ 2 ]

เทคนิคของดัฟฟ์

Duff กำลังคัดลอกจำนวนเต็ม 16 บิตที่ไม่มีเครื่องหมาย ("shorts" ในการใช้งาน C ส่วนใหญ่) จากอาร์เรย์ไปยัง รีจิสเตอร์ เอาต์พุตที่แมปหน่วยความจำซึ่งในภาษา C เรียกว่าตัวชี้ เขาต้องการเพิ่มประสิทธิภาพโค้ด C ของ K&Rต่อไปนี้: [ 3 ] [ 4 ]

ส่ง( ถึง, จาก, จำนวน) ลงทะเบียนshort * ถึง, * จาก; ลงทะเบียนจำนวน; { ทำ{ /* สมมติว่าจำนวน > 0 */ * ถึง= * จาก++ ; } ในขณะที่( -- จำนวน> 0 ); }

ในภาษา C ของ K&Rนั้น ประเภทที่ไม่ระบุใดๆ จะใช้ค่าเริ่มต้นเป็น `null` intรวมถึงตัวแปรต่างๆ เช่น ` null` countและประเภทการส่งคืนค่าของ `null` ด้วย คำหลัก send()` register`ใช้เพื่อแนะนำว่าควรเก็บตัวแปรไว้ในรีจิสเตอร์ของ CPU เพื่อหลีกเลี่ยงการใช้หน่วยความจำฟังก์ชันไม่สามารถส่งคืนค่า `null` ได้เนื่องจากยังไม่ใช่คำหลักที่สงวนไว้แต่ฟังก์ชันหลายฟังก์ชันก็ทำเช่นนั้นได้โดยการละเว้นคำสั่ง `return` ซึ่งเป็นคำสั่งเสริม รูปแบบการเขียนโค้ดนี้สามารถแสดงได้ในต้นแบบภาษา C สมัยใหม่ในรูปแบบ `null` แต่ไม่เทียบเท่ากับรูปแบบการเขียนโค้ดสมัยใหม่voidreturnvoidsend(short*to,short*from,intcount);

โค้ดนี้สมมติว่าค่าที่ส่งเข้ามานั้นcountมากกว่าศูนย์ เนื่องจากตำแหน่งเอาต์พุตเป็นรีจิสเตอร์ที่แมปกับหน่วยความจำ ตัวชี้toจึงไม่เพิ่มค่าขึ้น เหมือนกับการคัดลอกข้อมูลจากหน่วยความจำหนึ่งไปยังอีกหน่วยความจำหนึ่ง

ถ้าcountหารด้วยแปดลงตัวเสมอ การคลี่ลูปนี้ออกแปดครั้งจะได้ผลลัพธ์ดังต่อไปนี้:

ส่ง( ถึง, จาก, จำนวน) ลงทะเบียนshort * ถึง, * จาก; ลงทะเบียนจำนวน; { ลงทะเบียนn = จำนวน/ 8 ; ทำซ้ำ{ * ถึง= * จาก++ ; * ถึง= * จาก++ ; * ถึง= * จาก++ ; * ถึง= * จาก++ ; * ถึง= * จาก++ ; * ถึง= * จาก++ ; * ถึง= * จาก++ ; } ในขณะที่( -- n > 0 ) ; }

ดัฟฟ์ตระหนักว่าในการจัดการกรณีที่หารcountด้วยแปดไม่ลงตัว เทคนิคการกระโดดเข้าไปในตัวลูปของโปรแกรมเมอร์แอสเซมบลีสามารถนำไปใช้ได้โดยการสอดแทรกโครงสร้างของคำสั่ง switch และลูป โดยวางcaseป้ายกำกับของ switch ไว้ที่จุดของตัวลูปที่สอดคล้องกับเศษเหลือของcount / 8: [ 1 ]

ส่ง( ถึง, จาก, จำนวน) ลงทะเบียนshort * ถึง, * จาก; ลงทะเบียนจำนวน; { ลงทะเบียนn = ( จำนวน+ 7 ) / 8 ; สวิตช์( จำนวน% 8 ) { กรณี0 : ทำ{ * ถึง= * จาก++ ; กรณี7 : * ถึง= * จาก++ ; กรณี6 : * ถึง= * จาก++ ; กรณี5 : * ถึง= * จาก++ ; กรณี4 : * ถึง= * จาก++ ; กรณี3 : * ถึง= * จาก++ ; กรณี2 : * ถึง= * จาก++ ; กรณี1 : * ถึง= * จาก++ ; } ในขณะที่( -- n > 0 ); } }

อุปกรณ์ของดัฟฟ์สามารถนำไปใช้กับห่วงที่คลี่ออกได้ทุกขนาด ไม่ใช่แค่แปดขนาดอย่างในตัวอย่างข้างต้น

กลไก

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

  1. ข้อกำหนดที่ผ่อนปรนของswitchคำสั่งในคำจำกัดความของภาษา ในขณะที่อุปกรณ์นี้ถูกประดิษฐ์ขึ้น นี่คือฉบับแรกของภาษาการเขียนโปรแกรม Cซึ่งกำหนดเพียงว่าส่วนเนื้อหาของคำสั่งswitchต้องเป็นคำสั่งที่ถูกต้องตามหลักไวยากรณ์ (คำสั่งประกอบ) ซึ่งcaseป้ายกำกับสามารถปรากฏนำหน้าคำสั่งย่อยใดๆ ก็ได้ ประกอบกับข้อเท็จจริงที่ว่า ในกรณีที่ไม่มีคำbreakสั่ง การควบคุมการไหลของโปรแกรมจะไหลผ่านจากคำสั่งที่ควบคุมโดยcaseป้ายกำกับหนึ่งไปยังคำสั่งที่ควบคุมโดยป้ายกำกับถัดไป นั่นหมายความว่าโค้ดระบุลำดับการcountคัดลอกจากที่อยู่แหล่งที่มาตามลำดับไปยังพอร์ตเอาต์พุตที่แมปหน่วยความจำ
  2. ความสามารถในการกระโดดเข้าไปตรงกลางของลูปในภาษาซี

สิ่งนี้นำไปสู่สิ่งที่Jargon Fileเรียกว่า "การใช้ fall through ที่น่าทึ่งที่สุดเท่าที่เคยเห็นใน C" [ 5 ] fall-through เริ่มต้นของ C ในคำสั่ง case เป็นหนึ่งในคุณสมบัติที่ถกเถียงกันมากที่สุดมานานแล้ว Duff เองก็กล่าวว่า "โค้ดนี้ก่อให้เกิดข้อโต้แย้งบางอย่างในการถกเถียงนั้น แต่ผมไม่แน่ใจว่ามันเห็นด้วยหรือคัดค้าน" [ 5 ]

แม้ว่าวิธีการของ Duff จะใช้ได้ในภาษา C แต่ก็ขัดกับหลักเกณฑ์ทั่วไปของภาษา C เช่นหลักเกณฑ์ MISRAคอมไพเลอร์บางตัว (เช่นCompCert ) ถูกจำกัดด้วยหลักเกณฑ์ดังกล่าว ดังนั้นจึงปฏิเสธวิธีการของ Duff เว้นแต่จะได้รับคำสั่งเป็นอย่างอื่นโดยเฉพาะ

คำอธิบายแบบย่อ

เวอร์ชันที่เทียบเท่ากันในเชิงฟังก์ชันและแยกส่วนswitchwhile
ส่ง( ถึง, จาก, จำนวน) ลงทะเบียนshort * ถึง, * จาก; ลงทะเบียนจำนวน; { ลงทะเบียนn = ( จำนวน+ 7 ) / 8 ; สวิตช์( จำนวน% 8 ) { กรณี0 : * ถึง= * จาก++ ; กรณี7 : * ถึง= * จาก++ ; กรณี6 : * ถึง= * จาก++ ; กรณี5 : * ถึง= * จาก++ ; กรณี4 : * ถึง= * จาก++ ; กรณี3 : * ถึง= * จาก++ ; กรณี2 : * ถึง= * จาก++ ; กรณี1 : * ถึง= * จาก++ ; } ในขณะที่( -- n > 0 ) { * ถึง= * จาก++ ; * ถึง= * จาก++ ; * ถึง= * จาก++ ; * ถึง= * จาก++ ; * ถึง= * จาก++ ; * ถึง= * จาก++ ; * ถึง= * จาก++ ; } }

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

อุปกรณ์ของดัฟฟ์นำเสนอวิธีแก้ปัญหาโดยการดำเนินการวนซ้ำที่เหลือก่อน จากนั้นจึงวนซ้ำคำสั่งที่คล้ายกันจำนวนครั้งเท่าที่จำเป็นซึ่งเป็นจำนวนเท่าของแปด เพื่อกำหนดจำนวนการวนซ้ำที่เหลือ โค้ดจะคำนวณจำนวนการวนซ้ำทั้งหมดโมดูลแปดก่อน ตามเศษที่เหลือนี้การทำงานของโปรแกรมจะกระโดดไปยังcaseคำสั่งที่ตามด้วยจำนวนการวนซ้ำที่ต้องการพอดีเมื่อทำเช่นนี้เสร็จแล้ว ทุกอย่างก็ตรงไปตรงมา: โค้ดจะดำเนินการวนซ้ำกลุ่มคำสั่งแปดคำสั่งต่อไป ซึ่งเป็นไปได้เนื่องจากจำนวนการวนซ้ำที่เหลือเป็นจำนวนเท่าของแปด[ 1 ]

วิธีการของดัฟฟ์ช่วยให้การคลายลูปกระชับขึ้นโดยใช้คีย์เวิร์ด `case` ทั้งภายในและภายนอกลูปซึ่งเป็นเรื่องผิดปกติเพราะโดยทั่วไปแล้วเนื้อหาของคำสั่ง `case` จะถูกมองว่าเป็นบล็อกของโค้ดที่ซ้อนอยู่ภายในคำสั่ง `case` และผู้อ่านมักจะคาดหวังว่ามันจะสิ้นสุดก่อนคำสั่ง `case` ถัดไป แต่ตามข้อกำหนดของภาษาซีแล้ว ไม่จำเป็นต้องเป็นเช่นนั้น ที่จริงแล้ว คำสั่ง `case` สามารถปรากฏที่ใดก็ได้ภายใน บล็อกโค้ด `switch`และที่ระดับความลึกใดก็ได้ การทำงานของโปรแกรมจะข้ามไปยังคำสั่งถัดไปโดยอัตโนมัติ ไม่ว่าคำสั่งนั้นจะอยู่ที่ใดก็ตาม

ผลงาน

คอมไพเลอร์หลายตัวจะปรับแต่งการสลับไปใช้ตารางสาขาเช่นเดียวกับที่ทำในภาษาแอสเซมบลี

ความเร็วที่เพิ่มขึ้นหลักๆ เมื่อเทียบกับลูปแบบธรรมดา มาจากการคลายลูป (loop unwinding ) ซึ่งช่วยลดจำนวนการแยกสาขา (branch) ที่เกิดขึ้น ซึ่งใช้ทรัพยากรการคำนวณสูงเนื่องจากจำเป็นต้องล้าง( flush) และ ทำให้ไปป์ไลน์คำสั่งหยุดชะงัก (stall )คำสั่งนี้ใช้เพื่อจัดการข้อมูลส่วนที่เหลือที่ไม่สามารถหารลงตัวด้วยจำนวนการดำเนินการที่คลายลูป (ในตัวอย่างนี้ มีการคลายลูปแบบ short move แปดครั้ง ดังนั้นจึงจัดการ short move เพิ่มเติมอีก1-7ครั้งโดยอัตโนมัติ)switchswitch

การจัดการส่วนที่เหลือโดยอัตโนมัตินี้อาจไม่ใช่ทางออกที่ดีที่สุดสำหรับทุกระบบและคอมไพเลอร์ในบางกรณี การใช้ลูปสองลูปอาจเร็วกว่า (ลูปหนึ่งที่คลายออกเพื่อทำการคัดลอกหลัก และลูปที่สองเพื่อจัดการส่วนที่เหลือ) ปัญหาดูเหมือนจะขึ้นอยู่กับความสามารถของคอมไพเลอร์ในการเพิ่มประสิทธิภาพอุปกรณ์อย่างถูกต้อง นอกจากนี้ยังอาจรบกวนการทำงานแบบไปป์ไลน์และการคาดการณ์สาขาบนสถาปัตยกรรมบางอย่าง[ 6 ]เมื่อมีการลบอินสแตนซ์จำนวนมากของอุปกรณ์ของ Duff ออกจากXFree86 Server ในเวอร์ชัน 4.0 ประสิทธิภาพก็ดีขึ้นและขนาดของไฟล์ปฏิบัติการลดลงอย่างเห็นได้ชัด[ 7 ]ดังนั้น ก่อนที่จะนำการเพิ่มประสิทธิภาพโปรแกรม ใดๆ ไปใช้ ควรทำการวัดประสิทธิภาพหรือตรวจสอบผลลัพธ์ที่คอมไพล์แล้ว เพื่อตรวจสอบว่าทำงานได้ตามที่คาดหวังบนสถาปัตยกรรมเป้าหมาย ระดับการเพิ่มประสิทธิภาพ และคอมไพเลอร์ นอกจากนี้ ควรพิจารณาถึงความเสี่ยงของโค้ดที่เพิ่มประสิทธิภาพแล้วที่ใช้งานบนแพลตฟอร์มต่างๆ ซึ่งอาจไม่ใช่ตัวเลือกที่เร็วที่สุดเสมอไป 

เพื่อวัตถุประสงค์ในการคัดลอกหน่วยความจำไปยังหน่วยความจำ (ซึ่งดังที่กล่าวไว้ข้างต้น ไม่ใช่การใช้งานดั้งเดิมของอุปกรณ์ของดัฟฟ์) ไลบรารีC มาตรฐานมีฟังก์ชัน[ 8 ]ซึ่งจะทำงานได้ไม่แย่ไปกว่าเวอร์ชันการคัดลอกหน่วยความจำไปยังหน่วยความจำของโค้ดนี้ และอาจมีการปรับแต่งเฉพาะสถาปัตยกรรมที่ทำให้เร็วขึ้นอย่างมาก[ 9 ] [ 10 ]memcpy

ดูเพิ่มเติม

อ่านเพิ่มเติม

  • คำอธิบายและอีเมลต้นฉบับโดย Duff จาก Lysator
  • โครูทีนของไซมอน ทาแธมในภาษาซีใช้เทคนิค switch/case แบบเดียวกัน
  • Protothreads ของ Adam Dunkels - เธรดน้ำหนักเบาแบบไม่ใช้สแต็กในภาษา Cก็ใช้คำสั่ง switch/case แบบซ้อนกันเช่นกัน (ดูเพิ่มเติมที่ เธรดน้ำหนักเบาที่สุด Protothreads )
  • เทคนิค ของ Pigeonเกี่ยวข้องกับเรื่องนี้ โดยเป็นการผสมผสานคำสั่ง switch/case และ if/else เข้าด้วยกัน
ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Duff%27s_device&oldid=1358313437 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ อุปกรณ์ของดัฟฟ์

ในภาษาการเขียนโปรแกรมC อุปกรณ์ของดัฟฟ์เป็นวิธีการคลายลูป ด้วยตนเอง โดยการสลับโครงสร้างทางไวยากรณ์สองอย่างของภาษา C ได้แก่ ลูป do - whileและคำสั่ง...

เทคนิคของดัฟฟ์

Duff กำลังคัดลอกจำนวนเต็ม 16 บิตที่ไม่มีเครื่องหมาย ("shorts" ในการใช้งาน C ส่วนใหญ่) จากอาร์เรย์ไปยัง รีจิสเตอร์ เอาต์พุตที่แมปหน่วยความจำ ซึ่งในภาษา C เรียกว่า ตัวชี้ เขาต้องการเพิ่มประสิทธิภาพโค้ด C ของ K&R ต่อไปนี้: [ 3 ] [ 4 ]

กลไก

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

คำอธิบายแบบย่อ

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