Assembler optimizations

[puzzledsab]

I've started this discussion for more general talk about Python and file assembler optimizations. The 16 KB SSL discussion is getting a bit long and broad and it seems better to keep #2396 specifically for the technical issues of replacing MD5 with CRC32.

I have done some isolated testing of 750 KB blocks while calculating MD5. My conclusion is that it can be parallelized fairly well. Even with just one thread, the calculating and writing overlaps somewhat. It's probably because of the write cache. Doing MD5 in a separate thread can improve it to be more or less fully parallelized. In my test branch I've put it in a separate thread: https://github.com/sabnzbd/sabnzbd/pull/2391/files

We could even run multiple MD5 threads as long as most usenet posts consists of lots of RAR files by downloading blocks from multiple files simultaneously. If we have x threads with their own queue then we could attach threads with queues to each file (nzf) in a round robin fashion. It would make sure SAB could scale better as CPUs get more cores without increasing the frequency much. It wouldn't work on spinning disks but those probably won't be faster than single core MD5 calculations anyway.

There was some discussion about sparse files. I'm not sure if that's a good idea, for the same reason. I assume that if we write parts to random parts in a file then the write speed will go down on a spinning drive. I suspect that this may sometimes be the reason why some people get a higher speed with SAB than Nzbget.

@mnightingale: Regarding your last message, I think that in theory it shouldn't be necessary to release the GIL by using sleep. It happens anyway both when writing data and calculating MD5. Because of this I think it's already releasing the GIL most of the time it's running. If you want to try without the unnecessary loops and file openings you can apply this change: https://github.com/sabnzbd/sabnzbd/pull/2392/files

[animetosho]

If you want to stick with MD5, I'd recommend ignoring the file MD5 and try to compute block based MD5s instead. Block MD5s won't be less reliable than a file MD5 (unlike CRC32).
(I've argued that PAR2's file-based MD5 is rather useless and only limits performance; a PAR2 writer can't avoid computing it, due to the spec, but a PAR2 reader can easily pretend the file MD5 doesn't exist)

We could even run multiple MD5 threads as long as most usenet posts consists of lots of RAR files by downloading blocks from multiple files simultaneously

The assumption obviously breaks if the upload isn't a bunch of parts. But as you point out, you generally want to write sequentially as much as possible, without jumping across files.
I implemented a strategy for balancing MD5 parallelism and sequential I/O during PAR2 creation. If you really want to stick with file-based MD5, it might be worth considering - it may work better than round-robin scheduling for spinning disks (probably doesn't matter much for SSDs).

But even in the ideal scenario, it scales less than what a block-based MD5 approach can achieve, hence my recommendation to avoid relying on file-based MD5s if possible.

There was some discussion about sparse files. I'm not sure if that's a good idea, for the same reason. I assume that if we write parts to random parts in a file then the write speed will go down on a spinning drive.

Sparse/pre-allocated files doesn't prevent you from writing sequentially though. They just provide the option to perform a random write if necessary (e.g. missing articles, article cache fills up etc). Other benefits are listed here.

[puzzledsab]

If you want to stick with MD5, I'd recommend ignoring the file MD5 and try to compute block based MD5s instead. Block MD5s won't be less reliable than a file MD5 (unlike CRC32). (I've argued that PAR2's file-based MD5 is rather useless and only limits performance; a PAR2 writer can't avoid computing it, due to the spec, but a PAR2 reader can easily pretend the file MD5 doesn't exist)

Just to be clear, I'm very grateful for all your suggestions. There has been such a rush of big optimization ideas the last few days that it's a bit overwhelming. I will certainly look into this eventually if nobody else does it first.

Perhaps the main advantage of the file MD5 is that it's very simple. It can be used both to identify the file in the PAR2 set without knowing the block size and to verify the data. There have been a few cases where people put par2 files in rar files which can be used to deobfuscate the name after the download is complete. Those may not use the same part size. Of course, we could use the 16KB block for this.

Sparse/pre-allocated files doesn't prevent you from writing sequentially though. They just provide the option to perform a random write if necessary (e.g. missing articles, article cache fills up etc). Other benefits are listed here.

I can certainly see your point and in theory I don't think it should be all that hard to implement where it is supported. My main worry right now is how to determine when it can be used safely and when it would not work or degrade performance, for instance because it would allocate a huge file and fill it with zeros.

[animetosho]

Apologies if my comment came across as rather strong or inconsiderate - I mostly wanted to just start some discussion. I think your ideas + contribution has a lot of merit, particularly with its simplicity (so much so that you've already implemented it!).

I was focusing more on if further improvements are desired. If it's all too much, I completely understand and have no qualms about throwing it on the 'maybe think about it later' pile.

There have been a few cases where people put par2 files in rar files which can be used to deobfuscate the name after the download is complete

(rant) Uploaders really do like doing some of the silliest things... I really wish they'd cut down on the shenanigans, though I sometimes wonder whether I'm actually the crazy one.
PAR2 is designed to be resilient against corruption. That obviously falls apart if you do something as questionable as wrap it in a RAR that could fail to extract.

...anyway, if the PAR2 files are in a RAR:

• if it's in the same archive as the other files, then Quick Check just won't work, since everything needs to be extracted to check anything, and the PAR2 is much less useful if the files extracted without issue
• if it's in a separate archive, Sabnzbd would need to know which archive to extract to get the PAR2, so that it can check. In such a case, downloading and extracting the archive as the first step in the download process sounds feasible, though may add complexity
• if Sabnzbd can't tell which archive contains the PAR2, and just tries brute forcing all archives, it'll know if something is corrupt due to the extract failing. In such a case, Quick Check is much less useful (if at all).
• if the uploader supplies multiple PAR2 sets, with different block sizes, I suppose the only solution is to use the 16KB hash. With file-based MD5, you have the advantage of using that instead of the 16KB hash, so there's a benefit I guess, though it is more likely to break in the case of missing articles

Of course, the complexity with block-based MD5 is that the PAR2 needs to be downloaded first (or at least close enough) to obtain the relevant block size.

My main worry right now is how to determine when it can be used safely and when it would not work or degrade performance, for instance because it would allocate a huge file and fill it with zeros.

It should be fine on the most widely used filesystems out there (may have to check with the FAT family). Not sure about network attached storage - may need checking on that.

Most applications I've seen just expose it as an option, with preallocation enabled by default. If you want to stay cautious, you could just leave it disabled at first.

[mnightingale]

Duplicating from the 16 KB discussion and a few additional things from some observations I found of the assembler behaviour:

• My PC seems to be able to MD5 at around about 1 GB/s this has the consequence of bottlenecking the maximum speed the assembler can write at
• From this I observed that if the MD5 calculation was no longer required (I hardcoded it and commented out the update/digest calls) or replaced with a quicker calculation (CRC) and the bottleneck removed the result would be that the article cache can be flushed to disk more often - this is likely also the path most users experience currently, if they are downloading at say 50 MB/s then the assembler could be ran thousands of times using more CPU then if it could batch them together better:
  • I found 10 GB downloading at ~2 GB/s called the assembler ~250 times
  • The logic is roughly:
    • [IO] open nzf.filepath
    • for each article
    • continue if article has already been written
    • [IO] write article
    • [CPU] update MD5
    • [IO] close nzf.filepath
  • The actual path could be [IO] open => [IO] write very few files => [IO] close
  • Or in my case above with a 10 GB download assembled 250 times only write 40MB per iteration on average
  • I think it's expensive to open => write a small amount of data => close
  • Larger sequential writes can be written faster on SSD and HDD

My PC and in-memory testing setup is quite extreme however, if optimisations can be found allowing faster speeds to be possible then it will also have the effect of reducing CPU usage for slower connections or better performance on slower devices.

If any system can download faster than it can MD5 or I suppose faster than it can write the article cache then the article cache can become full, at which point it is bypassed and writes straight to disk which the assembler than needs to read again.
I think this aspect probably warrants a separate discussion.

I think there are a couple of areas we should consider optimisations to:

• The assembler IO open/close, perhaps don't use "with" and only open if something needs writing
  • Maybe the file could just be kept open - throughout the assemble state or for a time limit of inactivity.
• Logic around determining if it's worth the assembler running
  • On the 16 KB discussion I mentioned testing a naïve approach of just sleeping after every assemble, I agree with @animetosho that wouldn't be a good design
  • As @animetosho proposed maybe query the article cache length - article cache size could be 0 so something to be aware of.
  • @animetosho mentions write and writev, Python does have os.writev (unix only), but I would expect the high level file handling in Python is already handling that for us
  • Looping through all the articles to find one that hasn't been written Use index for assembler to reduce looping and file opening #2392 - I don't think the looping is very expensive, I see @puzzledsab has since revised it to only open the file if needed - instead I propose a design were nzf.decodetable is a queue and pops it if article.on_disk.
  • I think maybe a calculation related to article cache utilisation and/or how long an item has been cached or downloaded for, e.g. if the "next" article was downloaded >1 second ago then run the assembler consuming the cache and any articles that were downloaded in the last second.
  • May need to consider SSD vs HDD performance

Please share any thoughts on the above or your own ideas for the optimal "should the assembler run" logic.

[animetosho]

Previously, MD5 was computed, and MD5 must be computed in order. Now that's no longer being performed, assembling in order isn't strictly required.

Sequential writing is generally preferred, even on SSDs, so having an article cache makes sense, in my opinion. However, the current strategy of spilling to disk, when cache space is depleted, is worse than just doing an in-place out-of-order write (i.e. skipping ahead and writing); the spill isn't going to be a sequential write anyway (since it's to a separate file), so either way, you're doing an out-of-order write, but spilling has the added cost of needing to eventually re-read and write the article again.

This would also allow the article cache to be more modestly sized (<100MB), and eliminates the notion of temporary article storage altogether.

[mnightingale]

isnt the point of the article cache is to take in the decoded stuff and write the file in order?

Yes because sequential writes are faster requring fewer diskoperations and for HDDs it should result in less fragmented files.

After taking a look I don't think the assembler looping logic is a problem because it waits until it has a few articles ready to write anyway.

A quick look a line profile shows:

• 4.5 second total (CPU time)
• 11% opening the file (115 calls so some duplicates)
• 9% on sabnzbd.ArticleCache.load_article(article)
• 79% writing

So for instance files could be kept open and articles could have a weak reference to the data in the cache avoiding the dictionary lookup.

---

I think the in-order writing is desirable, but @animetosho raises a good point about what to do when the cache is full.

The current overflow logic just gives the bottlenecked disk even more work to do writing to temporary files which will eventually be re-read.

The downloader does try and slow down if there are many things waiting to be written to disk, I havent really looked at it properly to see how well it works but I think potentially if the cache is full downloading should wait until it's all flushed to disk and never write to temporary files.

I also have a PR in progress that's going to combine the download and decode operations which will cut out some operations and maybe help CPU cache hits 🤷

[puzzledsab]

I've been thinking a lot about improving the mechanism for finding the next article to fetch but it's difficult to improve because you have to take into account that there can be many servers. The 20 article list is more like a lock, which locks those articles to a particular server by setting the fetcher attribute until it has tried to download them. If it couldn't download them then the other servers will have to try. If there are two or more servers with the same priority then they will grab blocks of 20 articles each. If one fails then the other one has to effectively go back and try the articles it skipped while they were locked.

I changed the TryList to be a set once. It helps when several servers have to try the same article but usually it's fetched by the first so it doesn't matter much. Using normal attribute assignment (dict_["bytes"] = self.bytes) in article.__getstate__() instead of getattr() had a bigger impact because it's one of the most frequently called functions and it's about 30% faster. I'm not sure how much it means compared to all the other code. I had stashed it and then I deleted it by mistake and forgot about it.

The cache should no longer overflow as easily as it did in your first artificial tests. I believe the problem then was that they would appear to transfer a single huge file. SABnzbd would never add the same file to the assembler queue more than once so the download speed reduction would never kick in. I changed it so that the number of articles it would wait before it was added to the queue would be 5% of the total cache. Now it will wait 71 articles with a 1GB cache instead of the previously fixed number of 35.

I also changed it so that it always adds it to the queue. If the assembler can't keep up then the queue will normally fill up and the download speed will slow down long before the cache is full. It should now only overflow if there are a lot of missing articles that prevent the assembler from continuing to write the file until they have been checked by all servers.

I have tried writing sparse files in #2459 but I frequently end up with one or two errors according to the par2 check. The same nzbs download correctly with the develop version.

[mnightingale]

It's certainly a complicated and confusing, there are about three different get_article or get_articles functions in different places.
I did have a look at it but couldn't think of a more efficient way to structure it

Speaking of TryList I noticed every class inheritting from it shares the same global lock, I'm not sure if that is by design or an oversight.
I have noticed the state calls showing up in profiling a few times, are they for saving the queue state to disk? does that happen often?

Since the original post I have noticed the cache overflow behaviour is much better.

I'll take a look at #2459 when I can and see if I can find why it ends up incorrect sometimes, I'm just trying to figure out a race condition with combining download & decode.

[Safihre]

Regarding the Try List lock, it's a single lock because there is rarely need for a lock, only the queue reads and writes most of the time. Sometimes the decoder, so it's fine to just have one.

[puzzledsab]

We could do what we do several other places to reduce useless calls. Add a next_assemble_time to nzf which is a timestamp set for instance 0.2 seconds into the future after each full assemble run. Then we skip the assemble unless current time is higher or the file_done flag is true.

[Safihre]

@puzzledsab feel free to make a proposal PR :)

PS: I did not forget about your mypyc PR, I want to look into seeing how we can incorporate it.

[thezoggy]

looking at logs with latest dev (4.2.0a2), was curious why article cache doesnt seem to use too much and recalled this discussion. in logs i see "Assembler trigger = 72" what is the 72 in regards?

[Safihre]

After 72 articles we trigger data to be written to disk (if haven't gotten all articles of a file), it depends on cache size since larger caches can hold more data and write in more continuous larger bursts which is more effecient.
However, 72 articles is around 50MB so probably it just writes every Rar it gets since they'll all be smaller than that.

[thezoggy]

I was telling someone on usenet about how usenet parts are usually 100M or less and how we did stuff with article cache that you normally only see limited use because of it.. With my cache set to 1G, seems like it would always trigger at 72. I changed article cache to 4G and now I see that value getting to 244 now. Hard to really see what connections are working on since cache value is on a different tab than connections.. but do we flush to disk per file or really once we hit the article cache/space threshold which could spread across multiple files?

[Safihre]

That numerical limit is per file, not total.
If we exceed the total limit we start writing the raw data to disk in seperate files instead of as part of the final file. Very slow.