x86 32-bitowy kod maszynowy (z wywołaniami systemowymi Linux): 106 105 bajtów
dziennik zmian: zapisano bajt w szybkiej wersji, ponieważ stała off-by-one nie zmienia wyniku dla Fib (1G).
Lub 102 bajty dla wersji wolniejszej o 18% (w Skylake) (używając mov/ sub/ cmczamiast lea/ cmpw wewnętrznej pętli, aby wygenerować wykonanie i zawijanie 10**9zamiast 2**32). Lub 101 bajtów dla wolniejszej wersji ~ 5,3x z odgałęzieniem w obsłudze przenoszenia w najbardziej wewnętrznej pętli. (Zmierzyłem 25,4% wskaźnika nieprzewidzianych oddziałów!)
Lub 104/101 bajtów, jeśli dozwolone jest zero wiodące. (Potrzebny jest 1 dodatkowy bajt, aby pominąć 1 cyfrę kodu wyjściowego, co jest potrzebne w przypadku Fib (10 ** 9)).
Niestety tryb NASM TIO wydaje się ignorować -felf32flagi kompilatora. Oto i tak link do mojego pełnego kodu źródłowego, z całym bałaganem eksperymentalnych pomysłów w komentarzach.
To jest kompletny program . Drukuje pierwsze 1000 cyfr Fib (10 ** 9), a następnie kilka dodatkowych cyfr (kilka ostatnich jest niepoprawnych), a następnie kilka bajtów śmieci (bez nowego wiersza). Większość śmieci nie jest ASCII, więc możesz chcieć przepłynąć cat -v. konsoleJednak nie psuje mojego emulatora terminali (KDE ). „Bajty śmieci” przechowują Fib (999999999). Miałem już -1024w rejestrze, więc taniej było wydrukować 1024 bajty niż odpowiedni rozmiar.
Liczę tylko kod maszynowy (rozmiar segmentu tekstowego mojego statycznego pliku wykonywalnego), a nie puch, który sprawia, że jest to plik wykonywalny ELF. ( Możliwe są bardzo małe pliki wykonywalne ELF , ale nie chciałem się tym przejmować). Okazało się, że użycie pamięci stosu zamiast BSS jest krótsze, więc mogę uzasadnić, że nie liczę niczego innego w pliku binarnym, ponieważ nie zależę od żadnych metadanych. (Generowanie statycznego pliku binarnego z rozkładem w normalny sposób powoduje, że 340-bajtowy plik ELF jest wykonywalny.)
Z tego kodu można utworzyć funkcję, którą można wywołać z C. Zapisanie / przywrócenie wskaźnika stosu (być może w rejestrze MMX) może kosztować kilka bajtów, a także inne koszty ogólne, ale także zaoszczędzić bajty, zwracając ciąg znaków w pamięci zamiast write(1,buf,len)wywoływać system. Myślę, że golf w kodzie maszynowym powinien dać mi trochę luzu, ponieważ nikt inny nawet nie opublikował odpowiedzi w żadnym języku bez natywnej rozszerzonej precyzji, ale myślę, że wersja funkcji tego powinna nadal mieć mniej niż 120 bajtów bez ponownego gry w golfa rzecz.
Algorytm:
brutalna siła a+=b; swap(a,b), w razie potrzeby obcinana, aby zachować tylko wiodące> = 1017 cyfr dziesiętnych. Działa w ciągu 1 minuty 13 sekund na moim komputerze (lub 322,47 miliarda cykli zegara + - 0,05%) (i może być kilka% szybszy z kilkoma dodatkowymi bajtami rozmiaru kodu lub do 62 sekund przy znacznie większym rozmiarze kodu z rozwijania pętli. Nie sprytna matematyka, wykonująca tę samą pracę przy mniejszym obciążeniu). Opiera się na implementacji Pythona @ AndersKaseorg , która działa w 12min35s na moim komputerze (4.4GHz Skylake i7-6700k). Żadna wersja nie ma żadnych braków pamięci podręcznej L1D, więc moja pamięć DDR4-2666 nie ma znaczenia.
W przeciwieństwie do Pythona przechowuję liczby o rozszerzonej precyzji w formacie, który sprawia, że obcięcie cyfr dziesiętnych jest bezpłatne . Przechowuję grupy 9 cyfr dziesiętnych na 32-bitową liczbę całkowitą, więc przesunięcie wskaźnika odrzuca niskie 9 cyfr. To faktycznie podstawa 1 miliarda, czyli potęga 10. (To czysty zbieg okoliczności, że to wyzwanie wymaga 1 miliardowej liczby Fibonacciego, ale oszczędza mi to kilka bajtów w porównaniu do dwóch oddzielnych stałych).
Zgodnie z terminologią GMP każdy 32-bitowy fragment liczby o rozszerzonej precyzji jest nazywany „kończyną”. Wykonanie podczas dodawania musi zostać wygenerowane ręcznie za pomocą porównania z 1e9, ale następnie jest normalnie wykorzystywane jako dane wejściowe do zwykłej ADCinstrukcji dla następnej kończyny. (Muszę również ręcznie zawinąć do [0..999999999]zakresu, a nie przy 2 ^ 32 ~ = 4,295e9. Robię to bez rozgałęzień za pomocą lea+ cmov, używając wyniku przeprowadzania porównania.)
Kiedy ostatnia kończyna wykonuje niezerowe wykonanie, kolejne dwie iteracje zewnętrznej pętli odczytują z 1 kończyny wyżej niż normalnie, ale nadal piszą w tym samym miejscu. To jest jak memcpy(a, a+4, 114*4)przesunięcie w prawo o 1 kończynę, ale odbywa się to w ramach dwóch następnych pętli dodawania. Dzieje się tak co ~ 18 iteracji.
Hacki dla oszczędności rozmiaru i wydajności:
Zwykłe rzeczy jak lea ebx, [eax-4 + 1]zamiast mov ebx, 1, kiedy to wiem eax=4. A używanie loopw miejscach, w których LOOPpowolność ma niewielki wpływ.
Obetnij o 1 kończynę za darmo, przesuwając wskaźniki, z których czytamy, jednocześnie zapisując do początku bufora w adcpętli wewnętrznej. Czytamy [edi+edx]i piszemy do [edi]. Możemy więc uzyskać edx=0lub 4uzyskać przesunięcie odczytu-zapisu dla miejsca docelowego. Musimy to zrobić dla 2 kolejnych iteracji, najpierw kompensując oba, a następnie tylko kompensując dst. Drugi przypadek wykrywamy, sprawdzając esp&4przed zresetowaniem wskaźników z przodu buforów (używając &= -1024, ponieważ bufory są wyrównane). Zobacz komentarze w kodzie.
Środowisko uruchamiania procesu Linux (dla statycznego pliku wykonywalnego) zeruje większość rejestrów, a pamięć stosu poniżej esp/ rspjest zerowana. Mój program to wykorzystuje. W wersji tego z funkcją wywoływania (gdzie nieprzydzielony stos może być brudny), mógłbym użyć BSS do zerowania pamięci (kosztem może 4 dodatkowych bajtów do ustawienia wskaźników). Zerowanie edxzajmie 2 bajty. X86-64 System V ABI nie gwarantuje żadnego z nich, ale jego implementacja w Linuksie jest zerowa (aby uniknąć wycieku informacji z jądra). W dynamicznie połączonym procesie /lib/ld.sodziała wcześniej _starti pozostawia rejestry niezerowe (i prawdopodobnie śmieci w pamięci poniżej wskaźnika stosu).
Trzymam -1024się ebxdo stosowania na zewnątrz pętli. Użyj bljako licznik dla wewnętrznych pętli, kończących się na zero (co jest niskim bajtem -1024, przywracając w ten sposób stałą do użycia poza pętlą). Intel Haswell, a później nie ma częściowych kar za łączenie rejestrów za niskie rejestry (a nawet nie zmienia ich osobno) , więc istnieje zależność od pełnego rejestru, jak na AMD (tutaj nie ma problemu). Byłoby to okropne w przypadku Nehalem i wcześniejszych, które mają częściowe rejestracje podczas łączenia. Są inne miejsca, w których piszę częściowe regi, a następnie czytam pełny reg bez xorzerowania lub amovzx, zwykle dlatego, że wiem, że jakiś poprzedni kod zerował górne bajty, i znowu jest to w porządku w przypadku AMD i rodziny Intel SnB, ale powolne w przypadku Intel przed Sandybridge.
Używam 1024jako liczby bajtów do zapisu do stdout ( sub edx, ebx), więc mój program drukuje niektóre bajty śmieci po cyfrach Fibonacciego, ponieważ mov edx, 1000kosztuje więcej bajtów.
(nie używane) adc ebx,ebxz EBX = 0, aby uzyskać EBX = CF, oszczędzając 1 bajt vs setc bl.
dec/ jnzwewnątrz adcpętli zachowuje CF bez powodowania przeciągnięcia częściowej flagi podczas adcodczytywania flag na Intel Sandybridge i nowszych. Jest zły na wcześniejszych procesorach , ale AFAIK za darmo na Skylake. Lub, w najgorszym wypadku, dodatkowa zaleta.
Użyj pamięci poniżej espjako gigantycznej czerwonej strefy . Ponieważ jest to kompletny program dla systemu Linux, wiem, że nie zainstalowałem żadnych programów obsługi sygnałów i że nic innego nie asynchronicznie zablokuje pamięci stosu przestrzeni użytkownika. Może się tak nie zdarzyć w przypadku innych systemów operacyjnych.
Skorzystaj z silnika stosu, aby zaoszczędzić przepustowość problemową UOP, używając pop eax(1 uop + okazjonalne synchronizowanie stosu uop) zamiast lodsd(2 uops na Haswell / Skylake, 3 na IvB i wcześniejszych zgodnie z tabelami instrukcji Agner Fog ). IIRC, skróciło to czas działania z około 83 sekund do 73. Prawdopodobnie mógłbym uzyskać taką samą prędkość z używania movz trybem adresowania indeksowanego, tak jak mov eax, [edi+ebp]gdzie ebpzachowuje przesunięcie między buforami src i dst. (Sprawiłoby to, że kod poza pętlą wewnętrzną byłby bardziej złożony, ponieważ musiałby zanegować rejestr przesunięcia w ramach zamiany src i dst dla iteracji Fibonacciego.) Więcej informacji w sekcji „wydajność” poniżej.
rozpocznij sekwencję, nadając pierwszej iteracji przeniesienie (jeden bajt stc), zamiast zapisywać 1gdziekolwiek w pamięci. Wiele innych specyficznych dla problemu rzeczy udokumentowanych w komentarzach.
Lista NASM (kod maszynowy + źródło) , wygenerowana z nasm -felf32 fibonacci-1G.asm -l /dev/stdout | cut -b -28,$((28+12))- | sed 's/^/ /'. (Następnie ręcznie usunąłem kilka bloków komentowanych rzeczy, więc numeracja linii ma luki.) Aby usunąć główne kolumny i wprowadzić je do YASM lub NASM, użyj cut -b 27- <fibonacci-1G.lst > fibonacci-1G.asm.
1 machine global _start
2 code _start:
3 address
4 00000000 B900CA9A3B mov ecx, 1000000000 ; Fib(ecx) loop counter
5 ; lea ebp, [ecx-1] ; base-1 in the base(pointer) register ;)
6 00000005 89CD mov ebp, ecx ; not wrapping on limb==1000000000 doesn't change the result.
7 ; It's either self-correcting after the next add, or shifted out the bottom faster than Fib() grows.
8
42
43 ; mov esp, buf1
44
45 ; mov esi, buf1 ; ungolfed: static buffers instead of the stack
46 ; mov edi, buf2
47 00000007 BB00FCFFFF mov ebx, -1024
48 0000000C 21DC and esp, ebx ; alignment necessary for convenient pointer-reset
49 ; sar ebx, 1
50 0000000E 01DC add esp, ebx ; lea edi, [esp + ebx]. Can't skip this: ASLR or large environment can put ESP near the bottom of a 1024-byte block to start with
51 00000010 8D3C1C lea edi, [esp + ebx*1]
52 ;xchg esp, edi ; This is slightly faster. IDK why.
53
54 ; It's ok for EDI to be below ESP by multiple 4k pages. On Linux, IIRC the main stack automatically extends up to ulimit -s, even if you haven't adjusted ESP. (Earlier I used -4096 instead of -1024)
55 ; After an even number of swaps, EDI will be pointing to the lower-addressed buffer
56 ; This allows a small buffer size without having the string step on the number.
57
58 ; registers that are zero at process startup, which we depend on:
59 ; xor edx, edx
60 ;; we also depend on memory far below initial ESP being zeroed.
61
62 00000013 F9 stc ; starting conditions: both buffers zeroed, but carry-in = 1
63 ; starting Fib(0,1)->0,1,1,2,3 vs. Fib(1,0)->1,0,1,1,2 starting "backwards" puts us 1 count behind
66
67 ;;; register usage:
68 ;;; eax, esi: scratch for the adc inner loop, and outer loop
69 ;;; ebx: -1024. Low byte is used as the inner-loop limb counter (ending at zero, restoring the low byte of -1024)
70 ;;; ecx: outer-loop Fibonacci iteration counter
71 ;;; edx: dst read-write offset (for "right shifting" to discard the least-significant limb)
72 ;;; edi: dst pointer
73 ;;; esp: src pointer
74 ;;; ebp: base-1 = 999999999. Actually still happens to work with ebp=1000000000.
75
76 .fibonacci:
77 limbcount equ 114 ; 112 = 1006 decimal digits / 9 digits per limb. Not enough for 1000 correct digits, but 114 is.
78 ; 113 would be enough, but we depend on limbcount being even to avoid a sub
79 00000014 B372 mov bl, limbcount
80 .digits_add:
81 ;lodsd ; Skylake: 2 uops. Or pop rax with rsp instead of rsi
82 ; mov eax, [esp]
83 ; lea esp, [esp+4] ; adjust ESP without affecting CF. Alternative, load relative to edi and negate an offset? Or add esp,4 after adc before cmp
84 00000016 58 pop eax
85 00000017 130417 adc eax, [edi + edx*1] ; read from a potentially-offset location (but still store to the front)
86 ;; jz .out ;; Nope, a zero digit in the result doesn't mean the end! (Although it might in base 10**9 for this problem)
87
88 %if 0 ;; slower version
;; could be even smaller (and 5.3x slower) with a branch on CF: 25% mispredict rate
89 mov esi, eax
90 sub eax, ebp ; 1000000000 ; sets CF opposite what we need for next iteration
91 cmovc eax, esi
92 cmc ; 1 extra cycle of latency for the loop-carried dependency. 38,075Mc for 100M iters (with stosd).
93 ; not much worse: the 2c version bottlenecks on the front-end bottleneck
94 %else ;; faster version
95 0000001A 8DB0003665C4 lea esi, [eax - 1000000000]
96 00000020 39C5 cmp ebp, eax ; sets CF when (base-1) < eax. i.e. when eax>=base
97 00000022 0F42C6 cmovc eax, esi ; eax %= base, keeping it in the [0..base) range
98 %endif
99
100 %if 1
101 00000025 AB stosd ; Skylake: 3 uops. Like add + non-micro-fused store. 32,909Mcycles for 100M iters (with lea/cmp, not sub/cmc)
102 %else
103 mov [edi], eax ; 31,954Mcycles for 100M iters: faster than STOSD
104 lea edi, [edi+4] ; Replacing this with ADD EDI,4 before the CMP is much slower: 35,083Mcycles for 100M iters
105 %endif
106
107 00000026 FECB dec bl ; preserves CF. The resulting partial-flag merge on ADC would be slow on pre-SnB CPUs
108 00000028 75EC jnz .digits_add
109 ; bl=0, ebx=-1024
110 ; esi has its high bit set opposite to CF
111 .end_innerloop:
112 ;; after a non-zero carry-out (CF=1): right-shift both buffers by 1 limb, over the course of the next two iterations
113 ;; next iteration with r8 = 1 and rsi+=4: read offset from both, write normal. ends with CF=0
114 ;; following iter with r8 = 1 and rsi+=0: read offset from dest, write normal. ends with CF=0
115 ;; following iter with r8 = 0 and rsi+=0: i.e. back to normal, until next carry-out (possible a few iters later)
116
117 ;; rdi = bufX + 4*limbcount
118 ;; rsi = bufY + 4*limbcount + 4*carry_last_time
119
120 ; setc [rdi]
123 0000002A 0F92C2 setc dl
124 0000002D 8917 mov [edi], edx ; store the carry-out into an extra limb beyond limbcount
125 0000002F C1E202 shl edx, 2
139 ; keep -1024 in ebx. Using bl for the limb counter leaves bl zero here, so it's back to -1024 (or -2048 or whatever)
142 00000032 89E0 mov eax, esp ; test/setnz could work, but only saves a byte if we can somehow avoid the or dl,al
143 00000034 2404 and al, 4 ; only works if limbcount is even, otherwise we'd need to subtract limbcount first.
148 00000036 87FC xchg edi, esp ; Fibonacci: dst and src swap
149 00000038 21DC and esp, ebx ; -1024 ; revert to start of buffer, regardless of offset
150 0000003A 21DF and edi, ebx ; -1024
151
152 0000003C 01D4 add esp, edx ; read offset in src
155 ;; after adjusting src, so this only affects read-offset in the dst, not src.
156 0000003E 08C2 or dl, al ; also set r8d if we had a source offset last time, to handle the 2nd buffer
157 ;; clears CF for next iter
165 00000040 E2D2 loop .fibonacci ; Maybe 0.01% slower than dec/jnz overall
169 to_string:
175 stringdigits equ 9*limbcount ; + 18
176 ;;; edi and esp are pointing to the start of buffers, esp to the one most recently written
177 ;;; edi = esp +/- 2048, which is far enough away even in the worst case where they're growing towards each other
178 ;;; update: only 1024 apart, so this only works for even iteration-counts, to prevent overlap
180 ; ecx = 0 from the end of the fib loop
181 ;and ebp, 10 ; works because the low byte of 999999999 is 0xff
182 00000042 8D690A lea ebp, [ecx+10] ;mov ebp, 10
183 00000045 B172 mov cl, (stringdigits+8)/9
184 .toascii: ; slow but only used once, so we don't need a multiplicative inverse to speed up div by 10
185 ;add eax, [rsi] ; eax has the carry from last limb: 0..3 (base 4 * 10**9)
186 00000047 58 pop eax ; lodsd
187 00000048 B309 mov bl, 9
188 .toascii_digit:
189 0000004A 99 cdq ; edx=0 because eax can't have the high bit set
190 0000004B F7F5 div ebp ; edx=remainder = low digit = 0..9. eax/=10
197 0000004D 80C230 add dl, '0'
198 ; stosb ; clobber [rdi], then inc rdi
199 00000050 4F dec edi ; store digits in MSD-first printing order, working backwards from the end of the string
200 00000051 8817 mov [edi], dl
201
202 00000053 FECB dec bl
203 00000055 75F3 jnz .toascii_digit
204
205 00000057 E2EE loop .toascii
206
207 ; Upper bytes of eax=0 here. Also AL I think, but that isn't useful
208 ; ebx = -1024
209 00000059 29DA sub edx, ebx ; edx = 1024 + 0..9 (leading digit). +0 in the Fib(10**9) case
210
211 0000005B B004 mov al, 4 ; SYS_write
212 0000005D 8D58FD lea ebx, [eax-4 + 1] ; fd=1
213 ;mov ecx, edi ; buf
214 00000060 8D4F01 lea ecx, [edi+1] ; Hard-code for Fib(10**9), which has one leading zero in the highest limb.
215 ; shr edx, 1 ; for use with edx=2048
216 ; mov edx, 100
217 ; mov byte [ecx+edx-1], 0xa;'\n' ; count+=1 for newline
218 00000063 CD80 int 0x80 ; write(1, buf+1, 1024)
219
220 00000065 89D8 mov eax, ebx ; SYS_exit=1
221 00000067 CD80 int 0x80 ; exit(ebx=1)
222
# next byte is 0x69, so size = 0x69 = 105 bytes
Prawdopodobnie jest jeszcze miejsce na grę w golfa, ale spędziłem na tym co najmniej 12 godzin w ciągu 2 dni. Nie chcę poświęcać prędkości, mimo że jest ona o wiele bardziej niż wystarczająco szybka i jest miejsce na jej zmniejszenie w sposób, który kosztuje prędkość . Częścią mojego powodu publikowania postów jest pokazanie, jak szybko mogę stworzyć wersję asm brutalnej siły. Jeśli ktoś naprawdę chce wybrać rozmiar minimalny, ale może 10-krotnie wolniejszy (np. 1 cyfra na bajt), możesz skopiować go jako punkt wyjścia.
Wynikowy plik wykonywalny (z yasm -felf32 -Worphan-labels -gdwarf2 fibonacci-1G.asm && ld -melf_i386 -o fibonacci-1G fibonacci-1G.o) to 340B (pozbawiony):
size fibonacci-1G
text data bss dec hex filename
105 0 0 105 69 fibonacci-1G
Występ
adcPętla wewnętrzna to 10 skoków domeny połączonej w Skylake (+1 skok synchronizacji stosu co ~ 128 bajtów), więc może wydawać jeden na ~ 2,5 cykli w Skylake z optymalną wydajnością front-end (ignorując wzrost synchronizacji stosu) . Opóźnienie krytycznego ścieżka 2 cykli, gdyż adc-> cmp-> kolejnej iteracji w adcpętli prowadzi łańcuch zależność, a więc szyjka powinny być ograniczenie problem czołowy wynosi około 2,5 cykli na iteracji.
adc eax, [edi + edx]to 2 nieuprawnione nieuprawnione domeny dla portów wykonania: load + ALU. Mikro-topi się w dekoderach (1 UOP w domenie z fuzją), ale un-laminuje na etapie wydania do 2 UUP w domenie z fuzji, ze względu na tryb adresowania indeksowanego, nawet w Haswell / Skylake . Myślałem, że pozostanie mikro-skondensowany, podobnie jak add eax, [edi + edx]robi, ale być może utrzymywanie indeksowanych trybów adresowania mikro-skondensowany nie działa dla uops, które mają już 3 wejścia (flagi, pamięć i miejsce docelowe). Kiedy to napisałem, myślałem, że to nie będzie miało negatywnego wyniku, ale się myliłem. Ten sposób obsługi obcinania spowalnia wewnętrzną pętlę za każdym razem, niezależnie od tego, czy edxwynosi 0, czy 4.
Byłoby szybciej obsłużyć przesunięcie odczytu-zapisu dla dst poprzez przesunięcie edii użycie edxdo dostosowania magazynu. Więc adc eax, [edi]/ ... / mov [edi+edx], eax/ lea edi, [edi+4]zamiast stosd. Haswell i później mogą przechowywać indeksowany sklep w postaci mikro-bezpieczników. (Sandybridge / IvB też to rozwiąże).
Na Intel Haswell i wcześniejszych, adci cmovcsą 2 upops każdy, z opóźnieniem 2c . ( adc eax, [edi+edx]wciąż nie jest laminowany na Haswell i wydaje się, że 3 nie działa w domenie połączonej). Broadwell, a później zezwalają na 3-wejściowe uopsy dla więcej niż tylko FMA (Haswell), tworzenia adci cmovc(i kilku innych rzeczy) instrukcji dla pojedynczych uupów, jakby były na AMD od dłuższego czasu. (Jest to jeden z powodów, dla których AMD od dawna dobrze sobie radzi w testach porównawczych GMP o rozszerzonej precyzji.) W każdym razie wewnętrzna pętla Haswella powinna wynosić 12 jednostek (czasami +1 synchronizacja stosów), z wąskim gardłem na poziomie ~ 3 centów za sztukę iter najlepszy przypadek, ignorując ups synchronizacji stosu.
Używanie popbez równoważenia pushwewnątrz pętli oznacza, że pętla nie może uruchomić się z LSD (detektor strumienia pętli) i musi być za każdym razem ponownie odczytywana z pamięci podręcznej uop do IDQ. Jeśli już, to dobrze, że w Skylake jest dobra, ponieważ pętla 9 lub 10 jednostek nie wydaje się optymalnie przy 4 jednostkach każdego cyklu . Jest to prawdopodobnie część tego, dlaczego zastąpienie lodsdprzez poptak bardzo pomogło. (LSD nie może zablokować opcji Uops, ponieważ nie pozostawiłoby to miejsca na wstawienie opcji UOP synchronizacji stosu .) (BTW, aktualizacja mikrokodu wyłącza LSD całkowicie w Skylake i Skylake-X, aby naprawić błąd. Zmierzyłem powyżej przed otrzymaniem tej aktualizacji).
Profilowałem go na Haswell i stwierdziłem, że działa w 381,31 miliarda cykli zegara (niezależnie od częstotliwości procesora, ponieważ używa tylko pamięci podręcznej L1D, a nie pamięci). Przepustowość problemu front-end wyniosła 3,72 Uops-Fused-domena na zegar, w porównaniu do 3,70 dla Skylake. (Ale oczywiście instrukcje na cykl spadła do 2,42 z 2,87, bo adci cmovsą 2 UOPs na Haswell).
pushzastąpienie stosdprawdopodobnie nie pomogłoby tak bardzo, ponieważ adc [esp + edx]uruchamiałoby uop synchronizacji stosu za każdym razem. I kosztowałby bajt, stdwięc lodsdidzie w innym kierunku. ( mov [edi], eax/ lea edi, [edi+4]do zastąpienia stosdto wygrana, przechodząc z 32.909 motocykli dla iterów 100M do 31.954 motocykli dla iterów 100 mln. Wygląda na to, że stosddekoduje się jako 3 uops, przy czym uops-store / store-data uops nie są mikro-stopione, więc push+ synchronizacja stosu Ups może nadal być szybszy niż stosd)
Rzeczywista wydajność ~ 322,47 miliarda cykli dla iteracji 1G 114 kończyn wynosi 2,824 cykli na iterację pętli wewnętrznej , dla szybkiej wersji 105B na Skylake. (Patrz ocperf.pydane wyjściowe poniżej). Jest to wolniejsze niż przewidywałem na podstawie analizy statycznej, ale ignorowałem obciążenie związane z zewnętrzną pętlą i wszelkimi dodatkami synchronizacji stosu.
Perf liczy branchesi branch-missespokazuje, że wewnętrzna pętla błędnie przewiduje raz na zewnętrzną pętlę (podczas ostatniej iteracji, gdy nie jest pobierana). To także stanowi część dodatkowego czasu.
Mógłbym zapisać rozmiar kodu, sprawiając, że najbardziej wewnętrzna pętla ma 3-cyklowe opóźnienie dla ścieżki krytycznej, używając mov esi,eax/ sub eax,ebp/ cmovc eax, esi/cmc (2 + 2 + 3 + 1 = 8B) zamiast lea esi, [eax - 1000000000]/ cmp ebp,eax/ cmovc(6 + 2 + 3 = 11B ). cmov/ stosdJest wyłączony ścieżce krytycznej. (Edycja przyrostowa stosdmoże działać niezależnie od sklepu, więc każda iteracja wyklucza krótki łańcuch zależności). Dawniej zapisywał kolejny 1B, zmieniając instrukcję init ebp z lea ebp, [ecx-1]na mov ebp,eax, ale odkryłem, że źleebpnie zmienił wyniku. Pozwoliłoby to kończynie dokładnie == 1000000000 zamiast owijania i generowania przeniesienia, ale ten błąd propaguje się wolniej niż rośnie Fib (), więc nie zmienia to wiodących cyfr 1k końcowego wyniku. Myślę też, że ten błąd może się poprawić, gdy dodajemy, ponieważ w kończynie jest miejsce, aby go utrzymać bez przepełnienia. Nawet 1G + 1G nie przepełnia 32-bitowej liczby całkowitej, więc ostatecznie przesiąknie w górę lub zostanie obcięta.
Wersja 3c z opóźnieniem ma 1 dodatkowy UOP, więc front-end może wydawać go raz na 2,75c cykli w Skylake, tylko nieco szybciej niż back-end może go uruchomić. (W Haswell będzie to łącznie 13 uops, ponieważ nadal używa adci cmovoraz wąskie gardło w interfejsie na poziomie 3,25 c na iter).
W praktyce działa on o 1,18 wolniej na Skylake (3,34 cykli na kończynę), zamiast 3 / 2,5 = 1,2, które przewidywałem, że zastąpię wąskie gardło z przodu z wąskim gardłem od samego spojrzenia na wewnętrzną pętlę bez synchronizacji stosu ups. Ponieważ uops-sync stosy szkodzą tylko szybkiej wersji (wąskie gardło na froncie zamiast opóźnień), nie trzeba wiele wyjaśniać. np. 3 / 2,54 = 1,18.
Innym czynnikiem jest to, że wersja 3c z opóźnieniem może wykryć nieprzewidywalne wyjście z wewnętrznej pętli, gdy ścieżka krytyczna jest nadal wykonywana (ponieważ front-end może wyprzedzić back-end, pozwalając na wykonanie poza kolejnością, uruchamiając pętlę- counter uops), więc skuteczna kara za niepoprawne przewidywanie jest niższa. Utrata tych cykli front-end pozwala dogonić back-end.
Gdyby tak nie było, moglibyśmy przyspieszyć cmcwersję 3c , używając gałęzi w zewnętrznej pętli zamiast bezgałęziowej obsługi przeniesień carry_out -> edx i esp. Przewidywanie rozgałęzień + wykonywanie spekulatywne dla zależności sterującej zamiast zależności danych może pozwolić następnej iteracji na uruchomienie adcpętli, podczas gdy wzloty z poprzedniej pętli wewnętrznej były nadal w locie. W wersji bez rozgałęzienia adresy obciążenia w pętli wewnętrznej zależą od CF od ostatniej adcostatniej kończyny.
Wąskie gardła w wewnętrznej pętli z opóźnieniem 2c z przodu, więc back-end prawie nadąża. Gdyby kod pętli zewnętrznej miał duże opóźnienie, front-end mógłby wyprzedzić wydawanie wzlotów z następnej iteracji pętli wewnętrznej. (Ale w tym przypadku zewnętrzna pętla ma dużo ILP i nie ma opóźnień, więc back-end nie ma wiele do nadrobienia, gdy zaczyna przeżuwać błędy w harmonogramie poza kolejnością, ponieważ ich dane wejściowe są gotowe).
### Output from a profiled run
$ asm-link -m32 fibonacci-1G.asm && (size fibonacci-1G; echo disas fibonacci-1G) && ocperf.py stat -etask-clock,context-switches:u,cpu-migrations:u,page-faults:u,cycles,instructions,uops_issued.any,uops_executed.thread,uops_executed.stall_cycles -r4 ./fibonacci-1G
+ yasm -felf32 -Worphan-labels -gdwarf2 fibonacci-1G.asm
+ ld -melf_i386 -o fibonacci-1G fibonacci-1G.o
text data bss dec hex filename
106 0 0 106 6a fibonacci-1G
disas fibonacci-1G
perf stat -etask-clock,context-switches:u,cpu-migrations:u,page-faults:u,cycles,instructions,cpu/event=0xe,umask=0x1,name=uops_issued_any/,cpu/event=0xb1,umask=0x1,name=uops_executed_thread/,cpu/event=0xb1,umask=0x1,inv=1,cmask=1,name=uops_executed_stall_cycles/ -r4 ./fibonacci-1G
79523178745546834678293851961971481892555421852343989134530399373432466861825193700509996261365567793324820357232224512262917144562756482594995306121113012554998796395160534597890187005674399468448430345998024199240437534019501148301072342650378414269803983873607842842319964573407827842007677609077777031831857446565362535115028517159633510239906992325954713226703655064824359665868860486271597169163514487885274274355081139091679639073803982428480339801102763705442642850327443647811984518254621305295296333398134831057713701281118511282471363114142083189838025269079177870948022177508596851163638833748474280367371478820799566888075091583722494514375193201625820020005307983098872612570282019075093705542329311070849768547158335856239104506794491200115647629256491445095319046849844170025120865040207790125013561778741996050855583171909053951344689194433130268248133632341904943755992625530254665288381226394336004838495350706477119867692795685487968552076848977417717843758594964253843558791057997424878788358402439890396,�X\�;3�I;ro~.�'��R!q��%��X'B �� 8w��▒Ǫ�
... repeated 3 more times, for the 3 more runs we're averaging over
Note the trailing garbage after the trailing digits.
Performance counter stats for './fibonacci-1G' (4 runs):
73438.538349 task-clock:u (msec) # 1.000 CPUs utilized ( +- 0.05% )
0 context-switches:u # 0.000 K/sec
0 cpu-migrations:u # 0.000 K/sec
2 page-faults:u # 0.000 K/sec ( +- 11.55% )
322,467,902,120 cycles:u # 4.391 GHz ( +- 0.05% )
924,000,029,608 instructions:u # 2.87 insn per cycle ( +- 0.00% )
1,191,553,612,474 uops_issued_any:u # 16225.181 M/sec ( +- 0.00% )
1,173,953,974,712 uops_executed_thread:u # 15985.530 M/sec ( +- 0.00% )
6,011,337,533 uops_executed_stall_cycles:u # 81.855 M/sec ( +- 1.27% )
73.436831004 seconds time elapsed ( +- 0.05% )
( +- x %)jest odchyleniem standardowym dla 4 przebiegów dla tej liczby. Ciekawe, że działa tak okrągła liczba instrukcji. 924 miliardów to nie przypadek. Wydaje mi się, że w zewnętrznej pętli działa łącznie 924 instrukcji.
uops_issuedjest liczbą domen połączonych (istotną dla przepustowości problemów frontonu), podczas gdy uops_executedjest liczbą domen nieużywanych (liczba operacji wysyłania do portów wykonawczych). Mikro-fuzja pakuje 2 nieuprawnione domeny w jedną domenę o fuzji domeny, ale mov-eliminacja oznacza, że niektóre uopsy domeny nie wymagają portów wykonawczych. Zobacz połączone pytanie, aby uzyskać więcej informacji na temat liczenia domen upops i fused vs. (Zobacz także tabele instrukcji Agner Fog i przewodnik uarch oraz inne przydatne linki w wiki tagu SO x86 ).
Z innego pomiaru mierzącego różne rzeczy: brak pamięci podręcznej L1D jest całkowicie nieistotny, zgodnie z oczekiwaniami dla odczytu / zapisu tych samych dwóch buforów 456B. Gałąź pętli wewnętrznej błędnie przewiduje raz na pętlę zewnętrzną (gdy nie jest podejmowana, aby opuścić pętlę). (Całkowity czas jest dłuższy, ponieważ komputer nie był całkowicie bezczynny. Prawdopodobnie drugi logiczny rdzeń był aktywny przez pewien czas, a więcej czasu spędzano na przerwaniach (ponieważ częstotliwość mierzona w przestrzeni użytkownika była dalej niższa niż 4.400 GHz). Lub więcej rdzeni było aktywnych przez dłuższy czas, obniżając maksymalne turbo. Nie śledziłem, cpu_clk_unhalted.one_thread_activeczy konkurencja HT jest problemem.)
### Another run of the same 105/106B "main" version to check other perf counters
74510.119941 task-clock:u (msec) # 1.000 CPUs utilized
0 context-switches:u # 0.000 K/sec
0 cpu-migrations:u # 0.000 K/sec
2 page-faults:u # 0.000 K/sec
324,455,912,026 cycles:u # 4.355 GHz
924,000,036,632 instructions:u # 2.85 insn per cycle
228,005,015,542 L1-dcache-loads:u # 3069.535 M/sec
277,081 L1-dcache-load-misses:u # 0.00% of all L1-dcache hits
0 ld_blocks_partial_address_alias:u # 0.000 K/sec
115,000,030,234 branches:u # 1543.415 M/sec
1,000,017,804 branch-misses:u # 0.87% of all branches
Mój kod może być uruchamiany w mniejszej liczbie cykli na Ryzen, co może powodować 5 uopsów na cykl (lub 6, gdy niektóre z nich to instrukcje 2 uop, takie jak AVX 256b na Ryzen). Nie jestem pewien, co zrobiłby jego front-end stosd, czyli 3 ulepszenia na Ryzen (tak samo jak Intel). Myślę, że pozostałe instrukcje w wewnętrznej pętli mają takie same opóźnienia jak Skylake i wszystkie pojedynczo. (W tym adc eax, [edi+edx], co stanowi przewagę nad Skylake).
Mogłoby to być prawdopodobnie znacznie mniejsze, ale może 9-krotnie wolniejsze, jeśli zapisałem liczby jako 1 cyfrę dziesiętną na bajt . Generowanie wykonania cmpi dostosowywanie za pomocą cmovdziałałoby tak samo, ale wykonaj 1/9 pracy. Działa również 2 cyfry dziesiętne na bajt (base-100, nie 4-bitowy BCD ze spowolnieniemDAA ) i div r8/ add ax, 0x3030zamienia 0-99 bajtów na dwie cyfry ASCII w kolejności drukowania. Ale 1 cyfra na bajt wcale nie potrzebuje div, wystarczy zapętlić i dodać 0x30. Jeśli przechowam bajty w kolejności drukowania, to sprawi, że druga pętla stanie się naprawdę prosta.
Zastosowanie 18 lub 19 cyfr dziesiętnych na 64-bitową liczbę całkowitą (w trybie 64-bitowym) sprawiłoby, że działałby on około dwa razy szybciej, ale kosztował znaczny rozmiar kodu dla wszystkich prefiksów REX i dla 64-bitowych stałych. 32-bitowe kończyny w trybie 64-bitowym uniemożliwiają użycie pop eaxzamiast lodsd. Nadal mogłem uniknąć prefiksów REX, używając espjako rejestru non-point scratch (zamieniając użycie esii esp), zamiast używać r8djako 8. rejestr.
W przypadku wersji z funkcją wywoływania konwersja do wersji 64-bitowej i używanie r8dmoże być tańsze niż zapisywanie / przywracanie rsp. 64-bitowe również nie mogą używać dec r32kodowania jednobajtowego (ponieważ jest to przedrostek REX). Ale głównie skończyło się na dec bltym, że 2 bajty. (Ponieważ mam stałą w górnych bajtach ebxi używam jej tylko poza wewnętrznymi pętlami, co działa, ponieważ niski bajt stałej jest 0x00.)
Wersja o wysokiej wydajności
Aby uzyskać maksymalną wydajność (nie kod-golf), należy rozwinąć wewnętrzną pętlę, aby działała co najwyżej 22 iteracje, co jest wystarczająco krótkim wzorcem wziętym / nie wziętym, aby predyktory gałęzi działały dobrze. W moich eksperymentach, mov cl, 22zanim .inner: dec cl/jnz .innerpętla zawiera bardzo mało nieprzewidywalnych wyników (np. 0,05%, znacznie mniej niż jeden na pełny przebieg wewnętrznej pętli), ale mov cl,23błędnie przewiduje od 0,35 do 0,6 razy na wewnętrzną pętlę. 46jest szczególnie zły, nieprzewidywalny ~ 1,28 razy na pętlę wewnętrzną (128 mln razy dla iteracji 100M pętli zewnętrznej). 114źle przewidziany dokładnie raz na wewnętrzną pętlę, tak samo jak znalazłem jako część pętli Fibonacciego.
Zainteresowałem się i wypróbowałem to, rozwijając wewnętrzną pętlę o 6 za pomocą %rep 6(ponieważ to równomiernie dzieli 114). To w większości wyeliminowało brakujące oddziały. Zrobiłem edxujemny i użyłem go jako offsetu dla movsklepów, więc adc eax,[edi]mogłem pozostać mikro-stopiony. (I tak mogłem uniknąć stosd). Wyciągnąłem leaaktualizację ediz %repbloku, więc wykonuje tylko jedną aktualizację wskaźnika na 6 sklepów.
Pozbyłem się również wszystkich częściowych rejestrów w zewnętrznej pętli, choć nie sądzę, żeby to miało znaczenie. Być może pomógł nieznacznie mieć CF na końcu zewnętrznej pętli, niezależny od ostatecznego ADC, więc niektóre ze zmian w pętli wewnętrznej można zacząć. Kod pętli zewnętrznej można prawdopodobnie zoptymalizować nieco bardziej, ponieważ neg edxbyła to ostatnia rzecz, którą zrobiłem, po zastąpieniu xchgtylko 2 movinstrukcjami (ponieważ wciąż miałem 1) i ponownym rozmieszczeniu łańcuchów dep wraz z upuszczeniem 8-bitów zarejestrować rzeczy.
To jest źródło NASM tylko pętli Fibonacciego. Jest to drop-in zamiennik tej sekcji oryginalnej wersji.
;;;; Main loop, optimized for performance, not code-size
%assign unrollfac 6
mov bl, limbcount/unrollfac ; and at the end of the outer loop
align 32
.fibonacci:
limbcount equ 114 ; 112 = 1006 decimal digits / 9 digits per limb. Not enough for 1000 correct digits, but 114 is.
; 113 would be enough, but we depend on limbcount being even to avoid a sub
; align 8
.digits_add:
%assign i 0
%rep unrollfac
;lodsd ; Skylake: 2 uops. Or pop rax with rsp instead of rsi
; mov eax, [esp]
; lea esp, [esp+4] ; adjust ESP without affecting CF. Alternative, load relative to edi and negate an offset? Or add esp,4 after adc before cmp
pop eax
adc eax, [edi+i*4] ; read from a potentially-offset location (but still store to the front)
;; jz .out ;; Nope, a zero digit in the result doesn't mean the end! (Although it might in base 10**9 for this problem)
lea esi, [eax - 1000000000]
cmp ebp, eax ; sets CF when (base-1) < eax. i.e. when eax>=base
cmovc eax, esi ; eax %= base, keeping it in the [0..base) range
%if 0
stosd
%else
mov [edi+i*4+edx], eax
%endif
%assign i i+1
%endrep
lea edi, [edi+4*unrollfac]
dec bl ; preserves CF. The resulting partial-flag merge on ADC would be slow on pre-SnB CPUs
jnz .digits_add
; bl=0, ebx=-1024
; esi has its high bit set opposite to CF
.end_innerloop:
;; after a non-zero carry-out (CF=1): right-shift both buffers by 1 limb, over the course of the next two iterations
;; next iteration with r8 = 1 and rsi+=4: read offset from both, write normal. ends with CF=0
;; following iter with r8 = 1 and rsi+=0: read offset from dest, write normal. ends with CF=0
;; following iter with r8 = 0 and rsi+=0: i.e. back to normal, until next carry-out (possible a few iters later)
;; rdi = bufX + 4*limbcount
;; rsi = bufY + 4*limbcount + 4*carry_last_time
; setc [rdi]
; mov dl, dh ; edx=0. 2c latency on SKL, but DH has been ready for a long time
; adc edx,edx ; edx = CF. 1B shorter than setc dl, but requires edx=0 to start
setc al
movzx edx, al
mov [edi], edx ; store the carry-out into an extra limb beyond limbcount
shl edx, 2
;; Branching to handle the truncation would break the data-dependency (of pointers) on carry-out from this iteration
;; and let the next iteration start, but we bottleneck on the front-end (9 uops)
;; not the loop-carried dependency of the inner loop (2 cycles for adc->cmp -> flag input of adc next iter)
;; Since the pattern isn't perfectly regular, branch mispredicts would hurt us
; keep -1024 in ebx. Using bl for the limb counter leaves bl zero here, so it's back to -1024 (or -2048 or whatever)
mov eax, esp
and esp, 4 ; only works if limbcount is even, otherwise we'd need to subtract limbcount first.
and edi, ebx ; -1024 ; revert to start of buffer, regardless of offset
add edi, edx ; read offset in next iter's src
;; maybe or edi,edx / and edi, 4 | -1024? Still 2 uops for the same work
;; setc dil?
;; after adjusting src, so this only affects read-offset in the dst, not src.
or edx, esp ; also set r8d if we had a source offset last time, to handle the 2nd buffer
mov esp, edi
; xchg edi, esp ; Fibonacci: dst and src swap
and eax, ebx ; -1024
;; mov edi, eax
;; add edi, edx
lea edi, [eax+edx]
neg edx ; negated read-write offset used with store instead of load, so adc can micro-fuse
mov bl, limbcount/unrollfac
;; Last instruction must leave CF clear for next iter
; loop .fibonacci ; Maybe 0.01% slower than dec/jnz overall
; dec ecx
sub ecx, 1 ; clear any flag dependencies. No faster than dec, at least when CF doesn't depend on edx
jnz .fibonacci
Występ:
Performance counter stats for './fibonacci-1G-performance' (3 runs):
62280.632258 task-clock (msec) # 1.000 CPUs utilized ( +- 0.07% )
0 context-switches:u # 0.000 K/sec
0 cpu-migrations:u # 0.000 K/sec
3 page-faults:u # 0.000 K/sec ( +- 12.50% )
273,146,159,432 cycles # 4.386 GHz ( +- 0.07% )
757,088,570,818 instructions # 2.77 insn per cycle ( +- 0.00% )
740,135,435,806 uops_issued_any # 11883.878 M/sec ( +- 0.00% )
966,140,990,513 uops_executed_thread # 15512.704 M/sec ( +- 0.00% )
75,953,944,528 resource_stalls_any # 1219.544 M/sec ( +- 0.23% )
741,572,966 idq_uops_not_delivered_core # 11.907 M/sec ( +- 54.22% )
62.279833889 seconds time elapsed ( +- 0.07% )
To dotyczy tego samego Fib (1G), wytwarzając tę samą moc wyjściową w 62,3 sekundy zamiast 73 sekund. (273.146G cykli, w porównaniu z 322.467G. Ponieważ wszystko uderza w pamięć podręczną L1, cykle zegara rdzenia to naprawdę wszystko, na co musimy spojrzeć.)
Zwróć uwagę na znacznie niższą całkowitą uops_issuedliczbę, znacznie poniżej uops_executedliczby. Oznacza to, że wiele z nich zostało połączonych w trybie mikro: 1 uop w domenie z fuzją (problem / ROB), ale 2 uop w domenie bez fuzji (harmonogram / jednostki wykonawcze)). I niewielu zostało wyeliminowanych na etapie wydania / zmiany nazwy (np. movKopiowanie rejestru lub xorzerowanie, które wymagają wydania, ale nie potrzebują jednostki wykonawczej). Wyeliminowane ups będą równoważyć liczbę w drugą stronę.
branch-missesspada do ~ 400k, z 1G, więc rozwijanie działało. resource_stalls.anyjest teraz znaczący, co oznacza, że front-end nie jest już wąskim gardłem: zamiast tego back-end jest w tyle i ogranicza front-end. idq_uops_not_delivered.coreliczy tylko cykle, w których front-end nie dostarczał poprawek, ale back-end nie został zablokowany. To miłe i niskie, wskazujące na kilka wąskich gardeł z przodu.
Ciekawostka: wersja Pythona spędza ponad połowę czasu dzieląc przez 10, a nie dodając. (Wymiana a/=10z a>>=64prędkościami go o więcej niż współczynnik 2, ale zmienia wynik bo obcinanie binarnym! = Dziesiętny obcięcie).
Moja wersja asm jest oczywiście zoptymalizowana specjalnie dla tego rozmiaru problemu, a iteracja pętli liczy się na sztywno. Nawet przesunięcie liczby o dowolnej dokładności spowoduje jej skopiowanie, ale moja wersja może po prostu odczytać offset z następnych dwóch iteracji, aby pominąć nawet to.
Profilowałem wersję Pythona (64-bitowy python2.7 na Arch Linux):
ocperf.py stat -etask-clock,context-switches:u,cpu-migrations:u,page-faults:u,cycles,instructions,uops_issued.any,uops_executed.thread,arith.divider_active,branches,branch-misses,L1-dcache-loads,L1-dcache-load-misses python2.7 ./fibonacci-1G.anders-brute-force.py
795231787455468346782938519619714818925554218523439891345303993734324668618251937005099962613655677933248203572322245122629171445627564825949953061211130125549987963951605345978901870056743994684484303459980241992404375340195011483010723426503784142698039838736078428423199645734078278420076776090777770318318574465653625351150285171596335102399069923259547132267036550648243596658688604862715971691635144878852742743550811390916796390738039824284803398011027637054426428503274436478119845182546213052952963333981348310577137012811185112824713631141420831898380252690791778709480221775085968511636388337484742803673714788207995668880750915837224945143751932016258200200053079830988726125702820190750937055423293110708497685471583358562391045067944912001156476292564914450953190468498441700251208650402077901250135617787419960508555831719090539513446891944331302682481336323419049437559926255302546652883812263943360048384953507064771198676927956854879685520768489774177178437585949642538435587910579974100118580
Performance counter stats for 'python2.7 ./fibonacci-1G.anders-brute-force.py':
755380.697069 task-clock:u (msec) # 1.000 CPUs utilized
0 context-switches:u # 0.000 K/sec
0 cpu-migrations:u # 0.000 K/sec
793 page-faults:u # 0.001 K/sec
3,314,554,673,632 cycles:u # 4.388 GHz (55.56%)
4,850,161,993,949 instructions:u # 1.46 insn per cycle (66.67%)
6,741,894,323,711 uops_issued_any:u # 8925.161 M/sec (66.67%)
7,052,005,073,018 uops_executed_thread:u # 9335.697 M/sec (66.67%)
425,094,740,110 arith_divider_active:u # 562.756 M/sec (66.67%)
807,102,521,665 branches:u # 1068.471 M/sec (66.67%)
4,460,765,466 branch-misses:u # 0.55% of all branches (44.44%)
1,317,454,116,902 L1-dcache-loads:u # 1744.093 M/sec (44.44%)
36,822,513 L1-dcache-load-misses:u # 0.00% of all L1-dcache hits (44.44%)
755.355560032 seconds time elapsed
Liczby w (parens) określają, ile czasu próbkowany był licznik perf. Patrząc na więcej liczników niż obsługuje HW, perf obraca się między różnymi licznikami i ekstrapoluje. To całkiem dobrze na długi okres tego samego zadania.
Gdybym uruchomił perfpo ustawieniu sysctl kernel.perf_event_paranoid = 0(lub uruchomieniu perfjako root), to by to zmierzyło 4.400GHz. cycles:unie liczy czasu spędzonego na przerwaniach (lub wywołaniach systemowych), tylko cykle przestrzeni użytkownika. Mój pulpit był prawie całkowicie bezczynny, ale jest to typowe.
Your program must be fast enough for you to run it and verify its correctness.co z pamięcią?