Permalänk

Branch prediction (C++ och Java)

Om man har en lista med slumptal från 0 till 255 och alla tal ska jämföras med 128 så borde det inte ha någon betydelse om talen är sorterade eller inte. Men det gör det! CPUn spekulerar....
Sorterad array snabbare än osorterad (C++ och Java)

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 är den enkel 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 Pi3 (med g++ -O3 filnamn) 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++?

Permalänk
Hedersmedlem
Skrivet av Greyguy1948:

Det här är ett problem

På vilket sätt då?

Permalänk
Medlem
Skrivet av pv2b:

På vilket sätt då?

Skulle nog säga att det snarare är något att ha i bakhuvudet när man skriver koden. Har man en stor array som man behöver itterera och aggera på utifrån något condition så kanske man tjänar på att sortera den först.

I språk med pekare/referenser så behöver man inte sortera om den initiala arrayen heller utan akn skapa en array med pekare till elementen i den ursprungliga arrayen, men sorterad på det som man kommer använda som condition i sin if-sats.

Om arrayen i fråga är något som skall leva länge, kanske under hela programmets livslängd, så kan genereringen av denna sorterade variant, eller flera varianter om det behövs, vara en del av uppstart och inte påverka prestandan när programmet väl kör.

Visa signatur

Huvudriggen är en Gigabyte Aorus Xtreme | 128gb DDR5 6000 | Ryzen 7950X | 3080Ti
Utöver det är det för många datorer, boxar och servar för att lista :P

Permalänk
Hedersmedlem
Skrivet av inquam:

Skulle nog säga att det snarare är något att ha i bakhuvudet när man skriver koden. Har man en stor array som man behöver itterera och aggera på utifrån något condition så kanske man tjänar på att sortera den först.

Tja, jag vet inte. Borde det inte vara snabbare att splitta upp i två arrayer istället för att sortera arrayen i fråga? Ska slänga ihop lite kod och se om jag kan få lite resultat.

Permalänk
Medlem
Skrivet av pv2b:

På vilket sätt då?

Om det inte var ett problem som man gärna undviker så hade vi väl inte fått meltdown och liknande på halsen?

Permalänk
Medlem
Skrivet av inquam:

Skulle nog säga att det snarare är något att ha i bakhuvudet när man skriver koden. Har man en stor array som man behöver itterera och aggera på utifrån något condition så kanske man tjänar på att sortera den först.

I språk med pekare/referenser så behöver man inte sortera om den initiala arrayen heller utan akn skapa en array med pekare till elementen i den ursprungliga arrayen, men sorterad på det som man kommer använda som condition i sin if-sats.

Om arrayen i fråga är något som skall leva länge, kanske under hela programmets livslängd, så kan genereringen av denna sorterade variant, eller flera varianter om det behövs, vara en del av uppstart och inte påverka prestandan när programmet väl kör.

Men i fallet med att skapa en kopia med sorterade referenser och låter objekten ligga kvar på samma plats i minnet så tappar man väl cachelokaliteten? Och dessa cachemissar ger ett större straff i prestanda?

Permalänk
Medlem
Skrivet av pv2b:

Tja, jag vet inte. Borde det inte vara snabbare att splitta upp i två arrayer istället för att sortera arrayen i fråga? Ska slänga ihop lite kod och se om jag kan få lite resultat.

Beror ju självklart på. Men jag utgår ifrån att arrayen med data är ett dataset som man har som helhelt och andra delar tex jobbar på hela arrayen oberoende av if-satsen som kanske är intressant i annat ställe av programet. Om detta inte är ett krav utan man kan dela upp sina data hur man vill osv så är det självklart bäst att optimera den från start för exakt den användning programet har för den. Men det riskerar ett bli mer statiskt.

Visa signatur

Huvudriggen är en Gigabyte Aorus Xtreme | 128gb DDR5 6000 | Ryzen 7950X | 3080Ti
Utöver det är det för många datorer, boxar och servar för att lista :P

Permalänk
Hedersmedlem
Skrivet av pv2b:

Tja, jag vet inte. Borde det inte vara snabbare att splitta upp i två arrayer istället för att sortera arrayen i fråga? Ska slänga ihop lite kod och se om jag kan få lite resultat.

Kod:

// ConsoleApplication4.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <algorithm> #include <ctime> #include <iostream> const int ITERATIONS = 100000; void test(const char *desc, int *data, unsigned arraySize) { // Test clock_t start = clock(); long long sum = 0; for (unsigned i = 0; i < ITERATIONS; ++i) { // Primary loop for (unsigned c = 0; c < arraySize; ++c) { if (data[c] >= 128) sum += data[c]; } } double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC; std::cout << desc << ": " << elapsedTime << std::endl; std::cout << "sum = " << sum << std::endl; } int main() { // Generate data (f = filtered) const unsigned arraySize = 32768; unsigned fArraySize = 0; int data[arraySize]; int fData[arraySize]; for (unsigned c = 0; c < arraySize; ++c) data[c] = std::rand() % 256; for (int i = 0; i < arraySize; i++) if (data[i] >= 128) fData[fArraySize++] = data[i]; test("filtered", fData, fArraySize); test("unsorted", data, arraySize); std::sort(data, data + arraySize); test("sorted", data, arraySize); return 0; }

Kompilator: Microsoft Visual Studio 2017.
Processor: AMD Ryzen 5 1600

Testresultat med optimering avstängd (/Od):

filtered: 4.726 sum = 312275400000 unsorted: 24.831 sum = 312275400000 sorted: 8.992 sum = 312275400000

Testresultat med optimering på (/O2):

filtered: 0.826 sum = 312275400000 unsorted: 1.027 sum = 312275400000 sorted: 1.021 sum = 312275400000

Min slutats är att "sortera arrayen" inte är en generellt bra lösning på den här typen av problem. Däremot är det bra att fundera på hur man lagrar och itererar över sin data.

Och att slå på kompilatoroptimeringar. Och att moderna kompilatorer/CPU:er är rätt smarta.

Permalänk
Hedersmedlem
Skrivet av acura:

Om det inte var ett problem som man gärna undviker så hade vi väl inte fått meltdown och liknande på halsen?

Det här har inget med spectre/meltdown att göra.

Permalänk
Medlem

@pv2b: Angående dessa 3 olika typer anrop av "test()", om du upprepar samma typ av anrop "test()" 10ggr eller mer på rad efter varandra innan du byter till nästa typ av test() anrop , blir det samma resultat varje gång då?
Har inte Ryzen själv men tänker på detta med AMDs "neural net branch prediction" som kanske anpassar sig?
Vet inte om denna neural prefetch hjälper till vid branch prediction dock men kan tänka mig hjälpa till vid bransch miss kanske?, bara nyfiken

Permalänk
Skrivet av pv2b:

Det här har inget med spectre/meltdown att göra.

Om det bara vore ett mjukvaroproblem men om CPUn spekulerar kan det mycket väl ha med spectre/meltdown att göra.
De mest primitiva CPUerna gör allt i ordning och de har inga problem med spectre/meltdown.
Men sådana är ovanliga idag

Permalänk
Datavetare
Skrivet av HappyPie:

@pv2b: Angående dessa 3 olika typer anrop av "test()", om du upprepar samma typ av anrop "test()" 10ggr eller mer på rad efter varandra innan du byter till nästa typ av test() anrop , blir det samma resultat varje gång då?
Har inte Ryzen själv men tänker på detta med AMDs "neural net branch prediction" som kanske anpassar sig?
Vet inte om denna neural prefetch hjälper till vid branch prediction dock men kan tänka mig hjälpa till vid bransch miss kanske?, bara nyfiken

Har inget med saken att göra. Med koden postad ovan bygg med g++ 7.3 (Ubuntu 18.04)

Ryzen 2700X

filtered: 0.26316 sum = 314931600000 unsorted: 0.505868 sum = 314931600000 sorted: 0.505758 sum = 314931600000

i7-8559U

filtered: 0.186469 sum = 314931600000 unsorted: 0.365815 sum = 314931600000 sorted: 0.365691 sum = 314931600000

Med optimeringar påslaget finns ingen relevant skillnad oavsett CPU.

Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Permalänk
Hedersmedlem
Skrivet av Yoshman:

Har inget med saken att göra. Med koden postad ovan bygg med g++ 7.3 (Ubuntu 18.04)
...
Med optimeringar påslaget finns ingen relevant skillnad oavsett CPU.

Tack för att du testade detta! Jag hade faktiskt samma fundering som HappyPie.

Permalänk
Medlem
Skrivet av acura:

Om det inte var ett problem som man gärna undviker så hade vi väl inte fått meltdown och liknande på halsen?

Det är två helt olika saker, meltdown mm är inte pga tekniken i sig utan i implementationen där man inte kasserade oanvända grenar mm.
För relativt lite yta får du markant ökad effektivt och hastighet.

Skickades från m.sweclockers.com

Visa signatur

"One is always considered mad, when one discovers something that others cannot grasp."
- Ed Wood

Permalänk
Medlem
Skrivet av acura:

Men i fallet med att skapa en kopia med sorterade referenser och låter objekten ligga kvar på samma plats i minnet så tappar man väl cachelokaliteten? Och dessa cachemissar ger ett större straff i prestanda?

Det är iofs en intressant observation som jag missade. Att inte kunna nyttja cachelines kan förmodligen ha en stor effekt (beroende på storleken man jobbar med), om inte kompilatorn är smart nog att optimera det på något sätt när elementen man refererar till alla ursprungligen är medlemmar i samma array.
Det skulle det faktiskt vara lite intressant att testa.

Visa signatur

Huvudriggen är en Gigabyte Aorus Xtreme | 128gb DDR5 6000 | Ryzen 7950X | 3080Ti
Utöver det är det för många datorer, boxar och servar för att lista :P

Permalänk
Medlem
Skrivet av Greyguy1948:

Om det bara vore ett mjukvaroproblem men om CPUn spekulerar kan det mycket väl ha med spectre/meltdown att göra.
De mest primitiva CPUerna gör allt i ordning och de har inga problem med spectre/meltdown.
Men sådana är ovanliga idag

Meltdown och Spectre är inte enbart mjukvara nej men det är inte "spekulationen" som CPUn gör i sig som är problemet utan hur man efter hanterat resterna man inte använder och minnet de ligger i. Implementationen är gjord automatiskt för det är för mycket för vanliga människor att hålla reda på och räkna på när en dator kan göra det mer effektivt, problemet är dock att verktygen man använt inte haft "regler" för programmet som designat det utan enbart försökt få det så effektivt och snabbt som möjligt så det har öppnat luckor.
Därav blev det sådana slowdowns när man patchat det pga att man flyttade mycket av den datan till ett säkrare minne men som ligger längre ifrån och därmed tog längre tid att hantera.

Visa signatur

"One is always considered mad, when one discovers something that others cannot grasp."
- Ed Wood

Permalänk
99:e percentilen

Jag tyckte detta var intressant, så jag skrev ett liknande test i Haskell. (Det går inte att jämföra direkt med de länkade C++- och Java-programmen, då det inte gör samma sak.)

Klicka för mer information

Benchmark

import System.Random (getStdRandom, randomR) import Control.Monad (replicateM) import Criterion.Main (nf, bench, defaultConfig, runMode) import Criterion.Main.Options (Mode(Run), MatchType(Glob)) import Data.Sort (sort) import System.Environment (getArgs) import Safe (headMay) import Data.Maybe (fromMaybe) import Text.Read (readMaybe) defaultListSize :: Int defaultListSize = 32768 sumOfLarger :: [Int] -> Int sumOfLarger = sum . filter (>= 128) randomByte :: IO Int randomByte = getStdRandom $ randomR (0, 255) main :: IO () main = do args <- getArgs let listSize = fromMaybe defaultListSize $ readMaybe =<< headMay args ints <- replicateM listSize randomByte let sortedInts = sort ints let info = " (" ++ show listSize ++ " ints)" runMode (Run defaultConfig Glob []) [ bench ("DEFAULT" ++ info) (nf sumOfLarger ints) , bench ("SORTED" ++ info) (nf sumOfLarger sortedInts) ]

Testskript

#!/usr/bin/env bash rm -f benchmarks.hi benchmarks.o benchmarks benchmarks.exe set -x ghc $1 benchmarks.hs ./benchmarks $2

Visa mer

Programmet tar som argument storleken på den lista som ska skapas. Om ingen storlek anges blir listan 32768 element lång. För mätning och analys används Criterion. Haskell använder lat evaluering, så det är svårare att resonera kring prestanda i det än i C++, och jag är ingen expert på området. Peka gärna ut eventuella fel!

GHC kan fås att utföra olika grader av optimering. Jag har testat med ingen optimering (-O0) och med "every non-dangerous optimisation" (-O2). Förutom 32 768 element har jag även testat 1 048 576 stycken. Jag har kompilerat med GHC 8.6.3 och kört testerna i Git Bash.

Testsystem

  • CPU: 5930K @ 4,0 GHz

  • RAM: 32 GiB @ 2666 MHz

  • Moderkort: Asus X99‑Pro

  • OS: Windows 10 (1809)

Resultat utan optimeringar

Klicka för mer information

$ ./test -O0 32768 + ghc -O0 benchmarks.hs [1 of 1] Compiling Main ( benchmarks.hs, benchmarks.o ) Linking benchmarks.exe ... + ./benchmarks 32768 benchmarking DEFAULT (32768 ints) time 1.079 ms (1.073 ms .. 1.085 ms) 1.000 R² (1.000 R² .. 1.000 R²) mean 1.076 ms (1.074 ms .. 1.080 ms) std dev 9.768 μs (7.382 μs .. 13.86 μs) benchmarking SORTED (32768 ints) time 937.3 μs (934.7 μs .. 941.3 μs) 1.000 R² (1.000 R² .. 1.000 R²) mean 939.0 μs (936.3 μs .. 942.6 μs) std dev 10.54 μs (7.959 μs .. 13.61 μs)

$ ./test -O0 1048576 + ghc -O0 benchmarks.hs [1 of 1] Compiling Main ( benchmarks.hs, benchmarks.o ) Linking benchmarks.exe ... + ./benchmarks 1048576 benchmarking DEFAULT (1048576 ints) time 88.77 ms (84.18 ms .. 94.01 ms) 0.995 R² (0.989 R² .. 0.999 R²) mean 88.89 ms (85.70 ms .. 91.48 ms) std dev 5.043 ms (3.407 ms .. 7.925 ms) variance introduced by outliers: 18% (moderately inflated) benchmarking SORTED (1048576 ints) time 84.49 ms (81.18 ms .. 87.66 ms) 0.996 R² (0.988 R² .. 0.999 R²) mean 82.52 ms (79.54 ms .. 84.65 ms) std dev 4.373 ms (2.433 ms .. 7.495 ms)

Visa mer

Resultat med optimeringar

Klicka för mer information

$ ./test -O2 32768 + ghc -O2 benchmarks.hs [1 of 1] Compiling Main ( benchmarks.hs, benchmarks.o ) Linking benchmarks.exe ... + ./benchmarks 32768 benchmarking DEFAULT (32768 ints) time 170.5 μs (170.4 μs .. 170.7 μs) 1.000 R² (1.000 R² .. 1.000 R²) mean 170.6 μs (170.5 μs .. 170.7 μs) std dev 286.5 ns (213.2 ns .. 454.3 ns) benchmarking SORTED (32768 ints) time 85.59 μs (85.57 μs .. 85.61 μs) 1.000 R² (1.000 R² .. 1.000 R²) mean 85.60 μs (85.58 μs .. 85.62 μs) std dev 63.02 ns (46.25 ns .. 87.69 ns)

$ ./test -O2 1048576 + ghc -O2 benchmarks.hs [1 of 1] Compiling Main ( benchmarks.hs, benchmarks.o ) Linking benchmarks.exe ... + ./benchmarks 1048576 benchmarking DEFAULT (1048576 ints) time 6.217 ms (6.208 ms .. 6.227 ms) 1.000 R² (1.000 R² .. 1.000 R²) mean 6.211 ms (6.207 ms .. 6.217 ms) std dev 15.32 μs (10.67 μs .. 21.33 μs) benchmarking SORTED (1048576 ints) time 3.579 ms (3.565 ms .. 3.594 ms) 1.000 R² (1.000 R² .. 1.000 R²) mean 3.577 ms (3.573 ms .. 3.583 ms) std dev 15.20 μs (9.854 μs .. 21.95 μs)

Visa mer

Sammanfattning

Utan optimeringar var skillnaden mellan osorterad och sorterad lista liten. Med optimeringar aktiverade var det sorterade testet dubbelt så snabbt för den korta listan (och ca 75 % snabbare för den långa). Observera att siffrorna ovan inte inkluderar tiden det tar att sortera listan; när jag säger dubbelt så snabbt menar jag givet att listan redan är sorterad.

Visa signatur

Skrivet med hjälp av Better SweClockers

Permalänk
Datavetare

Testade mäta på lite mer "exotiska" CPUer, finns ett rätt uppenbart samband...

800 MHz Cortex A9, d.v.s. vad man hittade i en "smart"mobil för ungefär ett decennium sedan.

sum = 315783500000 unsorted: 51.016 sum = 315783500000 sorted: 51.016 sum = 315783500000

1,2 GHz PowerPC e500 (högre klockad variant av CPUn som robotarna på som är på Mars använder)

filtered: 9.95 sum = 315793800000 unsorted: 28.7 sum = 315793800000 sorted: 19.8 sum = 315793800000

RPi3 (ARM Cortex A53)

filtered: 8.53 sum = 315793800000 unsorted: 27.7 sum = 315793800000 sorted: 16.4 sum = 315793800000

Atom Silvermont J5005

filtered: 0.846 sum = 314931600000 unsorted: 1.65 sum = 314931600000 sorted: 1.65 sum = 314931600000

Cortex A53 och PowerPC e500 uppvisar rätt stor prestandavinst vid hanteringen av den sorterade datamängden (men kostnaden för att sortera ingår ju inte, totalt sett är det ändå ett minustecken på att först sortera!).

Dessa två delar också en väldigt distinkt egenskap, de är s.k. "in-order execution" designer och kan därför inte öka sin IPC genom att spekulera kring hur saker ska utfalla i framtiden.

Övriga två visar samma beteende som Zen och Skylake. Alla dessa är s.k. "out-of-order execution" designer. Uppenbarligen är detta fall så pass trivialt att även Cortex A9 och Atom, som båda är rätt simpla designer men som ändå kan spekulera, kan hantera fallet.

Lite lustigt dock att det är en klar skillnad om man inte slår på kompilatorn optimeringar. Det pekar på att kombinationen modern kompilator (körde med väldigt ny version av LLVM på ARM och väldigt modern variant av GCC på övriga) kan hantera den här typen av problematik bättre än de flesta skulle göra "för hand".

Bjarne Stroustrup har flera gånger nämnt att studenter brukar flasha med "smarta optimeringar" de kommit på. De brukar lägga fram det lite som att de uppenbarligen tänkt på saker ingen annan verkar tänkt på. Första frågan från Bjarne: har ni kompilerat med optimeringar på? Svarat är i princip alltid i dessa fall: kompilator-optimeringar?

#include <algorithm> #include <chrono> #include <iostream> #include <iterator> #include <numeric> #include <vector> const int ITERATIONS = 100000; using DurationT = std::chrono::milliseconds; void test(const char * desc, const std::vector<int> & data) { // Test auto start = std::chrono::steady_clock::now(); long long sum = 0; for (unsigned i = 0; i < ITERATIONS; ++i) { for (auto elem : data) { if (elem >= 128) { sum += elem; } } } auto stop = std::chrono::steady_clock::now(); auto duration = std::chrono::duration_cast<DurationT>(stop - start); std::cout << desc << ": " << duration.count() / 1000.0 << "s\n" << "sum = " << sum << std::endl; } int main() { // Generate data (f = filtered) const unsigned arraySize = 32768; static std::vector<int> data(arraySize); static std::vector<int> fData; std::generate(data.begin(), data.end(), []() { return std::rand() % 256; }); std::copy_if(data.begin(), data.end(), std::back_inserter(fData), [](unsigned elem) { return elem >= 128; }); test("filtered", fData); test("unsorted", data); std::sort(data.begin(), data.end()); test("sorted", data); return EXIT_SUCCESS; }

Edit: variant av koden som diskuteras i tråden i C++ i stället för C kompilerad med C++ kompilator, exakt samma prestanda för mig i alla fall
Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Permalänk

Tack

Tack för alla inlägg! Det var skoj att så många var intresserade.
Slutsatsen är nog att uppgiften var för lätt för dagens CPU och kompilator.
Så svårare uppgifer krävs.....
Här får ni lite historiska uppgifter om branch prediction:
Dan Luu om branch prediction
Tyvärr är det ganska lite om dagens CPUer.

SPEC.org började med tester av CPU, cache & minne 1989. Branch prediction har stor betydelse i vissa program.
Dagens testprogram är jättestora men framför allt är dagen CPUer betydligt "smartare" än 1989.

Permalänk

Info om ARM

Här finns det lite info om ARM11 och ARM Cortex A53
ARM11
Raspberry Pi 1 är en ARM1176

Cortex A53
Raspberry Pi 3 är en Cortex A53

Permalänk

Valgrind --tool=cachegrind

Detta analysverktyg kan installeras för de flesta system.Man måste dock köra i debugläge & tempo går ner rejält. Detta är 64bitar Linux med en Celeron J4005.
För den osorterade varianten ser det ut så här:

[person@localhost Dokument]$ valgrind --tool=cachegrind ./a.out
==32078== Cachegrind, a cache and branch-prediction profiler
==32078== Copyright (C) 2002-2017, and GNU GPL'd, by Nicholas Nethercote et al.
==32078== Using Valgrind-3.14.0 and LibVEX; rerun with -h for copyright info
==32078== Command: ./a.out
==32078==
225.929
sum = 314931600000
==32078==
==32078== I refs: 32,803,668,646
==32078== I1 misses: 1,855
==32078== LLi misses: 1,757
==32078== I1 miss rate: 0.00%
==32078== LLi miss rate: 0.00%
==32078==
==32078== D refs: 18,047,358,721 (18,046,763,783 rd + 594,938 wr)
==32078== D1 misses: 204,819,675 ( 204,815,118 rd + 4,557 wr)
==32078== LLd misses: 11,361 ( 7,866 rd + 3,495 wr)
==32078== D1 miss rate: 1.1% ( 1.1% + 0.8% )
==32078== LLd miss rate: 0.0% ( 0.0% + 0.6% )
==32078==
==32078== LL refs: 204,821,530 ( 204,816,973 rd + 4,557 wr)
==32078== LL misses: 13,118 ( 9,623 rd + 3,495 wr)
==32078== LL miss rate: 0.0% ( 0.0% + 0.6% )
[person@localhost Dokument]$

Man får bara data för 1a och sista cache.
Slutsatsen är att detta var för lätt....

Permalänk

En svårare uppgift för cache & minne- NSIEVE

@Greyguy1948:
gcc -g
Sieve of Eratosthenes (Scaled to 10 Iterations)
Version 1.2b, 26 Sep 1992

Array Size Number Last Prime Linear RunTime MIPS
(Bytes) of Primes Time(sec) (Sec)
8191 1899 16381 0.001 0.001 2861.2
10000 2261 19997 0.001 0.001 2783.5
20000 4202 39989 0.001 0.001 2794.5
40000 7836 79999 0.003 0.003 2686.5
80000 14683 160001 0.006 0.007 2307.7
160000 27607 319993 0.011 0.014 2383.0
320000 52073 639997 0.023 0.030 2297.8
640000 98609 1279997 0.045 0.061 2267.7
1280000 187133 2559989 0.091 0.124 2259.6
2560000 356243 5119997 0.181 0.272 2081.5
5120000 679460 10239989 0.362 0.854 1338.1
10240000 1299068 20479999 0.724 2.747 839.3
20480000 2488465 40960001 1.449 6.487 716.3
40960000 4774994 81919993 2.898 14.229 658.1

Relative to 10 Iterations and the 8191 Array Size:
Average RunTime = 0.001 (sec)
High MIPS = 2861.2
Low MIPS = 658.1

[person@localhost Dokument]$ valgrind --tool=cachegrind ./a.out
==32461== Cachegrind, a cache and branch-prediction profiler
==32461== Copyright (C) 2002-2017, and GNU GPL'd, by Nicholas Nethercote et al.
==32461== Using Valgrind-3.14.0 and LibVEX; rerun with -h for copyright info
==32461== Command: ./a.out
==32461==

Sieve of Eratosthenes (Scaled to 10 Iterations)
Version 1.2b, 26 Sep 1992

Array Size Number Last Prime Linear RunTime MIPS
(Bytes) of Primes Time(sec) (Sec)
8191 1899 16381 0.010 0.010 165.1
10000 2261 19997 0.012 0.013 162.4
20000 4202 39989 0.025 0.026 156.0
40000 7836 79999 0.049 0.056 147.8
80000 14683 160001 0.098 0.115 146.0
160000 27607 319993 0.196 0.236 144.3
320000 52073 639997 0.392 0.491 140.4
640000 98609 1279997 0.785 1.044 133.3
1280000 187133 2559989 1.569 2.215 126.8
2560000 356243 5119997 3.138 4.811 117.8
5120000 679460 10239989 6.277 10.513 108.7
10240000 1299068 20479999 12.554 22.003 104.8
20480000 2488465 40960001 25.107 45.567 102.0
40960000 4774994 81919993 50.215 92.344 101.4

Relative to 10 Iterations and the 8191 Array Size:
Average RunTime = 0.014 (sec)
High MIPS = 165.1
Low MIPS = 101.4

==32461==
==32461== I refs: 9,422,593,068
==32461== I1 misses: 1,262
==32461== LLi misses: 1,237
==32461== I1 miss rate: 0.00%
==32461== LLi miss rate: 0.00%
==32461==
==32461== D refs: 2,031,494,405 (1,040,542,800 rd + 990,951,605 wr)
==32461== D1 misses: 316,041,559 ( 4,069,489 rd + 311,972,070 wr)
==32461== LLd misses: 125,253,146 ( 1,428,619 rd + 123,824,527 wr)
==32461== D1 miss rate: 15.6% ( 0.4% + 31.5% )
==32461== LLd miss rate: 6.2% ( 0.1% + 12.5% )
==32461==
==32461== LL refs: 316,042,821 ( 4,070,751 rd + 311,972,070 wr)
==32461== LL misses: 125,254,383 ( 1,429,856 rd + 123,824,527 wr)
==32461== LL miss rate: 1.1% ( 0.0% + 12.5% )
[person@localhost Dokument]$

Permalänk

g++ ver 4.9.2

@Yoshman: Hur man optimerar spelar stor roll. Detta är g++ med Cortex-A53
Optimering ingen ..... -O1 ... -O2 ... -O3
filtered ......... 50 ... 7 ... 6 ... 11
unsorted ..... 86 ... 26 ... 24 ... 23
sorted ......... 76 ... 15 ... 14 ... 23

Permalänk
Datavetare
Skrivet av Greyguy1948:

@Yoshman: Hur man optimerar spelar stor roll. Detta är g++ med Cortex-A53
Optimering ingen ..... -O1 ... -O2 ... -O3
filtered ......... 50 ... 7 ... 6 ... 11
unsorted ..... 86 ... 26 ... 24 ... 23
sorted ......... 76 ... 15 ... 14 ... 23

Visst spelar optimeringen roll, framförallt om man kör på en in-order design, där är kompilatorn långt viktigare än för out-of-order CPUer.

Men ditt resultat ovan visar varför de flesta rekommenderar att inte använda -O3 som förval: det kan lika gärna göra saker långsammare som snabbare. I just ditt fall gör -O3 att det inte spelar någon roll om man sorterar eller ej, men det beror primärt på att det sorterade fallet blev rejält mycket långsammare än med -O2!

Resultatet ovan visar också varför out-of-order designer är så överlägsna. De är långt mer robusta i sin prestanda p.g.a. att de har massor med mekanismer att hantera den idag största flaskhalsen: latens mot minne. Det visar sig här i att för out-of-order designerna kvittar det om man kör sorterat eller ej, prestanda hamnar inom någon enstaka procent från varandra för en viss optimeringsnivå.

Och det här fallet visar också hur lynnig -O3 är. Testar man -O1, -O2 och -O3 på en i7-8665U (Skylake) är -O3 klart snabbare (GCC 9.2.1). Men det är inte generellt sant, även för moderna x86or bör man verifiera att -O3 faktiskt ger ett positivt tillskott, -O2 är det "säkra" default-värdet.

Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Permalänk

Här är Cortex-A72 och Cortex-A53 med samma g++ 8.3.0

Cortex-A72
========
no opt
filtered: 13.3192
sum = 314931600000
unsorted: 51.4361
sum = 314931600000
sorted: 21.5486
sum = 314931600000
------------------
-O1
filtered: 3.3743
sum = 314931600000
unsorted: 28.4209
sum = 314931600000
sorted: 5.9657
sum = 314931600000
------------------
-O2
filtered: 2.75359
sum = 314931600000
unsorted: 29.1285
sum = 314931600000
sorted: 7.0862
sum = 314931600000
------------------
-O3
filtered: 2.78083
sum = 314931600000
unsorted: 29.1289
sum = 314931600000
sorted: 7.08685
sum = 314931600000
pi@raspberrypi:~/Documents $

Cortex-a53 (g++ 8.3.0)
======================
no opt
filtered: 49.5509
sum = 314931600000
unsorted: 85.9883
sum = 314931600000
sorted: 75.4301
sum = 314931600000
------------------
-O1
filtered: 8.42041
sum = 314931600000
unsorted: 25.192
sum = 314931600000
sorted: 13.9809
sum = 314931600000
------------------
-O2
filtered: 7.0481
sum = 314931600000
unsorted: 24.0728
sum = 314931600000
sorted: 13.8839
sum = 314931600000
------------------
-O3
filtered: 7.04615
sum = 314931600000
unsorted: 24.2272
sum = 314931600000
sorted: 13.9499
sum = 314931600000
pi@raspberrypi:~/Documents $

Permalänk

Tinker-board (Cortex-A17)

Tyvärr lyckades jag inte boota med micro-SD från RPi4 så detta är version 6.3.0.

linaro@tinkerboard:~/Documents$ ./sort_unsort.bat
g++ 6.3.0

Cortex-A17
==========
no opt
filtered: 15.2739
sum = 314931600000
unsorted: 47.9447
sum = 314931600000
sorted: 30.1443
sum = 314931600000
------------------
-O1
filtered: 3.77982
sum = 314931600000
unsorted: 19.4488
sum = 314931600000
sorted: 5.97745
sum = 314931600000
------------------
-O2
filtered: 3.44087
sum = 314931600000
unsorted: 20.1309
sum = 314931600000
sorted: 6.08293
sum = 314931600000
------------------
-O3
filtered: 5.27834
sum = 314931600000
unsorted: 10.5112
sum = 314931600000
sorted: 10.5115
sum = 314931600000
linaro@tinkerboard:~/Documents$

Permalänk

Som vanligt är jag lite sen på bollen här, men har ni kikat på den genererade koden? Om ni fortfarande kör programmet som listas högre upp i tråden så är chanserna goda att kompilatorn kan vektorisera innersta loopen i test(). Då kommer innehållet i data inte att påverka exekveringen över huvud taget och man borde på mer eller mindre exakt samma körtid (vilket ni får).

Det är en optimering som har stor påverkan på koden, men den trollar bort villkoret i loopen och tar bort de effekterna av branch prediction ni sett tidigare.

Permalänk

X86 med 32bitars kompilator

core i7-8700 x86_32 g++ 5.4.0
====================
no opt
filtered: 3.22697
sum = 314931600000
unsorted: 17.9441
sum = 314931600000
sorted: 5.20427
sum = 314931600000
------------------
-O1
filtered: 2.11192
sum = 314931600000
unsorted: 10.4471
sum = 314931600000
sorted: 3.51297
sum = 314931600000
------------------
-O2
filtered: 0.771356
sum = 314931600000
unsorted: 9.99591
sum = 314931600000
sorted: 1.53507
sum = 314931600000
------------------
-O3
filtered: 1.0582
sum = 314931600000
unsorted: 10.1607
sum = 314931600000
sorted: 1.91352
sum = 314931600000
person@person-System-Product-Name:~/Documents$ g++ --version
g++ (Ubuntu 5.4.0-6ubuntu1~16.04.12) 5.4.0 20160609
Copyright (C) 2015 Free Software Foundation, Inc.

Permalänk
Medlem

Jag trodde jag var någotsånär smart innan jag läste den här tråden.

Visa signatur

R7 3700X | Gigabyte GeForce RTX 2070 8GB GAMING OC | Corsair Vengeance LPX 4x8gb @ 3000mhz | EVGA Supernova 650w G3 | ASUS PRIME X370-PRO | WD Black NVMe SSD M.2 500GB OS | Corsair Hydro H115i PRO RGB | Fractal Design Define C | AOC AG352UCG6

Permalänk
Skrivet av Ingetledigtnamn:

Som vanligt är jag lite sen på bollen här, men har ni kikat på den genererade koden? Om ni fortfarande kör programmet som listas högre upp i tråden så är chanserna goda att kompilatorn kan vektorisera innersta loopen i test(). Då kommer innehållet i data inte att påverka exekveringen över huvud taget och man borde på mer eller mindre exakt samma körtid (vilket ni får).

Det är en optimering som har stor påverkan på koden, men den trollar bort villkoret i loopen och tar bort de effekterna av branch prediction ni sett tidigare.

Du har säkert rätt. I regel ser man loopar i ASM till och med -O1 men inte med -O2 och -O3.
Raspberry Pi har samma program för 1176 och alla Cortex-varianter. Tinker board behöver inte vara kompatibel med 1176.
x86_32 och x86_64 beter sig helt olika. Antalet register är fler på 64 bitar!