In previous post we've used Go benchmarks to measure performance difference in total age computation for array of structs and struct of arrays. As expected parallel arrays, being cache and prefetch-friendly, delivered significant performance boost depending on the size of the metadata competing with age field. The only thing, we couldn't check is the impact of vectorization, since Go compiler still hasn't embraced SIMD instructions. So to verify our hypothesis, this time we'll use Rust, since its compiler is using LLVM under the hood. To control the number of users and metadata size following constants are used:

const USER_COUNT: usize = 10000;
const METADATA_SIZE: usize = 32;

The metadata is just an array of bytes with METADATA_SIZE size.

type Metadata = [u8; METADATA_SIZE];

Array of structs is implemented as follows:

#[derive(Clone, Copy)]
struct User {
    metadata: Metadata,
    age: u8,
}

impl User {
    fn with_age(age: u8) -> Self {
        User {
            metadata: [0; METADATA_SIZE],
            age: age,
        }
    }
}

struct Users([User; USER_COUNT]);

and parallel array:

struct ParallelUsers {
    metadata: [Metadata; USER_COUNT],
    ages: [u8; USER_COUNT],
}

For benchmarking we'll still be using code computing total age of users:

impl Users {
    fn total_age(&self) -> u64 {
        self.0.iter().map(|user| user.age as u64).sum()
    }
}

impl ParallelUsers {
    fn total_age(&self) -> u64 {
        self.ages.iter().map(|&age| age as u64).sum()
    }
}

When metadata size is set to 0, both implementations produce efficient vectorized code:

playground::Users::total_age: # @playground::Users::total_age
# %bb.0:
    pxor    %xmm0, %xmm0
    movl    $6, %eax
    pxor    %xmm2, %xmm2
    pxor    %xmm1, %xmm1

.LBB1_1:                                # =>This Inner Loop Header: Depth=1
    movzwl    -6(%rdi,%rax), %ecx
    movd    %ecx, %xmm4
    movzwl    -4(%rdi,%rax), %ecx
    movd    %ecx, %xmm3
    punpcklbw    %xmm0, %xmm4            # xmm4 = xmm4[0],xmm0[0],xmm4[1],xmm0[1],xmm4[2],xmm0[2],xmm4[3],xmm0[3],xmm4[4],xmm0[4],xmm4[5],xmm0[5],xmm4[6],xmm0[6],xmm4[7],xmm0[7]
    punpcklwd    %xmm0, %xmm4            # xmm4 = xmm4[0],xmm0[0],xmm4[1],xmm0[1],xmm4[2],xmm0[2],xmm4[3],xmm0[3]
    punpckldq    %xmm0, %xmm4            # xmm4 = xmm4[0],xmm0[0],xmm4[1],xmm0[1]
    paddq    %xmm2, %xmm4
    punpcklbw    %xmm0, %xmm3            # xmm3 = xmm3[0],xmm0[0],xmm3[1],xmm0[1],xmm3[2],xmm0[2],xmm3[3],xmm0[3],xmm3[4],xmm0[4],xmm3[5],xmm0[5],xmm3[6],xmm0[6],xmm3[7],xmm0[7]
    punpcklwd    %xmm0, %xmm3            # xmm3 = xmm3[0],xmm0[0],xmm3[1],xmm0[1],xmm3[2],xmm0[2],xmm3[3],xmm0[3]
    punpckldq    %xmm0, %xmm3            # xmm3 = xmm3[0],xmm0[0],xmm3[1],xmm0[1]
    paddq    %xmm1, %xmm3
    movzwl    -2(%rdi,%rax), %ecx
    movd    %ecx, %xmm2
    movzwl    (%rdi,%rax), %ecx
    movd    %ecx, %xmm1
    punpcklbw    %xmm0, %xmm2            # xmm2 = xmm2[0],xmm0[0],xmm2[1],xmm0[1],xmm2[2],xmm0[2],xmm2[3],xmm0[3],xmm2[4],xmm0[4],xmm2[5],xmm0[5],xmm2[6],xmm0[6],xmm2[7],xmm0[7]
    punpcklwd    %xmm0, %xmm2            # xmm2 = xmm2[0],xmm0[0],xmm2[1],xmm0[1],xmm2[2],xmm0[2],xmm2[3],xmm0[3]
    punpckldq    %xmm0, %xmm2            # xmm2 = xmm2[0],xmm0[0],xmm2[1],xmm0[1]
    paddq    %xmm4, %xmm2
    punpcklbw    %xmm0, %xmm1            # xmm1 = xmm1[0],xmm0[0],xmm1[1],xmm0[1],xmm1[2],xmm0[2],xmm1[3],xmm0[3],xmm1[4],xmm0[4],xmm1[5],xmm0[5],xmm1[6],xmm0[6],xmm1[7],xmm0[7]
    punpcklwd    %xmm0, %xmm1            # xmm1 = xmm1[0],xmm0[0],xmm1[1],xmm0[1],xmm1[2],xmm0[2],xmm1[3],xmm0[3]
    punpckldq    %xmm0, %xmm1            # xmm1 = xmm1[0],xmm0[0],xmm1[1],xmm0[1]
    paddq    %xmm3, %xmm1
    addq    $8, %rax
    cmpq    $10006, %rax                    # imm = 0x2716
    jne    .LBB1_1
# %bb.2:
    paddq    %xmm2, %xmm1
    pshufd    $238, %xmm1, %xmm0              # xmm0 = xmm1[2,3,2,3]
    paddq    %xmm1, %xmm0
    movq    %xmm0, %rax
    retq
...
playground::ParallelUsers::total_age: # @playground::ParallelUsers::total_age
# %bb.0:
    pxor    %xmm0, %xmm0
    movl    $6, %eax
    pxor    %xmm2, %xmm2
    pxor    %xmm1, %xmm1

.LBB2_1:                                # =>This Inner Loop Header: Depth=1
    movzwl    -6(%rdi,%rax), %ecx
    movd    %ecx, %xmm4
    movzwl    -4(%rdi,%rax), %ecx
    movd    %ecx, %xmm3
    punpcklbw    %xmm0, %xmm4            # xmm4 = xmm4[0],xmm0[0],xmm4[1],xmm0[1],xmm4[2],xmm0[2],xmm4[3],xmm0[3],xmm4[4],xmm0[4],xmm4[5],xmm0[5],xmm4[6],xmm0[6],xmm4[7],xmm0[7]
    punpcklwd    %xmm0, %xmm4            # xmm4 = xmm4[0],xmm0[0],xmm4[1],xmm0[1],xmm4[2],xmm0[2],xmm4[3],xmm0[3]
    punpckldq    %xmm0, %xmm4            # xmm4 = xmm4[0],xmm0[0],xmm4[1],xmm0[1]
    paddq    %xmm2, %xmm4
    punpcklbw    %xmm0, %xmm3            # xmm3 = xmm3[0],xmm0[0],xmm3[1],xmm0[1],xmm3[2],xmm0[2],xmm3[3],xmm0[3],xmm3[4],xmm0[4],xmm3[5],xmm0[5],xmm3[6],xmm0[6],xmm3[7],xmm0[7]
    punpcklwd    %xmm0, %xmm3            # xmm3 = xmm3[0],xmm0[0],xmm3[1],xmm0[1],xmm3[2],xmm0[2],xmm3[3],xmm0[3]
    punpckldq    %xmm0, %xmm3            # xmm3 = xmm3[0],xmm0[0],xmm3[1],xmm0[1]
    paddq    %xmm1, %xmm3
    movzwl    -2(%rdi,%rax), %ecx
    movd    %ecx, %xmm2
    movzwl    (%rdi,%rax), %ecx
    movd    %ecx, %xmm1
    punpcklbw    %xmm0, %xmm2            # xmm2 = xmm2[0],xmm0[0],xmm2[1],xmm0[1],xmm2[2],xmm0[2],xmm2[3],xmm0[3],xmm2[4],xmm0[4],xmm2[5],xmm0[5],xmm2[6],xmm0[6],xmm2[7],xmm0[7]
    punpcklwd    %xmm0, %xmm2            # xmm2 = xmm2[0],xmm0[0],xmm2[1],xmm0[1],xmm2[2],xmm0[2],xmm2[3],xmm0[3]
    punpckldq    %xmm0, %xmm2            # xmm2 = xmm2[0],xmm0[0],xmm2[1],xmm0[1]
    paddq    %xmm4, %xmm2
    punpcklbw    %xmm0, %xmm1            # xmm1 = xmm1[0],xmm0[0],xmm1[1],xmm0[1],xmm1[2],xmm0[2],xmm1[3],xmm0[3],xmm1[4],xmm0[4],xmm1[5],xmm0[5],xmm1[6],xmm0[6],xmm1[7],xmm0[7]
    punpcklwd    %xmm0, %xmm1            # xmm1 = xmm1[0],xmm0[0],xmm1[1],xmm0[1],xmm1[2],xmm0[2],xmm1[3],xmm0[3]
    punpckldq    %xmm0, %xmm1            # xmm1 = xmm1[0],xmm0[0],xmm1[1],xmm0[1]
    paddq    %xmm3, %xmm1
    addq    $8, %rax
    cmpq    $10006, %rax                    # imm = 0x2716
    jne    .LBB2_1
# %bb.2:
    paddq    %xmm2, %xmm1
    pshufd    $238, %xmm1, %xmm0              # xmm0 = xmm1[2,3,2,3]
    paddq    %xmm1, %xmm0
    movq    %xmm0, %rax
    retq

Now it's time to use benchmarks to see how they perform:

#[cfg(test)]
mod tests {
    use super::*;
    use rand::Rng;
    use test::Bencher;

    #[bench]
    fn bench_total_user_age(b: &mut Bencher) {
        let mut user_arr = [User::with_age(3); USER_COUNT];
        for idx in 0..USER_COUNT {
            user_arr[idx] = User::with_age(rand::random());
        }
        let users = Users(user_arr);
        b.iter(|| users.total_age());
    }

    #[bench]
    fn bench_total_parallel_user_age(b: &mut Bencher) {
        let mut ages = [0; USER_COUNT];
        rand::thread_rng().fill(&mut ages[..]);
        let users = ParallelUsers {
            metadata: [[0; METADATA_SIZE]; USER_COUNT],
            ages: ages,
        };
        b.iter(|| users.total_age());
    }
}

As expected, with no metadata, performance results are very close:

test tests::bench_total_parallel_user_age ... bench:       2,805 ns/iter (+/- 277)
test tests::bench_total_user_age          ... bench:       2,491 ns/iter (+/- 435)

As soon as we increase metadata size (4 for example), vectorization is no longer possible for array of structs:

playground::Users::total_age: # @playground::Users::total_age
# %bb.0:
    movl    $49, %ecx
    xorl    %eax, %eax

.LBB1_1:                                # =>This Inner Loop Header: Depth=1
    movzbl    -45(%rdi,%rcx), %edx
    addq    %rax, %rdx
    movzbl    -40(%rdi,%rcx), %eax
    addq    %rdx, %rax
    movzbl    -35(%rdi,%rcx), %edx
    addq    %rax, %rdx
    movzbl    -30(%rdi,%rcx), %eax
    addq    %rdx, %rax
    movzbl    -25(%rdi,%rcx), %edx
    addq    %rax, %rdx
    movzbl    -20(%rdi,%rcx), %eax
    addq    %rdx, %rax
    movzbl    -15(%rdi,%rcx), %edx
    addq    %rax, %rdx
    movzbl    -10(%rdi,%rcx), %eax
    addq    %rdx, %rax
    movzbl    -5(%rdi,%rcx), %edx
    addq    %rax, %rdx
    movzbl    (%rdi,%rcx), %eax
    addq    %rdx, %rax
    addq    $50, %rcx
    cmpq    $50049, %rcx                    # imm = 0xC381
    jne    .LBB1_1
# %bb.2:
    retq

but performance results are still fairly close:

test tests::bench_total_parallel_user_age ... bench:       2,505 ns/iter (+/- 577)
test tests::bench_total_user_age          ... bench:       2,563 ns/iter (+/- 467)

As soon as cache waste reaches 32 (half of the cache line), performance drops by ~2X:

test tests::bench_total_parallel_user_age ... bench:       2,752 ns/iter (+/- 509)
test tests::bench_total_user_age          ... bench:       4,693 ns/iter (+/- 739)

and by ~5X, similar to Go results, once metadata size reaches 64:

test tests::bench_total_parallel_user_age ... bench:       2,720 ns/iter (+/- 532)
test tests::bench_total_user_age          ... bench:      10,257 ns/iter (+/- 2,194)

So what are the conclusions?

• even though parallel array structure enabled vectorization, it hasn't had a significant performance impact
• memory bandwidth and cache efficiency played critical role on performance