Optimize BTreeMap::append() using CursorMut#153107
Optimize BTreeMap::append() using CursorMut#153107asder8215 wants to merge 1 commit intorust-lang:mainfrom
Conversation
|
I'd be curious to see if this shows any noticeable performance difference with the current implementation of |
| &mut self.length, | ||
| (*self.alloc).clone(), | ||
| ) | ||
| // Because `other` takes a &mut Self, in order for us to own |
There was a problem hiding this comment.
Do we think this is worth it vs. calling merge with the right conflict function?
There was a problem hiding this comment.
I guess it's a bit redundant with how merge does everything that append does with the added benefit on what you want the value to be on conflicting keys. I'm not sure why one would prefer having less flexibility deciding what the resultant value of conflicting keys should be with BTreeMap::append over using BTreeMap::merge.
I think I wanted the code internally for BTreeMap::append() to be consistent with BTreeMap::merge() since we can remove some code that only BTreeMap::append uses if we have BTreeMap::merge() and BTreeMap::append() sharing the same CursorMut functions. Moreover, I think I just found it unnecessary how the BTreeMap in BTreeMap::append constructs it from scratch rather than just placing the elements of other BTreeMap into the appropriate spots of self BTreeMap.
Since
BTreeMap::mergeusesCursorMutto avoid reconstructing the map from scratch and instead inserting otherBTreeMapat the right places or overwriting the value in selfBTreeMapon conflict, we might as well do the same forBTreeMap::append. This also means that some of the code inappend.rscan be removed;bulk_push()however is used bybulk_build_from_sorted_iterator(), which is used by theFrom/FromIteratortrait impl onBTreeMap. Feels like we should rename the file or place thebulk_push()in an existing file.The same additional optimization consideration that
BTreeMap::mergehas is also applied toBTreeMap::append.r? @Mark-Simulacrum since Mark has seen the
BTreeMap::mergecode already (only diff is theOrdering::Equalcase and now one of the test assertions on a panic case has the correct value now).