4 ms·
I disagree in the sense that you can rewrite the code to use the trick and also not allocate in advance. Nothing about the trick requires you to allocate up fro
by returningfory2 2mo ago
I disagree in the sense that you can rewrite the code to use the trick and also not allocate in advance. Nothing about the trick requires you to allocate up front: before writing to out[n] you can extend the vector if it’s out of bounds. Or, after incrementing n, do out.push(0).
- khuey 2mo agoYou should try writing it out. Doing it without introducing another unpredictable branch is harder than it looks. I discussed this with a coworker earlier this week and the best they were able to come up with was for &x in input { out.push(x); n += (x > threshold) as usize; out.truncate(n); } which works but is ugly af imo.
- returningfory2 2mo agoYep realized this after that my second solution (push a 0 if n is incremented) has the same branch prediction problem. I think yours works. Alternatively in the loop: if out.len() < n { out.push(0); } out[n] = x; n += (x > threshold) as usize; In this case the if will be predicted well because it only triggers log(N) times, given how the std lib extends vectors.