Document iteration order of `retain` functions by janikrabe · Pull Request #8679...

Copy link

Contributor

janikrabe commented 22 days ago

r? @kennytm

Assigning this to you because you're assigned the related #86789.

janikrabe commented 22 days ago

@rustbot label: +S-waiting-on-review

the8472 commented 22 days ago

Are there any theoretical optimizations that would be precluded by guaranteeing a specific order?

cuviper commented 21 days ago

BTree could visit in pre- or post-order, but I don't know if that would have any real advantages.

janikrabe commented 21 days ago •

Maybe someone more familiar with B-trees could comment on this, but for arbitrary closures I don't believe retain can be optimized significantly by changing the iteration order (perhaps slightly by reducing the number of rotations?) If it can, it may also be worth reconsidering the guarantees of the (still unstable) drain_filter functions the current implementation of retain uses, although in my opinion it makes sense to always guarantee ordered iteration for BTreeSet and BTreeMap regardless (as I think that's how people expect these data structures to work.)

m-ou-se commented 18 days ago

This promises .retain() on BTreeMap and BTreeSet visits the elements in order, as they already do right now.

My thoughts: I can imagine there might be some more efficient implementation that calls the predicate in a different order based on the structure of the tree, but there are probably already people depending on the order of .retain(), since we have the same promise for some other data structures. If we find out about an optimized version that does not call the predicate in order, we can consider adding a retain_unordered if the difference is significant. But for retain, it'd be good to promise the current behaviour as stable, since that's most likely what many users already expect and assume.

@rfcbot merge

rfcbot commented 18 days ago •

Team member @m-ou-se has proposed to merge this. The next step is review by the rest of the tagged team members:

No concerns currently listed.

Once a majority of reviewers approve (and at most 2 approvals are outstanding), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

rfcbot commented 16 days ago

This is now entering its final comment period, as per the review above.

rfcbot commented 6 days ago

The final comment period, with a disposition to merge, as per the review above, is now complete.

As the automated representative of the governance process, I would like to thank the author for their work and everyone else who contributed.

The RFC will be merged soon.