#BoundedArray much slower than ArrayList

1 messages · Page 1 of 1 (latest)

golden garnet
#

I was toying around porting a baremetal riscV code from Rust to Zig and noticed a critical section was performing an order of magnitude slower the orignal code. In this section, a piece of hardware ask for an address which is stored somewhere in memory, and the code should fetch this address and send it back to the hw.
Basically, the hot loop is continuously polling on the hw until there's a request, then it pops the asked item from a queue/array/whatever and writes it to the hw. Since the array maximum capacity is known at compile time, it felt natural to use BundedArray, which also avoid dealing with an allocator, but somehow this resulted much slower in performances than using an ArrayList with a FixedBufferAllocator (like 500us vs 50us on the riscV core I'm using to handle the request).

If someone is interested, I wrote a chunk of code which compares push/pop times for ArrayList and BoudedArray, which shows the same behavior when run on my x86 laptop:

const std = @import("std");
const ITERATIONS = 100000000;

fn test_bound(array: anytype, item: *u64) void {
    const t0 = std.time.microTimestamp();
    for (0..ITERATIONS) |_| {
        array.append(item.*) catch unreachable;
        item.* = array.pop();
    }
    const t1 = std.time.microTimestamp();
    std.debug.print("{} - {} elapsed {}\n", .{ @TypeOf(array), item.*, t1 - t0 });
}

pub fn main() !void {
    std.debug.print("hello\n", .{});

    var barr = try std.BoundedArray(u64, 100).init(0);

    var buffer: [1000]u8 = undefined;
    var fba = std.heap.FixedBufferAllocator.init(&buffer);
    const allocator = fba.allocator();

    var list = std.ArrayList(u64).init(allocator);
    defer list.deinit();

    var item: u64 = 3;
    test_bound(&list, &item);
    test_bound(&barr, &item);
}

Built with ReleaseSafe, this result in ~60ms for ArrayList and ~2600ms for BoundedArray.
Is this expected or am I doing something wrong?

covert bloom
#

interesting

covert bloom
#

ok i dug around in assembly for a bit but i don't really see anything obvious

#

tried using C backend but it segfaulted openissue

livid folio
#

im not sure if this is the issue, but the only difference I can see is that BoundedArray.pop() uses BoundedArray.slice() to get a slice of items, and that requires creating a slice
which is probably really cheap but maybe it adds up?
that’s just the only difference I see between ArrayList.pop and BoundedArray.pop

maybe a faster solution would be to do self.buffer[i] but then you wont get currect bounds checking (ofc, the function can just assert it though)

covert bloom
#

i wonder if it's memcpying the bounded array around unnecessarily

#

i ran into that in a personal project using some big structs

livid folio
#

it should only copy it once

covert bloom
#

and that was also a struct passed through a pointer with an array field

zenith seal
#

interesting, the time it takes definitely scales with the bounded array size

#

if you change the size to 1 it only is 2 times slower

# 
bounded_array_size_1:
        mov     eax, 1000000
        mov     cl, 1
.LBB3_1:
        sub     rax, 1
        jb      .LBB3_6
        test    byte ptr [rdi + 8], 1
        jne     .LBB3_3
        mov     rdx, qword ptr [rsi]
        mov     byte ptr [rdi + 8], 1
        xor     r8d, r8d
        test    cl, cl
        sete    r8b
        mov     qword ptr [rdi + 8*r8], rdx
        mov     dl, byte ptr [rdi + 8]
        and     dl, 1
        jmp     .LBB3_5
.LBB3_3:
        xor     edx, edx
.LBB3_5:
        xor     r8d, r8d
        test    dl, dl
        sete    r8b
        mov     rdx, qword ptr [rdi]
        mov     r9, qword ptr [rdi + 8]
        mov     qword ptr [rsp - 8], r9
        mov     qword ptr [rsp - 16], rdx
        mov     rdx, qword ptr [rsp + 8*r8 - 16]
        sete    byte ptr [rdi + 8]
        mov     qword ptr [rsi], rdx
        jmp     .LBB3_1
# 
arraylist:
        push    r15
        push    r14
        push    r13
        push    r12
        push    rbx
        sub     rsp, 16
        mov     rbx, rsi
        mov     r14, rdi
        xor     r15d, r15d
        push    -1
        pop     r12
.LBB2_1:
        cmp     r15, 1000000
        je      .LBB2_9
        mov     r13, qword ptr [rbx]
        mov     rcx, qword ptr [r14 + 8]
        mov     rax, rcx
        inc     rax
        sete    dl
        sete    byte ptr [rsp + 8]
        sete    byte ptr [rsp + 15]
        test    dl, dl
        jne     .LBB2_8
        mov     rsi, qword ptr [r14 + 16]
        cmp     rsi, rax
        jae     .LBB2_7
.LBB2_4:
        mov     rcx, rsi
        shr     rcx
        add     rcx, 8
        add     rsi, rcx
        cmovb   rsi, r12
        cmp     rsi, rax
        jb      .LBB2_4
        mov     rdi, r14
        call    "array_list.ArrayListAligned(u64,null).ensureTotalCapacityPrecise"
        mov     rcx, qword ptr [r14 + 8]
        test    ax, ax
        jne     .LBB2_8
        lea     rax, [rcx + 1]
.LBB2_7:
        mov     qword ptr [r14 + 8], rax
        mov     rax, qword ptr [r14]
        mov     qword ptr [rax + 8*rcx], r13
        mov     rcx, qword ptr [r14 + 8]
.LBB2_8:
        mov     rax, qword ptr [r14]
        mov     rax, qword ptr [rax + 8*rcx - 8]
        dec     rcx
        mov     qword ptr [r14 + 8], rcx
        mov     qword ptr [rbx], rax
        inc     r15
        jmp     .LBB2_1
.LBB2_9:
        add     rsp, 16
        pop     rbx
        pop     r12
        pop     r13
        pop     r14
        pop     r15
        ret
# 
bounded_array_size_100:
        push    r15
        push    r14
        push    r13
        push    r12
        push    rbx
        sub     rsp, 816
        mov     rbx, rsi
        mov     r14, rdi
        mov     r12d, 1000000
        lea     r15, [rsp + 8]
.LBB3_1:
        sub     r12, 1
        jb      .LBB3_5
        mov     al, byte ptr [r14 + 800]
        mov     ecx, eax
        and     cl, 124
        cmp     cl, 99
        ja      .LBB3_4
        mov     rcx, qword ptr [rbx]
        inc     al
        and     al, 127
        mov     byte ptr [r14 + 800], al
        dec     al
        and     al, 127
        movzx   eax, al
        mov     qword ptr [r14 + 8*rax], rcx
        mov     al, byte ptr [r14 + 800]
.LBB3_4:
        dec     al
        and     al, 127
        movzx   r13d, al
        mov     edx, 808
        mov     rdi, r15
        mov     rsi, r14
        call    memcpy@PLT
        mov     rax, qword ptr [rsp + 8*r13 + 8]
        mov     byte ptr [r14 + 800], r13b
        mov     qword ptr [rbx], rax
        jmp     .LBB3_1
.LBB3_5:
        add     rsp, 816
        pop     rbx
        pop     r12
        pop     r13
        pop     r14
        pop     r15
        ret
#

so yeah there is a copy of the entire thing inside the loop

# 
        mov     edx, 808
        mov     rdi, r15
        mov     rsi, r14
        call    memcpy@PLT

this is definitely why you're seeing numbers so large

#

it seems to be in pop()

# 
        /// Return the element at index `i` of the slice.
        pub fn get(self: Self, i: usize) T {
            return self.constSlice()[i];
        }

do you guys think it's the call to get(len - 1)?

#

since get takes self by value?

#

with fixed signature on get, 100 elements capacity:

        mov     eax, 1000000
.LBB3_1:
        sub     rax, 1
        jb      .LBB3_5
        mov     cl, byte ptr [rdi + 800]
        mov     edx, ecx
        and     dl, 124
        cmp     dl, 99
        ja      .LBB3_4
        mov     rdx, qword ptr [rsi]
        inc     cl
        and     cl, 127
        mov     byte ptr [rdi + 800], cl
        dec     cl
        and     cl, 127
        movzx   ecx, cl
        mov     qword ptr [rdi + 8*rcx], rdx
        mov     cl, byte ptr [rdi + 800]
.LBB3_4:
        dec     cl
        and     cl, 127
        movzx   ecx, cl
        mov     rdx, qword ptr [rdi + 8*rcx]
        mov     byte ptr [rdi + 800], cl
        mov     qword ptr [rsi], rdx
        jmp     .LBB3_1
.LBB3_5:
        ret
#

const item = self.get(self.len - 1); -> 13415us (with get taking a pointer)
const item = self.constSlice()[self.len - 1]; -> 4637us
compared to arraylists 9601us

#

yeah so something funky still going on with the call to get

#

it's way more heavy than just getting the slice

#

with fixed body of get, 100 elements capacity:

        mov     eax, 1000000
.LBB3_1:
        sub     rax, 1
        jb      .LBB3_5
        mov     cl, byte ptr [rdi + 800]
        mov     edx, ecx
        and     dl, 124
        cmp     dl, 99
        ja      .LBB3_4
        mov     rdx, qword ptr [rsi]
        inc     cl
        and     cl, 127
        mov     byte ptr [rdi + 800], cl
        dec     cl
        and     cl, 127
        movzx   ecx, cl
        mov     qword ptr [rdi + 8*rcx], rdx
        mov     cl, byte ptr [rdi + 800]
.LBB3_4:
        add     cl, 127
        movzx   ecx, cl
        mov     edx, ecx
        and     edx, 127
        mov     rdx, qword ptr [rdi + 8*rdx]
        and     cl, 127
        mov     byte ptr [rdi + 800], cl
        mov     qword ptr [rsi], rdx
        jmp     .LBB3_1
.LBB3_5:
        ret
#

so yeah I can beat arraylist but I don't know why get kills it so bad

#

who maintains boundedarray?

#

const item = self.buffer[self.len - 1]; -> 1768us

#

this generates the best code

vivid hill
#

what happens if you mark get and (const)slice inline

zenith seal
#

great question

#

I'll try that in a sec

#

well I mean

#

they are getting inlined

#

there must be something else happening by crossing the function call boundary

#

I figured something else out

vivid hill
#

well zigs inline is semantic not just an optimization
curious if that has an effect

zenith seal
#

this thing was a giant perf pessimization

vivid hill
#

oof

zenith seal
#

I changed const Len = u32; and now pop codegen is like half as large

#

and runtime down to 1400us

vivid hill
zenith seal
#

20% perf win just by changing size to u32

vivid hill
#

i think that pr wasnt very helpful even if it didnt make it worse

zenith seal
#

codegen with u32 size:

example.test_bound__anon_3500:
        mov     eax, 1000000
.LBB3_1:
        sub     rax, 1
        jb      .LBB3_5
        mov     ecx, dword ptr [rdi + 2048]
        cmp     rcx, 255
        ja      .LBB3_4
        mov     rdx, qword ptr [rsi]
        lea     r8d, [rcx + 1]
        mov     dword ptr [rdi + 2048], r8d
        mov     qword ptr [rdi + 8*rcx], rdx
        mov     ecx, dword ptr [rdi + 2048]
.LBB3_4:
        dec     ecx
        mov     rdx, qword ptr [rdi + 8*rcx]
        mov     dword ptr [rdi + 2048], ecx
        mov     qword ptr [rsi], rdx
        jmp     .LBB3_1
.LBB3_5:
        ret
#

a shitton better

vivid hill
#

the struct is the size of probably tens to hundreds of bytes
a fitting int like that isnt gonna do a thing for saving space

zenith seal
#

yeah not only that

#

like the alignment

#

it will be padded anyways

#

we need fastIntFittingRange()

#

which only returns ints that are fast on the target platform

vivid hill
#

maybe std.math.ceilPowerOfTwo?

zenith seal
#

no

#

you don't want u4

#

you want u8

vivid hill
#

thats true

zenith seal
#

and you never want anything less than u32 on x86

# 
        dec     ecx
        mov     rdx, qword ptr [rdi + 8*rcx]
#

this only works with u32/u64 on x86

#

this works because modifying a 32 bit reg on x86 implicitly zero extends it

#

which doesn't happen with 8/16 bit registers

#

fastSizeIntFittingRange

#

watch me contribute to the stdlib again...

vivid hill
#

doit

covert bloom
zenith seal
vivid knot
#

Yeah unofficial guidance would be to use initBuffer with ArrayList instead of BoundedArray, unless you need the copy semantics. Of course, that is orthogonal as to why BoundedArray is so slow in this case

zenith seal
#

Don't worry, I will make BoundedArray faster than ArrayList with initBuffer

#

because it should be...

covert bloom
#

while you're at it can we get an infallible initEmpty function

zenith seal
#

for BoundedArray??

vivid knot
#

you can use default initialization

zenith seal
#

yeah

#

you can just use .{}

covert bloom
#

oh snap i'm silly