2014-06-02 21:30:56
HrCrc32c

Kolejny wpis z serii "Jak dostałem Haswella". W poprzednim odcinku - Popcnt, więc tym razem pora na crc32c, czyli CRC32 z wielomianem 0x11EDC6F41. Do czego to można wykorzystać? Oczywiście do liczenia sumy kontrolnej, ale i do hashowania (np. w hashmapach).

Wstępu teoretycznego nie będzie, bo szkoda mi robić konkurencję Internetom. Ale w skrócie - do liczenia CRC32 mamy do wyboru parę algorytmów - najbardziej znany to algorytm Sarwate'go, który ma niskie wymagania pamięciowe i działa całkiem szybko. Oczywiście wcześniej czy później do zabawy musiał się podłączyć Intel i wymyślił algorytmy Slicing-by-4 oraz Slicing-by-8, jednak wykorzystują tablice o wielkościach odpowiednio 4KB i 8KB, więc na maszynach z małymi pamięciami podręcznymi te metody będą wolniejsze od (teoretycznie) wolniejszego algorytmu Sarwate'go. A co z instrukcją crc32 z procesorów Nehalem i nowszych? Nie ma żadnego wymagania. I do tego jest piekielnie szybka, nawet w najprostszej, szeregowej implementacji. Wydajność na moim Core i3-4130t przedstawia się tak:

  • Sarwate: 342MB/s
  • Slicing-By-4: 840MB/s
  • Slicing-By-8: 1285MB/s
  • HCM (hash): 890MB/s
  • Hardware: 3562MB/s (3,5GB/s)

(Hasher używany w HCMie znalazł się celowo, nawet jeśli nie służy do liczenia CRC32c)

Natomiast już na Pentium 200 (które nie ma sprzętowego CRC32) tak fajnie nie jest:

  • Sarwate: 2,9MB/s
  • Slicing-By-4: 3,1MB/s
  • Slicing-By-8: 2,85MB/s
  • HCM (hash): 3,28MB/s

Zadowolony z wyników stworzyłem moduł HrCrc32c, który pozwala obliczać sumę CRC32c sprzętowo albo programowo, używając Slicing-by-4 albo Slicing-by-8. Wybór metody między sprzętową a programową jest automatyczny (w trakcie wykonania, przy uruchamianiu, w zależności od tego co umie procesor), natomiast między Slicing-by-4 a Slicing-by-8 - na etapie kompilacji (jednym $DEFINE'm), dzięki czemu można oszczędzić 4KB pamięci.

Moja implementacja nie jest idealna, ale i nie miała być idealna. Miała być prostym, działającym zamiennikiem dla funkcji hashującej używanej w HCMie i dla funkcji liczącej różne sumy kontrolne używane przeze mnie w różnych miejscach. W każdym razie, jeśli komuś się to przyda, to do ściągnięcia wszystko z Branchware. Z braków na pewno zaboleć może brak możliwości liczenia CRC32c na raty - ta implementacja liczy tylko dla kompletnych, ciągłych bloków pamięci. No i zżeranie 4/8KB nawet jeśli nie zamierza się używać implementacji software'owej, a jedynie sprzętowej. Ale zmiana tego to już ćwiczenie dla czytelnika.


Może Cię zainteresować...

Link | Komentarzy: 3 | Programowanie, Tech, Techblog
Pokazuj komentarze.
Powered by:
Hellcore Mailer - polski program pocztowyOpera Web BrowserFreeBSD - The Power to Serve!Slackware
RSSy:
Sidekick:
Projekty:
O autorze:
Zobacz:
Kategorie:
Archiwum:
Szukaj: