Vinnaren i pepparkakshustävlingen!
2018-12-12, 18:08
  #1
Medlem
https://stackoverflow.com/questions/...unsorted-array

Det här är ett problem som gäller både hårdvara och mjukvara så det kanske ska vara på någon annan plats. Men ni som är här kan troligen köra både C++ och Java så det borde passa.
Enligt Agner Fog som undersökt branch prediction på djupet saknas den i Pentium men har senare blivit bättre och bättre.
De jämförelser ni ser i länken kan köras på de flesta CPUer tex Raspberry Pi där den sorterade varianten tar 68 sek jämfört med den osorterade 79 sek. Någon som har en ovanlig CPU?
Några andra tester av branch prediction i C eller C++?
Citera
2019-02-17, 04:00
  #2
Medlem
Citat:
Ursprungligen postat av grabb1948
https://stackoverflow.com/questions/...unsorted-array

Det här är ett problem som gäller både hårdvara och mjukvara så det kanske ska vara på någon annan plats. Men ni som är här kan troligen köra både C++ och Java så det borde passa.
Enligt Agner Fog som undersökt branch prediction på djupet saknas den i Pentium men har senare blivit bättre och bättre.
De jämförelser ni ser i länken kan köras på de flesta CPUer tex Raspberry Pi där den sorterade varianten tar 68 sek jämfört med den osorterade 79 sek. Någon som har en ovanlig CPU?
Några andra tester av branch prediction i C eller C++?


Alltså det här med när en CPU gör en branch split eller vad man nu ska kalla det har ju att göra med vilken kompilator som har kompilerat koden, och vilket OS som körs, och om det tillåter branch split. Vilken CPU den körs på och dessutom om hur mycket cacheminne och tillgängligt RAM den har. Ju större cache desto mera kan CPUn splitta jobbet på fler trådar/processer.
Dessutom så körs ju dagens CPUer i en multitaskingmiljö, dvs OSet, där alla möjliga andra trådar plötsligt kan störa ekekveringen av din tråd, eller trådträd. Därför kan resultatet variera ifrån körning till körning. Ett svårt område som det är svårt att få överblick över.
Man kan ju köra extremt lätta op system så att man kan få den körmiljö man önskar. En del kör ju samma kod i olika virtuella maskiner där "hårdvaran" är finjusterad, tex man kan klocka ner hastigheten lite grand på så vis med ett nedklockat system så får man mer "rättvis" jämförelse mellan olika algoritmer.

Hursomhelst så ids jag just nu inte pilla på mina Raspberries, och testköra koden, de är också utlånade ett tag Så istället så går jag iväg imorrn och köper mig en påse geléhallon (raspberries) och tröstäter en eller två påsar

Fiffigt nog så med virtuella maskiner så kan man emulera multicore CPUer och se om antalet kärnor påverkar körtiden.
Om hastigheten verkligen har kritisk betydelse så är det ett hästjobb att testa sig fram, och man bör försöka göra sig en uppskattning om hur mycket man kan snabba upp koden, ifall det ens är lönsamt att göra det. Somliga uppgifter kommer fortfarande vara riktigt tunga även i framtiden Hoppas någon här kan ge ett bättre svar på en sådan här delikat fråga.
Att detaljanalysera när koden gör en branch är tidsödande. Bla har man kört virtuella maskiner i så låg hastighet att det finns tid nog att dumpa CPU + cacheinnehåll på fil så att de kan studeras i detalj, och spela upp exekveringen i typ slowmo. Även om detta inte är mycket till svar så kanske det visar hur knepigt problemet kan vara...
Citera
2019-02-21, 13:12
  #3
Medlem
Citat:
Ursprungligen postat av DrSvenne
Alltså det här med när en CPU gör en branch split eller vad man nu ska kalla det har ju att göra med vilken kompilator som har kompilerat koden, och vilket OS som körs, och om det tillåter branch split. Vilken CPU den körs på och dessutom om hur mycket cacheminne och tillgängligt RAM den har. Ju större cache desto mera kan CPUn splitta jobbet på fler trådar/processer.
Dessutom så körs ju dagens CPUer i en multitaskingmiljö, dvs OSet, där alla möjliga andra trådar plötsligt kan störa ekekveringen av din tråd, eller trådträd. Därför kan resultatet variera ifrån körning till körning. Ett svårt område som det är svårt att få överblick över.
Man kan ju köra extremt lätta op system så att man kan få den körmiljö man önskar. En del kör ju samma kod i olika virtuella maskiner där "hårdvaran" är finjusterad, tex man kan klocka ner hastigheten lite grand på så vis med ett nedklockat system så får man mer "rättvis" jämförelse mellan olika algoritmer.

Hursomhelst så ids jag just nu inte pilla på mina Raspberries, och testköra koden, de är också utlånade ett tag Så istället så går jag iväg imorrn och köper mig en påse geléhallon (raspberries) och tröstäter en eller två påsar

Fiffigt nog så med virtuella maskiner så kan man emulera multicore CPUer och se om antalet kärnor påverkar körtiden.
Om hastigheten verkligen har kritisk betydelse så är det ett hästjobb att testa sig fram, och man bör försöka göra sig en uppskattning om hur mycket man kan snabba upp koden, ifall det ens är lönsamt att göra det. Somliga uppgifter kommer fortfarande vara riktigt tunga även i framtiden Hoppas någon här kan ge ett bättre svar på en sådan här delikat fråga.
Att detaljanalysera när koden gör en branch är tidsödande. Bla har man kört virtuella maskiner i så låg hastighet att det finns tid nog att dumpa CPU + cacheinnehåll på fil så att de kan studeras i detalj, och spela upp exekveringen i typ slowmo. Även om detta inte är mycket till svar så kanske det visar hur knepigt problemet kan vara...

Valgrind analysverktyg fungerar bra på X86 då den "ser" storleken på cache (första & sista) men för Raspberry Pi behöver man ange hur stor den är och antal vägar.
Citera
2019-02-26, 01:47
  #4
Medlem
Citat:
Ursprungligen postat av grabb1948
https://stackoverflow.com/questions/...unsorted-array

Det här är ett problem som gäller både hårdvara och mjukvara så det kanske ska vara på någon annan plats. Men ni som är här kan troligen köra både C++ och Java så det borde passa.
Enligt Agner Fog som undersökt branch prediction på djupet saknas den i Pentium men har senare blivit bättre och bättre.
De jämförelser ni ser i länken kan köras på de flesta CPUer tex Raspberry Pi där den sorterade varianten tar 68 sek jämfört med den osorterade 79 sek. Någon som har en ovanlig CPU?
Några andra tester av branch prediction i C eller C++?

För Raspberry PI så skulle även andra faktorer kunna spela in, om du inte har write-allocate, (https://www.raspberrypi.org/forums/v...c.php?t=144579) så kommer du åka på en cache-miss första gången du accessar datan, om du sorterar innan så kommer sorteringen värma upp cachen med relevant data. (Om datan får plats i cachen osv).

Sen beror det ju mycket på vad kompilatorn gör av det hela, som tråden du länkar nämner så fixar en cmove biffen för så pass korta conditional block. Och hittar du någon mer exotisk CPU så skulle de potentiellt kunna optimera bort branches över större block, https://en.wikipedia.org/wiki/Predic...rchitecture%29
utan att använda branch-prediction.

Med det sagt så är branch-mispredict väldigt dyrt, så om du mispredictar något 50% av gångerna som den där kodsnutten skulle kunna göra naivt så kommer du få usel performance.

Kan varmt rekommendera: https://www.coursera.org/learn/comparch
om du är intresserad av ämnet.
Citera

Stöd Flashback

Flashback finansieras genom donationer från våra medlemmar och besökare. Det är med hjälp av dig vi kan fortsätta erbjuda en fri samhällsdebatt. Tack för ditt stöd!

Stöd Flashback