(리눅스 시스템 호출 포함)의 x86 32 비트 컴퓨터 코드 (106) 105 바이트

changelog : off-by-one 상수는 Fib (1G)의 결과를 변경하지 않으므로 빠른 버전에서 바이트를 저장했습니다.

또는 v (스카이 레이크)에 18 % 느린 102 바이트 (사용은 mov/ sub/ cmc대신 lea/ cmp내부 루프에서 반출 및 포장지를 생성하는 10**9대신 2**32). 또는 가장 안쪽 루프의 캐리 처리에 분기가있는 ~ 5.3x 느린 버전의 경우 101 바이트입니다. (저는 25.4 %의 지사 예측률을 측정했습니다!)

또는 선행 0이 허용되는 경우 104/101 바이트. (출력의 1 자리를 건너 뛰는 하드 코드에는 1 바이트가 더 필요하므로 Fib (10 ** 9)에 필요합니다.)

불행히도 TIO의 NASM 모드 -felf32는 컴파일러 플래그에서 무시 되는 것 같습니다 . 어쨌든 주석에 실험 아이디어가 엉망인 내 소스 코드와 의 링크가 있습니다.

이것은 완전한 프로그램 입니다. Fib (10 ** 9)의 첫 1000 자리 숫자 다음에 여분의 숫자 (마지막 소수가 잘못됨)와 가비지 바이트 (줄 바꿈 제외)가 뒤 따릅니다. 가비지의 대부분은 비 ASCII이므로을 통해 파이프 할 수 있습니다 cat -v. 그래도 터미널 에뮬레이터 (KDE konsole)를 중단하지 않습니다 . “쓰레기 바이트”는 Fib (999999999)를 저장하고 있습니다. 이미 -1024레지스터에 있었으므로 적절한 크기보다 1024 바이트를 인쇄하는 것이 더 저렴했습니다.

ELF 실행 파일로 만드는 보풀이 아닌 머신 코드 (정적 실행 파일의 텍스트 세그먼트 크기) 만 계산합니다. ( 매우 작은 ELF 실행 파일이 가능 하지만 귀찮게하고 싶지 않았습니다). BSS 대신 스택 메모리를 사용하는 것이 더 짧았습니다. 따라서 메타 데이터에 의존하지 않기 때문에 바이너리에서 다른 것을 계산하지 않을 수 있습니다. (일반적으로 제거 된 정적 바이너리를 생성하면 340 바이트 ELF가 실행 가능합니다.)

C에서 호출 할 수있는이 코드에서 함수를 만들 수 있습니다. 스택 포인터 (MMX 레지스터에있을 수 있음) 및 기타 오버 헤드를 저장 / 복원하는 데 몇 바이트가 필요하지만 문자열과 함께 반환하여 바이트를 절약 할 수 있습니다 write(1,buf,len)시스템 호출 대신 메모리에 . 기계 코드로 골프를 타면 여기에서 약간의 여유를 얻을 수 있다고 생각합니다. 다른 누구도 네이티브 확장 정밀도없이 어떤 언어로도 답변을 게시하지 않았지만이 기능 버전은 전체를 다시 골핑하지 않고 여전히 120 바이트 미만이어야한다고 생각합니다. 의회.

연산:

brute force a+=b; swap(a,b), 선행> = 1017 소수만 유지하기 위해 필요에 따라 잘립니다. 내 컴퓨터에서 1 분 13 초 (또는 322.47 억 클럭 사이클 +-0.05 %)로 실행됩니다 (코드 크기의 몇 바이트가 더 있으면 몇 % 빠르거나 루프 언 롤링으로 인해 코드 크기가 훨씬 커 62 %까지 떨어질 수 있습니다). 영리한 수학, 오버 헤드를 줄이면서 동일한 작업을 수행하십시오). 내 컴퓨터 (4.4GHz Skylake i7-6700k)에서 12min35s에서 실행되는 @AndersKaseorg의 Python 구현을 기반으로 합니다. 두 버전 모두 L1D 캐시 누락이 없으므로 DDR4-2666은 중요하지 않습니다.

파이썬과는 달리, 확장 자릿수는 잘린 십진수를 자유롭게 만드는 형식으로 저장합니다 . 32 비트 정수 당 9 자리 숫자 그룹을 저장하므로 포인터 오프셋은 하위 9 자리를 버립니다. 이것은 10의 거듭 제곱 인 사실상 10 억의 기본입니다. (이 도전이 10 억 피보나치 수를 필요로하는 것은 순수한 우연의 일치이지만, 2 바이트와 2 개의 상수를 절약 할 수 있습니다.)

다음 의 GMP 용어, 확장 밀도 숫자의 각 32 비트 청크는 “사지”라고합니다. 추가하는 동안 수행은 1e9와 비교하여 수동으로 생성해야하지만 일반적으로 다음 팔다리 의 일반적인 ADC명령에 대한 입력으로 사용됩니다 . (또한 [0..999999999]2 ^ 32 ~ = 4.295e9가 아닌 수동으로 범위를 줄 바꿈해야합니다 . 비교의 수행 결과를 사용하여 lea+ 없이 분기 없이이 작업을 cmov수행합니다.)

마지막 사지가 0이 아닌 캐리 아웃을 생성 할 때 외부 루프의 다음 두 번의 반복은 정상보다 1 사지에서 읽지 만 여전히 동일한 위치에 씁니다. 이것은 memcpy(a, a+4, 114*4)1 사지만큼 오른쪽으로 이동하는 것과 같지만 다음 두 추가 루프의 일부로 수행됩니다. 이것은 ~ 18 반복마다 발생합니다.

크기 절약 및 성능을위한 해킹 :

• 내가 알면 lea ebx, [eax-4 + 1]대신 같은 일반적인 것들 . 그리고 속도 가 느려지 는 곳 에서만 사용하십시오.mov ebx, 1eax=4loopLOOP

• adc내부 루프 에서 버퍼의 시작 부분에 계속 쓰는 동안 우리가 읽는 포인터를 오프셋하여 1 개의 팔 다리를 무료로 자릅니다 . 에서 읽고 [edi+edx]씁니다 [edi]. 따라서 대상에 대한 읽기 / 쓰기 오프셋을 얻 edx=0거나 얻을 수 있습니다 4. 먼저 두 가지를 모두 오프셋 한 다음 dst 만 오프셋하는 두 번의 연속 반복에 대해이 작업을 수행해야합니다. esp&4버퍼 앞쪽으로 포인터를 재설정하기 전에 ( &= -1024버퍼가 정렬되어 있기 때문에를 사용하여 ) 두 번째 경우를 감지합니다 . 코드에서 주석을 참조하십시오.

• (정적 실행 파일의 경우) Linux 프로세스 시작 환경은 대부분의 레지스터를 0으로 만들고 esp/ 아래의 스택 메모리 rsp는 0으로 설정합니다. 내 프로그램은 이것을 활용합니다. 호출 할 수없는 기능 버전 (할당되지 않은 스택이 더러울 수있는 곳)에서 0으로 된 메모리에 BSS를 사용할 수 있습니다 (포인터를 설정하는 데 4 바이트가 더 필요합니다). 제로화에는 edx2 바이트가 필요합니다. x86-64 System V ABI는 이들 중 하나를 보증하지 않지만 Linux의 구현은 커널에서 정보 유출을 피하기 위해 제로를 수행하지 않습니다. 동적으로 연결된 프로세스에서 /lib/ld.sobefore 실행 _start하고 레지스터를 0이 아닌 상태로 둡니다 (아마도 스택 포인터 아래의 메모리에서 가비지).

• 루프 외부 -1024에서 ebx사용하기 위해 보관 합니다. bl내부 루프의 카운터로 사용 하여 0으로 끝납니다 (의 하위 바이트 -1024이므로 루프 외부에서 사용하기 위해 상수를 복원). Intel Haswell 이상에는 low8 레지스터에 대한 부분 레지스터 병합 처벌이 없으며 실제로 이름을 따로 바꾸지 않아도 되므로 AMD와 같이 전체 레지스터에 대한 종속성이 있습니다 (여기에서는 문제가 아닙니다). 그러나 이것은 Nehalem 및 그 이전 버전에서 끔찍한 일이지만 병합 할 때 부분 등록 마구간이 있습니다. 부분 xor정규식을 작성한 다음 -zeroing 또는 a 없이 전체 정규식 을 읽는 다른 장소가 있습니다 .movzx일반적으로 이전 코드 중 일부가 상위 바이트를 0으로 만들었으므로 AMD와 Intel SnB 제품군에서는 괜찮지 만 Intel 사전 Sandybridge에서는 느립니다.

  1024stdout ( sub edx, ebx) 에 쓸 바이트 수로 사용 하므로 mov edx, 1000더 많은 바이트 비용이 들기 때문에 프로그램에서 피보나치 숫자 뒤에 가비지 바이트를 인쇄 합니다.

• (사용되지 않음) adc ebx,ebxEBX = 0을 사용하여 EBX = CF를 얻고 1 바이트를 절약 setc bl합니다.

• dec/ jnz내부 adc루프 adc는 Intel Sandybridge 이상에서 플래그를 읽을 때 부분 플래그 스톨을 발생시키지 않고 CF를 유지 합니다. 초기 CPU 에서는 나쁘지만 Skylake에서는 AFAIK가 무료입니다. 또는 최악의 경우, 여분의 UOP.

• 아래의 메모리를 esp거대한 적색 영역 으로 사용하십시오 . 이것은 완전한 Linux 프로그램이므로 신호 처리기를 설치하지 않았으며 사용자 공간 스택 메모리를 비동기식으로 클로버하는 것은 없습니다. 다른 OS에서는 그렇지 않을 수 있습니다.

• 스택 엔진 을 활용 하여 pop eax( lodsdHaswell / Skylake에서 2 개, IvB에서 3 개 이하, Agner Fog의 명령어 표 에 따라 이전에 ) 대신 (1 uop + 가끔 스택 동기화 uop) 을 사용하여 uop 문제 대역폭을 절약하십시오 . IIRC,이 내가 아마를 사용하는 같은 속도를 얻을 수 (73) (83)에 대한 초에서 런타임을 떨어 mov처럼, 색인 어드레싱 모드와 함께 mov eax, [edi+ebp]어디 ebpSRC에와 DST 버퍼 사이의 오프셋을 보유하고 있습니다. 피보나치 반복을 위해 src와 dst를 교체하는 과정에서 오프셋 레지스터를 무효화해야하므로 내부 루프 외부의 코드가 더 복잡해집니다. 자세한 내용은 아래 “성능”섹션을 참조하십시오.

• 어디서나 메모리 stc에 저장하는 대신 첫 번째 반복에 캐리 인 (1 바이트 ) 을 부여하여 시퀀스를 시작하십시오 1. 주석에 문서화 된 다른 많은 문제 관련 내용.

NASM 목록 (기계 코드 + 소스) , 생성 nasm -felf32 fibonacci-1G.asm -l /dev/stdout | cut -b -28,$((28+12))- | sed 's/^/ /'. 그런 다음 주석 처리 된 일부 블록을 수동으로 제거했기 때문에 행 번호 매기기에 공백이 있습니다. 선행 열을 제거하여 YASM 또는 NASM에 공급할 수 있도록하려면을 사용하십시오 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

이 중 몇 바이트를 더 골프를 칠 여지가 있지만 이미 2 일 동안 12 시간 이상을 보냈습니다. 속도가 충분히 빠르지 만 속도를 낮추는 방법이 있지만 속도를 희생하고 싶지 않습니다 . 내가 게시 한 이유 중 하나는 무차별 asm 버전을 얼마나 빨리 만들 수 있는지 보여주는 것입니다. 누군가가 실제로 최소 크기로 가고 싶지만 아마도 10 배 느리게 (예 : 바이트 당 1 자리), 이것을 시작점으로 자유롭게 복사하십시오.

결과 실행 파일 ( yasm -felf32 -Worphan-labels -gdwarf2 fibonacci-1G.asm && ld -melf_i386 -o fibonacci-1G fibonacci-1G.o)은 340B (스트립)입니다.

size fibonacci-1G
 text    data     bss     dec     hex filename
  105       0       0     105      69 fibonacci-1G

공연

내부 adc루프는 Skylake에서 10 개의 융합 도메인 uops (~ 128 바이트마다 +1 스택 동기화 uop)이므로 최적의 프론트 엔드 처리량 (스택 동기화 uops 무시)으로 Skylake에서 ~ 2.5 사이클 당 하나씩 발행 할 수 있습니다. . 임계 경로 대기 시간은 adc-> cmp-> 다음 반복의 adc루프 전달 종속성 체인에 대해 2주기 이므로 병목 현상은 반복 당 ~ 2.5주기의 프런트 엔드 문제 제한이어야합니다.

adc eax, [edi + edx]실행 포트에 대한 2 개의 융합되지 않은 도메인 uops : load + ALU. 그것은 디코더 (1 융합 도메인 uop)에서 마이크로 융합하지만 , Haswell / Skylake 에서조차도 인덱싱 된 어드레싱 모드로 인해 이슈 단계에서 2 융합 도메인 uops로 라미네이트되지 않습니다 . 필자는 마이크로 퓨전을 add eax, [edi + edx]유지하는 것처럼 생각 했지만 인덱싱 된 주소 지정 모드를 유지하면 이미 3 개의 입력 (플래그, 메모리 및 대상)이있는 Uops에서는 작동하지 않을 수 있습니다. 내가 그것을 썼을 때, 그것은 성능 저하가 없을 것이라고 생각했지만 잘못되었습니다. 이 잘림 처리 방법 edx은 0 또는 4에 관계없이 매번 내부 루프를 느리게합니다 .

저장소를 오프셋 edi하고 edx조정 하여 dst에 대한 읽기 / 쓰기 오프셋을 처리하는 것이 더 빠릅니다 . 그래서 adc eax, [edi]/ … / mov [edi+edx], eax/ lea edi, [edi+4]대신 stosd. Haswell 이상은 인덱싱 된 저장소를 마이크로 퓨즈 한 상태로 유지할 수 있습니다. (Sandybridge / IvB도 라미네이트하지 않습니다.)

인텔 하 스웰과에 이전 adc과는 cmovc2C 대기 시간이 2 마이크로 연산 각각이다 . ( adc eax, [edi+edx]여전히 Haswell에 라미네이팅되어 있으며 3 개의 통합 도메인 Uops로 문제가 있습니다). Broadwell 이상 은 AMD에서 오랫동안 사용했던 것처럼 단일 FOP (Haswell), 단일 Uop 명령어 작성 adc및 cmovc(및 기타 몇 가지) 이상의 3 입력 UOP를 허용 합니다. (이것이 AMD가 오랫동안 확장 정밀 GMP 벤치 마크에서 잘 수행 한 이유 중 하나입니다.) 어쨌든 Haswell의 내부 루프는 12uops (때로는 +1 스택 동기화 uop) 여야하며 프런트 엔드 병목 현상은 ~ 3c입니다. 스택 싱크 uops를 무시하고 최상의 경우.

루프 내 pop에서 밸런싱없이 사용 push하면 루프가 LSD (loop stream detector)에서 실행될 수 없으며 매번 uop 캐시에서 IDQ로 다시 읽어야합니다. 9 또는 10 uop ​​루프가 매 사이클마다 4 uops에서 최적으로 발행되지 않기 때문에 Skylake에서 좋은 점입니다 . 이것은 아마도 대체 lodsd가 pop많은 도움 이 된 이유 중 일부 일 것입니다 . (LSD는 스택 동기화 uop 을 삽입 할 공간을 남기지 않기 때문에 Uops를 잠글 수 없습니다 .) 해당 업데이트를 받기 전에

필자는 Haswell에서 프로파일을 작성했으며 메모리가 아닌 L1D 캐시 만 사용하므로 CPU 주파수에 관계없이 381.31 십억 클럭 사이클로 실행되는 것을 발견했습니다. 프런트 엔드 문제 처리량은 Skylake의 경우 3.70에 비해 클록 당 3.72 개의 융합 도메인 uops였습니다. (기 때문에 물론 사이클 당 지침은 2.87에서 2.42로 내려했다 adc및 cmov스웰 2 마이크로 연산이다.)

push매번 스택 동기화 uop을 트리거 stosd하기 때문에 대체하는 것이별로 도움이되지 않습니다 adc [esp + edx]. 그리고 바이트가 필요하기 std때문에 lodsd다른 방향으로 진행됩니다. ( mov [edi], eax/ lea edi, [edi+4]대체 stosd100M iters위한 31,954Mcycles에 100M iters위한 32,909Mcycles에서가는 승이다. 그것은 보인다 stosd3 마이크로 연산 등의 복호를, 스토어 어드레스 / 저장 데이터로는하지 마이크로 융합하므로 마이크로 연산 push+ 스택 동기화 죄송합니다. stosd)

Skylake의 빠른 105B 버전 의 경우 1,114 개의 사지 1G 반복에 대해 ~ 322.47 십억 사이클의 실제 성능은 내부 루프 반복마다 2.824 사이클로 작동합니다 . (아래 ocperf.py출력 참조). 정적 분석에서 예상 한 것보다 느리지 만 외부 루프 및 스택 동기화 UOP의 오버 헤드를 무시하고있었습니다.

받침대를 성능 branches및 branch-misses쇼 그 내부 루프 예측 오류 외부 루프 당 (이 촬영 아니에요 마지막 반복에) 한 번. 그것은 또한 여분의 시간의 일부를 설명합니다.

mov esi,eaxsub eax,ebpcmovc eax, esicmclea esi, [eax - 1000000000]/ cmp ebp,eax/ cmovc(6 + 2 + 3 = 11B 대신 / / / (2 + 2 + 3 + 1 = 8B)를 사용하여 가장 안쪽의 루프가 임계 경로에 대해 3 사이클 대기 시간을 갖도록하여 코드 크기를 절약 할 수 있습니다 ). cmov/는 stosd임계 경로 꺼져 있습니다. (증분-에디 오 stosd의 상점과 별도로 실행할 수 있으므로 각 반복은 짧은 종속성 체인을 분기합니다.) ebp init 명령을에서 lea ebp, [ecx-1]로 변경하여 다른 1B를 저장하는 데 사용 mov ebp,eax되었지만 잘못된 것을 발견했습니다.ebp결과를 바꾸지 않았습니다. 이렇게하면 캐리를 래핑하고 생성하는 대신 팔다리를 정확히 == 1000000000으로 만들 수 있지만이 오류는 Fib ()가 성장하는 것보다 느리게 전파되므로 최종 결과의 선행 1k 자리를 변경하지 않습니다. 또한 오버플로없이 유지할 수있는 공간이 있기 때문에 우리가 추가 할 때 오류가 스스로 해결할 수 있다고 생각합니다. 1G + 1G조차도 32 비트 정수를 오버플로하지 않으므로 결국 위쪽으로 스며 들거나 잘립니다.

3c 대기 시간 버전은 1 개의 추가 UOP이므로 프런트 엔드는 Skylake에서 2.75c주기마다 하나씩 발행 할 수 있으며 백 엔드가 실행할 수있는 것보다 약간 더 빠릅니다. (Haswell에서는 여전히을 사용 adc하고 있기 때문에 총 13 cmovuops가 될 것입니다.

실제로 3 / 2.5 = 1.2가 아닌 Skylake에서 1.18 느린 속도 (사지 당 3.34주기)를 실행합니다. 스택 동기화없이 내부 루프를 보면서 프런트 엔드 병목 현상을 대기 시간 병목 현상으로 대체 할 것으로 예상했습니다. 죄송합니다. 스택 동기화 Uops는 빠른 버전에만 영향을 미치기 때문에 (레이턴시 대신 프런트 엔드에서 병목 현상이 발생 함)이를 설명하는 데 많은 시간이 걸리지 않습니다. 예 : 3 / 2.54 = 1.18.

또 다른 요인은 3c 대기 시간 버전이 임계 경로가 여전히 실행되는 동안 내부 루프를 떠날 때의 오해를 감지 할 수 있다는 것입니다 (프론트 엔드가 백엔드보다 앞서 갈 수 있기 때문에 비 순차적 실행으로 인해 루프가 실행될 수 있음) 카운터 잘못된), 따라서 효과적인 잘못된 예측 페널티가 낮습니다. 이러한 프론트 엔드 사이클을 잃으면 백엔드를 따라 잡을 수 있습니다.

그렇지 않은 경우 cmccarry_out-> edx 및 esp 오프셋을 분기없이 처리하는 대신 외부 루프에서 분기를 사용하여 3c 버전의 속도를 높일 수 있습니다. 데이터 종속성 대신 제어 종속성에 대한 분기 예측 + 추론 실행 adc은 이전 내부 루프의 UOP가 여전히 비행 중일 때 다음 반복에서 루프를 실행하기 시작할 수 있습니다. 분기없는 버전에서 내부 루프의로드 주소 adc는 마지막 사지 의 마지막 CF로부터 데이터 종속성을 갖습니다 .

프론트 엔드에서 2c 대기 시간 내부 루프 버전 병목 현상이 발생하므로 백엔드는 거의 유지됩니다. 외부 루프 코드가 대기 시간이 길면 프런트 엔드는 다음 내부 루프 반복에서 uops를 발행 할 수 있습니다. (그러나이 경우 외부 루프 항목에는 ILP 가 많고 대기 시간이 긴 항목이 없으므로 백엔드는 비 주문형 스케줄러에서 Uops를 통해 씹기 시작할 때 따라 잡을 수 없습니다. 입력이 준비됩니다).

### 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 %)해당 횟수에 대한 4 회 실행의 표준 편차입니다. 그것이 많은 수의 명령을 실행한다는 점이 흥미 롭습니다. 924 십억은 우연의 일치 가 아닙니다 . 외부 루프가 총 924 개의 명령을 실행한다고 생각합니다.

uops_issued통합 도메인 수 (프런트 엔드 문제 대역폭 uops_executed과 관련됨 )이고 통합 되지 않은 도메인 수 (실행 포트로 전송 된 uops 수)입니다. Micro-fusion은 2 개의 unfused-domain uops를 하나의 fused-domain uop으로 압축하지만, mov-elimination 은 일부 fused-domain uops에는 실행 포트가 필요하지 않음을 의미합니다. uops 및 fused vs. unfused 도메인 계산에 대한 자세한 내용은 연결된 질문을 참조하십시오. (또한 Agner Fog의 명령어 표 및 uarch 안내서 및 SO x86 태그 위키 의 기타 유용한 링크를 참조하십시오 ).

다른 것을 측정하는 또 다른 실행에서 : 동일한 두 개의 456B 버퍼를 읽거나 쓸 것으로 예상되는 L1D 캐시 미스는 전혀 중요하지 않습니다. 내부 루프 분기는 외부 루프 당 한 번 잘못 예측합니다 (루프를 떠나지 않는 경우). (컴퓨터가 완전히 유휴 상태가 아니기 때문에 총 시간이 더 높습니다. 아마도 다른 논리 코어가 일정 시간 동안 활성화되어 인터럽트에 더 많은 시간을 소비했을 것입니다 (사용자 공간 측정 주파수가 4.400GHz보다 훨씬 낮기 때문에). 또는 여러 개의 코어가 더 많은 시간 동안 활성화되어 최대 터보를 낮추었습니다 cpu_clk_unhalted.one_thread_active.HT 경쟁이 문제인지 여부를 추적하지 않았습니다 .)

     ### 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

내 코드는 Ryzen에서 더 적은 사이클로 잘 실행될 수 있습니다. 이는 사이클 당 5 uops를 발행 할 수 있습니다 (또는 일부는 Ryzen의 AVX 256b와 같은 2-uop 명령 인 경우 6). stosdRyzen (Intel과 동일)에서 3 개의 UPS 인 프론트 엔드가 무엇을 할 것인지 잘 모르겠습니다 . 내부 루프의 다른 명령은 Skylake 및 모든 단일 UOP와 동일한 대기 시간이라고 생각합니다. (를 포함하여 adc eax, [edi+edx]Skylake보다 유리합니다).

바이트 당 10 진수로 숫자를 저장하면 아마도 훨씬 작을 수도 있지만 9 배 느릴 수도 있습니다. 수행 cmp및 조정 cmov수행은 동일하지만 작업의 1/9를 수행합니다. 바이트 당 2 진수 (베이스 (100),하지 4 비트의 BCD 느린DAA ) 것 같은 작업 및 div r8/ add ax, 0x3030위해 인쇄 두 ASCII 숫자로 99 바이트집니다. 그러나 바이트 당 1 자리는 전혀 필요하지 않으며 div0x30을 반복하고 추가하기 만하면됩니다. 바이트를 인쇄 순서대로 저장하면 두 번째 루프가 실제로 간단 해집니다.

64 비트 정수 (64 비트 모드) 당 18 또는 19 개의 십진수를 사용하면 약 2 배 빠르지 만 모든 REX 접두사 및 64 비트 상수에 대해 상당한 코드 크기가 소요됩니다. 64 비트 모드의 32 비트 팔다리 pop eax대신을 (를) 사용할 수 없습니다 lodsd. 나는 8 번째 레지스터로 사용 하는 대신 esp포인터가 아닌 스크래치 레지스터로 사용하고 ( esi및 의 사용법을 교환 하여) REX 접두사를 피할 수 있습니다 .espr8d

호출 가능한 기능 버전을 만드는 경우 64 비트로 변환하여 사용하는 r8d것이 저장 / 복원보다 저렴할 수 있습니다 rsp. 64 비트는 1 바이트 dec r32인코딩 도 사용할 수 없습니다 (REX 접두사이므로). 그러나 대부분 dec bl2 바이트를 사용했습니다. (의 상위 바이트에 상수가 있고 ebx내부 루프 외부에서만 사용하기 때문에 상수의 하위 바이트가이므로 작동합니다 0x00.)

고성능 버전

코드 골프가 아닌 최대 성능을 얻으려면 내부 루프를 풀고 최대 22 회 반복을 실행해야합니다. 이는 분기 예측자가 잘 수행 할 수있는 짧거나 짧은 패턴입니다. 내 실험에서 루프가 잘못 예측 mov cl, 22되기 전에 .inner: dec cl/jnz .inner(내부 루프의 전체 실행 당 1보다 훨씬 적은 0.05 %와 같은) 오해가 거의 발생하지 않지만 mov cl,23내부 루프 당 0.35에서 0.6 배로 잘못 예측됩니다. 46내부 루프 당 ~ 1.28 배 (100M 외부 루프 반복의 경우 128M 회)를 잘못 예측하여 특히 나쁩니다. 114피보나치 루프의 일부로 찾은 것처럼 내부 루프 당 정확히 한 번 잘못 예측했습니다.

나는 호기심을 가지고 그것을 시도하여 내부 루프를 6으로 풀었습니다 %rep 6(114를 균등하게 나누기 때문). 그것은 대부분 분기 결석을 제거했습니다. 나는 edx음수를 만들어 mov상점 의 오프셋으로 사용 했으므로 adc eax,[edi]마이크로 융합 상태를 유지할 수 있습니다. (그래서 피할 수 있습니다 stosd). 블록에서 lea업데이트 edi하기 위해 를 꺼내서 %rep6 상점 당 하나의 포인터 업데이트 만 수행합니다.

나는 그것이 중요하다고 생각하지는 않지만 외부 루프의 모든 부분 레지스터 내용을 제거했습니다. 외부 루프 끝에서 CF가 최종 ADC에 의존하지 않는 데 약간 도움이되었으므로 일부 내부 루프 Uops를 시작할 수 있습니다. 외부 루프 코드는 아마도 2 개의 명령으로 neg edx교체 한 후 (아직 1 개가 있었기 때문에) 마지막으로 수행 한 이후로 8 비트를 떨어 뜨리고 뎁 체인을 다시 정렬 한 이후 로 조금 더 최적화 될 수 있습니다. 물건을 등록하십시오.xchgmov

피보나치 루프의 NASM 소스입니다. 원래 버전의 해당 섹션을 대체 할 수 있습니다.

  ;;;; 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

공연:

 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% )

이는 동일한 Fib (1G) 용으로 73 초 대신 62.3 초에 동일한 출력을 생성합니다. (273.146G 사이클 vs. 322.467G. 모든 것이 L1 캐시에서 발생하므로 코어 클럭 사이클만으로도 볼 수 있습니다.)

총계보다 훨씬 낮은 총계를 uops_issued기록하십시오 uops_executed. 즉, 융합 도메인 (문제 / ROB)에서는 1 uop, 융합되지 않은 도메인 (스케줄러 / 실행 단위)에서는 2 uop가 마이크로 퓨즈되어 있음을 의미합니다. 그리고 이슈 / 이름 바꾸기 단계에서 제거 된 적은 수 ( mov레지스터 복사 또는- xor제로화 와 같이 발행해야하지만 실행 단위는 필요하지 않음). 제거 된 웁스는 다른 방법으로 카운트의 불균형을 줄 것입니다.

branch-misses1G에서 ~ 400k까지 낮아 졌으므로 언 롤링이 효과가있었습니다. resource_stalls.any이제 중요합니다. 이는 프런트 엔드가 더 이상 병목 현상이 아니라는 것을 의미합니다. 대신 백 엔드가 뒤쳐져 프런트 엔드를 제한합니다. idq_uops_not_delivered.core전용 프런트 엔드는 마이크로 연산을 제공하지 않았다 사이클을 계산하지만 백엔드가 되지 않았다 정체. 훌륭하고 낮으며 프런트 엔드 병목 현상이 거의 없음을 나타냅니다.

재미있는 사실 : 파이썬 버전은 시간을 반으로 늘리지 않고 10으로 나누는 데 절반 이상을 소비합니다. 합니다 (교체 a/=10로 a>>=64보다 2 배 이상으로 속도를 최대하지만, 바이너리 잘라 내기 때문에 결과를 변경! = 소수점 절사).

내 asm 버전은 물론 루프 반복 횟수를 하드 코딩 하여이 문제 크기에 맞게 최적화되었습니다. 임의의 정밀도 숫자를 이동하더라도 복사 할 수 있지만 내 버전은 다음 두 반복에 대한 오프셋에서 읽은 것만으로도 건너 뛸 수 있습니다.

파이썬 버전 (Arch Linux의 64 비트 python2.7)을 프로파일했습니다 .

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

(단위)의 숫자는 성능 카운터가 샘플링되는 시간입니다. HW가 지원하는 것보다 더 많은 카운터를 볼 때, perf는 다른 카운터 사이에서 회전하고 외삽합니다. 동일한 작업을 장기간 수행해도 좋습니다.

내가 실행 한 경우 perfsysctl을 설정 한 후 kernel.perf_event_paranoid = 0(또는 실행 perf루트로), 그것을 측정하는 것입니다 4.400GHz. cycles:u인터럽트 (또는 시스템 호출)에 소비 된 시간은 계산하지 않고 사용자 공간 주기만 계산합니다. 데스크탑이 거의 유휴 상태 였지만 이는 일반적입니다.

답변

p(a,b)(c,d)=(a*d+b*c-a*c,a*c+b*d)
t g=g.g.g
t(t$t=<<t.p)(1,1)

Fibonacci@1*^9&

a,b=0,1
i=1e9
while i:
 a,b=b,a+b;i-=1
 if a>>3360:a/=10;b/=10
print a

(a%b)n|n<1=b|odd n=b%(a+b)$n-1|r<-2*a*b-a*a=r%(a*a+b*b)$div n 2
1%0$2143923439