PureBoard

Verfasst: **13.04.2014 21:02**

Da für CRC32 hier lange nichts Neues rüberkam, habe ich mich mal diesbezüglich aufgerafft. Halbwegs moderne Prozis bringen dafür einige schöne Instruktionen mit. Thorium hatte vor Jahren Code für die CRC32-Instruktion veröffentlicht, aber dies ergibt CRC32C-Werte (C=Castagnoli), die wegen anderem Ausgangs-Polynom nicht mit dem PB-CRC32 kompatibel sind. Ich habe im Internet Code für die Instruktion PCLMULQDQ gefunden, der wie PB (und allgemein) mit dem "richtigen Polynom" arbeitet. Benötigt wird natürlich eine CPU, die PCLMULQDQ unterstützt: Intel seit 2010 und AMD seit 2011. Wird aber im Code getestet.

Code: Alles auswählen

;CRC32-Fingerprint mit PCLMULQDQ. Verwendet wird Polynomial Reversed ($EDB88320)
;Basierend auf: http://stuff.mit.edu/afs/sipb/contrib/linux/arch/x86/crypto/crc32-pclmul_asm.S
;Lizenz beachten!
;PureBasic 5.22 LTS (Windows - x64)
;Helle 13.04.2014

Global.l CRC32

Procedure.l CRC32_CL(Mem, Laenge)
  ;Test auf PCLMULQDQ
  !MOV eax,1
  !CPUID
  !TEST ecx,2
  !JNZ CL_OK                           ;kann losgehen!
   CRC32Fingerprint(Mem, Laenge)       ;doch wieder mit PB
 ProcedureReturn

!CL_OK:
  !MOV [v_CRC32],0                     ;falls Laenge < 64
  !MOV r9,[p.v_Laenge]
  !AND r9,0FFFFFFFFFFFFFFC0h
!JZ less_64

  !MOV eax,0FFFFFFFFh                  ;Initialisierungswert für CRC32
  !MOVD xmm0,eax

  !MOV r8,[p.v_Mem]
  !MOVDQA xmm1,[r8]
  !MOVDQA xmm2,[r8+10h]
  !MOVDQA xmm3,[r8+20h]
  !MOVDQA xmm4,[r8+30h]
  !PXOR xmm1,xmm0

  !SUB r9,40h
  !ADD r8,40h

  !MOVDQA xmm0,[Lconstant_R2R1]

!loop_64:
  !PREFETCHNTA [r8+0c0h]              ;Cache "vorfüllen"
  !MOVDQA xmm5,xmm1
  !MOVDQA xmm6,xmm2
  !MOVDQA xmm7,xmm3
  !MOVDQA xmm8,xmm4

  !PCLMULQDQ xmm1,xmm0,00h
  !PCLMULQDQ xmm2,xmm0,00h
  !PCLMULQDQ xmm3,xmm0,00h
  !PCLMULQDQ xmm4,xmm0,00h

  !PCLMULQDQ xmm5,xmm0,11h
  !PCLMULQDQ xmm6,xmm0,11h
  !PCLMULQDQ xmm7,xmm0,11h
  !PCLMULQDQ xmm8,xmm0,11h

  !PXOR xmm1,xmm5
  !PXOR xmm2,xmm6
  !PXOR xmm3,xmm7
  !PXOR xmm4,xmm8

  !PXOR xmm1,[r8]
  !PXOR xmm2,[r8+10h]
  !PXOR xmm3,[r8+20h]
  !PXOR xmm4,[r8+30h]

  !SUB r9,40h
  !ADD r8,40h
  !CMP r9,40h
!JGE loop_64

  !MOVDQA xmm0,[Lconstant_R4R3]
  !PREFETCHNTA [r8]

  !MOVDQA xmm5,xmm1
  !PCLMULQDQ xmm1,xmm0,00h
  !PCLMULQDQ xmm5,xmm0,11h
  !PXOR xmm1,xmm5
  !PXOR xmm1,xmm2

  !MOVDQA xmm5,xmm1
  !PCLMULQDQ xmm1,xmm0,00h
  !PCLMULQDQ xmm5,xmm0,11h
  !PXOR xmm1,xmm5
  !PXOR xmm1,xmm3

  !MOVDQA xmm5,xmm1
  !PCLMULQDQ xmm1,xmm0,00h
  !PCLMULQDQ xmm5,xmm0,11h
  !PXOR xmm1,xmm5
  !PXOR xmm1,xmm4

  !PCLMULQDQ xmm0,xmm1,01h
  !PSRLDQ xmm1,08h
  !PXOR xmm1,xmm0

  !MOVDQA xmm2,xmm1

  !MOVDQA xmm0,[Lconstant_R5]
  !MOVDQA xmm3,[Lconstant_mask32]

  !PSRLDQ xmm2,04h
  !PAND xmm1,xmm3
  !PCLMULQDQ xmm1,xmm0,00h 
  !PXOR xmm1,xmm2

  !MOVDQA xmm0,[Lconstant_RUpoly]

  !MOVDQA xmm2,xmm1
  !PAND xmm1,xmm3
  !PCLMULQDQ xmm1,xmm0,10h
  !PAND xmm1,xmm3
  !PCLMULQDQ xmm1,xmm0,00h
  !PXOR xmm1,xmm2
  !PEXTRD eax,xmm1,01h

  !NOT eax                             ;wegen Polynomial Reversed 
  !MOV [v_CRC32],eax

!less_64:                              ;Rest mit PB (max.63 Bytes)
   CRC32Fingerprint(Mem + Laenge - (Laenge & $3F), Laenge & $3F, CRC32)
 ProcedureReturn

;Konstanten
!Align 16
!Lconstant_R2R1:
  !dq 0000000154442bd4h
  !dq 00000001c6e41596h
!Lconstant_R4R3:
  !dq 00000001751997d0h
  !dq 00000000ccaa009eh
!Lconstant_R5:
  !dq 0000000163cd6124h
  !dq 0000000000000000h
!Lconstant_mask32:
  !dq 00000000FFFFFFFFh
  !dq 0000000000000000h
!Lconstant_RUpoly:
  !dq 00000001DB710641h
  !dq 00000001F7011641h

EndProcedure

;Test
A$ = "The quick brown fox jumps over the lazy dog."
LA = Len(A$)
Debug LA
Faktor = 9999999
Buffer = AllocateMemory(LA * (Faktor + 1) + 16)

If Buffer
  BufferA = Buffer
  If BufferA & $0F                     ;muss Alignment 16 sein!
    BufferA = Buffer + 16 - (BufferA & $0F) 
  EndIf

  For i = 0 To Faktor
    PokeS(BufferA + (i * LA), A$)
  Next
  Length = LA * (Faktor + 1)

  Time_PB_A = ElapsedMilliseconds()
  CRC32 = CRC32Fingerprint(BufferA, Length) ;Achtung, bei > 4GB splitten!
  Time_PB_E = ElapsedMilliseconds() - Time_PB_A
  PB$ = "CRC32_PB = " + Hex(CRC32 & $FFFFFFFF) + "  in " + Str(Time_PB_E) + " ms"

  Time_CL_A = ElapsedMilliseconds()
  CRC32 = CRC32_CL(BufferA, Length)
  Time_CL_E = ElapsedMilliseconds() - Time_CL_A
  CL$ = "CRC32_CL = " + Hex(CRC32 & $FFFFFFFF) + "  in " + Str(Time_CL_E) + " ms"

  FreeMemory(Buffer)
  MessageRequester("CRC32 für " + Str(Length) + " Bytes", PB$ + #LFCR$ + CL$)
EndIf

Meine Werte für einen i7-4770K@4.0 GHZ:
PB: 797 ms
CL: 30 ms.

Viel Spaß!
Helle

Verfasst: **13.04.2014 21:24**

Hm. Komischerweise scheint das bei mir nicht zu funktionieren. Ich bekomme folgenden Fehler gemeldet:

purebasic.asm [423]:
MP0
purebasic.asm [106] MP0 [47]:
PCLMULQDQ xmm1,xmm0,00h
error: illegal instruction.

Das heißt dein Test glaubt die Instruktion gibt es, aber dann existiert sie wohl doch nicht?
Mein Prozessor ist ein Intel(R) Core(TM) i7-3820QM.

Verfasst: **13.04.2014 21:32**

Spontan fällt mir ein, die FASM.EXE zu aktualisieren (PureBasic/Compilers). Mache ich schon automatisch bei jeder neuen PB-Installation.

Verfasst: **13.04.2014 21:47**

Okay. Das hat geholfen. Jetzt hab ich statt der Version 1.67.18 die Version 1.71.17 und folgendes Resultat:

CRC32 für 440000000 Bytes hat geschrieben:CRC32_PB = 5FCF543F in 1911 ms
CRC32_CL = 5FCF543F in 145 ms

Also nen ganzen Batzen langsamer also du.

Verfasst: **08.05.2014 16:45**

Helle, das war ein guter Job, das ist schnell, bleibt fexibel und kompatibel.
Wenn man bei der native crc32i instruction bleibt, wird es nicht nur mit Faktor >50 richtig schnell, sondern auch noch richtig klein: No cache pollution at all.
Das ist eine Überlegung wert, den Nachteil der Inkompatabilität zu schlucken.
Enjoy!

Code: Alles auswählen

;CRC32-Fingerprint mit PCLMULQDQ. Verwendet wird Polynomial Reversed ($EDB88320). http://www.purebasic.fr/german/viewtopic.php?f=8&t=27925
;Basierend auf: http://stuff.mit.edu/afs/sipb/contrib/linux/arch/x86/crypto/crc32-pclmul_asm.S
;Lizenz beachten!
;PureBasic 5.22 LTS (Windows - x64)
;Helle 13.04.2014

Global.l CRC32, crc32i, MS

Procedure.l CRC32_CL(Mem, Laenge)
  ;Test auf PCLMULQDQ
  !MOV eax,1
  !CPUID
  !TEST ecx,2
  !JNZ CL_OK                           ;kann losgehen!
   CRC32Fingerprint(Mem, Laenge)       ;doch wieder mit PB
 ProcedureReturn

!CL_OK:
  !MOV [v_CRC32],0                     ;falls Laenge < 64
  !MOV r9,[p.v_Laenge]
  !AND r9,0FFFFFFFFFFFFFFC0h
!JZ less_64

  !MOV eax,0FFFFFFFFh                  ;Initialisierungswert für CRC32
  !MOVD xmm0,eax

  !MOV r8,[p.v_Mem]
  !MOVDQA xmm1,[r8]
  !MOVDQA xmm2,[r8+10h]
  !MOVDQA xmm3,[r8+20h]
  !MOVDQA xmm4,[r8+30h]
  !PXOR xmm1,xmm0

  !SUB r9,40h
  !ADD r8,40h

  !MOVDQA xmm0,[Lconstant_R2R1]

!loop_64:
  !PREFETCHNTA [r8+0c0h]              ;Cache "vorfüllen"
  !MOVDQA xmm5,xmm1
  !MOVDQA xmm6,xmm2
  !MOVDQA xmm7,xmm3
  !MOVDQA xmm8,xmm4

  !PCLMULQDQ xmm1,xmm0,00h
  !PCLMULQDQ xmm2,xmm0,00h
  !PCLMULQDQ xmm3,xmm0,00h
  !PCLMULQDQ xmm4,xmm0,00h

  !PCLMULQDQ xmm5,xmm0,11h
  !PCLMULQDQ xmm6,xmm0,11h
  !PCLMULQDQ xmm7,xmm0,11h
  !PCLMULQDQ xmm8,xmm0,11h

  !PXOR xmm1,xmm5
  !PXOR xmm2,xmm6
  !PXOR xmm3,xmm7
  !PXOR xmm4,xmm8

  !PXOR xmm1,[r8]
  !PXOR xmm2,[r8+10h]
  !PXOR xmm3,[r8+20h]
  !PXOR xmm4,[r8+30h]

  !SUB r9,40h
  !ADD r8,40h
  !CMP r9,40h
!JGE loop_64

  !MOVDQA xmm0,[Lconstant_R4R3]
  !PREFETCHNTA [r8]

  !MOVDQA xmm5,xmm1
  !PCLMULQDQ xmm1,xmm0,00h
  !PCLMULQDQ xmm5,xmm0,11h
  !PXOR xmm1,xmm5
  !PXOR xmm1,xmm2

  !MOVDQA xmm5,xmm1
  !PCLMULQDQ xmm1,xmm0,00h
  !PCLMULQDQ xmm5,xmm0,11h
  !PXOR xmm1,xmm5
  !PXOR xmm1,xmm3

  !MOVDQA xmm5,xmm1
  !PCLMULQDQ xmm1,xmm0,00h
  !PCLMULQDQ xmm5,xmm0,11h
  !PXOR xmm1,xmm5
  !PXOR xmm1,xmm4

  !PCLMULQDQ xmm0,xmm1,01h
  !PSRLDQ xmm1,08h
  !PXOR xmm1,xmm0

  !MOVDQA xmm2,xmm1

  !MOVDQA xmm0,[Lconstant_R5]
  !MOVDQA xmm3,[Lconstant_mask32]

  !PSRLDQ xmm2,04h
  !PAND xmm1,xmm3
  !PCLMULQDQ xmm1,xmm0,00h
  !PXOR xmm1,xmm2

  !MOVDQA xmm0,[Lconstant_RUpoly]
  !MOVDQA xmm2,xmm1
  !PAND xmm1,xmm3
  !PCLMULQDQ xmm1,xmm0,10h
  !PAND xmm1,xmm3
  !PCLMULQDQ xmm1,xmm0,00h
  !PXOR xmm1,xmm2
  !PEXTRD eax,xmm1,01h

  !NOT eax                             ;wegen Polynomial Reversed
  !MOV [v_CRC32],eax

!less_64:                              ;Rest mit PB (max.63 Bytes)
   CRC32Fingerprint(Mem + Laenge - (Laenge & $3F), Laenge & $3F, CRC32)
 ProcedureReturn

;Konstanten
!Align 16
!Lconstant_R2R1:
  !dq 0000000154442bd4h
  !dq 00000001c6e41596h
!Lconstant_R4R3:
  !dq 00000001751997d0h
  !dq 00000000ccaa009eh
!Lconstant_R5:
  !dq 0000000163cd6124h
  !dq 0000000000000000h
!Lconstant_mask32:
  !dq 00000000FFFFFFFFh
  !dq 0000000000000000h
!Lconstant_RUpoly:
  !dq 00000001DB710641h
  !dq 00000001F7011641h

EndProcedure

Macro crc1024pcl
!MOV r9, [v_BufferA]                      ; @ is 16 byte aligned, this helps. PREFETCHNTA is no help here
!XOR rdx, rdx                             ; rdx = crc0 = crc_init
!XOR r8, r8                               ; r8  = crc1
!XOR rax, rax                             ; rax = crc2
!CRC32 rdx, qword[r9]                     ; do first 8 bytes in rdx here for better pipelining
                                          ; this is a non-pipelined single instruction: latency 3, througput 1 cycle                                       
!i = 8                                        ; no CPU-instruction
!Repeat BLOCKSIZE/8                           ; no CPU-instruction, 42 repeats * 8 bytes = 336 bytes
!CRC32  r8, qword[r9 + i + 1*BLOCKSIZE]   ; crc1
!CRC32 rax, qword[r9 + i + 2*BLOCKSIZE]   ; crc2
!CRC32 rdx, qword[r9 + i + 0*BLOCKSIZE]   ; crc0, process rdx last to avoid dependency with crc32 above
!i = i + 8                                    ; no CPU-instruction                            
!end repeat                                   ; no CPU-instruction, 336 * 3 bytes = 1.008 + first 8 = 1.016 bytes

!MOVDQa xmm0, xword[K344_1]               ; 2 constans: K1:K2
                                          ; now merge crc0 and crc1 into crc2
!MOVQ xmm1, r8                            ; crc1
!PCLMULQDQ xmm1, xmm0, 0x10               ; multiply by K1, high qw to low qw in xmm1
!MOVQ xmm2, rdx                           ; crc0
!PCLMULQDQ xmm2, xmm0, 0x00               ; multiply by K2, low qw to low qw in xmm2
!CRC32 rax, qword[r9 + 1016]              ; last 8 bytes, 1.024 bytes processed
!XOR r9, r9
!MOVQ r8, xmm1
!CRC32 r9, r8
!XOR rax, r9
!XOR r9, r9
!MOVQ r8, xmm2
!CRC32 r9, r8
!XOR rax, r9
!MOV [v_crc32i], eax                      ; output result
EndMacro

;Test Helle
A$ = "The quick brown fox jumps over the lazy dog."
LA = Len(A$)
Debug LA
Faktor = 9999999                          ; = 10 Mio.
Buffer = AllocateMemory(LA * (Faktor + 1) + 16)

If Buffer
  BufferA = Buffer
  If BufferA & $0F                        ; muss Alignment 16 sein!
    BufferA = Buffer + 16 - (BufferA & $0F)
  EndIf

  For i = 0 To Faktor
    PokeS(BufferA + (i * LA), A$)
  Next
  Length = LA * (Faktor + 1)
  
  Time_PB_A = ElapsedMilliseconds()
  CRC32 = CRC32Fingerprint(BufferA, Length) ; Achtung, bei > 4GB splitten!
  Time_PB_E = ElapsedMilliseconds() - Time_PB_A
  PB$ = "CRC32_PB = " + Hex(CRC32 & $FFFFFFFF) + "  in " + Str(Time_PB_E) + " ms"

  Time_CL_A = ElapsedMilliseconds()
    CRC32 = CRC32_CL(BufferA, Length)
  Time_CL_E = ElapsedMilliseconds() - Time_CL_A
  
;Test Sooraa
; - crc32i extension by Sooraa, 05.05.2014; PureBasic 5.22 LTS (Windows - x64). SSE4.2 required. Feel free To use my code without restriction.
; - Helle created an high-speed design for PB and other polynomina with a factor of 1 to 6 against PB
; - With the extension of my ASM Macro "crc1024pcl" there is another speed factor of 1 to 9 against Helle's approach (approx. 1 to 55 ag. PB)
; - Helle mentioned 30 ms on his CPU. This will be a Haswell CPU, since with 18 * PCLMULQDQ Haswell's improved CRC32-latency shines through
; - But "non-Haswell riders" can use the native CRC32i machine instruction in a heavy pipelined fashion (crc32 latencies are close to zero)

; - My design is converted from the Intel White Paper 323405, "Fast CRC Computation for iSCSI Polynomial Using CRC32 Instruction"
; - "Function to compute iSCSI CRC32 with PCLMULQDQ Instruction", by almost completely eliminating the crc32i-latencies by 3-stage pipelining
; - crc done "by 3" for fixed input size of 1.024 bytes, = 336 * 3 * 8 + 16, (BLOCKSIZE = 336). For insight purposes the code is commented.
; - The conversionrate for i5 (Westmere, 3.6 GHz): 19 ms for 440 MB = ca. 23,2 GB/Sek. = 0,155 cycle per byte like Intels performance test
; - The conversionrate for i7 (Sandy Bridge, 4.0 GHz): 15 ms for 440 MB = ca. 29,3 GB/Sek. = 0,136 cycle per byte 
; - Plus the code is extremely small (<27 instructions with approx. 140 bytes) and the datasegment is tableless and just 8 bytes.
; - That means that since Sandy Bridge the code can even stay preprocessed in RISC code at the "L0 cache" with really no clock waisted.  
; - So we achieved the maximum throughput and pressure "at the execution unit" under PB. Dont't forget the cache-warmup during tests.
; - Since we are that "close to the transistor", it would be interesting to see comparisons to state of the art AMD-CPUs.

MS = MemorySize(BufferA) / 1024                   ; 429.687
T1 = ElapsedMilliseconds() 
For I = 1 To MS                                   ; let´s keep the testloop counter outside the ASM Macro 
  crc1024pcl                                      ; polynom 0x11EDC6F41
Next I 
T2 = ElapsedMilliseconds() - T1
  
CL$ = "CRC32_CL =  " + Hex(CRC32 & $FFFFFFFF)  + "  in   " + Str(Time_CL_E) + " ms" 
AL$ = "CRC32iPCL= " + Hex(crc32i & $FFFFFFFF) + "   in    " + Str(T2) + " ms"
FreeMemory(Buffer)
MessageRequester("CRC32 für " + Str(Length) + " Bytes", PB$ + #LFCR$ + CL$ + #LFCR$ + AL$)
EndIf
End

!align 16
!K344_1: dq 0x0e417f38a
!K344_2: dq 0x08f158014
!BLOCKSIZE = 336

Verfasst: **08.05.2014 17:07**

Irgendwas ist da komisch. Mein Ergebnis:
Faktor = 99999999

CRC32 für 440000000 Bytes hat geschrieben:CRC32_PB = 94B9524B in 429 ms
CRC32_CL = E122791C in 1382 ms
CRC32iPCL = 0 in 0 ms

Faktor = 9999999

CRC32 für 4400000000 Bytes hat geschrieben:CRC32_PB = 5FCF543F in 1796 ms
CRC32_CL = 5FCF543F in 136 ms
CRC32iPCL = 0 in 0 ms

Bei den 4,4 GB (erstes Zitat) fängt mein Rechner aber auch an zu Swappen, weil meine ganzen anderen Programme zusammen auch schon so viel Speicher belegen.

Verfasst: **08.05.2014 17:23**

Mir fällt nur auf, der erste Code von Helle läßt meine CPU im Stromspartakt (Faktor 7 = 1,4 GHz), während
beim zweiten Code wird die CPU wach

und arbeitet mit Faktor 19 = 3,8 GHz.
Jetzt fehlt noch ein Viagra-Code, der den Turbo einschaltet

Verfasst: **08.05.2014 19:59**

Hallo ts,
was für Ergebnisse gibt das denn im 19er Viagra-Modus auf der FX-6300 ?

Verfasst: **08.05.2014 20:05**

Sooraa hat geschrieben:Hallo ts,
was für Ergebnisse gibt das denn im 19er Viagra-Modus auf der FX-6300 ?

Der Viagra-Modus ist kein 19er sondern ein 20,5er

(4,1 GHz).

Nach welchen genauen Kriterien die Taktfrequenz umgeschaltet wird, ist mir bis jetzt
noch nicht so richtig klar geworden.

MessageRequester hat geschrieben:---------------------------
CRC32 für 440000000 Bytes
---------------------------
CRC32_PB = FC8F3B76 in 1065 ms

CRC32_CL = FC8F3B76 in 107 ms

CRC32iPCL= 4622968D in 126 ms
---------------------------
OK
---------------------------

bei 1,4 GHz.

Verfasst: **08.05.2014 21:40**

Die Ergebnisse von hier auf Sandy Bridge @4.0 GHz:
---------------------------
CRC32 für 440000000 Bytes
---------------------------
CRC32_PB = 5FCF543F in 1005 ms ----> mixed code, sehr ähnlich, OK

CRC32_CL = 5FCF543F in 121 ms ----> hier ist Intel mit 14 latency / 8 für PCLMULQDQ gegenüber AMD langsamer

CRC32iPCL= D4456BBB in 15 ms ----> hier sollte Intel mit 3 lat. / 1 gegenüber AMD zwar von den cycles etwas schneller sein, aber das kann aber den Riesenunterschied von 15 ms zu 126 ms nicht erklären?!?
---------------------------
ts: die angegeben CRC32 Ergebnisse stimmen nicht überein!?
---------------------------

PureBoard

Schnelles CRC32 mit PCLMULQDQ

Schnelles CRC32 mit PCLMULQDQ

Re: Schnelles CRC32 mit PCLMULQDQ

Re: Schnelles CRC32 mit PCLMULQDQ

Re: Schnelles CRC32 mit PCLMULQDQ

Re: Schnelles CRC32 mit PCLMULQDQ

Re: Schnelles CRC32 mit PCLMULQDQ

Re: Schnelles CRC32 mit PCLMULQDQ

Re: Schnelles CRC32 mit PCLMULQDQ

Re: Schnelles CRC32 mit PCLMULQDQ

Re: Schnelles CRC32 mit PCLMULQDQ