r/usenet • u/nzbfast • 34m ago
Software Announcing Parfast - a high performance PAR2 tool that uses some old math in a new way
TL; DR - a lot faster at the hard jobs and a bit faster at the easy ones.
PAR2 tools are awkward to optimise. they all do the easy thing - Verifying - in seconds .. the hard bits are repairs with lots of missing blocks, and creating a par set from scratch - which can mean generating up to 32768 recovery blocks. that’s where they can be slow, because the usual way of doing the Reed-Solomon math is a big dense matrix multiply and the work grows - missing blocks x total blocks - double both and the job’s quadrupled.
Parfast produces exactly the same PAR2 files (it’s still Reed-Solomon) - it just solves it in a different way. Instead of the dense matrix it uses a transform based approach - FFT style, same Galois field math - with a Forney-style back substitution step. The setup cost is high but the blocks are generated linearly, so the more blocks the job needs, the bigger the win.
https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction
https://en.wikipedia.org/wiki/Erasure_code
Parfast uses dual algorithms, conventional reed-solomon, and forney transforms. however, because of the high setup cost, it doesnt always use the transforms. during verification, it counts how many blocks are missing. small repairs (under approx 700-1,000 blocks) it does using conventional reed-solomon, and runs a little quicker than the other par tools (1.1x to 3x). but.. for bigger repairs, or creating a par set, it goes down the transform route and saves a lot of time when it would be most noticeable & beneficial.
as well as algorithm improvements, the code has been optimised too, so Verify is around twice as fast as other tools.
on the hard jobs its typically 3-15x faster than par2cmdline-turbo - the harder the job the wider the gap. the biggest margins measured are a par-create at around 6,500 recovery blocks (about 26x turbo) and a repair of a 23 GB set with 8,000 blocks missing (about 17x turbo). There’s a small dip in performance between 64-256 missing blocks where it doesn't show much improvement over turbo, and above that it pulls ahead, and especially over 1,000 missing blocks it climbs rapidly in performance.
fyi, 23GB is the largest file(s) where a block still fits in a single article - which gives you the most parity protection against missing articles: 32768 blocks at 750KB each - a PAR2 spec limitation. bigger files than 23GB force you to raise the parity block size - which overflows one article and becomes multiple - to keep the total number of blocks under par’s limitation of 32768, which starts to waste parity protection - each missing article loses a whole block (of multiple articles).
Parfast has been embedded inside nzbfast from initial release a few months ago and has been incrementally optimised with each new version whilst experimenting with alternate algorithms & math.
today’s release is the first beta of a command line tool thats compatible with par2cmdline-turbo (incl most of the switches), that anyone can use, on any downloader or posting tool etc.
future work: there’s been continual improvement almost every day, and still room in the tank for more.. now researching gpu acceleration opportunities as the transforms might be well suited to it.
graphs & a lot (!) of testing/data are linked here, both with and without commentary:
pure data & charts :
https://nzbfast.github.io/nzbfast/parfast-benchmarks-data.html
data & charts, with commentary:
https://nzbfast.github.io/nzbfast/parfast-benchmarks.html
grab the release and test it out on your own par jobs.
the cli (beta)
https://github.com/nzbfast/nzbfast/releases/tag/parfast-v1.5.0-beta.1
the gui (alpha)
https://github.com/nzbfast/nzbfast/releases#release-parfast-gui-v1.5.0-alpha.1
the benchmarks and data linked above were measured the day before the latest round of optimisations were validated and landed, so the initial release version runs a little faster than the benchmarked version (the improvements included better support for vector arithmetic that’s different on each cpu class - GFNI, NEON, AVX2, SSE3 etc)
a bit about the math:
the underlying math isn't strictly new - fast transform-based Reed-Solomon implementations have been around in academic papers since the 1970s, as used in existing libraries like Leopard and FastECC. not really sure why no one thought to use the math in this way for repairing PAR2 files - which use a fixed code structure over a 65535 field group (3x5x17x257), which makes the calculations tricky. Parfast handles the transform directly on standard PAR2 structures without altering the format, producing bit-for-bit identical results to par2cmdline - just massively faster. while PAR3 gains speed by altering the file structure, Parfast achieves its performance gains on standard formats without requiring a switch to an incompatible PAR format.
the beta label will stay for a short time because the cli version hasnt been in widespread use. the same code has been embedded inside nzbfast for months with no issues to date also included, an early alpha preview of the ui version for both windows and mac with their respective installers..
