Excessive array copies on deserialization of arrays

[sirasistant]

Aim

Write efficient deserialization fns

Expected Behavior

Should not copy result when building with this pattern

        let mut result: [T; M] = std::mem::zeroed();
        for i in 0..M {
            result[i] = T::stream_deserialize(reader);
        }
        result

Bug

It copies

To Reproduce

pub struct Reader<let N: u32> {
    data: [Field; N],
    offset: u32,
}

impl<let N: u32> Reader<N> {
    pub fn new(data: [Field; N]) -> Self {
        Self { data, offset: 0 }
    }

    pub fn read(&mut self) -> Field {
        let result = self.data[self.offset];
        self.offset += 1;
        result
    }

    pub fn finish(self) {
        assert_eq(self.offset, self.data.len(), "Reader did not read all data");
    }
}

pub trait Deserialize {
    let N: u32;

    fn deserialize(fields: [Field; Self::N]) -> Self;

    fn stream_deserialize<let K: u32>(reader: &mut Reader<K>) -> Self;
}

impl<T, let M: u32> Deserialize for [T; M]
where
    T: Deserialize,
{
    let N: u32 = <T as Deserialize>::N * M;

    fn deserialize(fields: [Field; Self::N]) -> Self {
        let mut reader = Reader::new(fields);
        let result = Self::stream_deserialize(&mut reader);
        reader.finish();
        result
    }

    fn stream_deserialize<let K: u32>(reader: &mut Reader<K>) -> Self {
        let mut result: [T; M] = std::mem::zeroed();
        for i in 0..M {
            result[i] = T::stream_deserialize(reader);
        }
        result
    }
}

impl Deserialize for bool {
    let N: u32 = 1;

    fn deserialize(fields: [Field; Self::N]) -> Self {
        let mut reader = Reader::new(fields);
        let result = Self::stream_deserialize(&mut reader);
        reader.finish();
        result
    }

    fn stream_deserialize<let K: u32>(reader: &mut Reader<K>) -> bool {
        reader.read() != 0
    }
}

impl Deserialize for u64 {
    let N: u32 = 1;

    fn deserialize(fields: [Field; Self::N]) -> Self {
        let mut reader = Reader::new(fields);
        let result = Self::stream_deserialize(&mut reader);
        reader.finish();
        result
    }

    fn stream_deserialize<let K: u32>(reader: &mut Reader<K>) -> Self {
        reader.read() as u64
    }
}

impl Deserialize for u8 {
    let N: u32 = 1;

    fn deserialize(fields: [Field; Self::N]) -> Self {
        let mut reader = Reader::new(fields);
        let result = Self::stream_deserialize(&mut reader);
        reader.finish();
        result
    }

    fn stream_deserialize<let K: u32>(reader: &mut Reader<K>) -> Self {
        reader.read() as u8
    }
}

pub struct Node {
    pub rows: [[u64; 4]; 16],
    pub row_exist: [bool; 16],
    pub node_type: u8,
}

impl Deserialize for Node {
    let N: u32 = 16 * 4 + 16 + 1;

    fn deserialize(fields: [Field; Self::N]) -> Self {
        let mut reader = Reader::new(fields);
        let result = Self::stream_deserialize(&mut reader);
        reader.finish();
        result
    }

    fn stream_deserialize<let K: u32>(reader: &mut Reader<K>) -> Self {
        let rows = <[[u64; 4]; 16] as Deserialize>::stream_deserialize(reader);
        let row_exist = <[bool; 16] as Deserialize>::stream_deserialize(reader);
        let node_type = <u8 as Deserialize>::stream_deserialize(reader);
        Self { rows, row_exist, node_type }
    }
}

unconstrained fn main(calldata: [Field; 1215]) -> pub [Node; 15] {
    let mut reader = Reader::new(calldata);
    let result = <[Node; 15] as Deserialize>::stream_deserialize(&mut reader);
    reader.finish();
    result
}

profile result

Total arrays copied in main: 270

Workaround

None

Workaround Description

Due to blanket implementation of deserialize of arrays, we can't unroll the loop (which does fix it)

Additional Context

No response

Project Impact

Public dispatch performance on aztec highly impacted

Blocker Context

No response

Nargo Version

No response

NoirJS Version

No response

Proving Backend Tooling & Version

No response

Would you like to submit a PR for this Issue?

None

Support Needs

No response