Implement range_mut for BptreeMap

[Ekleog]

Hey!

I'm trying to port code from BTreeMap to BptreeMap, and am hitting a wall. Do you know why there seems to not be any BptreeMapWriteTxn::range_mut function available?

Anyway, I'm currently just looking into concread, but it looks quite awesome, I'm just a bit sad not to be able to have code as clean and efficient as with my BTreeMap :)

(BTW, I'm kind of curious, do you have any benchmarks of concread vs. rwlock performance for a few scenarios?)

[Firstyear]

I'm trying to port code from BTreeMap to BptreeMap, and am hitting a wall. Do you know why there seems to not be any BptreeMapWriteTxn::range_mut function available?

Because I haven't written it :)

It's quite hard to actually do range_mut. Because the structure is "copy on write" this adds a whole lot of extra "challenges" to making sure these changes are safe.

In the iterator the current way we traverse this is with depth-first. When you "change" a node, you have to update everything a long the branch which would require invalidation of the iterator's current location because the node you are looking at may now have been cloned and it's content changed.

So you have to either pre-touch and clone every node in the tree along the range and then provide the iterator OR you have to have a process when as the iterator proceeds it invalidates and clones as it goes. This would require multiple traversals (or new logic paths in the code).

Remember also, when you clone a leaf, you also have to clone it's parent too because the pointers need updating. That's part of the problem here is when we "touch" a node, we need to unwind our iterators current stack because the higher nodes may have been changed too now!

Another consideration is if the iterator is dropped early. Imagine you did iter_mut and we cloned "every node in the tree" but the caller only updates a small number of nodes. That's a huge waste of memory and time! So we need to be smarter about how we actually do the mutable interactions as the iterator progresses.

In summary, it's possible I just would need to actually implement it and it's not trivial.

Anyway, I'm currently just looking into concread, but it looks quite awesome, I'm just a bit sad not to be able to have code as clean and efficient as with my BTreeMap :)

(BTW, I'm kind of curious, do you have any benchmarks of concread vs. rwlock performance for a few scenarios?)

There are benchmarks in the source if you want to run them. Generally concread "blows rwlock out of the water" for performance even with EbrCell or ArcCell. But I'm always open to more benches if you want to add them.

[Ekleog]

This is very cool, thank you! :D And sorry for not having answered your message sooner, I'm quite a bit behind on reading my emails :sweat_smile:

[Firstyear]

Released in 0.4.4