이 웹 사이트에는 수십억 건의 피보나치 챌린지가 있었으므로 수십억 건의 피보나치 챌린지로 일을 꾸미십시오!
당신의 도전은 가능한 한 짧은 프로그램으로 1,000,000,000 번째 피보나치 수의 첫 1000 자리를 출력하는 것입니다. 그런 다음 선택적으로 나머지 숫자를 포함하되 이에 국한되지 않는 추가 출력이 선택 될 수 있습니다.
나는 규칙 것을 사용하고 fib 0 = 0
, fib 1 = 1
.
프로그램을 실행하고 정확성을 검증 할 수있을 정도로 빠른 프로그램이어야합니다. 이를 위해 처음 1000 자리 숫자는 다음과 같습니다.
7952317874554683467829385196197148189255542185234398913453039937343246686182519370050999626136556779332482035723222451226291714456275648259499530612111301255499879639516053459789018700567439946844843034599802419924043753401950114830107234265037841426980398387360784284231996457340782784200767760907777703183185744656536253511502851715963351023990699232595471322670365506482435966586886048627159716916351448788527427435508113909167963907380398242848033980110276370544264285032744364781198451825462130529529633339813483105771370128111851128247136311414208318983802526907917787094802217750859685116363883374847428036737147882079956688807509158372249451437519320162582002000530798309887261257028201907509370554232931107084976854715833585623910450679449120011564762925649144509531904684984417002512086504020779012501356177874199605085558317190905395134468919443313026824813363234190494375599262553025466528838122639433600483849535070647711986769279568548796855207684897741771784375859496425384355879105799
답변
Python 2 + Sympy, 72 바이트
from sympy import*
n=sqrt(5)
print'7'+`((.5+n/2)**1e9/n).evalf(1e3)`[2:]
Jeff Dege 덕분에 실질적으로 -0 바이트를 제거하여 -10 바이트
-1 바이트 (Zachari 덕분에 1000-> 1e3)
-2 바이트 -Erik the Outgolfer 덕분에 불필요한 변수를 제거하여
-2 바이트 Zacharý 덕분에 Python 2로 이동하여 -2 바이트
ThePirateBay -11
덕분에 -3 바이트 str
11 notjagan 덕분에 백틱 으로 교체 하여 -3 바이트
이제 OP의 게시되지 않은 haskell 솔루션을 능가합니다!
답변
파이썬 2 , 106 바이트
a,b=0,1
for c in bin(10**9):
a,b=2*a*b-a*a,a*a+b*b
if'1'==c:a,b=b,a+b
while a>>3340:a/=10;b/=10
print a
라이브러리가없고 정수 산술입니다. 거의 즉시 실행됩니다.
핵심은 분할 정복 정체성입니다.
f(2*n) = 2*f(n)*f(n+1) - f(n)^2
f(2*n+1) = f(n)^2 + f(n+1)^2
이를 통해 (a,b) = (f(n),f(n+1))
double로 업데이트 할 수 있습니다 n -> 2*n
. 우리는 get을 원하기 때문에 반복 n=10**9
만 log_2(10**9)=30
필요합니다. 우리 는 이진 확장의 각 숫자 에 대해 반복적으로 수행 n
하여 구축 합니다 . 일 때 피보나치 이동 으로 두 배의 값이 위로 이동10**9
n->2*n+c
c
c==1
2*n -> 2*n+1
(a,b)=(b+a,b)
값을 a,b
관리 가능 하게 유지하기 위해 첫 번째 1006
자리 만 바닥에 10
나올 때까지 나눕니다 2**3340 ~ 1e1006
.
답변
(리눅스 시스템 호출 포함)의 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, 1
eax=4
loop
LOOP
-
adc
내부 루프 에서 버퍼의 시작 부분에 계속 쓰는 동안 우리가 읽는 포인터를 오프셋하여 1 개의 팔 다리를 무료로 자릅니다 . 에서 읽고[edi+edx]
씁니다[edi]
. 따라서 대상에 대한 읽기 / 쓰기 오프셋을 얻edx=0
거나 얻을 수 있습니다4
. 먼저 두 가지를 모두 오프셋 한 다음 dst 만 오프셋하는 두 번의 연속 반복에 대해이 작업을 수행해야합니다.esp&4
버퍼 앞쪽으로 포인터를 재설정하기 전에 (&= -1024
버퍼가 정렬되어 있기 때문에를 사용하여 ) 두 번째 경우를 감지합니다 . 코드에서 주석을 참조하십시오. -
(정적 실행 파일의 경우) Linux 프로세스 시작 환경은 대부분의 레지스터를 0으로 만들고
esp
/ 아래의 스택 메모리rsp
는 0으로 설정합니다. 내 프로그램은 이것을 활용합니다. 호출 할 수없는 기능 버전 (할당되지 않은 스택이 더러울 수있는 곳)에서 0으로 된 메모리에 BSS를 사용할 수 있습니다 (포인터를 설정하는 데 4 바이트가 더 필요합니다). 제로화에는edx
2 바이트가 필요합니다. x86-64 System V ABI는 이들 중 하나를 보증하지 않지만 Linux의 구현은 커널에서 정보 유출을 피하기 위해 제로를 수행하지 않습니다. 동적으로 연결된 프로세스에서/lib/ld.so
before 실행_start
하고 레지스터를 0이 아닌 상태로 둡니다 (아마도 스택 포인터 아래의 메모리에서 가비지). -
루프 외부
-1024
에서ebx
사용하기 위해 보관 합니다.bl
내부 루프의 카운터로 사용 하여 0으로 끝납니다 (의 하위 바이트-1024
이므로 루프 외부에서 사용하기 위해 상수를 복원). Intel Haswell 이상에는 low8 레지스터에 대한 부분 레지스터 병합 처벌이 없으며 실제로 이름을 따로 바꾸지 않아도 되므로 AMD와 같이 전체 레지스터에 대한 종속성이 있습니다 (여기에서는 문제가 아닙니다). 그러나 이것은 Nehalem 및 그 이전 버전에서 끔찍한 일이지만 병합 할 때 부분 등록 마구간이 있습니다. 부분xor
정규식을 작성한 다음 -zeroing 또는 a 없이 전체 정규식 을 읽는 다른 장소가 있습니다 .movzx
일반적으로 이전 코드 중 일부가 상위 바이트를 0으로 만들었으므로 AMD와 Intel SnB 제품군에서는 괜찮지 만 Intel 사전 Sandybridge에서는 느립니다.1024
stdout (sub edx, ebx
) 에 쓸 바이트 수로 사용 하므로mov edx, 1000
더 많은 바이트 비용이 들기 때문에 프로그램에서 피보나치 숫자 뒤에 가비지 바이트를 인쇄 합니다. -
(사용되지 않음)
adc ebx,ebx
EBX = 0을 사용하여 EBX = CF를 얻고 1 바이트를 절약setc bl
합니다. -
dec
/jnz
내부adc
루프adc
는 Intel Sandybridge 이상에서 플래그를 읽을 때 부분 플래그 스톨을 발생시키지 않고 CF를 유지 합니다. 초기 CPU 에서는 나쁘지만 Skylake에서는 AFAIK가 무료입니다. 또는 최악의 경우, 여분의 UOP. -
아래의 메모리를
esp
거대한 적색 영역 으로 사용하십시오 . 이것은 완전한 Linux 프로그램이므로 신호 처리기를 설치하지 않았으며 사용자 공간 스택 메모리를 비동기식으로 클로버하는 것은 없습니다. 다른 OS에서는 그렇지 않을 수 있습니다. -
스택 엔진 을 활용 하여
pop eax
(lodsd
Haswell / Skylake에서 2 개, IvB에서 3 개 이하, Agner Fog의 명령어 표 에 따라 이전에 ) 대신 (1 uop + 가끔 스택 동기화 uop) 을 사용하여 uop 문제 대역폭을 절약하십시오 . IIRC,이 내가 아마를 사용하는 같은 속도를 얻을 수 (73) (83)에 대한 초에서 런타임을 떨어mov
처럼, 색인 어드레싱 모드와 함께mov eax, [edi+ebp]
어디ebp
SRC에와 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
과는 cmovc
2C 대기 시간이 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]
대체 stosd
100M iters위한 31,954Mcycles에 100M iters위한 32,909Mcycles에서가는 승이다. 그것은 보인다 stosd
3 마이크로 연산 등의 복호를, 스토어 어드레스 / 저장 데이터로는하지 마이크로 융합하므로 마이크로 연산 push
+ 스택 동기화 죄송합니다. stosd
)
Skylake의 빠른 105B 버전 의 경우 1,114 개의 사지 1G 반복에 대해 ~ 322.47 십억 사이클의 실제 성능은 내부 루프 반복마다 2.824 사이클로 작동합니다 . (아래 ocperf.py
출력 참조). 정적 분석에서 예상 한 것보다 느리지 만 외부 루프 및 스택 동기화 UOP의 오버 헤드를 무시하고있었습니다.
받침대를 성능 branches
및 branch-misses
쇼 그 내부 루프 예측 오류 외부 루프 당 (이 촬영 아니에요 마지막 반복에) 한 번. 그것은 또한 여분의 시간의 일부를 설명합니다.
mov esi,eax
sub eax,ebp
cmovc eax, esi
cmc
lea 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 cmov
uops가 될 것입니다.
실제로 3 / 2.5 = 1.2가 아닌 Skylake에서 1.18 느린 속도 (사지 당 3.34주기)를 실행합니다. 스택 동기화없이 내부 루프를 보면서 프런트 엔드 병목 현상을 대기 시간 병목 현상으로 대체 할 것으로 예상했습니다. 죄송합니다. 스택 동기화 Uops는 빠른 버전에만 영향을 미치기 때문에 (레이턴시 대신 프런트 엔드에서 병목 현상이 발생 함)이를 설명하는 데 많은 시간이 걸리지 않습니다. 예 : 3 / 2.54 = 1.18.
또 다른 요인은 3c 대기 시간 버전이 임계 경로가 여전히 실행되는 동안 내부 루프를 떠날 때의 오해를 감지 할 수 있다는 것입니다 (프론트 엔드가 백엔드보다 앞서 갈 수 있기 때문에 비 순차적 실행으로 인해 루프가 실행될 수 있음) 카운터 잘못된), 따라서 효과적인 잘못된 예측 페널티가 낮습니다. 이러한 프론트 엔드 사이클을 잃으면 백엔드를 따라 잡을 수 있습니다.
그렇지 않은 경우 cmc
carry_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). stosd
Ryzen (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 자리는 전혀 필요하지 않으며 div
0x30을 반복하고 추가하기 만하면됩니다. 바이트를 인쇄 순서대로 저장하면 두 번째 루프가 실제로 간단 해집니다.
64 비트 정수 (64 비트 모드) 당 18 또는 19 개의 십진수를 사용하면 약 2 배 빠르지 만 모든 REX 접두사 및 64 비트 상수에 대해 상당한 코드 크기가 소요됩니다. 64 비트 모드의 32 비트 팔다리 pop eax
대신을 (를) 사용할 수 없습니다 lodsd
. 나는 8 번째 레지스터로 사용 하는 대신 esp
포인터가 아닌 스크래치 레지스터로 사용하고 ( esi
및 의 사용법을 교환 하여) REX 접두사를 피할 수 있습니다 .esp
r8d
호출 가능한 기능 버전을 만드는 경우 64 비트로 변환하여 사용하는 r8d
것이 저장 / 복원보다 저렴할 수 있습니다 rsp
. 64 비트는 1 바이트 dec r32
인코딩 도 사용할 수 없습니다 (REX 접두사이므로). 그러나 대부분 dec bl
2 바이트를 사용했습니다. (의 상위 바이트에 상수가 있고 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
하기 위해 를 꺼내서 %rep
6 상점 당 하나의 포인터 업데이트 만 수행합니다.
나는 그것이 중요하다고 생각하지는 않지만 외부 루프의 모든 부분 레지스터 내용을 제거했습니다. 외부 루프 끝에서 CF가 최종 ADC에 의존하지 않는 데 약간 도움이되었으므로 일부 내부 루프 Uops를 시작할 수 있습니다. 외부 루프 코드는 아마도 2 개의 명령으로 neg edx
교체 한 후 (아직 1 개가 있었기 때문에) 마지막으로 수행 한 이후로 8 비트를 떨어 뜨리고 뎁 체인을 다시 정렬 한 이후 로 조금 더 최적화 될 수 있습니다. 물건을 등록하십시오.xchg
mov
피보나치 루프의 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-misses
1G에서 ~ 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는 다른 카운터 사이에서 회전하고 외삽합니다. 동일한 작업을 장기간 수행해도 좋습니다.
내가 실행 한 경우 perf
sysctl을 설정 한 후 kernel.perf_event_paranoid = 0
(또는 실행 perf
루트로), 그것을 측정하는 것입니다 4.400GHz
. cycles:u
인터럽트 (또는 시스템 호출)에 소비 된 시간은 계산하지 않고 사용자 공간 주기만 계산합니다. 데스크탑이 거의 유휴 상태 였지만 이는 일반적입니다.
답변
하스켈, 83 61 바이트
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)
출력 ( F 1000000000 , F 1000000001 ). 내 노트북에서는 1.35GiB의 메모리를 사용하여 133 초 내에 왼쪽 패런과 첫 1000 자리 숫자를 올바르게 인쇄합니다.
작동 원리
피보나치 반복은 행렬 지수를 사용하여 해결할 수 있습니다.
[ F I – 1 , F I ; F i , F i + 1 ] = [0, 1; 1, 1] i ,
여기서 우리는 이러한 정체성을 도출합니다.
[ F I + J – 1 , F I + J ; F I + J , F I + J + 1 ] = [ F I – 1 , F I ; F i , F i + 1 ] ⋅ [ F j -1 , F j ; F의 J , F의 J + 1 ],
F는 I + J = F의 난+ 1 F j + 1 − F i − 1 F j − 1 = F i + 1 F j + 1 − ( F i + 1 − F i ) ( F j + 1 − F j ),
F i + j + 1 = F i F j + F i + 1 F j + 1 입니다.
p
함수로 계산 ( F I + J , F I + J + 1 ) 소정 ( F I , F I + 1 ) 및 ( F에서 J , F의 J + 1 ). 쓰기 f n
위해 ( F I , F의 I + 1 ), 우리는이 p (f i) (f j)
=을 f (i + j)
.
그때,
(t=<<t.p) (f i)
= t ((t.p) (f i)) (f i)
= t (p (f i).p (f i).p (f i)) (f i)
= (p (f i).p (f i).p (f i).p (f i).p (f i).p (f i).p (f i).p (f i).p (f i)) (f i)
= f (10 * i)
,
(t$t=<<t.p) (f i)
= ((t=<<t.p).(t=<<t.p).(t=<<t.p)) (f i)
= f (10^3 * i)
,
t(t$t=<<t.p) (f i)
= ((t$t=<<t.p).(t$t=<<t.p).(t$t=<<t.p)) (f i)
= f (10^9 * i)
,
그리고 우리는 f 1
=를 연결 (1,1)
합니다.
답변
매스 매 티카, 15 34 바이트
Fibonacci
그 자체가 내 컴퓨터에 ~ 기가 걸립니다. 그리고 프론트 엔드가 그것을 표시하기 위해 95 (+/- 5).
Fibonacci@1*^9&
처음 1000 자리 (34 바이트) : ⌊Fibonacci@1*^9/1*^208986640⌋&
길지만 빠름 ToString@Fibonacci@1*^9~StringTake~1000&
:
답변
파이썬 2, 70 바이트
a,b=0,1
i=1e9
while i:
a,b=b,a+b;i-=1
if a>>3360:a/=10;b/=10
print a
이것은 내 랩톱에서 18 분 31 초 만에 실행되어 올바른 1000 자리 숫자와 그 뒤에 74100118580
올바른 숫자가 표시됩니다 74248787892
.