search

drahnr / rs-ec-perf

13 stars 7 forks source link

erasure coding with GF64 #1

Open kilic opened 3 years ago

kilic commented 3 years ago

Hi! I just wanted to drop a note here that I also implemented erasure coding using 64 bit binary field and with the ideas here. I've thought that it might be useful for the performance comparison.

https://github.com/kilic/gf/blob/master/rs.go

drahnr commented 3 years ago

I read that pretty early on, but discarded it due to the fact of the field being not a binary field, at least that is stated as an open question at the very end of the article. If you have news about that (or if I just didn't get it), I'd be intrigued to take another look :)

burdges commented 3 years ago

We expect the fastest current binary field implementation are based upon gf-complete and the paper Screaming Fast Galois Field Arithmetic Using Intel SIMD Instructions by James Plank, Kevin Greenan, and Ethan Miller. These implements GF(2^4) using multiplication tables and then build the extension fields using SIMD instructions.

There is a GF(2^8) implementation in https://github.com/darrenldl/reed-solomon-erasure based upon gf-complete, upon which we build a GF(2^16) in a more naive way. We'll explore if porting the GF(2^16) code from gf-complete improves this enough to be worth using. I'm still surprised that multiplication tables for GF(2^4) gives a faster solution than using log tables for GF(2^8), but it meshes better with SIMD lookups I guess.

kilic commented 3 years ago

@drahnr

It is successfully applied on binary fields.

@burdges

I used carry-less multiplication instruction set named PCLMUL. So there is no lookup is performed in multiplication.

burdges commented 3 years ago

I see, we should definitely explore those then. :)

@drskalman https://doc.rust-lang.org/core/arch/x86_64/fn._mm_clmulepi64_si128.html?search=clmul