# \`UnorderedVec\` (or slice?) **URL:** \ **Category:** Uncategorized\ **Created:** [March 9, 2025, 7:39pm UTC](https://internals.rust-lang.org/t/unorderedvec-or-slice/22527 "2025-03-09T19:39:09Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![Rudxain](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/rudxain/32/12209_2.png) [@Rudxain](https://internals.rust-lang.org/u/Rudxain)\ **Post date:** [March 9, 2025, 7:39pm UTC](https://internals.rust-lang.org/t/unorderedvec-or-slice/22527/1 "2025-03-09T19:39:09Z")
[Potentially related](https://internals.rust-lang.org/t/pre-rfc-std-noorder/22514) The core idea is ~~a trait equivalent to `IntoIterator`~~ iteration (in general), but with **no guarantees about consistent iteration order** (to allow more optimizations). The title mentions slices and `Vec`s, because it makes more sense for specialized ("niche") data structures. Despite being niche, this is something that could never be implemented by user-land code, as it requires "compiler magic" to work as intended. Features of an `UnorderedVec`: - Must not `impl Index*`, as there are no keys, indices, or "pointers to elements" of any kind. - Unlike `HashSet`, the elements don't need to `impl` `Hash` or `*Eq` - Unlike `HashSet`, elements are contiguous, which is good for cache locality and memory usage. - There is no `Hash` overhead, but lookups (`contains` method) are `O(n)` (average), and require `PartialEq` - [Duplicates are allowed](https://internals.rust-lang.org/t/unorderedvec-or-slice/22527/5), for faster `push`ing - `IntoIterator` (or an equivalent trait) can yield the elements in arbitrary orders, **even if the order is observable** by side-effects. The only guarantee is that each element is hit once (assuming nothing interrupts the iterator). (Contrived) Example: ```rust // Which module would be appropriate? // ("_" is a placeholder) let v = std::_::UnorderedVec::new(); v.push(0); v.push(1); v.push(2); // compile-time error //v[0]; // typically: 0 1 2 // if reverse is optimal: 2 1 0 // might even be: 2 0 1 for x in v { println!("{x}"); } /* this is allowed to differ, so it could be: 1 2 0, but it's more likely the rev of the previous loop, as that allows reusing the pointer register, and is more likely to cache-hit */ for x in v { println!("{x}"); } ``` I'm not sure if this idea should also be applied to slices and arrays, as that would probably require more lang types instead of lib types ---
**Author:** ![binarycat](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/binarycat/32/12210_2.png) [@binarycat](https://internals.rust-lang.org/u/binarycat)\ **Post date:** [March 9, 2025, 8:51pm UTC](https://internals.rust-lang.org/t/unorderedvec-or-slice/22527/2 "2025-03-09T20:51:38Z")
Rust datatypes in the standard library generally refer to concrete datatypes, not abstract ones. that's why we have `HashMap` and `BTreeMap`, not just `Map`. the name for an unordered collection is a _set_ and we already have `HashSet`, which already doesn't guarantee iteration order. datastructures are generally chosen for what they can do, not what they can't, so you don't immediately gain anything just from giving up iteration order. the only upside you list is... eliminating a single register-to-register load? in the very specific situation where you are iterating over the same list twice? it sounds like you don't actually want a new datatype, but instead a magic method on slices that itetates over them in an unspecified order. ---
**Author:** ![josh](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/josh/32/5934_2.png) [@josh](https://internals.rust-lang.org/u/josh)\ **Post date:** [March 9, 2025, 9:25pm UTC](https://internals.rust-lang.org/t/unorderedvec-or-slice/22527/3 "2025-03-09T21:25:44Z")
So, is this effectively `ArraySet`? ---
**Author:** ![HjVT](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/hjvt/32/10365_2.png) [@HjVT](https://internals.rust-lang.org/u/HjVT)\ **Post date:** [March 9, 2025, 9:37pm UTC](https://internals.rust-lang.org/t/unorderedvec-or-slice/22527/4 "2025-03-09T21:37:53Z")
"contiguous in memory" requirement sure sounds like it. I think that's not the first time a Vec-based structure with Map/Set-like API is being brought up. I've certainly cobbled together enough AssocArray type datastructures to get ideas that maybe, lib alloc should just include one. ---
**Author:** ![CAD97](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/cad97/32/3460_2.png) [@CAD97](https://internals.rust-lang.org/u/CAD97)\ **Post date:** [March 9, 2025, 9:57pm UTC](https://internals.rust-lang.org/t/unorderedvec-or-slice/22527/5 "2025-03-09T21:57:51Z")
Given the OP's description still allows duplicate elements, I believe the more correct term is `Bag` instead of `Set`, although I haven't actually seen the term used super widely (probably due to the limited utility of removing the orderedness constraint from a vector). ---
**Author:** ![dlight](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/dlight/32/8462_2.png) [@dlight](https://internals.rust-lang.org/u/dlight)\ **Post date:** [March 9, 2025, 10:35pm UTC](https://internals.rust-lang.org/t/unorderedvec-or-slice/22527/6 "2025-03-09T22:35:57Z")
There is also [multiset](https://crates.io/search?q=multiset). Bag is probably better though ---
**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:** [March 9, 2025, 11:30pm UTC](https://internals.rust-lang.org/t/unorderedvec-or-slice/22527/7 "2025-03-09T23:30:44Z")
> [@CAD97](#): > > although I haven't actually seen the term used super widely (probably due to the limited utility of removing the orderedness constraint from a vector) DotNet has [ConcurrentBag\ Class (System.Collections.Concurrent) | Microsoft Learn](https://learn.microsoft.com/en-us/dotnet/api/system.collections.concurrent.concurrentbag-1) where the concurrent-ness is why not having a canonical order makes sense. ---
**Author:** ![the8472](https://avatars.discourse-cdn.com/v4/letter/t/0ea827/32.png) [@the8472](https://internals.rust-lang.org/u/the8472)\ **Post date:** [March 9, 2025, 11:37pm UTC](https://internals.rust-lang.org/t/unorderedvec-or-slice/22527/8 "2025-03-09T23:37:41Z")
Concurrency and random sampling are where I have wanted iterators for sets that actually guarantee unorderedness by starting at different points in the collection. > > > I have a large map of IDs -\> items, some fraction of those items is in a ready s…tate. I'm using a set of IDs to pick the next ready item and remove it from the ready-set. > > Having a way to extract a random item from a set would be useful and likely faster. > > \* Random sampling would avoid the multi-step, non-atomic approach of first iterating to find an ID, copying it, then removing it from the set, it could instead remove an item under a single write lock. > When multiple threads try this concurrently they'll collide on trying to remove the same ID (since the iterators always start at shard 0) and the other threads will have to retry > \* Random sampling could optimistically attempt try-locking some shards before blocking since the order doesn't matter ---
**Author:** ![Rudxain](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/rudxain/32/12209_2.png) [@Rudxain](https://internals.rust-lang.org/u/Rudxain)\ **Post date:** [March 10, 2025, 2:24am UTC](https://internals.rust-lang.org/t/unorderedvec-or-slice/22527/9 "2025-03-10T02:24:53Z")
> [@binarycat](#): > > `HashSet`, which already doesn't guarantee iteration order. Yes, but that's just a _human_ statement about the API contract. If the PRNG seed was constant and the Rust-toolchain version was pinned, the iteration order would always be the same for a given `HashMap` 😉 (assuming I'm not mistaken about the implementation details). The **compiler/optimizer doesn't know about the spec** unless explicitly told about it. My real intention is to tell the compiler "I don't care at all about the order of this loop, just make it fast and complete" (attributes, maybe?). Although a data-type with this default behavior could also be useful, especially since not implementing `Index` could allow the compiler to do even more optimizations > for some reason, this reminds me of JS [`WeakSet`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/WeakSet), even though it doesn't support iteration ---
**Author:** ![kpreid](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/kpreid/32/8484_2.png) [@kpreid](https://internals.rust-lang.org/u/kpreid)\ **Post date:** [March 10, 2025, 4:42am UTC](https://internals.rust-lang.org/t/unorderedvec-or-slice/22527/10 "2025-03-10T04:42:57Z")
Do you have any examples of what sort of optimization that would be possible via this property and not otherwise? ---
**Author:** ![SkiFire13](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/skifire13/32/7579_2.png) [@SkiFire13](https://internals.rust-lang.org/u/SkiFire13)\ **Post date:** [March 10, 2025, 6:49am UTC](https://internals.rust-lang.org/t/unorderedvec-or-slice/22527/11 "2025-03-10T06:49:05Z")
> [@Rudxain](#): > > Yes, but that's just a _human_ statement about the API contract. If the PRNG seed was constant and the Rust-toolchain version was pinned, the iteration order would always be the same for a given `HashMap` 😉 (assuming I'm not mistaken about the implementation details). For a given `HashMap`/`HashSet` instance the iteration order is already always the same. What's non-deterministic is the iteration order of different `HashMap`/`HashSet` instances using the default hasher, even when created in the same way (e.g. inserting elements in the same order). ---
**Author:** ![riking](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/riking/32/2818_2.png) [@riking](https://internals.rust-lang.org/u/riking)\ **Post date:** [March 10, 2025, 9:50am UTC](https://internals.rust-lang.org/t/unorderedvec-or-slice/22527/12 "2025-03-10T09:50:50Z")
See also `Vec::swap_remove` which will get you most of the efficiency wins you want, because remove is the only remaining expensive basic operation on Vecs. ---
**Author:** ![Rudxain](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/rudxain/32/12209_2.png) [@Rudxain](https://internals.rust-lang.org/u/Rudxain)\ **Post date:** [March 10, 2025, 1:33pm UTC](https://internals.rust-lang.org/t/unorderedvec-or-slice/22527/13 "2025-03-10T13:33:05Z")
Not yet, but that's a good question! ---
**Author:** ![Aloso](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/aloso/32/5039_2.png) [@Aloso](https://internals.rust-lang.org/u/Aloso)\ **Post date:** [March 11, 2025, 12:09am UTC](https://internals.rust-lang.org/t/unorderedvec-or-slice/22527/14 "2025-03-11T00:09:35Z")
`Vec` already ticks all the boxes, except the first one: > Must not `impl Index*` And I don't think this is a deal-breaker. > [@Rudxain](#): > > If the PRNG seed was constant and the Rust-toolchain version was pinned, the iteration order would always be the same for a given `HashMap` You didn't say that the iteration order should be non-deterministic, and I don't see how that would be useful. Making it completely non-deterministic would be expensive, it would require calling `getrandom` or something similar before every iteration. > I don't care at all about the order of this loop, just make it fast and complete If you don't care about the iteration order, then a deterministic order should be fine! For arrays and slices, the fastest way to iterate over all items is from start to end—unless you want a concurrent iterator. ---
**Author:** ![the8472](https://avatars.discourse-cdn.com/v4/letter/t/0ea827/32.png) [@the8472](https://internals.rust-lang.org/u/the8472)\ **Post date:** [March 11, 2025, 1:41pm UTC](https://internals.rust-lang.org/t/unorderedvec-or-slice/22527/15 "2025-03-11T13:41:29Z")
> [@Rudxain](#): > > My real intention is to tell the compiler "I don't care at all about the order of this loop, just make it fast and complete" (attributes, maybe?) It's not so much individual collections that may cause slowdowns - they're usually already implemented to use whatever strategy is optimal to loop over their contents - but iterator adapter implementations. The standard library iterator adapters are a bit conservative about side-effects and short-circuiting. E.g. even if `.inspect().take_while().count()` could operate in chunks to get better vectorization it doesn't do that due to possible side-effects or divergence in the `inspect` closure if it overshoots the short-circuit endpoint in `take_while`. Adapters that more aggressively optimize for the final result of the pipeline at the expense of some observable behavior would be possible. But that would require some more complex type system gymnastics than just a trait to opt into such optimizations. ---
**Author:** ![Rudxain](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/rudxain/32/12209_2.png) [@Rudxain](https://internals.rust-lang.org/u/Rudxain)\ **Post date:** [March 11, 2025, 5:13pm UTC](https://internals.rust-lang.org/t/unorderedvec-or-slice/22527/16 "2025-03-11T17:13:14Z")
> [@Aloso](#): > > Making it completely non-deterministic would be expensive, it would require calling `getrandom` or something similar before every iteration. [Non-determ doesn't mean random](https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton), and [determinism isn't always predictable](https://mattiheino.com/2016/12/27/deterministic-not-predictable) (proof: [Halting Problem](https://en.wikipedia.org/wiki/Halting_problem)). This is why "RAM" is a [misnomer](https://en.wikipedia.org/wiki/Misnomer), it should be " **arbitrary** access memory" in contrast to "_sequential_ access memory". To be fair, if we pin compiler version (like the previous thought experiment), the iteration-order would be "the same", so long as the source code that we're compiling is left untouched (just like many kinds of auto-optimizations). > [@Aloso](#): > > concurrent iterator I agree with this. Concurrency can significantly improve performance compared to loop re-ordering. But both can be worthwhile optimizations, depending on use-case ---
**Author:** ![Rudxain](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/rudxain/32/12209_2.png) [@Rudxain](https://internals.rust-lang.org/u/Rudxain)\ **Post date:** [March 11, 2025, 5:13pm UTC](https://internals.rust-lang.org/t/unorderedvec-or-slice/22527/17 "2025-03-11T17:13:39Z")
> [@the8472](#): > > that would require some more complex type system gymnastics than just a trait to opt into such optimizations. This is a very valid concern. As an alternative, I was considering that this sort of optimization could be implemented on the LLVM side (I assume it already is), and that `rustc` could then "expose" that feature to allow users to easily apply it. That would likely require `unsafe`, so I'm unsure if it's worth it. Another alt would be **macros**. I remember macros can do amazing low-level things. So this _could_ be implemented in user-land as a safe macro: ```rust iter_reorder![ for x in v_0 { // do something } // re-ordering can happen even // if the collections are different for x in v_1 { // do something } ] ``` Ideally, it would be cross-platform. In practice, it would only support x86 and ARM, because of the auto-generated assembly. ---
**Author:** ![the8472](https://avatars.discourse-cdn.com/v4/letter/t/0ea827/32.png) [@the8472](https://internals.rust-lang.org/u/the8472)\ **Post date:** [March 11, 2025, 5:49pm UTC](https://internals.rust-lang.org/t/unorderedvec-or-slice/22527/18 "2025-03-11T17:49:56Z")
LLVM mostly performs semantics-preserving optimizations, except in a few cases where the some attributes signal that specific behaviors can be ignored. The ones I was talking about would be high-level, lossy optimizations that llvm is unlikely to ever do. So they would have to be implemented by a library. ---
**Author:** ![Aloso](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/aloso/32/5039_2.png) [@Aloso](https://internals.rust-lang.org/u/Aloso)\ **Post date:** [March 11, 2025, 7:56pm UTC](https://internals.rust-lang.org/t/unorderedvec-or-slice/22527/19 "2025-03-11T19:56:51Z")
> [@Rudxain](#): > > [Non-determ doesn't mean random](https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton), and [determinism isn't always predictable](https://mattiheino.com/2016/12/27/deterministic-not-predictable) "Determinism" has different meanings. In CS theory, a "nondeterministic Turing machine" is a theoretical computer that can execute multiple branches simultaneously. Therefore, it can efficiently answer whether an input matches an NFA. Real-world computers cannot do that. But when we say that computers are deterministic, we mean something very different: We mean that given the same inputs, they always produce the same output. In practice, there are a few exceptions where computers aren't deterministic: Randomness (assuming the PRNG is outside our control), concurrency (where the time a computation takes can affect the output), and other external factors like network conditions. As you have pointed out, HashSet's iteration order is deterministic. You haven't actually explained how UnorderedVec's iteration should behave, only that the order can be "arbitrary", which is also true for HashSet. ---
**Author:** ![toc](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/toc/32/6692_2.png) [@toc](https://internals.rust-lang.org/u/toc)\ **Post date:** [March 12, 2025, 4:05am UTC](https://internals.rust-lang.org/t/unorderedvec-or-slice/22527/20 "2025-03-12T04:05:44Z")
I would expect the proposed functionality would just be an extension trait on `Vec` or similar. As an example of an extension trait which literally sacrifices ordering for performance\[1\]: [rayon's `par_iter`](https://docs.rs/rayon/latest/rayon/iter/trait.IntoParallelRefIterator.html) (and friends). But otherwise, @Rudxain, can you write a _much more concrete_ example of the functionality you want. Perhaps as an extension trait? Or explain why writing that extension trait is impossible/difficult in current rust? Creating an alternate iterator for `Vec` (if that is all this is) is not a high friction area of rust. * * * 1. YMMV [Next page](https://internals.rust-lang.org/t/unorderedvec-or-slice/22527.md?page=2)