yEnc SSE decode ideas

I was amazed to find this repo, I have been thinking of some way to do yEnc-decoding (as a Python-C-extension) using SSE instructions but my knowledge of C is just too rudimentary for now.

Do you think think SSE can help compared to regular char-by-char decoding of yEnc body?
How would you go about the decoding-escaping problem? I can imagine finding the escape chars, but how to remove them later on when building the output string?
I tried to grasp your encoding-code, but I think I probably miss the main idea due to the included edge-cases and optimizations.

Thanks!

EDIT: I think I am getting more and more of the code and how you handle the encoding-escaping here: https://github.com/animetosho/node-yencode/blob/master/yencode.cc#L718-L752
I don't completly understand the shuffle operations just yet and how they handle the extra chars, what are shufMixLUT and shufLUT?

SIMD isn't really designed for text processing tasks like yEnc, so implementation isn't so straight forward unfortunately. Because of this, a scalar (byte by byte) implementation usually isn't so bad, but doing a SIMD implementation is intellectually interesting and works for the epeen factor (as for Nyuu, I intend to integrate PAR2 generation, so reducing CPU usage may help a bit on fast connections).

Having said that, a SIMD implementation of yEnc encoding can usually beat the naive implementation by several factors, due to corner cases that an encoder has to deal with.

I've been thinking about writing up how the algorithm works. Unfortunately the code isn't the easiest to read (I'm a little lazy there, admittedly), but here's a rough diagram showing an overview of the main loop:

Note that the byte shuffle instruction requires a CPU with SSSE3 support (which most people should have these days). If the CPU doesn't have SSSE3 support, the algorithm just switches to doing the escaping using standard non-SIMD methods if special characters are found (the 16-bit mask != 0). Despite this, it's still a bit faster than a pure scalar implementation because most bytes aren't escaped in yEnc, and hence, end up hitting the fast route of: load 16 bytes, +42 to all bytes, check special characters, store to memory.

Line endings are a bit complicated, since they have different rules to the rest of the line (more characters to escape). When the algorithm crosses a line boundary, it needs to 'revert' (back-track) until the last character of the line, process the line boundary, then go back to the main loop. A large portion of the code is there just to deal with this case.

Generating vectors for the shuffle and add operation isn't exactly fast, so we pre-generate these instead and just do a lookup when encoding data. shufLUT is a 256 x 16-byte table for the shuffle vectors, whilst shufMixLUT is the corresponding lookup table for add vectors.

Hope that all makes sense.

As for decoding, I've actually thought about it, and have tried a few things. A naive implementation is surprisingly fast, since decoding is somewhat simpler than encoding, though you could still probably beat it by a few factors with SIMD.

Here's my scalar implementation:

static size_t do_decode_scalar(const unsigned char* src, unsigned char* dest, size_t len) {
	unsigned char *p = dest; // destination pointer
	unsigned long i; // input position
	unsigned char c; // input character
	
	for(i = 0; i < len - 1; i++) {
		c = src[i];
		switch(c) {
			case '\n': case '\r': continue;
			case '=':
				i++;
				c = src[i] - 64;
		}
		*p++ = c - 42;
	}
	// do final char; we process this separately to prevent an overflow if the final char is '='
	if(i < len) {
		c = src[i];
		if(c != '\n' && c != '\r' && c != '=') {
			*p++ = c - 42;
		}
	}
	
	return p - dest;
}

I see that in your implementation, you handle two dots after a newline which I don't. yEnc doesn't actually allow such to happen (first dot must be escaped), but I suppose a valid decoder should still deal with it.

A general workflow for a SIMD version may be:

load 16 bytes
check for special characters, = \r \n similar to the encoding algorithm
subtract 42 from all bytes
if there's no special characters, simply store the vector to memory
otherwise take all matches to =, shift one byte across and put the number 64 in each place. All other elements of this vector should be 0
perform a vector subtract (data - vector_partially_filled_with_64)
use shuffles to remove occurrences of = \r \n (similar idea to the encoding algorithm, just instead of expanding data, it compacts it)
store to memory

I actually have a somewhat working implementation of the above.
Against a valid yEnc encoder this works, however, if you want to be fully spec compliant, you'll need to handle invalid yEnc representations, such as a sequence like ====. A spec compliant decoder must treat that as two characters, however the above algorithm won't, even though no good yEnc encoder should ever create such a sequence. There's also the \n.. sequence mentioned above.

I haven't yet thought of a way to deal with such invalid sequences well, but it may be doable. A compromise may be to detect such cases instead (rather than actually handle them), and if encountered, fallback to scalar processing. As I expect most yEnc implementations to be reasonably valid, it's unlikely the slower scalar fallback will ever be invoked, but remains there to be spec compliant.

Hope that's useful. I may eventually add decoding support to this library. Welcome any ideas.
Otherwise, if you wish to implement it yourself, hope that this gives you some ideas on how.

That's a great overview, thank you! 👍

What would you do with the case where the = is the last character of the 16 byte block? So the character-to-unescape is actually in the next 16 byte block.

The double-dot thing is unrelated to yEnc but inherent to NNTP, the servers will add this extra dot when transmitting the message. While I initially ignored it as an edge case, it actually happens quite often (once per file almost).

I was experimenting a bit with implementing this yesterday, but I am sort of stuck in the "finally understanding what pointers do and how to use them"-stage.. so this stuff is a bit above my head.
You say you already have a somewhat working implementation of it? That would make me and the SABnzbd users very happy 😃

What would you do with the case where the = is the last character of the 16 byte block? So the character-to-unescape is actually in the next 16 byte block.

That's not too hard to deal with. Once you have the bit mask indicating the location of = characters:

escape_first_char = mask >> 15;

// on next loop
data = read_next_16_bytes();
// check for special characters
if(escape_first_char)
  data = vector_subtract(data, make_vector(42, 42, 42... 42+64)); // note, first byte is at the end
else
  data = vector_subtract(data, make_vector(42, 42, 42... 42));

// ...or, you could optimize the above four lines with a small LUT based on escape_first_char

While I initially ignored it as an edge case, it actually happens quite often (once per file almost).

That's interesting, because a correctly yEnc encoded message should never have a dot as the first character of a line.
Perhaps these messages were encoded incorrectly?

but I am sort of stuck in the "finally understanding what pointers do and how to use them"-stage

I'm sure you'll get it. It's likely a bit different to what you're used to, but you seem to be a very experienced programmer, so it won't take you long to understand.
Programming in SIMD may be more challenging as it requires you to think a bit differently to how you'd usually write code, and stuff like yEnc can require a little creativity. But it just boils down to yet another programming problem, and use it enough and you should be fine too.

Perhaps these messages were encoded incorrectly?

No, it's not yEnc et al. It's the NNTP server that has to add a dot to every line that starts with a dot per-NNTP-spec during the transmission, some leftovers from ancient times I think.

It's the NNTP server that has to add a dot to every line that starts with a dot

But there should be never be a line that starts with a dot, no?

Why not? It's not a special character in the already encoded data, just a char of which 42 can be subtracted.

Looks like I made a mistake - had thought that yEnc requires dots to be escaped if it's the first character in a line, but re-reading the spec, it's actually optional. Sorry about that.
So it looks like that will need to be handled by most decoders.

So I've been thinking about this, and I think that dealing with invalid sequences can be solved. But the double-dot issue looks challenging.

Looking at RFC3977:

When a multi-line block is interpreted, the "dot-stuffing" MUST
be undone; i.e., the recipient MUST ensure that, in any line
beginning with the termination octet followed by octets other
than a CRLF pair, that initial termination octet is disregarded

This seems to define how invalid sequences such as \n.a are handled - the dot at the start of the line needs to be discarded, regardless of what comes after it. I can't tell if the document covers how sequences like a\n.. should be handled, other than saying that it's invalid. Presumably, from the language, a line must be terminated by \r\n, hence no special treatment should be done for a\n.., however \r\n.. should have the first dot removed.
In other words, dots should be removed if preceded by \r\n (and not a valid = before that), or the dot is the first character in the article/yEnc body (since it's implicitly at the beginning of a line).

I had a quick look at Nzbget's code and it doesn't appear to handle lines starting with a dot. Presumably SABnzbd didn't do this for a long time either? All yEnc decoders I've seen, apart from SABYenc don't handle this case (which isn't an issue if they go through some NNTP layer, but I have doubts that typically happens).
So is it really the case that most downloaders don't handle this, or am I missing something?

Interestingly, I haven't yet seen an yEnc encoder that doesn't escape dots which start a line. But there's obviously posts out there that have it.

I'll probably take the approach of stripping out all instances of \r\n., even though this is likely different to all existing implementations. It also seems difficult to do from a SIMD perspective.

This does also make incremental processing a little more difficult, as it may need to know the preceeding two characters to be correct.

NZBGet does it will receiving the data in the NNTP layer:
https://github.com/nzbget/nzbget/blob/develop/daemon/nntp/ArticleDownloader.cpp#L388-L392
NZBGet can have a worker thread per connection that decodes the stream as it comes in and do the check then, however, due to the Python GIL the overhead of thread-switching in Python is terrible and we cannot do this.
Maybe when we switch to Python 3 and can use async/greenlet/etc approaches, but switching to Python 3 is still a long road for us.

I just checked some test-articles, and it seems that usually less than 1% of all 16-byte blocks contains a dot.
So as a first 'solution' I was thinking of doing the check if there is a dot present in the 16-byte block, then revert back to char-by-char processing for the whole block and also the block before/after it (in case it was at the start or finish of the current block).
It's a bit convoluted, but it would allow still a vast majority to be done via SIMD.
I tried to implement something of the sorts, but so far not much luck.

EDIT: All usenet downloaders must correct for this, 60% of posts I tried have the \r\n.. at least once.

Add experimental yEnc decoding support

I see, thanks for pointing that out!

I think a SIMD version should be fast enough to make threading not that needed. I mean, this yEnc library is single threaded and synchronous, as I feel that it's fast enough to not really warrant the need (I'll probably eventually add async support though).

I've committed up a very rough implementation. From my quick testing, it seems to work and handles all edge cases I've tried so far. Still needs work though, including more testing, tidying up, optimizations etc. I've just pushed it up in case you're interested. Unfortunately the algorithm is a bit convoluted, but maybe can be streamlined better.

The algorithm supports incremental processing by supporting 4 possible previous states (preceeding character is a =, \r, \r\n or something else).

Quick speed test of the current code on a 3.8GHz Haswell CPU, using random input data:
Scalar version: ~400MB/s
SIMD version: ~1700MB/s

Once this is tidied up, maybe I can write up something to help others port the code across (though it's mostly copy the functions across, a few defines, and lookup-table generation code).

Coool! 💯
I will need to take a closer look and dissect it a bit so I understand it well!

Wow, very impressive & cool.

I wanted to ask a noob question: is _mm_movemask_epi8() generic Intel SIMD / SSE, or is it Microsoft specific (because most Google hits are to microsoft.com)? ... But I can answer that question myself:

$ cat /usr/lib/gcc/x86_64-linux-gnu/6/include/emmintrin.h | grep _mm_or_si128
_mm_or_si128 (__m128i __A, __m128i __B)

So: also on Linux, so generic Intel SIMD/SSE. 👍

The Intel Instrinsics Guide (obviously lacks AMD extensions) is a handy reference. The movemask instruction is one useful instruction SSE has over ARM NEON.

I just realized a mistake: I've been treating =\r\n as a non-newline sequence, but thinking about it, this is incorrect because the NNTP layer doesn't care about yEnc's escaping semantics. So a sequence like =\r\n. should have its dot removed (NNTP protocol), then yEnc kicks in and unescapes the \r, so it should be converted to \xA3 instead of \xA3.. I'll need to fix that up.

Fix handling of =\r\n. sequences in decoder

@animetosho

Cool, nice to see my random thought bubble making this issue resulted in something usefull. If it's possible for NZBget, SABnzbd will also be able to take advantage of it 👍 All thanks to @animetosho!

@hugbug Did you possibly also have test results on ARM? Would be very interested to see how much Neon adds!

I've shifted my focus now to first converting SABnzbd to Python 3, so that it can also use VS2017 for compiling the C extensions (in 2.7 you're locked to VS2008) and use async stuff to also start decoding in chunks instead of having to use the current convoluted approach of list of chunks.
SABnzbd 2.3.1 maxes out a gigabit connection using my old i5, so I need to buy a slower device to even start testing real world impact of these things 😄

Reposting test results from NZBGet topic here as this is very much related to the discussion.

When making tests on two ARM devices discovered and fixed a performance bottleneck in NServ. The CPU usage of NServ has been greatly reduced, which in turn gives more CPU time to NZBGet and increases speed. All tests were rerun with improved NServ (including tests on Mac).

Test devices

MacBook 2010 with Intel Core i5-520 (2 cores @ 2.4 GHz, 4 threads), macOS 64 bit;
PVR with ARMv7 Cortex A-15 (2 cores @ 1.7GHz), Broadcom BCM 7251s, Linux 32 bit;
NanoPi NEO2 with ARMv8 Cortex A-53 (4 cores @ 1.5GHz), Allwinner H5, Linux 64 bit. NZBGet runs in 32 bit.

Test results

All numbers are in MB/s. For each decoder two test cases were measured - with and without CRC calculation; the latter is shown in parentheses. The overhead of CRC calculation shows how much improvement potential is still there - the CRC routine isn't optimised for SIMD yet.

Once again a reminder that the speeds below represent overall download speed in NZBGet, not just decoding speed.

Decoder	MacBook 2010	PVR ARMv7	NEO2 ARMv8
new-decoder per-line mode	307 (354)	89 (99)	102 (118)
simd-decoder per-line mode	336 (404)	89 (100)	101 (119)
simd-decoder raw mode	467 (570)	99 (109)	121 (141)
scalar-decoder raw mode	369 (421)	93 (105)	107 (124)
no-decoder raw mode	544 (693)	111 (128)	145 (168)

Observations

significant improvement when going from scalar to SIMD on Intel: 369 -> 467 MB/s: +25%;
good speed increase on ARMv8: 107 -> 121 MB/s: +13%;
small difference on ARMv7: +6%;
raw mode increases speed (compared to line mode) even without SIMD decoder; and SIMD decoder can show full potential in raw mode (thanks to larger blocks);
CRC calculation eats significant amount of speed and is worth improving. We can get potential speed increase up to 22% on Intel and 17% on ARMv8 (theoretical limit).

Thanks for those benchmarks - very interesting to know!

The ARM results are interesting. I don't really know ARM uArchs anywhere as well as I do x86, but I suspect lower performance on ARM cores which have a separate NEON unit (I believe older designs do this). But interestingly, from these slides, it seems that the Cortex A15 fully integrates NEON into the regular pipeline, so I'm a bit surprised with the lack of speed gain there. Perhaps this could mean that the SIMD decoder is slower than the scalar decoder on something like a Cortex A7.

I can't find much information on SIMD width on ARM chips. I believe the Cortex A57 and later use 128-bit units, so am guessing the A53 and A15 possibly use 64-bit units. That in itself will reduce the benefit of SIMD (half the throughput).

On Wikipedia page Comparison of ARMv7-A cores Cortex A-12, A-15 and A-17 are listed as having 128 bit NEON.

What wonders me in benchmark results is that the performance difference between the slowest (new-decoder per-line mode crc on) and the fastest (no-decoder raw mode crc off) is only 29% (68 vs 88) on ARMv7 whereas on Intel it's 125% (307 vs 693). As if CPU spends far more time doing other things and therefore doesn't respond so well to optimisations in decoder. May be it's not CPU itself but other system components such as slow RAM, I don't know.

@hugbug

@hugbug do you run NServ also on the ARM devices themselves? What if you run it on your Mac/Windows and then connect to the ARMv7 via Gigabit?
Just to see where the bottleneck is. In the end it's of course real life performance, in a fully working setup, that counts.

On Wikipedia page Comparison of ARMv7-A cores Cortex A-12, A-15 and A-17 are listed as having 128 bit NEON.

That's an interesting and useful comparison table.

Somewhat interestingly though, I just found this article which seems to imply that A15 is not 128b:

Architecturally, the Cortex A57 is much like a tweaked Cortex A15 with 64-bit support. The CPU is still a 3-wide/3-issue machine with a 15+ stage pipeline. ARM has increased the width of NEON execution units in the Cortex A57 (128-bits wide now?)

Similarly, the same site mentions that the A7 and A53 are single issue 64-bit units. Of course, the site could be wrong, but if it was true, it'd make a little bit more sense.

Your PVR benchmarks do seem a little odd still - I'd expect a 1.7GHz 3 wide out-of-order core to easily beat the 1.5GHz 2 wide in-order CPU at almost everything, but it seems to be significantly weaker. ARM claims that the A53 should be about as performant as an A9, but the A15 should be more powerful than an A9.

The NEO2 benchmarks make more sense to me, though your point about there being much less gain with everything disabled is certainly on the mark still.

connect to the ARMv7 via Gigabit?

Gigabit maxes out at 125MB/s, which I suspect could be a bit of a bottleneck (perhaps not for the PVR). Not exactly knowledgeable about the test server, but if it runs on a different core, hopefully it doesn't have much of an effect. Unless there's a memory bottleneck or similar - might be worth a try nonetheless (can get an idea for how network transfers affect the device).

I'm testing in NZBGet which is multithreaded and for tests 10 connections was configured, meaning 10 threads all doing similar jobs (on different articles): downloading, decoding, computing CRC, then normally also writing into disk but that last part was disabled during tests.

Therefore 4 cores @ 1.5GHz is better than 2 cores @ 1.7GHz.

What if you run it on your Mac/Windows and then connect to the ARMv7 via Gigabit?

Tried that too and got similar results. Now process ksoftirqd takes roughly the same amount of CPU as NServ was taking (40% from total 200%) . My guess is that has something to do with ethernet chip.

Decoder	PVR ARMv7 via Ethernet
new-decoder per-line mode	67 (74)
simd-decoder per-line mode	68 (74)
simd-decoder raw mode	73 (81)
scalar-decoder raw mode	71 (78)
no-decoder raw mode	82 (91)

When redoing tests on PVR I've noticed that I'm now getting lower CPU usage in NServ and better speeds in benchmark (97 MB/s in simd-decoder raw mode, crc on vs 72 MB/s in previous test). It seems in my previous test on PVR I was using an older version of NServ which didn't include the latest optimisation.

I'm redoing tests on PVR and will post updated results.

Results for ARMv7 (NServ) updated directly in the benchmark post.

ARMv7 and ARMv8 can now be better compared because the same nzbget binaries and same NServ were used in all tests.

If you are not tired of benchmarks here are numbers for SIMD CRC, which I've got just integrated (reposting from NZBGet issue tracker).

SIMD CRC

Integrated SIMD CRC routines for Intel and ARMv8 into NZBGet.

scalar-crc - CRC routine used in previous test (slice by 4);
simd-crc - SIMD routine: on Intel crc_fold, a sophisticated routine which uses CPU instruction PCLMUL. On ARMv8 it's a simple routine whose job is to execute dedicated CPU instruction crc32.

All numbers are in MB/s. For each decoder two test cases were measured - with and without CRC calculation; the latter is shown in parentheses. All tests were performed 4 times, the worst result was discarded and the average of the remaining three results were taken.

For convenience the table also includes all previous measurements with scalar-crc routine.

Decoder	MacBook 2010	PVR ARMv7	NEO2 ARMv8
new-decoder per-line mode, scalar-crc	307 (354)	89 (99)	102 (118)
simd-decoder per-line mode, scalar-crc	336 (404)	89 (100)	101 (119)
simd-decoder raw mode, scalar-crc	467 (570)	99 (109)	121 (141)
scalar-decoder raw mode, scalar-crc	369 (421)	93 (105)	107 (124)
no-decoder raw mode, scalar-crc	544 (693)	111 (128)	145 (168)

simd-decoder raw mode, simd-crc	520 (563)	n/a	136 (141)
scalar-decoder raw mode, simd-crc	397 (420)	n/a	118 (125)
no-decoder raw mode, simd-crc	621 (684)	n/a	165 (169)

Conclusion

Intel: with SIMD CRC routine the speed has improved from 467 MB/s -> 520 MB/s, significantly reducing the gap between CRC-ON (520 MB/s) and CRC-OFF (563 MB/s);
ARMv8: with dedicated crc-instruction we are getting CRC calculation almost for free: 136 MB/s CRC-ON vs. 141 MB/s CRC-OFF. Speed improvement: 121 MB/s -> 136 MB/s.

Thanks again for the benchmarks - they're quite interesting.

which is multithreaded

Oops, forgot about that, thanks for the correction!

I've gotten around to implementing the end scanning version of the decoder. Have been a little busy with other stuff, so took longer than expected.

Function signatures have changed to accommodate signaling how much input/output is consumed. I've also moved code around ~~to be rather annoying~~ because the interfaces have changed anyway. Return value signals what end sequence was hit. If it returns 0, then all input was consumed, otherwise *src is updated to point to the byte following \r\n=y or \r\n.\r\n.

Turns out that \r\n.=y needs to also be identified as a valid end sequence, due to the NNTP layer removing the dot, then the yEnc layer seeing \r\n=y. As such, I've decided to handle \r\n.\r\n accurately in the SIMD portion as well.

Searching for the end sequence is sometimes noticeably slower than not doing it, but hopefully faster than a second scan of the data.

Thanks so much! I'll integrate the new version and report back.

In the meantime I've done more tests, in particular on Dell 2015 notebook when running Linux. The numbers are crazy high (MB/s):

Improvement	MacBook macOS i5-520	Dell Windows i7‑5600U	Dell Linux i7‑5600U	PVR Linux ARMv7	NEO2 Linux ARMv8
improved decoder, scalar crc	305	389	480	89	102
raw decoder, scalar crc	369	414	636	93	107
simd decoder, scalar crc	467	493	836	99	121
simd decoder, simd crc	520	541	1011	n/a	136

For description of devices, test conditions and more results (not related to SIMD) please see original post.

Results for one-pass simd decoder with end-of-stream detection (simd-end):

Improvement	MacBook macOS i5-520	Dell Windows i7‑5600U	Dell Linux i7‑5600U	PVR Linux ARMv7	NEO2 Linux ARMv8
simd decoder	520	541	1011	99	136
simd-end decoder	520	570	1140	106	157

scalar crc for ARMv7, simd crc for all other devices.

Cool to see how within 1 month from creating this issue it has now a working implementation in NZBget. So I would say this issue served its purpose and in case I have specific implementation questions for SABnzbd I will open another topic!
Thanks all!

It has been interesting - thanks for creating the topic!

Are you planning to migrate to Python 3 before using this decoder? I imagine that SABYenc could be changed to use it, as is, but I'd imagine that Python 3's API would be different - if that's the goal.

Navigation Menu

Repository navigation

yEnc SSE decode ideas #4

28 remaining items

Test devices

Test results

Observations

SIMD CRC

Conclusion

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

yEnc SSE decode ideas #4

Description

Activity

animetosho commented on Sep 17, 2017

Safihre commented on Sep 17, 2017

animetosho commented on Sep 17, 2017

Safihre commented on Sep 17, 2017

animetosho commented on Sep 17, 2017

Safihre commented on Sep 17, 2017

animetosho commented on Sep 17, 2017

animetosho commented on Sep 18, 2017

Safihre commented on Sep 18, 2017

animetosho commented on Sep 19, 2017

Safihre commented on Sep 19, 2017

sanderjo commented on Sep 19, 2017

animetosho commented on Sep 19, 2017

28 remaining items

Safihre commented on Oct 9, 2017

hugbug commented on Oct 10, 2017

Test devices

Test results

Observations

animetosho commented on Oct 11, 2017

hugbug commented on Oct 11, 2017

Safihre commented on Oct 12, 2017

animetosho commented on Oct 12, 2017

hugbug commented on Oct 12, 2017

hugbug commented on Oct 12, 2017

hugbug commented on Oct 12, 2017

SIMD CRC

Conclusion

animetosho commented on Oct 15, 2017

hugbug commented on Oct 15, 2017

hugbug commented on Oct 19, 2017

Safihre commented on Oct 28, 2017

animetosho commented on Oct 29, 2017

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions