`WeakVec` should consider using `Vec::swap_remove` instead of a freelist

gfx-rs / wgpu

A cross-platform, safe, pure-Rust graphics API.

https://wgpu.rs

Apache License 2.0

12.75k stars 935 forks source link

`WeakVec` should consider using `Vec::swap_remove` instead of a freelist #6580

Open jimblandy opened 4 days ago

jimblandy commented 4 days ago

wgpu_core::weak_vec::WeakVec maintains a freelist, but it's not important that elements stay at their original indices, so it should be possible to use std::vec::Vec::swap_remove to remove broken weak references, thus keeping all live references contiguous at the start of the vector, making the freelist unnecessary.

teoxoy commented 3 days ago

I was thinking it might be better to keep them in insertion order since I would imagine older items to be more likely to be dropped first (leading to less branch mispredictions in the loop) but I don't know how much better that is compared to not using the free list and not having as many branches in the first place.

I opened https://github.com/gfx-rs/wgpu/pull/6587.

teoxoy commented 3 days ago

Actually, the current implementation doesn't have that property either once the free list starts to be used, I think we can just go with https://github.com/gfx-rs/wgpu/pull/6587.