align lowlevel datastructures about borg

[ThomasWaldmann]

The specific issue was solved by jborg. I'm leaving this open nevertheless so in case we touch the datastructures, we can keep this in mind.

[enkore]

I experimented with alignment in ChunksIndex a bit today. Results:

• Padding the key-value length to 64 byte (up from 44 byte) improves overall performance a bit (~5 % – so quite a good bit when only looking at the Cache) for Cache-intensive stuff and has no impact on other stuff (as expected)
• It breaks the on-disk format of the Cache
• Currently Cache loading aborts if the version has changed (instead of automatically recovering, i.e. deleting the cache and recreating it)
• Upgrading the chunks cache when changing the layout is difficult (without using twice as much memory)

I tried this as an efficient way for borg rewrite to tag seen chunks; using a dedicated set requires approx 100 byte per chunk, so 100 MB per 1 million chunks.

I dropped the ChunksIndex approach because of these compatibility issues, and added a "save memory" option instead). And because it changed quite a lot of code.
Nevertheless, if we decide to pad it at some point, using part of the padding in a few places for tagging chunks might be a nice bonus.

[ThomasWaldmann]

it looks like what you did is for performance optimization, which is a somehow different topic than this issue, which is about avoiding alignment errors on cpus that require alignment (e.g. on 32bit boundaries) due to their architecture.

also, i think increasing the entry size of the chunks index for a small speed increase is out of question as the chunks index might get huge, so adding almost 50% to that makes it a even bigger problem.

the chunks index entries are 256bit + 32bit + 32bit + 32bit, so they are already 32bit aligned, but some header structures are not.

[enkore]

In a sense. The 5 % or something are nice, but nothing worth breaking anything.

For rewrite it's pretty important to know which chunks have been processed already (-- in certain scenarios, e.g. rechunking or recompressing), because otherwise a chunk will be processed as often as it's refcount.

So the first - obvious - approach was to have a set around and put the chunk IDs processed in that set, and skip processing for IDs in that set. But that isn't memory efficient (100 MB / 1 million chunks), putting it the chunkindex required the padding, but as said above breaks the Cache - which does not recover automatically -, requires more memory for all operations and increases on-disk index size even further.

I pondered if there was any way to more efficiently store the seen chunks, but I haven't had any idea. Memory wise it could re-use the string memory (32 bytes / chunk) used by the Cache[1], but that's a) dirty b) a lot of effort c) still needs the hash set structure. Maybe something structurally similar to a rainbow-table, but that doesn't work.

[1] Which might be a good lead for realistically optimizing the cache. As it's now the chunk IDs are stored in the HashIndex and copied on access by Python. That not only needs more memory but also needs to go ask daddy the allocator. This is somewhat remedied by the ChunkBuffer (when creating archives), which will deallocate the chunk ID bytes when they're serialized. Maybe using memoryviews or something.

[ThomasWaldmann]

Hmm, i had a look at the code:

• the HashHeader length is still not divisable by 4
• but as the buckets are not loaded together with the header, but by a separate read op into a separate buffer, i guess this is no real problem.

[ThomasWaldmann]

#6960 made the header 1024 bytes long, so the buckets array after it is aligned (even if the whole file were mmapped).