Hacker News new | ask | show | jobs
by Bulat-Ziganshin 3331 days ago
Speed of RS coder depends on the amount of data/parity blocks. From the URL you mentioned, speed with 50+20 blocks is 713 MB/s. This algorithms is O(N^2) that means the speed is proportional to 1/N. So if it will support 500000+200000 blocks, the speed in this configuration will be 70 KB/s

My algorithm is the only open-source one that has O(N*Log(N)) speed so it runs 500000+200000 blocks at 1.2 GB/s. Overall, FastECC should be faster than existing libraries starting from ~32 parity blocks

It's like bublle sort vs quick sort - for small datasets they may be comparable, for larger ones they are just different worlds. It's all FFT magic, after all. I have added descriptions of method used, but will try to make a longer version since the math behind is is really wonderful
1 comments
nemo1618 3331 days ago
Thanks for clarifying. What is the use case for 500000+200000 blocks/shards though? I can't imagine a real-world scenario that requires more than ~100 parity blocks. Even still, it would be a big deal if FastECC is 10x+ faster at something like 20+60 blocks.
link
Bulat-Ziganshin 3331 days ago
Well, i don't know :)

When you want to protect files on disk, f.e. 30 GB video, you may want to use as much RAM as possible to increase protection level. So if you have 8 GB RAM, and use 4 KB data blocks, you can fit one million blocks into RAM easily. That's one possible usecase, and dream of some data protection geeks

But aside of that, it's exactly what i'm looking for - possible usecases. Today i've checked speed with small n/k and found that fastecc should be faster than MultiPar starting from 16-32 parity blocks. So sorry, with 20+60 blocks speed will be pretty the same, and i hope that Intel's isa-l is even faster than MultiPar. Moreover, fastecc doesn't work in GF(2^n) fields, it requires GF(p) or GF(p^2) instead, which means extra problems what you don't want to solve for a small speed increase

So, overall, fastecc territory starts where GF(256) territory ends. Also, there is no soft decoder, so it's not interesting for any hardware (ssd, lte and so on)

link