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 Vecs, 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 implHash 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
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:
// 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
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.
"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.
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).
Concurrency and random sampling are where I have wanted iterators for sets that actually guarantee unorderedness by starting at different points in the collection.
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, even though it doesn't support iteration
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).
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.
Vec already ticks all the boxes, except the first one:
Must not impl Index*
And I don't think this is a deal-breaker.
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.
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.
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).
I agree with this. Concurrency can significantly improve performance compared to loop re-ordering. But both can be worthwhile optimizations, depending on use-case
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:
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.
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.
"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.
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 (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.
(assuming I'm not mistaken about the implementation details). The compiler/optimizer doesn't know about the spec unless explicitly told about it.