I would like write a function which iterates over the elements of a Vec, processes each element with some function, and sometimes pushes a new element to the back of the Vec depending on the outcome of this processing. Something along the lines of this:
// Process a single element from the queue and determine if a new element needs
// to be enqueued
fn process_element(input: u8) -> bool { todo!() }
// Process a sequence of elements until it is exhausted, adding a new element to
// the back of the sequence on each iteration if so dictated by the processing
// algorithm
fn process_list(mut v: Vec<u8>) {
for &elem in &v {
if process_element(elem) { v.push(42) }
}
}
Importantly, process_list should iterate over all elements of v, including the new ones that were pushed to the back during processing of earlier elements.
This does not compile though:
error[E0502]: cannot borrow `v` as mutable because it is also borrowed as immutable
--> src/lib.rs:12:36
|
11 | for &elem in &v {
| --
| |
| immutable borrow occurs here
| immutable borrow later used here
12 | if process_element(elem) { v.push(42) }
| ^^^^^^^^^^ mutable borrow occurs here
For more information about this error, try `rustc --explain E0502`.
It seems that in order to create the iterator which powers thisfor loop, v must be either moved or borrowed, both of which disallow the mutable borrow needed by Vec::push within the loop.
I believe the implementation problem can be solved by switching to a while loop like this:
fn process_list(mut v: Vec<u8>) {
let mut i = 0;
while let Some(&elem) = v.get(i) {
if process_element(elem) { v.push(42) }
i += 1;
}
}
But this requires manual management of an iteration index (i) and just doesn't feel as clean or idiomatic as using iterators. Is there a way to implement this behavior using iterators?
Mutating collections while iterating them is the anti-pattern ("iterator invalidation"). The Vec::iter iterator assumes the collection isn't mutated -- for one example, if you pushed somehow and that caused a reallocation, the previous references from the iterator would be invalid, as would any new ones.[1] Or even if you just obtained a &mut i32 that aliased a &i32 from the iterator you're holding on to, that's UB.
Any Iterator returning &i32 allows holding on to all the &i32 for longer than the iterator is around, which rules out the possibility of mutating the Vec while the iterator is still valid, so not really.
I havent seemed to find a way - intermediates seemed like the best option but alas.
I believe the best way is to recurse and propagate or even simpler, use a while loop and track if len is still greater than i
#![allow(unused_variables)]
// Process a single element from the queue and determine if a new element needs
// to be enqueued
fn process_element(input: u8) -> bool { input % 2 == 0 }
// Process a sequence of elements until it is exhausted, adding a new element to
// the back of the sequence on each iteration if so dictated by the processing
// algorithm
fn process_list(mut v: Vec<u8>) {
let mut i = 0;
while i < v.len() {
if process_element(v[i]) { v.push(23);
}
i += 1
}
println!("{:#?}", v);
}
fn main() {
let mut vli: Vec<u8> = Vec::new();
for i in 0..=255u8 {
vli.push(i)
}
process_list(vli);
}
that's completely fine for this use case, which is already an atypical access pattern for a Vec.
btw, mutate the collection while iterating it has the risk of being not covergent, which may or may not be desired, depending on the use case.
in typical simulation systems, newly spawned entitiies are usually buffered and tick-delayed so the simulation is guaranteed to advance its time steps.
I think this is a bit misleading. “Anti-pattern” implies that there is code that would compile and run, but is a bad idea to write.
You can't mutate a collection while using an Iterator over it — that’s not an anti-pattern, it is just impossible.
Iterating using indices instead of an Iterator, while mutating, is a perfectly fine thing for an algorithm to do, as long as it handles the implications of the mutation (which might include incrementing or decrementing the current index, for example).
I would perhaps qualify it as "writing code that incidentally mutates a collection while iterating it" is an anti pattern: eg, it's a risky enough thing to do that it should be using a dedicated algorithm that is known to correctly handle it, as you say.
if your vec is a queue of tasks to consume then something like this is perfectly valid
let queue=VecDeque::new();
.........
while let OK(next)=queue.pop_front(){
//do stuff
if some_condition{
queue.push_back(some_element);
}
}
alternatively
while to_process.len()>0{
to_process=to_process.flat_map(|task|/*some processing*/).collect()
}
in both cases you have to be absolutely sure the vec empties in a reasonable time.
if you want to keep a full vec of the elements you have iterated over you can just have it be a separated one from the work queue and push items in there once they have been processed
use std::collections::VecDeque;
fn process_list(v: Vec<u8>) {
let mut queue = VecDeque::from(v);
while let Some(elem) = queue.pop_front() {
if process_element(elem) {
queue.push_back(42)
}
}
}
Just for additional information, I just played around with 8 different approachs :v
The branching is compiled to normal loop, the branchless is compiled to SIMD loop (branching inside loop and using value from previous index will prevent auto SIMD)
The result :
STEP 1: VALIDATING OUTPUT EQUIVALENCE
Group 1 (Conditional Append 1-6) Outputs are 100% Identical
Group 2 (Fixed Step 7-8) Outputs are 100% Identical
All integrity checks passed successfully
STEP 2: RUNNING BENCHMARKS
process_list : 96.154256ms
process_list2 : 154.157304ms
process_list3 : 101.570096ms
process_list4 : 105.920611ms
process_list5 : 100.383588ms
process_list6 : 93.82583ms
process_list7 : 11.824045ms
process_list8 : 11.488457ms
Final System Checksum: 2595363200
Branching that is compiled to Jump if code that skip multiple code is high percentage will be compiled to Jump instruction because it skips multiple code, it prevents auto SIMD. Where simple if will be compiled to CMOV instruction, it is branchless thus auto SIMD friendly, eg : let a = if cond { 10 } else { 20 }. Rust playground, Godbolt compiler explorer, Cargo-ASM are good tools to see the assembly
Unknown start and end
Auto SIMD needs the start and end of the loop known at compile time if not using iterator. If it can not be known at compile time, auto SIMD can still be achieved by writing 2 loops = chunked loop + fallback normal loop. Eg :
loop chunk 64 {
}
loop normal 1 by 1 {
}
Or simple
// but this style is fixed to 128bit, the compiler will not auto upgrade to higher than 128bit eventhough the machine supports it
loop counter < len {
loop 0..8 {
}
}
loop 1 by 1 {
}
So if the elements > 64, it will use auto SIMD, if not it will use normal
A guarantee that the access will not out of bound
Iterator gives guarantee it will never out of bound, so it is SIMD friendly (if the other requirements are also met). Where pointer does not know length, a loop containing raw pointer access never be compiled to auto SIMD. The solution is, creating slice from the pointer then using iterator + reference to loop and edit the slice (std::slice_from_raw_parts, std::slice_from_raw_parts_mut), slice knows length so it is auto SIMD friendly
Additional information :
If the end of the loop is already between bound, and accessing the element with the i, it is safe to use get_unchecked when iterator can not be used, because the compiler sometimes can not remove the bound check as happened in my code before when I saw the assembly, eg :
// vec already has 10 items
for i in 0..10 {
unsafe { vec.get_unchecked(i) }
}
But the performance of auto SIMD assembly is below the assembly produced by manual SIMD intrinsics using std::arch. Because with manual SIMD instrinsics, many unnecessary operations can be removed, branchless programming can be maximized, and can hand pick the best SIMD instruction determisticly
In term of assembly quality, manual SIMD instrinsics (std::arch) > the nightly portable SIMD >=< auto SIMD (sometime portable SIMD result is better than auto SIMD, sometime auto SIMD is better than portable SIMD)
I just share additional knowledge that I know (I wrote it in the top first comment). Because he may want to write it differently after knowing more info as he was looking for better way
The problem isn't the performance considerations; after all, the question is about "a better way", and it's good to have that insight when you learn patterns.
But I'm not comfortable with the unsafe code that corresponds to the fastest results or the conclusion it might suggest. In particular, I'm not convinced at all it wouldn't lead to undefined behaviour, and I don't find that very didactic. EDIT: And it doesn't look like the actual behaviour answers the initial problem.
Yeah, after reading the post I tried to use it as learning material, then I found that ones
The unsafe code is safe if you read it line by line and understand what it does. The reason for why the latest 2 unsafe code is fast because it makes the compiler can optimize more, the result it is compiled to wider SIMD, where only the safe code number 1 that is compiled to SIMD but process less items per SIMD compared to the unsafe one. It is when no target native is passed (as the playground doesn't support passing rust flags). When there is no target native, the compiler only result at maximum SSE2, eventhough the CPU support AVX2 and AVX512 (it needs hint, eg making the 1 iteration loop process the same size of AVX2, it will result AVX2, but this has downside it will not upgrade to higher bandwidth (eg from 256bit to 512bit automatically if the CPU supports it, it can only upgrade to the same SIMD register used in AVX512 but in size of 256)
If the flag target CPU native is passed, all the auto SIMD will use the best SIMD that the CPU support. The safe version of number 1 become fast around 50 ms, but if the requirement is the element that will be pushed to the vector is always potentially different, it can not be used because it assumes all the value that will be pushed to the vector is same value. If it is changed back to push inside the loop that require if that the if will be compiled to Jump instruction, it is not compiled to SIMD that makes it slower. The same algorithm used in the unsafe code can be written in safe code, minus there are unnecerery operations eg memset for zeroing the vector, and some bound check. The gap is about 10 ms, so it is also much faster than the branching version but slower than the unsafe one
fn process_list9(mut v: Vec<u8>) -> Vec<u8> {
let initial_len = v.len();
// this is memset
v.resize(initial_len * 2, 0);
// this has bound check that is not removed
let (read_part, write_part) = v.split_at_mut(initial_len);
for (&elem, write_dst) in read_part.iter().zip(write_part.iter_mut()) {
// a simple if is compiled to CMOV branchless
*write_dst = if process_element(elem) { 42 } else { 0 };
}
v
}
That one has same SIMD bandwith with version 7 and 8 because exact same algorithm, minus the memset and bound check
Now that you mention it, it may be safe, but does that code do what the OP was trying to achieve? It looks like it pushes a value no matter what, then stops after processing the initial values, instead of adding a number of values depending on the previous values and the new inserted values.
Now I want to share my understanding of the unsafe code why it is safe. I hope it can add more info. Correct me if my understanding is false :<
fn process_list7(mut v: Vec<u8>) -> Vec<u8> {
// the vector already has capacity len
let initial_len = v.len();
// reserve add capacity, initial_len + initial_len = 2 * initial_len, no zeroing memory happen
v.reserve(initial_len);
// taking the pointer
let ptr = v.as_mut_ptr();
// creating slice (a pointer + length that can be incremented safely via iterator + reference) to index 0 until initial_len, that will be used to read the input
let read_slice = unsafe { std::slice::from_raw_parts(ptr, initial_len) };
// creating mutable slice to index initial_len until 2 * initial_len, to be used to store the results
let write_slice = unsafe { std::slice::from_raw_parts_mut(ptr.add(initial_len), initial_len) };
// they point to different index
// the unsafe part is paused at here, entering the full safe in the loop
// combining 2 iterators, and iterating them at the same time
for (&elem, write_dst) in read_slice.iter().zip(write_slice.iter_mut()) {
// instead of calling conditional push, eg
// if process_element(elem) { vec.push(42) };
// or
// if process_element(elem) { *write_dst = 42 };
// it is changed to writing whether process_element return true or false, if false then writing 0. This makes the resulted assembly becomes branchless, no Jump, thus auto SIMD friendly
*write_dst = if process_element(elem) { 42 } else { 0 };
}
// exiting the full safe loop, entering the final unsafe code
// reserve handles the physical memory allocation, it does not update the len of the vector
// writing to slice does not update the len of the original data structure that the slice is pointing to. Slice is like a view data structure, it will be freed after it is done. The physical memory of the original data structure (the vector) is already updated by the slice, but the len is not yet
// so summing that up, the slice just wrote additional data (the results) that the total len is = initial_len, so the total len of the written data is 2 * initial len, so the len is updated to 2 * initial_data to make the vector can read the stored results
unsafe {
v.set_len(initial_len * 2);
}
v
}
//#[unsafe(no_mangle)]
fn process_list8(mut v: Vec<u8>) -> Vec<u8> {
let initial_len = v.len();
v.reserve(initial_len);
let ptr = v.as_mut_ptr();
let slice = unsafe { std::slice::from_raw_parts_mut(ptr, initial_len * 2) };
// the code number 8 is agorithmatically same with the number 7, it is also compiled to same assembly. The only difference is, number 7 creates 2 slices directly, number 8 creates 1 slice then splitting it into 2 slices. The final result is same
let (read_slice, write_slice) = slice.split_at_mut(initial_len);
for (&elem, write_dst) in read_slice.iter().zip(write_slice.iter_mut()) {
*write_dst = if process_element(elem) { 42 } else { 0 };
}
unsafe {
v.set_len(initial_len * 2);
}
v
}
I just share additional knowledge to the poster and all other users. Because I saw all other users use branching inside the loop, that makes me want to write this
Yes, that is the branchless technique. Instead of jumping if it is false, it writes anyway (writing value 0). Then to read it, if the value is 0 it means it is not valid, it is like masking technique
.