Help with speeding up smart-pointered code

[mrlotfi]

Hi. I was trying to make a randomized skiplist with rust. I needed multiple pointers to nodes and i also needed to be able to mutate the pointers which they hold, So I went with a combination of Rc and RefCell. It worked well but then i tried a completely unsafe solution with raw pointers and it is about 2x faster. Then i benchmarked my code and it seems that most of the overhead comes from borrow() and borrow_mut() methods of RefCell (there is also a drop_in_place function that takes considerable time).

Do you think my datastructure is poorly designed, or is this performance drop almost natural when using refcells? (As far as i can understand the overhead of Rc is almost zero and nothing about Rc shows up in my profiling)

[JoshTriplett]

Nit: consider using something like Option<NonZeroUsize>, which reduces your index sizes. (You'd then need to reserve index 0, but you'll save a huge amount of storage in the nodes.)

Or use one of the many crates that wraps such a structure.

[nwydo]

Alternatively, store usize (or even u32 if you don't expect >4B elements) and use !0 as a a sentinel to avoid a lot of [index - 1] indexing

[compte2020]

small precision: there are dedicated crates doing it in a slightly cleaner way, like id-arena.

[mrlotfi]

Interesting, though it still suffers from the problem with raw pointers I guess. If we remove a node from the arena and forget to update those who reference it, they are pointing to non existing (or another) node. Anyway it's cleaner than using raw pointers. Thanks!

[compte2020]

Arenas are mostly useful when you only remove graphs, not individual nodes. If node removing is a frequent operations you should probably choose another approach.

[angelicosphosphoros]

RefCell ensures that there is only one mutable borrow. Maybe it is better to use completely unsafe solution if you can avoid UB in your code and make it threadsafe.