Inflate: `copy_rep_matches` can be faster

[Shnatsel]

This is a very hot function responsible for 30% of the time spent in inflate on an exr crate benchmark:

zune-image/zune-inflate/src/utils.rs

Lines 93 to 102 in 5097f4c

	for i in 0..length
	{
	// Safety: We assert the worst possible length is in place
	// before the loop for both src and dest.
	//
	// Reason: This is perf sensitive, we can't afford such slowdowns
	// and it activates optimizations i.e see
	let byte = dest[offset + i];
	dest[dest_offset + i] = byte;
	}

There are at least two ways to speed it up:

1. https://crates.io/crates/rle-decode-fast implements an algorithm copying data in batches exponentially increasing in size rather than byte-by-byte. This should be faster than the current approach, although may need some tweaking (e.g. capping the exponent at some size - needs benchmarks). Disclaimer - I took part in developing that, I may be biased.
2. Nothing is done to eliminate bounds checks. I don't think using an iterator will work here, but there's ample room for optimizer hints. I've successfully applied those in the inflate crate for this very algorithm.

[etemesi254]

Isn't the first one unsafe?

It does the equivalent of the below C code

while (dst<src){
   *dst++ =*src++;
}

And what exact optimizer hints? Would love to explore them.
Lemme experiment with some few ideas and see how it turns out

[Shnatsel]

rle-decode-fast crate impements RLE in safe code. It includes some unsafe for a function that was since included in the standard library, vec.extend_from_within(), but the RLE code itself is safe.

And no, it doesn't do what you described - it copies regions that are exponentially increasing in size instead of copying byte-by-byte:

https://github.com/WanzenBug/rle-decode-helper/blob/bdafaedc43accc2c7c53408144f2bc58bfc1bb0a/src/lib.rs#L35-L65

Same result, different and faster implementation.

And what exact optimizer hints? Would love to explore them.

I meant the bounds check elision tricks I covered in the article. Adding assert!s on slice lengths allowed the optimizer to remove bounds checks in this function in the inflate crate, see image-rs/inflate#43

[etemesi254]

Assert hints are finicky, they are amazing when they work but they don't work mostly

e.g say assert(offset+12<dest.len()); won't help remove bounds check, because offset may be a big integer and adding 12 in release mode causes it to wrap around and become smaller than dest.len(), meaning that passes but during indexing it's an out of bounds.
The compiler knows this and hence it can't elide it.

Theoretically saturating add should work but it also doesn't, this is probably a missed optimization.

I've done a small change in the dev branch, should reduce the number of times we call copy_rep_matches, I've tested on my machine that fuzzing still works, and all tests pass.

Could you check if that helps

[Shnatsel]

Sadly my machine is very noisy and is not really usable for benchmarking. I could get a cloud VM for the tests, but you'll need to tell me what I'm looking for exactly - criterion benchmark times or something else? The generated assembly, maybe?

[Shnatsel]

Anyway I'm probably off for the night, but I'll try to take a look tomorrow or so.

[etemesi254]

just Criterion Benchmarks, or whatever you used for exr checks, hopefully the region should be smaller.

[Shnatsel]

$ cargo +nightly fuzz run decode_buffer -- -timeout=1s

Almost immediately prints:

thread '<unnamed>' panicked at 'assertion failed: self.bits_left >= num_bits', /home/shnatsel/Code/zune-image/zune-inflate/src/bitstream.rs:106:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Also I think exr tests hang. PR: johannesvollmer/exrs#179 but the decode_buffer fuzzer should find it too

[etemesi254]

Fixed in 0.2.3

[etemesi254]

just Criterion Benchmarks, or whatever you used for exr checks, hopefully the region should be smaller.

The check that was added makes us call copy_rep_matches for matches less than FASTCOPY_BYTES and whose offsets would cause overlap on the current source.

Previously as long as the match was an overlap, we would call copy_rep_matches.

This now means for the hot loop, copy_rep_matches is called only for situations where loop is less than 16, remember we have room to do sloppy copies, but I can't get the compiler to elide bounds check even with a fixed/constant and asserts

[etemesi254]

THere is a faster rep copy algorithm with this commit 6bb95ac I think it should boost the speeeds currently.

Fuzz tested the three fuzzers this time,(sorry for the 0.2 release), so I don't think there are mistakes, but additional fuzzing wouldn't hurt.

CI should run fuzzing now.

[Shnatsel]

I confirm it has improved the exr benchmark. Before:

test read_single_image_non_parallel_zips_rgba        ... bench: 199,622,716 ns/iter (+/- 338,823)

After:

test read_single_image_non_parallel_zips_rgba        ... bench: 187,659,328 ns/iter (+/- 76,902)

miniz_oxide for comparison:

test read_single_image_non_parallel_zips_rgba        ... bench: 196,783,469 ns/iter (+/- 172,721)

[Shnatsel]

sorry for the 0.2 release

No worries. Nobody's using it in prod yet, and it's good that we broke something now and learned from it rather than later!

[Shnatsel]

I see that in 6bb95ac the copying loop is still very hot. I have an idea on how this could be improved, and how to remove bounds checks here.

We can write the output without bounds checks by iterating over the output slice with chunks_exact_mut as long as we have somewhere to copy from that doesn't overlap with the place to which we're writing.

imagine we have the fragment abc which we need to RLE-decode into abc.abc.abc.a (dots inserted for readability only, don't appear in the output).

The possible permutations we may have to write, assuming we copy 4 bytes at a time (FASTCOPY_BYTES = 4), are: abca, bcab, cabc, and that's it. So as long as we have written a slice that contains all of them, namely abc.abc, we can do split_at_mut on the stream, have the abc.abc on the left side, iterate over chunks_exact_mut on the right side, and copy the abca bcab cabc chunks from the left to the right.

This is guaranteed to remove the bounds checks from the hot loop.

We need to do one final copy of the remainder afterwards for correctness, as is common for chunks_exact_mut, to process any remaining data less than FASTCOPY_BYTES, but that's not hard.

[etemesi254]

I confirm it has improved the exr benchmark. Before:

test read_single_image_non_parallel_zips_rgba        ... bench: 199,622,716 ns/iter (+/- 338,823)

After:

test read_single_image_non_parallel_zips_rgba        ... bench: 187,659,328 ns/iter (+/- 76,902)

miniz_oxide for comparison:

test read_single_image_non_parallel_zips_rgba        ... bench: 196,783,469 ns/iter (+/- 172,721)

This does also improve png decoding by 3% , almost hitting 2x faster speeds than imagers/png