What architecture did you run on? D

What architecture did you run on? Did you compile with good optimization settings? I just tried your code, with and without the sort (the C++ variant) and did not find any runtime difference. Having a look at the assembler output (gcc.godbolt.org is handy for that) I could also see that there is no branch done on the if, but a cmovge is being used. When using -O2 I see a difference in speed only, but not with -O3... – PlasmaHH Jun 27 '12 at 14:10
159
@GManNickG: I did investigate a bit further, and things are "funny". With O3, both versions (sort/non sort) are the same speed (4.5) but with O2, both are different (3.1/15.7) so I looked at the O2 version. There is a branch. So gcc seems to optimize for "random data" here. To further test if it is branch prediction, I tested the O2 code not with sort, but in the creation phase I set/removed the top bit of the byte for one half, but not the other. Things are the same result here, so it really has nothing to do with the data being sorted, but with the if condition being true/false for one half. – PlasmaHH Jun 27 '12 at 14:16
102
Just to add more fun, on my CPU, when alternating the bits in the input, the branch predictor seems to be able to recognize the pattern. The same for some other alternating bit patterns. – PlasmaHH Jun 27 '12 at 14:37
17
instead of doing a complete sorting then summing, in this particular case try doing a partial sorting (i.e. partitioning) with pivot of 128, then sum from the pivot to the end without any branch statements or unreadable bitwise twiddling. – Lie Ryan Jun 28 '12 at 2:57
24
I think what's most interesting is that the Java VM executes the same code faster than the native C++ version for in original case

ผลลัพธ์ (ไทย) 1:

สถาปัตยกรรมอะไรที่คุณทำงานบน คุณไม่ได้คอมไพล์ ด้วยการตั้งค่าเพิ่มประสิทธิภาพดี ผมเพียงแค่พยายามรหัสของคุณ มี และไม่ มีการเรียงลำดับ (ตัวแปร c ++) และไม่พบความแตกต่างขณะทำงาน มีดูที่ผลผลิตมิเตอร์ (gcc.godbolt.org จะมีประโยชน์สำหรับ) อาจยังเห็นว่า มีสาขาไม่ทำบน แต่ถูกใช้เป็น cmovge เมื่อใช้ - O2 เห็นความแตกต่าง ในความเร็วเท่านั้น แต่ไม่ มี PlasmaHH - O3...-27 jun ' 12 14:10159 @GManNickG: ฉันไม่ได้ตรวจสอบบิตเพิ่มเติม และสิ่ง "ตลก" กับ O3 (ไม่ใช่/เรียงเรียง) ทั้งสองรุ่นมีความเร็วเท่ากัน (4.5) แต่ O2 ทั้งมีแตกต่างกัน (3.1/15.7) ดังนั้นผมมองรุ่น O2 มีสาขา ดังนั้น gcc น่าจะ ปรับให้เหมาะสำหรับ "ข้อมูลสุ่ม" ที่นี่ การทดสอบเพิ่มเติม หากจะทำนายสาขา ผมทดสอบรหัส O2 ไม่ได้เรียงลำดับ ในระยะสร้าง ฉันตั้ง/เอาออกบิตสูงสุดของไบต์สำหรับครึ่ง แต่ไม่อื่น ๆ สิ่งที่เป็นผลเดียวกันที่นี่ ให้มันจริง ๆ ไม่มีการเรียงลำดับข้อมูล มีถ้าเงื่อนไขเป็นจริง/เท็จสำหรับครึ่งหนึ่ง -PlasmaHH 27 Jun ' 12 ที่ 14:16102 เพื่อเพิ่มความสนุกสนานเพิ่มเติม ใน CPU ของฉัน เมื่อสลับบิตในการป้อนข้อมูล จำนวนประตูสาขาน่าจะ สามารถจดจำรูปแบบ เหมือนกันสำหรับบางอื่น ๆ สลับบิตรูปแบบ -PlasmaHH 27 Jun ' 12 ที่ 14:3717 แทนที่จะทำแบบสมบูรณ์เรียงลำดับแล้ว รวม ในกรณีนี้ได้ทำการบางส่วนเรียงลำดับ (เช่นพาร์ทิชัน) มีสาระสำคัญของ 128 แล้วผลจาก pivot ตามโดยงบสาขาหรือการอ่าน twiddling ระดับบิตใด ๆ -นอน Ryan 28 มิ.ย. 55 2:5724 ผมคิดว่า สิ่งที่น่าสนใจที่สุดคือ ว่า Java VM ดำเนินรหัสเดียวกันเร็วกว่าภาษา c ++เวอร์ชันสำหรับในกรณีที่ต้นฉบับ

ผลลัพธ์ (ไทย) 2:

สถาปัตยกรรมอะไรคุณไม่ได้ทำงานบน? คุณไม่ได้รวบรวมกับการตั้งค่าการเพิ่มประสิทธิภาพที่ดี? ฉันพยายามรหัสของคุณที่มีและไม่มีการจัดเรียง (C ++ ตัวแปร) และไม่พบความแตกต่างใด ๆ runtime มีลักษณะที่การส่งออกประกอบ (gcc.godbolt.org เป็นประโยชน์สำหรับที่) ฉันยังจะได้เห็นว่ามีสาขาทำไม่เกี่ยวกับหาก แต่ cmovge จะถูกใช้ เมื่อใช้ -O2 ผมเห็นความแตกต่างในความเร็วเพียง แต่ไม่ได้มี -O3 ... - PlasmaHH 27 มิถุนายน '12 ที่ 14:10
159
@GManNickG: ฉันไม่ตรวจสอบบิตต่อไปและสิ่งที่ "ตลก" ด้วย O3, ทั้งสองรุ่น (ประเภท / การจัดเรียงไม่) มีความเร็วเท่ากัน (4.5) แต่มี O2 ทั้งสองมีความแตกต่างกัน (3.1 / 15.7) ดังนั้นผมจึงมองไปที่รุ่น O2 มีสาขาที่เป็น GCC ดังนั้นดูเหมือนว่าจะเพิ่มประสิทธิภาพสำหรับ "ข้อมูลแบบสุ่ม" ที่นี่ ในการทดสอบต่อไปถ้ามันเป็นคำทำนายสาขาผมทดสอบรหัส O2 ไม่ได้มีการจัดเรียง แต่ในขั้นตอนการสร้างผมตั้ง / ลบออกบิตด้านบนของไบต์สำหรับครึ่งหนึ่ง แต่ไม่ได้อื่น ๆ สิ่งที่มีผลเหมือนกันนี่จึงจริงๆมีอะไรจะทำอย่างไรกับข้อมูลที่ถูกจัดเรียง แต่ถ้าเงื่อนไขเป็นจริง / เท็จครึ่งหนึ่ง - PlasmaHH 27 มิถุนายน '12 เวลา 14:16
102
เพียงเพื่อเพิ่มความสนุกสนานมากขึ้นบน CPU ของฉันเมื่อสลับบิตในการป้อนข้อมูล, ทำนายสาขาดูเหมือนว่าจะสามารถที่จะรับรู้รูปแบบ เดียวกันสำหรับบางรูปแบบสลับบิตอื่น ๆ - PlasmaHH 27 มิถุนายน '12 ที่ 14:37
17
แทนการทำเรียงลำดับสมบูรณ์แล้วข้อสรุปในกรณีนี้โดยเฉพาะลองทำเรียงลำดับบางส่วน (เช่นแบ่งพาร์ทิชัน) โดยมีสาระสำคัญของ 128 แล้วสรุปผลจากการหมุนจนจบโดยไม่ต้องงบสาขาใดก็ได้ หรือไม่สามารถอ่านค่าที่เหมาะสม twiddling - โกหกไรอัน 28 มิถุนายน '12 ที่ 02:57
24
ผมคิดว่าสิ่งที่น่าสนใจที่สุดก็คือ Java VM รันรหัสเดียวกันเร็วกว่าพื้นเมือง C ++ รุ่นสำหรับในกรณีที่เดิม

ผลลัพธ์ (ไทย) 3:

สถาปัตยกรรมอะไรที่คุณใช้ ? เธอรวบรวมกับการตั้งค่าที่เหมาะสมดี ฉันแค่พยายามรหัสของคุณที่มีและไม่มีการจัดเรียง ( C ) ) และไม่พบใด ๆขณะทำงานแตกต่าง มีลักษณะที่ประกอบผลผลิต ( gcc.godbolt.org สะดวกที่ ) ฉันยังสามารถเห็นได้ว่า ไม่มีสาขาแล้วบนถ้า แต่ cmovge จะถูกใช้ เมื่อใช้ - O2 ผมเห็นความแตกต่างในความเร็วเท่านั้นแต่ไม่ใช่กับ - O3 . . . . . . . - plasmahh จุน 27 ' 12 14 : 10

@ 159 gmannickg : ผมศึกษาเพิ่มเติมบิต และสิ่งที่เป็น " ตลก " กับ O3 ทั้งสองรุ่น ( เรียง / ไม่เรียง ) ที่ความเร็วเดียวกัน ( 4.5 ) แต่กับ O2 มันไม่เหมือนกัน ( 1 / 4 ) ดังนั้นผมมองรุ่น O2 . มีสาขา ดังนั้น GCC จะเพิ่มประสิทธิภาพสำหรับข้อมูล " สุ่ม " ที่นี่ ได้ทดสอบ ถ้าเป็นสาขาการพยากรณ์ผมทดสอบรหัส O2 ไม่เรียง แต่ในการสร้าง / ลบเฟสผมตั้งค่าบิตด้านบนของไบต์สำหรับครึ่งหนึ่ง แต่ไม่อื่น ๆ สิ่งที่จะได้ผลเหมือนกันนะ ดังนั้นมันไม่เกี่ยวกับข้อมูลถูกเรียง แต่ถ้าเงื่อนไขเป็นจริง / เท็จสำหรับครึ่ง - plasmahh จุน 27 ' 12 เวลา 14 : 16

แค่ 102 เพื่อเพิ่มความสนุกสนานมากขึ้นใน CPU ของฉันเมื่อสลับบิตในการป้อนข้อมูลสาขา ) ดูเหมือนว่าจะสามารถจำรูปแบบ เช่นเดียวกับอื่น ๆบาง สลับลวดลายนิดหน่อย - plasmahh จุน 27 ' 12 14 : 37 17

แทนที่จะทำสมบูรณ์แยกแล้วรวมในกรณีนี้โดยเฉพาะ ลองทำคัดบางส่วน ( เช่นพาร์ทิชัน ) กับเดือย 128 แล้วผลรวมจากเดือยที่จะสิ้นสุด ไม่มีสาขาหรืออ่านข้อความบิตกระดิกนิ้ว .- โกหก ไรอัน จุน 28 ' 12 ใน 2:57 24

ฉันคิดว่าสิ่งที่น่าสนใจที่สุดก็คือ Java VM รันรหัสเดียวกันได้เร็วกว่าภาษา C รุ่นสำหรับในคดีเดิม