[HN Gopher] FastECC - Reed-Solomon coder computing one million p...
___________________________________________________________________
FastECC - Reed-Solomon coder computing one million parity blocks at
1 GB/s
Author : pabs3
Score : 111 points
Date : 2022-07-10 09:10 UTC (13 hours ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| cynusx wrote:
| In case your code theory is a bit rusty, practically this means
| that recovering from transmission errors (bitflips, lost packets)
| will be faster if this encoder is used.
|
| It will lower CPU requirements on routers and network
| infrastructure if adopted and potentially your torrent download
| may be validated faster.
|
| Nothing impacting blockchains, which was my first thought.
| lijogdfljk wrote:
| Yea. On the note of Blockchains, i have been long fascinated by
| immutable storage engines. Blockchain being just one
| implementation in the broader landscape. I've implemented
| several of them...
|
| and with that said, i often wanted to add Reed Solomon simply
| because i found it fascinating. Truly an ingenious "trick".
| Though i never got past the idea phase, as it felt i was just
| double encoding everything and if bits were to flip then my
| storage mechanisms (HDD/S3/etc) would be the one seeing the
| flip and fixing it. I figured my software was never going to
| see bitflips to make this type of feature useful.
|
| I'd be curious if any blockchains/immutable storage/etc
| actually use this type of error recovery. Ie if the layer
| _above_ network and storage actually benefit from error
| recovery. Since i often expect both network and storage
| themselves to bake error recovery in.. /shrug
| adrian_b wrote:
| The author explains in the README that this specific algorithm
| is not suited for some of the applications of Reed-Solomon
| codes, e.g. hardware RAID controllers or communication
| channels.
|
| However, it is appropriate for protecting archive files against
| corruption, by adding redundancy that enables the recovery of
| the complete file when any part of it is lost, as long as the
| lost parts do not exceed the size of the extra redundant data.
|
| I happen to add such Reed-Solomon redundancy to all my
| backup/archive files (using "PAR2"). For multi-terabyte
| archived data, the Reed-Solomon computation can be quite time-
| consuming, second only to compression, so a faster algorithm
| can be useful.
| nullc wrote:
| That it uses a prime field is a bit awkward, as it requires
| repacking bytes to and from the field.
|
| Leopard (https://github.com/catid/leopard) is similarly fast but
| constructed over GF(2^16) so it doesn't need any repacking. OTOH,
| that also limits it to 2^16 packets per codeword.
| cvccvroomvroom wrote:
| Uh, okay. Optimization math fu for encoding only.
|
| There are quite a few possible ECC constructions to select for a
| given application considering the error modes,
| computational/energy/time budgets, and channel type and rate.
|
| You can, for example, use a turbo code if you have an enormous
| stream channel ( compared to the actual average symbol size and
| rate) with lots of noise.
|
| Another possible use-case is having copious amounts of flash
| storage but much less data with the intent of leveled write
| counts well beyond wearing of N% of cells. It's an exercise for
| the reader to choose an appropriate algorithm for the intended
| application.
| sllabres wrote:
| previous discussion:
| https://news.ycombinator.com/item?id=14290617
| blacklion wrote:
| Bulat Ziganshin?.. Hmm, this name rings the bell. A-HA! I know
| this name from 1990's and Russian (!) FIDO echoconference
| RU.COMPRESSION. He designed and wrote some impressive compressors
| which beats all these RAR and HA on (English) texts, as far as I
| remember.
|
| It was place where Dmitry Shkarin showcases his PPMd, and Igor
| Pavlov (think: 7zip) was here too, if my memory serves me right.
|
| Good old days.
|
| I'm happy, that Bulat is alive and kicking.
|
| Update: Ooops, last change in repo is ~5 years ago, it is sad.
| naillo wrote:
| If it's any consolance, he has been commiting quite recently
| too. This was updated 9 days ago https://github.com/Bulat-
| Ziganshin/magus. So far from not alive and kicking it seems.
| mananaysiempre wrote:
| He also seems quite active on encode.su ex encode.ru, in case
| you understand enough compression arcana to read that (English-
| language) board (I don't).
| dragontamer wrote:
| The 1GB/Second figure isn't impressive at all (or at least,
| shouldn't be the headline).
|
| The impressive part is that this is a 2^20 field (RS(million,
| half-million)). Most RS-encoders/decoders are much smaller,
| either 2^8 or even smaller (CD ROMs are RS(28, 24). Satellite is
| around RS(256, xxx) or so).
|
| 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.
|
| --------
|
| Because of the computational difficulty of large RS
| encoders/decoders, today seems to be focused on Turbo codes or
| LDPC codes instead of RS. 2^20 is probably the largest RS code
| I've ever heard of, very impressive that it's actually at
| 'practical speeds' (1 GB/sec should be practical albeit a bit
| slow)
|
| 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.
|
| ------
|
| And I do believe this is limited to half-million parity blocks,
| not 1 million parity.
| omazurov wrote:
| _> 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).
| eps wrote:
| 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.
| miohtama wrote:
| Sir, people like you and replies like yours make HackerNews
| worth it.
| anonymousiam wrote:
| "Current implementation is limited to 2^20 blocks, removing this
| limit is the main priority for future work aside of decoder
| implementation."
___________________________________________________________________
(page generated 2022-07-10 23:01 UTC)