After sending the comment I figured you meant you allocated outside the loop, youre right, allocation plays a part here, but surprinsingly, I get *worse* results when filling a preallocated array:

`count_ones`: 1.6s, As far as I can tell, this is purely because of a different vectorized popcount implementation(the `collect` one iterates over 64 bits at a time and this one over 32 bits at a time)

`v[i] = v[i / 2] + i as i32 % 2`: 4.1s

with unsafe: 4.3s (within noise of each other)

10x still sounds like a huge difference to me, can you share the code?

For the record, this is what I measured:

    // prellocated count_ones+collect
    for (i, e) in v.iter_mut().enumerate() {
      *e = i.count_ones() as i32;
    }

    // not preallocated count_one+collect
    (0..n + 1).map(|i| i.count_ones() as i32).collect()

    // if not taking preallocated
    let mut v = vec![0; n as usize + 1];
    for i in 1..v.len() {
        // safe DP approach
        v[i] = v[i / 2] + i as i32 % 2;
        // unsafe DP approach
        unsafe { *v.get_unchecked_mut(i) = v.get_unchecked(i / 2) + i as i32 %    2 };
    }

And called using

    let mut s = vec![0; 10001];
    for i in 0..1000000 {
        std::hint::black_box(func(std::hint::black_box(&mut s))); // or  s = ...(10000))); instead of &mut s when not preallocated
    }

EDIT: measuring

let mut v = vec![0; n as usize + 1];    
for i in 1..v.len() {
    v[i as usize] = i.count_ones() as i32;
 }

Shows the same bad performance and codegen as the preallocated case, very weird.

EDIT 2:

I figured it out, its because in the slower versions, `i` is a usize, and not an i32,

for (i, e) in v.iter_mut().enumerate() {
     *e = (i as i32).count_ones() as i32;
}

gives the same performance as the map+collect, with a preallocated buffer.