[Pre-RFC] Abandonning Morals In The Name Of Performance: The Raw Entry API

[nikomatsakis]

One thing we discussed with @nikomatsakis at the meetup was whether we should have a new std module like std::lowlevel that contains traits for low-level access to various Rust data-structures (e.g., HashMap). This has the nice added benefit that in order to use things like raw_entry_at, you would need to do explicitly something like use std::lowlevel::HashMapSuperPowerfulMethods.

Oh yeah, I forgot about that. I liked this idea =)

[Centril]

you would need to do explicitly something like use std::lowlevel::HashMapSuperPowerfulMethods.

Small bikeshed: std::collections::hash_map::raw::SuperPowerfulStuff might be more “local”?

[jonhoo]

Maybe, though I suspect we might end up with these kinds of “raw” APIs for a handful of different types (e.g., BTreeMap), and it’d be nice if there was one place to “collect” all these sort-of-kind-of-unsafe methods.

[Centril]

Perhaps you could use re-exports and have ::raw modules in std::collections::raw and std::collections::hash_map::raw so that we have our cake and eat it? (we get a raw collections prelude of sorts)

[Gankro]

I’m a bit dubious about letting you walk around in the buckets of a HashMap, as that’s the sort of thing that can get us more locked into specific implementations. Haven’t thought about it much though.

In generally I’d rather not have a std::low_level sort of thing for the same reason. The standard library is too general to ever justify exposing ultra-low-level details. You’ll always need to fork for that kind of stuff, I think.

[jonhoo]

The bucket walking (at least in our case) is not really about the semantics of what goes in each bucket, but rather wanting sequential memory access to semi-random elements. Being able to do batch inserts/lookups in bucket order is similarly not about knowledge of bucketing. I think there is some room for exposing the fact that there are buckets that are sequential in memory, without exposing the exact mapping from keys to buckets.

I’m not sure I understand your objection to std::low_level? The proposal would be to take the methods you proposed in the original post and have them be behind a trait defined in std::low_level and implemented only explicitly for HashMap. That way, users would need to explicitly state that they’re using a low-level API (use std::low_level::RawHashMap). In a sense that proposal is only about how people would be able to access whatever API we’d end up exposing, not what that API is.

[fintelia]

I’ve done some benchmarking of Rust HashMaps here. The current public APIs on HashMap do not provide the most optimal performance. In particular, I found two pieces of functionality to be missing:

1. There is no way to provide a precomputed hash value during an insertion, despite batch precomputation of hashes providing a ~25% speedup on bulk insertions. (I didn’t track down the cause of the speedup, but I suspect that vectorization played a role)

2. Computing the bucket index that a key will land in is quite brittle. Yet, creating a HashMap from entries sorted by this value can be several times faster. This could be improved either by making bucket computation more predictable as @jonhoo mentioned or directly exposing a function to compute the index.

[jethrogb]

I’m not sure I understand your objection to std::low_level? The proposal would be to take the methods you proposed in the original post and have them be behind a trait defined in std::low_level and implemented only explicitly for HashMap. That way, users would need to explicitly state that they’re using a low-level API (use std::low_level::RawHashMap). In a sense that proposal is only about how people would be able to access whatever API we’d end up exposing, not what that API is.

The objection is that once something gets into std, it’s stable and the API must be maintained indefinitely. The current HashMap API doesn’t expose too much of the internals, so we have some leeway to change the HashMap internals in the future. The more we expose of the inner workings, the less we can change in the future.

[jonhoo]

Oh, sure, I realize that. The proposal to have std::low_level was premised on @Gankro’s suggestions making it into std at all. I’m saying that if we are to add these methods then I think they should be behind this kind of explicit trait, rather than be methods directly on HashMap. I separately think that it is indeed a good idea to add some methods along these lines, though you are totally right that we’d want to be careful about what we commit to. In particular, I think it’d probably be fine to committing to open addressing (as opposed to per-bucket chaining), but I don’t think it’d be fine to, say, commit to Robin Hood hashing.

[gnzlbg]

I have the same concerns as @Gankro.

IMO, if @jonhoo and @fintelia need to use the exact implementation details of the std::collections, what they are currently doing is the right way to do so. That is, to fork the collection, put it in a crate, and rely on that.

So a different approach to help them here would be to make that easier, for example, by moving liballoc/libstd into the nursery, and splitting the different collections into different crates, so that they can have their own finer-grained fork that they can synchronize with upstream at their own pace.

OTOH, some of the operations they want are pretty high level, like bulk inserting items, or inserting with an intial pre-computed hash. These operations, like the operations that @Gankro proposes, are operations that any potential future HashMap improvements are going to be able to offer anyways. Or at least, one could design these APIs in such a way such that the evolution of the implementation is not constrained by them.

What I don’t understand exactly is why do we need to put these utilities in std::low_level or some other special place. They are reasonable things to do when one needs to, and I don’t really see how adding special extra hoops for these helps anybody in any way. They should just sit along the other collection operations, have good docs, and the unsafe operations should require unsafe code to use them. That would be good enough for me.

[JoeyAcc]

Just FTR, Having to make wrapper types to do custom search logic is annoying seems like a red herring to me. The reason is that extension methods are always an option, even for types in libstd.

[fintelia]

@JoeyAcc I’m not sure what you mean by using wrapper types for custom search logic. AFAIK neither they nor extension methods allow an end user to access private fields within standard library types. In order to adjust the hash to index computation like I described above, I had to copy the ~5000 lines of HashMap implementation into my own crate, manually remove the stability annotations from every single public function, and then switch the randomness implementation back to using the rand crate.

@gnzlbg None of the operations that have been proposed so far are unsafe. In fact, that’s probably part of the concern: these additions would open up tons of subtle ways of accidentally shooting yourself in the foot. For instance, the compiler won’t stop you from providing the wrong hash to insert_hashed_nocheck, but if you do, other seemingly unrelated lookups in the HashMap might fail later on.

Plus, there’s also just a lot of functions that we’d want. At very least, every function that takes a key (i.e. most of them) should also have a *_hashed_nocheck version that lets the user pass along the hash.

[gnzlbg]

None of the operations that have been proposed so far are unsafe. In fact, that’s probably part of the concern: these additions would open up tons of subtle ways of accidentally shooting yourself in the foot.

The question is whether using these functions can lead to other safe code invoking undefined behavior. For example, Vec::set_len does not invoke undefined behavior, but a consequence of using it incorrectly is that calling some other safe Rust methods might invoke undefined behavior. That is, Vec::set_len allows you to break Vec's invariants in such a way that it could lead to undefined behavior in safe Rust later on.

[fintelia]

My understanding is they can’t. HashMap is currently implemented entirely using safe code* by making it a wrapper around RawTable (which is basically "just a tricked out Vec<Option<(u64, K, V)>>"). The changes we’ve been discussing would presumably all be at the HashMap level and thus be similarly safe.

*except for the the experimental implementation of collection_placement

[gnzlbg]

The changes we’ve been discussing would presumably all be at the HashMap level and thus be similarly safe.

@fintelia does this mean that none of the proposed changes can result in undefined behavior being invoked, and that the only consequences of breaking the invariants of these collections is potential logic errors?

[fintelia]

@fintelia does this mean that none of the proposed changes can result in undefined behavior being invoked, and that the only consequences of breaking the invariants of these collections is potential logic errors?

Yes, the proposed changes can introduce potential logic errors but cannot trigger undefined behavior. In fact, the potential logic errors are the same ones that are already possible if the key’s Hash implementation does not respect the required invariants. (e.g. you’ll see some very strange behavior if keys that are equal can produce hashes that aren’t.)

[gnzlbg]

Then that’s great news, they don’t even need to be unsafe. A doc warning would be enough.

[jonhoo]

@Gankro do you think there’s any chance we might see this kind of lower-level API surface? We’re currently relying on a painful-to-maintain fork of HashMap in rahashmap to get randomized eviction from a map for use in a cache…

[Gankro]

I’ve had https://github.com/rust-lang/rust/pull/50821 up for a while, but i’ve been waiting on more libs team feedback to finish it.

[jonhoo]

That’s awesome! Looks like @alexcrichton followed up on it with a question about the safety of the API?