Cell::as_slice_of_cells() replaces windows_mut and eliminates bounds checks

[Shnatsel]

We've been having trouble with bounds checks in the RLE hot loop in zune-inflate, and couldn't eliminate them because the slices we wanted to operate on were overlapping. Since there's no windows_mut in Rust, we could not use iterators to get rid of bounds checks.

Following the release of my article, a PR has been merged into the standard library explaining how to work around this.

You can see it in action on the samples from the article here.

[etemesi254]

On it

Lemme take a look this weekend .

Hope it helps in the benchmarks.

Also loved the article, (esp the anti-patterns, fell prey to some)

Will update this very soon

[etemesi254]

A little bit complicated, needs some comments around it
But does the job https://godbolt.org/z/Y4e4qqhaE

#[inline(always)]
pub fn copy_rep_matches_new(dest: &mut [u8], offset: usize, dest_offset: usize, length: usize)
{
    let diff = dest_offset - offset + 1;

    for window in Cell::from_mut(&mut dest[offset..offset+length+1])
        .as_slice_of_cells()
        .windows(diff)
    {
        window.last().unwrap().set(window[0].get());
    }
}

[etemesi254]

The batching was to remove the number of copies we needed to do to finish a copy depending on the situation.

With this it becomes difficult, batch copy moves in batches and windows() can't move in batches, (always moves by one byte)

[Shnatsel]

Well, you could definitely eliminate several branches from fixed_copy_within just by using slice_of_cells + windows instead of loop + break. Although you'll probably have to hand-roll fixed_copy_within instead of just using slice::copy_within.

[etemesi254]

A small poc would be nice, as I can't see how that works.

The compiler does two bounds check there, one to check end is greater than start, and one to check end is in bounds.

Number of instructions to beat is 4

[Shnatsel]

Something like this? Shnatsel@5c88389

But you're right, this really hinges on whether the compiler will load every byte individually when they're all behind a Cell or load them in bulk.

My hope is that copying to an intermediate buffer will be desugared into a load and store into a 128-bit register. But if that's not the case, then this approach isn't viable.

[Shnatsel]

You were right, using Cells in the overlapping bulk copy loop resulted in a massive performance drop. I'm going to abandon this line of inquiry.

[etemesi254]

Btw this Cells::as_slice is goood.

Kills bounds checks in png filterings

I.e this

pub fn handle_avg(
    prev_row: &[u8], raw: &[u8], current: &mut [u8], components: usize, _use_sse4: bool
)
{
    if raw.len() < components || current.len() < components
    {
        return;
    }


    // no simd, so just do it the old fashioned way

    // handle leftmost byte explicitly
    for i in 0..components
    {
        current[i] = raw[i].wrapping_add(prev_row[i] >> 1);
    }
    // raw length is one row,so always keep it in check
    let end = current.len().min(raw.len()).min(prev_row.len());

    if components > 8
    {
        // optimizer hint to tell the compiler that we don't see this ever happening
        return;
    }
    for i in components..end
    {
        let a = u16::from(current[i - components]);
        let b = u16::from(prev_row[i]);

        let c = (((a + b) >> 1) & 0xFF) as u8;

        current[i] = raw[i].wrapping_add(c);
    }
}

And this

use std::cell::Cell;

pub fn handle_avg(
    prev_row: &[u8], raw: &[u8], current: &mut [u8], components: usize, _use_sse4: bool
)
{
    if raw.len() < components || current.len() < components
    {
        return;
    }
    // handle leftmost byte explicitly
    for i in 0..components
    {
        current[i] = raw[i].wrapping_add(prev_row[i] >> 1);
    }
    // raw length is one row,so always keep it in check
    let end = current.len().min(raw.len()).min(prev_row.len());

    if components > 8
    {
        // optimizer hint to tell the compiler that we don't see this ever happening
        return;
    }
    let current_as_cells = Cell::from_mut(&mut current[..end])
        .as_slice_of_cells()
        .windows(components + 1);

    for ((current_window, byte), r) in current_as_cells
        .zip(&prev_row[components..])
        .zip(&raw[components..])
    {
        let a = u16::from(current_window.first().unwrap().get());
        let b = u16::from(*byte);

        let c = (((a + b) >> 1) & 0xFF) as u8;

        current_window.last().unwrap().set(r.wrapping_add(c));
    }   
}

Are semantically equivalent,but the latter doesn't have bounds check. My only problem is that the latter is a code bloat since it generates sse code for paths greater than 8, the only one I can think of is 16 bit RGBA images(4 (colorspace)* 2(number of bytes)), I should probably add a benchmark for that.

[etemesi254]

Sadly doesn't help, e.g benchmark numbers for 16 bit png unfiltering

decoder	speed
zune-png	672 ms
image-rs/png-decoder	692 ms
spng	711 ms

If i add a SSE path for 16 bit unfiltering,we have

decoder	speed
zune-png	303.14 ms