How to pack multiple arrays into an Arc

help
1

I currently have (Arc<[Instruction]>, Arc<[Metadata]>), but this isn't very satisfying because they live equally long, so the second Arc shouldn't be needed. I could put two boxes inside an Arc but I'd prefer no extra indirection.

I came up with this, which is almost what I want.

struct ProgramImpl<const N: usize> {
    instructions: [u16; N],
    code_page: [u8; N],
}
trait Program {
    fn instructions(&self) -> &[u16];
    fn code_page(&self) -> &[u8];
}
impl<const N: usize> Program for ProgramImpl<N> {
    fn instructions(&self) -> &[u16] {
        &self.instructions
    }
    fn code_page(&self) -> &[u8] {
        &self.code_page
    }
}

The issue with it is that it generates a separate vtable for every program length. What I actually want is a fat pointer with N instead of the vtable pointer.

2

Could you restructure this to have Arc<[(Instruction, Metadata)]> instead?

3

No. It is very important that the Instruction array is tightly packed, as it is mostly accessed via a raw pointer that is incremented to get the next instruction. That would work with your proposal but the cache layout would be much worse.

1 Like
4

Thank you for the fun challenge :slight_smile:

#![feature(new_uninit)]

use std::{
    sync::Arc,
    mem::MaybeUninit,
    ptr::slice_from_raw_parts,
};

#[derive(Clone)]
pub struct Program {
    data: Arc<[MaybeUninit<u16>]>,
    n: usize,
}

impl Program {
    pub fn new<I1, I2>(n: usize, instructions_src: I1, code_page_src: I2) -> Self
    where
        I1: IntoIterator<Item=u16>,
        I2: IntoIterator<Item=u8>,
    {
        let mut instructions_src = instructions_src.into_iter();
        let mut code_page_src = code_page_src.into_iter();
    
        unsafe {
            // allocating as u16 may waste a single byte of allocation if the code
            // page is an uneven size, but is the only way I can figure out to force
            // Arc to align the allocation to 2 bytes
            let num_shorts = n + if n % 2 == 0 { n / 2 } else { n / 2 + 1 };
            let mut data = Arc::<[u16]>::new_uninit_slice(num_shorts);
            let instructions_ptr = Arc::get_mut(&mut data).unwrap()
                as *mut [MaybeUninit<u16>]
                as *mut u16;
            for i in 0..n {
                let instruction = instructions_src.next().unwrap();
                instructions_ptr.add(i).write(instruction);
            }
            let code_page_ptr = instructions_ptr.add(n) as *mut u8;
            for i in 0..n {
                let code_page_byte = code_page_src.next().unwrap();
                code_page_ptr.add(i).write(code_page_byte);
            }
    
            Program { data, n }
        }
    }
    
    pub fn instructions(&self) -> &[u16] {
        unsafe {
            &*slice_from_raw_parts(self.data.as_ptr() as *const u16, self.n)
        }
    }
    
    pub fn code_page(&self) -> &[u8] {
        unsafe {
            &*slice_from_raw_parts(
                (self.data.as_ptr() as *const u16).add(self.n) as *const u8,
                self.n,
            )
        }
    }
}

fn main() {
    let program = Program::new(
        5,
        [3001, 3002, 3003, 3004, 3005],
        [6, 7, 8, 9, 10],
    );
    dbg!(program.instructions());
    dbg!(program.code_page());
}
5

Nice! The fat pointer representation looks perfect.

I'll try to make it support other alignments and sizes.

1 Like
6

I'd be easier in some ways if you could create your own version of Arc, because the methods I want to use on it to do this most naturally aren't actually public

7

You can get rid of the unsafe with bytemuck.

8

Very nice. However, that will make two heap allocations within the constructor, the first as just an temporary copying location and the second as the actual Arc, and then drop the temporary copying location, whereas mine only allocates the Arc and copies directly to it. On the other hand, yours compiles on stable, whereas I'm relying on nightly feature-gated API surface of Arc. Things to keep in mind.

9

Since its not super bad if accessing metadata is slow, this kind of structure is also possible:

struct Program {
    metadata: Box<[u16]>,
    instructions: [u8],
}
3 Likes
10

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.