Vec<T> Compact implementation causes storage bloat for fixed-size types

[AshinGau]

Problem Description

The current Vec<T> implementation of the Compact trait in crates/storage/codecs/src/lib.rs has a significant storage inefficiency for fixed-size types:

Storage Bloat: The default Vec<T>::to_compact implementation stores a length prefix for each element, which doubles the storage requirement for fixed-size types like u8. This is particularly problematic when Vec<u8> is used in database tables.

Current Implementation Analysis

impl<T> Compact for Vec<T>
where
    T: Compact,
{
    fn to_compact<B>(&self, buf: &mut B) -> usize
    where
        B: bytes::BufMut + AsMut<[u8]>,
    {
        self.as_slice().to_compact(buf)
    }
}

The &[T]::to_compact implementation:

impl<T> Compact for &[T]
where
    T: Compact,
{
    fn to_compact<B>(&self, buf: &mut B) -> usize
    where
        B: bytes::BufMut + AsMut<[u8]>,
    {
        encode_varuint(self.len(), buf);

        let mut tmp: Vec<u8> = Vec::with_capacity(64);

        for element in *self {
            tmp.clear();

            // We don't know the length until we compact it
            let length = element.to_compact(&mut tmp);
            encode_varuint(length, buf);  // ← Stores length for each element!

            buf.put_slice(&tmp);
        }
        0
    }
}

Impact Example

For Vec<u8> with 1000 elements:

• Actual data: 1000 bytes
• Current storage: ~2000 bytes (1000 bytes data + ~1000 bytes length prefixes)
• Storage overhead: ~100% increase

Real-World Impact

The StageCheckpointProgresses table uses Vec<u8> as its value type:

table StageCheckpointProgresses {
    type Key = StageId;
    type Value = Vec<u8>;  // ← Affected by this issue
}

While this table is relatively small, the pattern could be repeated in other tables, leading to significant storage waste.

Root Cause

The issue stems from the generic Vec<T> implementation assuming all types T have variable sizes. For fixed-size types like u8, u32, B256, etc., storing individual length prefixes is unnecessary and wasteful.

Proposed Solution

Option 1: Type-Specific Specializations

Add specialized implementations for common fixed-size types:

// Specialized implementation for Vec<u8>
impl Compact for Vec<u8> {
    fn to_compact<B>(&self, buf: &mut B) -> usize
    where
        B: bytes::BufMut + AsMut<[u8]>,
    {
        encode_varuint(self.len(), buf);
        buf.put_slice(self);
        0
    }

    fn from_compact(buf: &[u8], _: usize) -> (Self, &[u8]) {
        let (length, mut buf) = decode_varuint(buf);
        let data = buf[..length].to_vec();
        buf.advance(length);
        (data, buf)
    }
}

// Similar specializations for other fixed-size types
impl Compact for Vec<u32> {
    fn to_compact<B>(&self, buf: &mut B) -> usize
    where
        B: bytes::BufMut + AsMut<[u8]>,
    {
        encode_varuint(self.len(), buf);
        for &element in self {
            element.to_compact(buf);
        }
        0
    }

    fn from_compact(buf: &[u8], _: usize) -> (Self, &[u8]) {
        let (length, mut buf) = decode_varuint(buf);
        let mut list = Self::with_capacity(length);
        for _ in 0..length {
            let (element, new_buf) = u32::from_compact(buf, 4);
            buf = new_buf;
            list.push(element);
        }
        (list, buf)
    }
}

Option 2: Trait-Based Approach

Create a trait to identify fixed-size types:

pub trait FixedSize {
    const SIZE: usize;
}

impl FixedSize for u8 {
    const SIZE: usize = 1;
}

impl FixedSize for u32 {
    const SIZE: usize = 4;
}

impl FixedSize for B256 {
    const SIZE: usize = 32;
}

// Then modify Vec<T> implementation
impl<T> Compact for Vec<T>
where
    T: Compact + FixedSize,
{
    fn to_compact<B>(&self, buf: &mut B) -> usize
    where
        B: bytes::BufMut + AsMut<[u8]>,
    {
        encode_varuint(self.len(), buf);
        for element in self {
            element.to_compact(buf);
        }
        0
    }

    fn from_compact(buf: &[u8], _: usize) -> (Self, &[u8]) {
        let (length, mut buf) = decode_varuint(buf);
        let mut list = Self::with_capacity(length);
        for _ in 0..length {
            let (element, new_buf) = T::from_compact(buf, T::SIZE);
            buf = new_buf;
            list.push(element);
        }
        (list, buf)
    }
}

Implementation Plan

1. Phase 1: Implement specializations for Vec<u8>, Vec<u32>
2. Phase 2: Add specializations for other common fixed-size types
3. Phase 3: Consider a more systematic approach if many more specializations are needed

Impact

• Storage Savings: 50% reduction for Vec<u8>, significant savings for other fixed-size types
• Performance: Faster serialization/deserialization due to fewer length calculations
• Memory: Reduced memory usage during serialization

[Rjected]

I think this doesn't really matter w.r.t the checkpoint progress table because it doesn't have much data, so I don't think this is super critical to fix. This is also better for uints that are not u8, because we use varint encoding / decoding. These types are not fixed size on disk, so we actually save space from using this encoding, it's only u8 that double-encodes. B256 also has a specialized implementation:

reth/crates/storage/codecs/src/lib.rs

Lines 464 to 478 in f6ffeac

	impl<const N: usize> Compact for FixedBytes<N> {
	#[inline]
	fn to_compact<B>(&self, buf: &mut B) -> usize
	where
	B: bytes::BufMut + AsMut<[u8]>,
	{
	self.0.to_compact(buf)
	}
	#[inline]
	fn from_compact(buf: &[u8], len: usize) -> (Self, &[u8]) {
	let (v, buf) = <[u8; N]>::from_compact(buf, len);
	(Self::from(v), buf)
	}
	}

which calls to:

reth/crates/storage/codecs/src/lib.rs

Lines 417 to 437 in f6ffeac

	impl<const N: usize> Compact for [u8; N] {
	#[inline]
	fn to_compact<B>(&self, buf: &mut B) -> usize
	where
	B: bytes::BufMut + AsMut<[u8]>,
	{
	buf.put_slice(&self[..]);
	N
	}
	#[inline]
	fn from_compact(mut buf: &[u8], len: usize) -> (Self, &[u8]) {
	if len == 0 {
	return ([0; N], buf)
	}
	let v = buf[..N].try_into().unwrap();
	buf.advance(N);
	(v, buf)
	}
	}