# \[Feature Request\] Expose bulk\_build\_from\_sorted\_iter in BTreeMap **URL:** \ **Category:** libs\ **Created:** [June 14, 2022, 7:24am UTC](https://internals.rust-lang.org/t/feature-request-expose-bulk-build-from-sorted-iter-in-btreemap/16815 "2022-06-14T07:24:21Z")\ **Posts on this page:** 18\ **Page:** 1
**Author:** ![azy](https://avatars.discourse-cdn.com/v4/letter/a/90db22/32.png) [@azy](https://internals.rust-lang.org/u/azy)\ **Post date:** [June 14, 2022, 7:24am UTC](https://internals.rust-lang.org/t/feature-request-expose-bulk-build-from-sorted-iter-in-btreemap/16815/1 "2022-06-14T07:24:21Z")
BTreeMap's from\_iter implementation collects all values into a vec and sorts them, before passing into bulk\_build\_from\_sorted\_iter. Sometimes, the data comes sorted. For my use case, from\_iter is already insanely fast; I am looking mainly to avoid the extra Vec allocation necessary for sorting. Use case is a dictionary of 1mil+ terms each containing some misc info, parsed using a custom iterator (not in contiguous Vec\<\_\> form so I think this can't possibly be compiler-optimized away). This is a wasm app as well (where the allocation is never really "reclaimed" due to the ArrayBuffer never shrinking again). Not sure if there's an alternative to achieve the allocation removal. But I imagine this might also be useful for other use cases if the sort operation itself is expensive. Maybe: also a from\_sorted\_unique\_iter method - useful if the equality comparison in DedupSortedIter is costly. ---
**Author:** ![gbutler](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/gbutler/32/3670_2.png) [@gbutler](https://internals.rust-lang.org/u/gbutler)\ **Post date:** [June 14, 2022, 1:31pm UTC](https://internals.rust-lang.org/t/feature-request-expose-bulk-build-from-sorted-iter-in-btreemap/16815/2 "2022-06-14T13:31:41Z")
> [@azy](#): > > BTreeMap's from\_iter implementation collects all values into a vec and sorts them, before passing into bulk\_build\_from\_sorted\_iter. What makes you think that? I"m pretty sure it just traverses the tree in order. ---
**Author:** ![RustyYato](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/rustyyato/32/13627_2.png) [@RustyYato](https://internals.rust-lang.org/u/RustyYato)\ **Post date:** [June 14, 2022, 1:40pm UTC](https://internals.rust-lang.org/t/feature-request-expose-bulk-build-from-sorted-iter-in-btreemap/16815/3 "2022-06-14T13:40:17Z")
See the source: > ---
**Author:** ![gbutler](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/gbutler/32/3670_2.png) [@gbutler](https://internals.rust-lang.org/u/gbutler)\ **Post date:** [June 14, 2022, 1:44pm UTC](https://internals.rust-lang.org/t/feature-request-expose-bulk-build-from-sorted-iter-in-btreemap/16815/4 "2022-06-14T13:44:38Z")
Derp! I misread "from\_iter" as "into\_iter". I'm so sorry for adding nothing useful to the discussion. ---
**Author:** ![scottmcm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/scottmcm/32/2355_2.png) [@scottmcm](https://internals.rust-lang.org/u/scottmcm)\ **Post date:** [June 14, 2022, 4:45pm UTC](https://internals.rust-lang.org/t/feature-request-expose-bulk-build-from-sorted-iter-in-btreemap/16815/5 "2022-06-14T16:45:26Z")
One interesting question here: are you expecting this to double-check the sorting? For example, should it be an unsafe `from_sorted_unique_iter_unchecked`? Because I'd hope that I can trust a `BTreeMap` at least, since it's a known and trusted type, even if I can't necessarily trust an arbitrary `BTreeSet` where I don't know if `T: Ord` is well-behaved. ---
**Author:** ![cgwalters](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/cgwalters/32/1065_2.png) [@cgwalters](https://internals.rust-lang.org/u/cgwalters)\ **Post date:** [June 14, 2022, 6:26pm UTC](https://internals.rust-lang.org/t/feature-request-expose-bulk-build-from-sorted-iter-in-btreemap/16815/6 "2022-06-14T18:26:01Z")
Wouldn't it work to have `from_iter` compare each item as it comes in in a loop and if the input is already sorted (i.e. compare with the last item read), take the optimal path; otherwise as soon as we detect an out-of-order item, take all the remaining items into a vector, sort it and append the rest as before? In other words; the fast path becomes automatic; there's no need for a separate API. ---
**Author:** ![cuviper](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/cuviper/32/1897_2.png) [@cuviper](https://internals.rust-lang.org/u/cuviper)\ **Post date:** [June 14, 2022, 7:02pm UTC](https://internals.rust-lang.org/t/feature-request-expose-bulk-build-from-sorted-iter-in-btreemap/16815/7 "2022-06-14T19:02:28Z")
That's an interesting idea. There may also be room for "mostly" sorted sequences -- only collect those that go backwards on the side, but continue with the forward ones directly, then sort and merge the others later. Although I guess one `MAX` out of order will interrupt the rest anyway. ---
**Author:** ![azy](https://avatars.discourse-cdn.com/v4/letter/a/90db22/32.png) [@azy](https://internals.rust-lang.org/u/azy)\ **Post date:** [June 15, 2022, 9:20am UTC](https://internals.rust-lang.org/t/feature-request-expose-bulk-build-from-sorted-iter-in-btreemap/16815/8 "2022-06-15T09:20:52Z")
Thanks for the replies! ps: I just found the rfc repo and this issue [Make BTreeMap's from\_sorted\_iter public · Issue #1805 · rust-lang/rfcs · GitHub](https://github.com/rust-lang/rfcs/issues/1805), sorry for the duplicate post. > [@scottmcm](#): > > One interesting question here: are you expecting this to double-check the sorting? For example, should it be an unsafe `from_sorted_unique_iter_unchecked`? I hadn't considered this when I posted, but was thinking and still favouring an unchecked version as a safe method, preferably named `from_sorted_iter`: - @dtolnay raised some great points in the above [issue](https://github.com/rust-lang/rfcs/issues/1805) on the assertion, and binary search: > I would prefer not to assert. The caller can wrap their iterator in an iterator adapter containing the assert if they want that. > > [binary search](https://doc.rust-lang.org/std/primitive.slice.html#method.binary_search) also does not verify that its input is sorted. - As an api user, I think its pretty clear as well from the potential method name "`from_sorted_iter`" that the onus of ensuring the iterator is sorted would fall on the user. (even more so than `binary_search`) - As for `T:Ord`, my take is that its fine to leave that responsibility to the user much like `vec.sort()` methods (and anything that relies on a properly defined Ord I guess) which are also not unsafe unchecked. - Maximum performance (without the checks) Though, this is mostly just going by precedent, I'm not quite familiar as to what warrants labelling an api `unsafe`. > [@cgwalters](#): > > otherwise as soon as we detect an out-of-order item, take all the remaining items into a vector, sort it and append the rest as before? Hmm to clarify, how would the appending work exactly? E.g: `vec![1, 2, 3, 4, 2].into_iter()` (2 needs to be inserted before 3, but `1,2,3,4` was already consumed) - We could clone the iterator (at the start) then collect the entire sequence into a `Vec` once `4, 2` is detected but it may be costly to re-iterate (e.g. custom iterators with a fair bit of stuff going on inside, and having to restart the `bulk_push` subroutine from element 0 presumably). - Or collect `1,2,3,4` (up until an out of order element) into a `Vec` right from the start, but this reintroduces the need for an extra `Vec<_>` allocation. - Do something "smart" with the `bulk_push` subroutine -- Is this it? I'm not too familiar with BTrees to know if this is possible. My limited understanding is that the entire sorted iterator needs to be present in "one go" for `bulk_push`'s benefits to be preserved. 🤔 > [@cuviper](#): > > only collect those that go backwards on the side, but continue with the forward ones directly, then sort and merge the others later. Although I guess one `MAX` out of order will interrupt the rest anyway. Sounds interesting too, but might be subject to the same issue per the above: how to deal with the already consumed elements. ---
**Author:** ![cuviper](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/cuviper/32/1897_2.png) [@cuviper](https://internals.rust-lang.org/u/cuviper)\ **Post date:** [June 15, 2022, 4:43pm UTC](https://internals.rust-lang.org/t/feature-request-expose-bulk-build-from-sorted-iter-in-btreemap/16815/9 "2022-06-15T16:43:55Z")
The idea as I understood it was that you'd already be pushing the pre-sorted items into a new map, then you'd sort the rest on the side and merge them together -- using `BTreeMap::append` or a similar internal mechanism. ---
**Author:** ![scottmcm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/scottmcm/32/2355_2.png) [@scottmcm](https://internals.rust-lang.org/u/scottmcm)\ **Post date:** [June 15, 2022, 6:04pm UTC](https://internals.rust-lang.org/t/feature-request-expose-bulk-build-from-sorted-iter-in-btreemap/16815/10 "2022-06-15T18:04:28Z")
> [@azy](#): > > I'm not quite familiar as to what warrants labelling an api `unsafe`. It depends what the invariants of the type that unsafe code can rely on are deemed to be. For example, with the current API surface I can know that `BTreeSet` is strictly increasing, and thus I could do something like rely on that for knowing there's no overlap to return a bunch of `&mut`s, even if someone else passed me the tree. Whereas if `from_sorted_iter` is safe _and_ doesn't check that it's actually sorted, then the set I get could actually be `[3, 2, 2, 1]`, _even though_ `usize` is a type that I trust and which has a correct `Ord` impl. ---
**Author:** ![azy](https://avatars.discourse-cdn.com/v4/letter/a/90db22/32.png) [@azy](https://internals.rust-lang.org/u/azy)\ **Post date:** [June 17, 2022, 6:14am UTC](https://internals.rust-lang.org/t/feature-request-expose-bulk-build-from-sorted-iter-in-btreemap/16815/11 "2022-06-17T06:14:27Z")
I see, thanks @cuviper @scottmcm for clarifying. Speaking as a user, I think I would prefer an `unsafe` unchecked method in that case if indeed necessary, since the main point of such an api would be to reap maximum performance gains. The automatic fast path ideas are interesting as well if easily feasible, but I personally wouldn't mind having to slap an `unsafe { from_sorted_iter(...) }`, and giving up a single `from_iter` method's convenience. (also, digging around to find this method after I've indeed identified the application bottleneck to be BTree construction - which I speculate is rarely the case). Might also avoid having any negative performance impact on existing use cases of randomly-sorted sequences. > [@cuviper](#): > > The idea as I understood it was that you'd already be pushing the pre-sorted items into a new map, then you'd sort the rest on the side and merge them together -- using `BTreeMap::append` or a similar internal mechanism. As the `append` implementation is currently, this looks identical to collecting the pre-sorted items into a `Vec` in terms of memory usage. It currently converts both BTrees with `into_iter` and interleaves them into a new BTree with the bulk building function. Not quite sure on other existing internal mechanisms. I'll try to dig around in the coming days and post back here if I find anything worthwhile 😀 ---
**Author:** ![Nemo157](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/nemo157/32/11585_2.png) [@Nemo157](https://internals.rust-lang.org/u/Nemo157)\ **Post date:** [June 17, 2022, 8:05am UTC](https://internals.rust-lang.org/t/feature-request-expose-bulk-build-from-sorted-iter-in-btreemap/16815/12 "2022-06-17T08:05:30Z")
> [@scottmcm](#): > > Whereas if `from_sorted_iter` is safe _and_ doesn't check that it's actually sorted, then the set I get could actually be `[3, 2, 2, 1]`, _even though_ `usize` is a type that I trust and which has a correct `Ord` impl. This assumes that there is no “safe-transmute” that would allow taking a `BTreeMap, ()>` and converting it to a `BTreeMap`. I’m not sure if there is any API allowing that today, but it seems possible to have a safe API that does (since `BTreeMap` doesn’t rely, or make guarantees, about the ordering). ---
**Author:** ![scottmcm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/scottmcm/32/2355_2.png) [@scottmcm](https://internals.rust-lang.org/u/scottmcm)\ **Post date:** [June 17, 2022, 5:08pm UTC](https://internals.rust-lang.org/t/feature-request-expose-bulk-build-from-sorted-iter-in-btreemap/16815/13 "2022-06-17T17:08:19Z")
> [@Nemo157](#): > > since `BTreeMap` doesn’t rely, or make guarantees, about the ordering I think that's the question being discussed, not a _fait accompli_. I agree that if you just have an unknown type in a set then you can't know that its `Ord` is well-behaved. But it seems silly to me to say that you can't even trust a set of a trusted type like `usize`, where you know that its `Ord` is definitely correct. ---
**Author:** ![cuviper](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/cuviper/32/1897_2.png) [@cuviper](https://internals.rust-lang.org/u/cuviper)\ **Post date:** [June 17, 2022, 5:36pm UTC](https://internals.rust-lang.org/t/feature-request-expose-bulk-build-from-sorted-iter-in-btreemap/16815/14 "2022-06-17T17:36:16Z")
> [@azy](#): > > As the `append` implementation is currently, this looks identical to collecting the pre-sorted items into a `Vec` in terms of memory usage. It currently converts both BTrees with `into_iter` and interleaves them into a new BTree with the bulk building function. I'm not sure, the peak memory usage might be lower with fine-grained nodes being allocated and freed on the fly, rather than an entire `Vec` buffer on the side. ---
**Author:** ![elidupree](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/elidupree/32/4304_2.png) [@elidupree](https://internals.rust-lang.org/u/elidupree)\ **Post date:** [June 18, 2022, 12:27pm UTC](https://internals.rust-lang.org/t/feature-request-expose-bulk-build-from-sorted-iter-in-btreemap/16815/15 "2022-06-18T12:27:49Z")
I believe [the BTreeSet documentation](https://doc.rust-lang.org/std/collections/struct.BTreeSet.html) already guarantees that _using `unsafe` code to modify a `BTreeSet` to be out-of-order_ cannot be a memory safety error (emphasis mine): > It is a logic error for an item to be modified in such a way that the item’s ordering relative to any other item, as determined by the Ord trait, changes while it is in the set. **This is normally only possible through** Cell, RefCell, global state, I/O, **or unsafe code**. The behavior resulting from **such a logic error** is not specified (it could include panics, incorrect results, aborts, memory leaks, or non-termination) but **will not be undefined behavior**. ETA: I suppose you could argue that it's only saying "if this somehow were to happen, in a way that is otherwise permitted, then none of _the BTreeSet methods specifically_ would invoke UB", but not saying that you are actually permitted to do it (because BTreeSet doesn't provide any APIs that would allow you to use unsafe code for this in a way that is sound, because it doesn't make any guarantees about its layout and things like `get()` only give you an &, which means that modifying it is specifically [called out as UB by the Reference](https://doc.rust-lang.org/stable/reference/behavior-considered-undefined.html)). But still, given that documentation, if I was writing unsafe code myself, I certainly wouldn't feel comfortable relying on "a `BTreeSet` passed from someone else's crate" to be in-order for memory safety. ---
**Author:** ![tczajka](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/tczajka/32/8923_2.png) [@tczajka](https://internals.rust-lang.org/u/tczajka)\ **Post date:** [June 18, 2022, 6:52pm UTC](https://internals.rust-lang.org/t/feature-request-expose-bulk-build-from-sorted-iter-in-btreemap/16815/16 "2022-06-18T18:52:56Z")
I think that whole section should be rewritten -- the intent of that documentation has nothing to do with items being **modified**. It doesn't matter whether the items are modified or not, what matters is whether `Ord` returns contradictory results, i.e. results inconsistent with a linear order (which may happen regardless of whether anything is being modified). Personally I think it would be totally sufficient to say that if `Ord` ever tells `BTreeSet` results inconsistent with a linear order, a panic may happen, or `BTreeSet` will pick a subset of those comparisons that does result in a linear order. In other words: if `BTreeSet` ever makes any redundant comparisons, and the results are contradictory, it will either panic or ignore some of them. This was previously discussed at length [here](https://internals.rust-lang.org/t/using-std-collections-and-unsafe-anything-can-happen/16640). Using `unsafe` to modify items owned by `BTreeMap` would be unsound. I agree with @scottmcm that `BTreeMap` should always be in order, so any such new API should either verify the order or be `unsafe`. ---
**Author:** ![scottmcm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/scottmcm/32/2355_2.png) [@scottmcm](https://internals.rust-lang.org/u/scottmcm)\ **Post date:** [June 18, 2022, 8:07pm UTC](https://internals.rust-lang.org/t/feature-request-expose-bulk-build-from-sorted-iter-in-btreemap/16815/17 "2022-06-18T20:07:31Z")
> [@elidupree](#): > > It is a logic error for an item to be modified in such a way that the item’s ordering relative to any other item, as determined by the Ord trait, changes while it is in the set. And that's _not possible_ for a `usize`. There's no way to change the value of a `usize` inside a set. (And before anyone says they could do it with `unsafe`, any attempt to do so is UB because it's behind a reference but not in an `UnsafeCell`, and thus can't happen.) ---
**Author:** ![system](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/system/32/14092_2.png) [@system](https://internals.rust-lang.org/u/system)\ **Post date:** [September 16, 2022, 8:08pm UTC](https://internals.rust-lang.org/t/feature-request-expose-bulk-build-from-sorted-iter-in-btreemap/16815/18 "2022-09-16T20:08:12Z")
Closed on September 16, 2022, 8:08pm UTC This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.