"The optimizer may further assume that allocation is infallible"

language design
5

Can the optimizer replace an allocation with a realloc? Or otherwise reduce the size of memory being allocated

Dumb example to show what I mean:

pub fn dumb<T: Copy>(s1: Vec<T>, s2: &[T]) -> Option<Vec<T>> {
    assert!(s1.len() == 128);
    assert!(s2.len() == 128);
    
    let mut v = Vec::new();
    v.try_reserve(256).ok()?;
    
    v.extend(s1);
    v.extend(s2);
    
    Some(v)
}

It's clear that the programmer's intent is that there is a single allocation for v, of 256 items in size. But it wouldn't be unreasonable for the optimizer to exploit the fact that we own s1 and it's going to be deallocated at the end of this function to convert the allocation of 256 items into reallocating s1 from 128 to 256 items in size, potentially reducing the memory demand.

This also (if allowed) leads to a possible case where the optimizer might make an allocation larger, via merging of allocations:

pub fn calls_dumb<T: Copy>(s2: &[T]) -> Option<Vec<T>> {
    assert!(s2.len() == 128);
    
    let mut v = Vec::new();
    v.try_reserve(128).ok()?;
    
    v.resize(128, s2[0]);

    dumb(v, s2)
}

Here, calls_dumb allocates 128 items worth of space, and then fills them in; it then calls dumb, which allocates 256 items worth of space. The optimizer could, in theory, inline dumb into calls_dumb, then note that the following code has exactly the same observable behaviour and optimize calls_dumb into optimized:

pub fn optimized<T: Copy>(s2: &[T]) -> Option<Vec<T>> {
    assert!(s2.len() == 128);
    
    let mut v = Vec::new();
    v.try_reserve(256).ok()?;
    
    v.resize(128, s2[0]);

    v.extend(s2);

    Some(v)
}

I could well be missing something, mind, but I would have thought that this is legitimate behaviour for the optimizer, even though the allocator can no longer observe my allocation for 128 items.

2 Likes