C# : CRC32 code te langzaam. _mm_crc32_u8 intrinsics ?

[LDenninger]

Ik heb een C# app waarin ik de de CRC32 calculatie-code wil optimizen, die kost me te veel tijd.
De huidige code is gewoon de standaard 2-xor-1-and-en-een-table-lookup versie in native C#.

Ik zie dat met Visual Studio 2010 / .NET 4.0 er intrinsics bijgekomen zijn voor het berekenen van CRCs :
_mm_crc32_u8
_mm_crc32_u16
_mm_crc32_u32
_mm_crc32_u64

Leuk en aardig, maar met C# heb ik hier weinig aan, daarmee kan ik geen intrinsics gebruiken.
En als ik ze wrap in C++ en gebruik via pInvoke heb ik daar weer de overhead van (marshallen van de parameters van managed naar unmanaged geheugen, stack constructen).

Heeft iemand een slim idee om een CRC32 sneller te krijgen ?

[Snake]

De volledige CRC berekenen in C++ en enkel het resultaat terugsturen naar C# lijkt me een goede manier.

[farlane]

LDenninger schreef op maandag 07 december 2009 @ 16:10:
Heeft iemand een slim idee om een CRC32 sneller te krijgen ?

Waarom is die table-lookup zo langzaam in C#?

[LDenninger]

Snake schreef op maandag 07 december 2009 @ 16:11:
De volledige CRC berekenen in C++ en enkel het resultaat terugsturen naar C# lijkt me een goede manier.

Het probleem is dat de CRC's berekend worden over niet-al-te-grote blokken.
't is dus niet 1 blok data van 800MB waar een CRC32 over moet worden berekend,
eerder een boel kleine... En ik decode ze liever direct als ik ze binnen krijg, ipv. wachten tot ik er een boel heb en dan een boel kleine blokken naar een C++ CRC32 doorpasen... Maar misschien zal dat toch maar moeten.

[ Voor 19% gewijzigd door LDenninger op 07-12-2009 16:16 ]

[LDenninger]

farlane schreef op maandag 07 december 2009 @ 16:14:
[...]


Waarom is die table-lookup zo langzaam in C#?

Als je 'm niet 'fixed' en unsafe benadert gaat ie elke keer checken of de index niet out of bounds is.
Maar daar valt dus makkelijk onder uit te komen.

[Soultaker]

LDenninger schreef op maandag 07 december 2009 @ 16:10:
En als ik ze wrap in C++ en gebruik via pInvoke heb ik daar weer de overhead van (marshallen van de parameters van managed naar unmanaged geheugen, stack constructen).

Ik ken de details van de .NET implementatie niet, maar hierbij twee vragen:

1. Is je programma traag omdat je grote blokken data wil CRCen, of omdat je véél kleine blokken CRCt?
   Inmiddels beantwoord; kleine blokken dus. Maar wat is klein precies?
2. Worden bij het marshallen arrays gekopieerd/verplaatst?

Als het antwoord op de eerste vraag "grote bokken" is en op de tweede "nee", dan lijkt me dat de overhead van het aanroepen van de C++ code wel mee moet vallen. Wellicht kostbaarder dan een call naar managed code, maar zolang er maar genoeg data verwerkt wordt is de call overhead waarschijnlijk te verwaarlozen.

Kun je bovendien niet ook (unmanaged) .NET code schrijven met C++? Lijkt me dat marshalling dan niet aan de orde is? Is dat geen optie?

[ Voor 3% gewijzigd door Soultaker op 07-12-2009 16:18 ]

[farlane]

LDenninger schreef op maandag 07 december 2009 @ 16:17:
Als je 'm niet 'fixed' en unsafe benadert gaat ie elke keer checken of de index niet out of bounds is.
Maar daar valt dus makkelijk onder uit te komen.

Dus zelfs als je 'em fixed en unsafe maakt is de implementatie te langzaam?

[LDenninger]

Hmm, ik had me verkeken op de _mm_crc32_u8 intrinsics,
die doen enkel CRC32-C, da's niet de polynoom die ik nodig heb.

Dan hoeft het pInvoken ook niet meer, ik betwijfel of een 'simpele' C++ implementatie sneller is dan een C# implementatie.

[farlane]

LDenninger schreef op maandag 07 december 2009 @ 16:25:
Dan hoeft het pInvoken ook niet meer, ik betwijfel of een 'simpele' C++ implementatie sneller is dan een C# implementatie.

Daar probeerde ik eigenlijk ook achter te komen...

[LDenninger]

farlane schreef op maandag 07 december 2009 @ 16:25:
[...]

Dus zelfs als je 'em fixed en unsafe maakt is de implementatie te langzaam?

"te langzaam" is subjectief natuurlijk
Als ik met Ants profile en ik zie dat 10% van mijn tijd in de CRC32-berekening zit wil ik die gewoon sneller hebben als dat kan

Ik had me verkeken op die nieuwe VS2010 intrinsics, het had wel erg leuk geweest als 't mogelijk was om m'n crc32-berekening daar supersnel mee te doen

[ Voor 17% gewijzigd door LDenninger op 07-12-2009 16:28 ]

[Soultaker]

Nou ja, 10%... vind ik persoonlijk nog niet echt boeiend.

[LDenninger]

Soultaker schreef op maandag 07 december 2009 @ 16:29:
Nou ja, 10%... vind ik persoonlijk nog niet echt boeiend.

Dat zeg ik, "te langzaam" is subjectief

Edit: voor het geval iemand anders dit ooit leest omdat ie z'n crc32 sneller wil hebben,
ik ga nu dit eens proberen : http://guru.multimedia.cx/fast-crc/

[ Voor 25% gewijzigd door LDenninger op 07-12-2009 16:43 ]

[Soultaker]

Als je ook je bevindingen post, zou dat helemaal super zijn.

[MSalters]

Deze vraag lijkt overigens verdacht veel op deze

[Phyxion]

LDenninger schreef op maandag 07 december 2009 @ 16:10:
Ik heb een C# app waarin ik de de CRC32 calculatie-code wil optimizen, die kost me te veel tijd.
De huidige code is gewoon de standaard 2-xor-1-and-en-een-table-lookup versie in native C#.

Ik zie dat met Visual Studio 2010 / .NET 4.0 er intrinsics bijgekomen zijn voor het berekenen van CRCs :
_mm_crc32_u8
_mm_crc32_u16
_mm_crc32_u32
_mm_crc32_u64

Leuk en aardig, maar met C# heb ik hier weinig aan, daarmee kan ik geen intrinsics gebruiken.
En als ik ze wrap in C++ en gebruik via pInvoke heb ik daar weer de overhead van (marshallen van de parameters van managed naar unmanaged geheugen, stack constructen).

Heeft iemand een slim idee om een CRC32 sneller te krijgen ?

Multithreaded maken?

[pedorus]

Welk probleem bedoelde je met van managed naar unmanaged geheugen? byte[] is gewoon blittable.

Ik denk trouwens dat met managed c# boundschecking nog wel eens relatief veel tijd kan gaan kosten met die laatste implementatie. En het is nog de vraag of je niet gewoon de optimizer in de weg zit als je de boel buiten VS en andere debuggers/profilers runt. Zeker als je om kleine blokjes gaat, die je af en toe crc't, vraag ik me af wat sneller gaat zijn (cache misses zijn duur).

[MLM]

intrinsics zijn wel architecture dependant natuurlijk. de crc intrinsics specifiek zijn SSE4.2, aka, alleen supported op nehalem (core i7) en nieuwer. ik weet niet wat de doelgroep van je applicatie is maar uitgaan van SSE4 support is niet echt een aanrader als je normale desktopgebruikers onder je doelgroep wilt rekenen.

wat is de gemiddelde grootte van de buffer waarover je CRC wilt berekenen?

[.oisyn]

LDenninger schreef op maandag 07 december 2009 @ 16:25:
Hmm, ik had me verkeken op de _mm_crc32_u8 intrinsics,
die doen enkel CRC32-C, da's niet de polynoom die ik nodig heb.

[farlane]

Hoeveel sneller zou een instrinsic zijn tov een versie met een lookup table vraag ik me af. ( Als het wel de goede polynoom zou zijn )

[.oisyn]

De instructie zal zelf ook wel geïmplementeerd zijn met een on-die LUT, en daarop heb je vervolgens gegarandeerd nooit cache misses. En je hebt ook nog eens wat minder instruction overhead.

Overigens bestaan de betreffende intrinsics ook al in VS 2008.

[ Voor 15% gewijzigd door .oisyn op 08-12-2009 14:10 ]

[Soultaker]

@Farlane:
Ik denk dat je met de intrinsic de look-up table in de processor hebt zitten en dat het daardoor wel aanzienlijk sneller is. Meta-argument: als het niet significant sneller zou zijn om dit in de processor te doen, had Intel die instructie waarschijnlijk niet aan de instructieset toegevoegd. (Behalve misschien om AMD te stangen. )

offtopic:
Wow, was ik echt een kwartier later met die reactie? Ik moet blijkbaar minder tabjes openen...

[ Voor 14% gewijzigd door Soultaker op 08-12-2009 14:25 ]