4 ms·
Worth noting that as written the "trick" results in memory usage proportional to the size of the input rather than the output. If the filter rejects most of the
by khuey 2mo ago
Worth noting that as written the "trick" results in memory usage proportional to the size of the input rather than the output. If the filter rejects most of the input the difference could be quite noticeable.
- returningfory2 2mo agoI 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.