Hacker News Reader

Have you commented without looking at the link?

> Because this is a matrix multiplication operation fundamentally, the order is O(n^2) or so in terms of scaling. Sooooo yeah, quadratically difficult to calculate as the data per block grows.

It's literally in repo's description -

  Reed-Solomon coder computing one million parity
  blocks at 1 GB/s. O(N*log(N)) algo employing FFT.

That's what makes FastECC notable. The repo is 5 years old. Obviously, it's going to be more than 1.2 GB/s on a modern hardware.

Kind of surprised that GB/s was even a metric that was used considering how variable CPUs are, even ones manufactured in the same year.

1. As of 2017, we had quadcores as top desktop CPUs for years, and very little IPC and frequency improvements since 2011 2. But the main reason is that I can say "70 MB/s per Haswell core*GHz" and noone will feel whether it's good or not. Performance stated for top modern CPU is much easier to grok

> Larger and larger block sizes are important. LDPC probably is the more practical methodology today, though I admit that I'm ignorant about them. Still cool to see someone try to push Reed Solomon to such an absurdly huge size though.

Multi-dimensional RS codes are an easy way to get to an absurdly huge size for real (granted they stop being MDS). Long term archiving is an obvious application. One-way communication, like in deep space, is another. Though, speed requirements are less demanding there. That one tried to push the envelope for a one-dimensional RS code to those limits is a curiosity. Some techniques may be useful in other practical approaches. It's a pity the code representation had to depart from GF(2^n).

> Multi-dimensional RS codes are an easy way to get to an absurdly huge size for real (granted they stop being MDS)

Yeah, that's the traditional way of doing things. CD-ROMs used multi-dimensional RS (the RS(28,24) was just one bit of the inner-code IIRC, which would fit inside another multidimensional RS code).

But since its no longer MDS, the "search space" of non-MDS codes is quite large. So you have the question of "which code has a higher-probability of successfully correcting errors/erasures" ??

LDPC and Turbo codes apparently have better probabilities of fixing errors/erasures, at far lower computational costs. To the point where a fair number of applications seem to prefer Turbo / LDPC codes today over multidimensional codes (built out of RS)

I'm not talking about CD-ROMs or immediate availability in any form. How would you encode a petabyte (for a starter) with LDPC/Turbo? Not available right away but accumulated over months with no predefined upper limit? Computational cost remains an important factor but other requirements take over.

> How would you encode a petabyte (for a starter) with LDPC/Turbo?

I'm fairly certain that particular problem you're asking for is solved by "fountain LDPC codes", and can't be solved by RS by any methodology.

RS is limited to its block size (in this case, 2^20 sized block), which can be "extended" by interleaving the codes (with various kinds of interleaving). But interleaving a petabyte of data is unreasonable for RS.

I admit I'm not hugely studied in practical codes, mostly just got the college-textbook understanding of them.

I can only repeat my initial statement:

> Multi-dimensional RS codes are an easy way to get to an absurdly huge size for real.

"Multi-dimensional" may mean 3,4,..,10 dimensions. "Absurdly huge" means a petabyte and beyond. "For real" means practical recovery of swaths of lost or damaged data. "Fountain LDPC codes" are essentially one-dimensional. Extending them to the ability of recovering an annihilated data center would make them impractical. Making them multi-dimensional would make them inferior to RS (which is still MDS in every single dimension).

There is Leopard codec implementing very similar approach in GF(2^n). AFAIR, it's a bit slower, but overall it looks more useful than FastECC

(OTOH, since we anyway store hashes and other info, we may store there extra overflow bits required for recoding into GF(p). That said, FastECC on practice works like a slightly non-MDS code, but at least there are guarantees how much extra data we need to store)

The field I've used in benchmarks is GF(0xFFF00001) which has root of unity of 0xFFF00000 = 0x100000 * 0xFFF order. Since my code implemented only FFT for 2^N sizes, it was limited to 2^20 order for this particular field and thus 2^20 blocks total.

It can process larger amount of blocks in other fields (f.e. GF(2^64-2^32+1)). Also, I have implemented other FFT algorithms, which will be published soon.

I ahve chosen this field for the speed (and million blocks is more than other RS implementations provide anyway), but RS in GF(2^64-2^32+1) will be even faster and allows 2^32 blocks even with the current limited FFT implementation.

Sir, people like you and replies like yours make HackerNews worth it.