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


#1

Yes, the coffee is bitter. Drink it down. The real bitterness will come when it wakes you up enough to contemplate your failures.

- Existential Comics

Here are some ways in which the current map APIs suck, and potentially make your program Slower And Therefore Terrible:

  • Entry requires an owned key upfront, even if all you have is a borrowed key and the entry is occupied
  • You can’t memoize hashes (easily)
  • We require K: Eq + Hash to insert keys, like cowards
  • Having to make wrapper types to do custom search logic is annoying

There have been many attempts to variously resolve these issues, by myself and others. These attempts have failed because they have tried to achieve goals like “ergonomics”, “safety”, and “basic decency”. Today we abandon these goals and just solve the dang problem, allowing our users to write abominations like:

let borrowed_key = ...;
let entry = map.raw_entry()
    .hash_with(|_| borrowed_key.get_memoized_hash())
    .search_with(|k| borrowed_key.field == k.field);

match entry {
  Vacant(entry) => { entry.insert(borrowed_key.clone(), val) }
  Occupied(entry) => { entry.insert(val) }
}

Here is the API:

pub struct RawEntryBuilder<'a, K: 'a, V: 'a, S: 'a>;
pub struct RawEntryBuilderHashed<'a, K: 'a, V: 'a>;
pub enum RawEntry<'a, K: 'a, V: 'a> {
    Occupied(RawOccupiedEntry<'a, K, V>),
    Vacant(RawVacantEntry<'a, K, V>),
}
pub struct RawOccupiedEntry<'a, K: 'a, V: 'a>;
pub struct RawVacantEntry<'a, K: 'a, V: 'a>;

pub struct RawImmutableEntryBuilder<'a, K: 'a, V: 'a, S: 'a>;
pub struct RawImmutableEntryBuilderHashed<'a, K: 'a, V: 'a>;

impl<K, V, S> HashMap<K, V, S> {
    /// Creates a raw entry builder for the HashMap.
    ///
    /// Raw entries provide the lowest level of control for searching and
    /// manipulating a map. They must be manually initialized with hash and
    /// then manually searched. After this, insertions into the entry also 
    /// still require an owned key to be provided.
    ///
    /// Raw entries are useful for such exotic situations as:
    ///
    /// * Hash memoization
    /// * Deferring the creation of an owned key until it is known to be required
    /// * Using a HashMap where the key type can't or shouldn't be hashed and/or compared
    ///
    /// Unless you are in such a situation, higher-level and more foolproof APIs like 
    /// `entry` should be preferred.
    fn raw_entry(&mut self) -> RawEntryBuilder<K, V, S>;

    /// Creates a raw immutable entry builder for the HashMap.
    ///
    /// This is useful for 
    /// * Hash memoization
    /// * Querying a HashMap where the key type can't or shouldn't be hashed and/or compared
    ///
    /// Unless you are in such a situation, higher-level and more foolproof APIs like 
    /// `entry` should be preferred. 
    ///
    /// Immutable raw entries have very limited use; you might instead want `raw_entry`.
    fn raw_entry_immut(&self) -> RawImmutableEntryBuilder<K, V, S>;
}

impl<'a, K, V, S> RawEntryBuilder<'a, K, V, S>
    where S: BuildHasher,
{
    /// Initializes the raw entry builder with the hash of the given query value.
    fn hash_by<Q: ?Sized>(self, k: &Q) -> RawEntryBuilderHashed<'a, K, V>
        where Q: Hash;

    /// Initializes the raw entry builder with the hash yielded by the given function.
    fn hash_with<F>(self, func: F) -> RawEntryBuilderHashed<'a, K, V>
        where F: FnOnce(S::Hasher) -> u64;

    /// Searches for the location of the raw entry with the given query value.
    fn search_by<Q: ?Sized>(self, k: &Q) -> RawEntry<'a, K, V>
        where K: Borrow<Q>,
              Q: Eq + Hash;
}

impl<'a, K, V> RawEntryBuilderHashed<'a, K, V>
{
    /// Searches for the location of the raw entry with the given query value.
    ///
    /// Note that it isn't required that the query value be hashable, as the
    /// builder's hash is used.
    fn search_by<Q: ?Sized>(self, k: &Q) -> RawEntry<'a, K, V>
        where K: Borrow<Q>,
              Q: Eq;

    /// Searches for the location of the raw entry with the given comparison function.
    ///
    /// Note that mutable access is given to each key that is visited, because
    /// this land is truly godless, and *someone* might have a use for this.
    fn search_with<F: ?Sized>(self, func: F) -> RawEntry<'a, K, V> 
        F: FnMut(&mut K) -> bool;
}

impl<'a, K, V> RawEntry<'a, K, V> {
    // At this point, basically an Entry except `insert` APIs take a `K` as well.
}



// raw_entry_immut is basically exactly the same except:

/// Searches for the location of the raw entry with the given comparison function.
///
/// If the location is empty, None is returned as nothing useful can be done in
/// this case.
fn search_with<F: ?Sized>(self, func: F) -> Option<(&'a K, &'a V)> 
    where F: FnMut(&K) -> bool; // Only immutable access to F!

The API for BTreeMap is much the same except everything about hashing is removed. It’s possible it would also just support prev()/next() on entries, in which case a Real immutable entry type would be necessary. At that point we may also wish to swap the API naming polarity back to the typical raw_entry + raw_entry_mut scheme.

I started implementing this on HashMap and it seems like we’re mostly already setup for it. The only kinda annoying thing is exposing the keys mutably during search for RawEntryBuilder, but I’m pretty sure this just means copy-pasting search_hashed_nonempty to add some mut’s and being sad.


#2

I like the overall idea of having a “lowest possible level” API that everything else is/can be implemented on top of.

You can play some tricks to avoid having to have three separate types to model the stages of the builder (i.e. start out with a RawEntryBuilder<Missing, Missing> and then have impl<A, B> RawEntryBuilder<A, B> where A: FnOnce(..), B: FnMut(...) { fn build(self) -> ... }).


#3

You can play some tricks to avoid having to have three separate types to model the stages of the builder

It’s possible but I don’t think it’s worth the effort. The only real win is you could get more of the API surface on one page, but this is already an issue Entry suffers from pretty bad.


#4

I also like the idea of having a low-level API for advanced use cases, but I don’t think “I want to look up and mutate a key without unnecessarily cloning it” should be an advanced use case. If anything, it’s the most common case.

It seems that this RFC is the most recent attempt to fix Entry to support borrowed keys, and it was mainly blocked on figuring out a way to support map.entry(owned_key) and map.entry(&key) in the same method, while minimizing backwards compatibility breakage. If we want to “just solve the dang problem”, we could just make a separate method, entry_ref or something, for borrowed keys: no compat issues, no need for a fancy new trait or use of specialization. It’s not the most elegant solution, but for use cases that it supports, it’s a lot less inelegant than this :slight_smile:

I suppose this RFC can be seen as orthogonal - you could say “nah, we’ll fix entry the right way, we just haven’t gotten around to it yet, and a raw API is separately desirable”. But given how long it can take the RFC process to get around to things, I’m not thrilled about the idea of landing this first, effectively encouraging everyone to migrate to the raw API as the only way to make HashMap ‘not be stupid’, even for very basic uses.


#5

This is, IMO, just a cleaner way to do entry_ref (I said as much in the RFC comments). Keep in mind entry_ref also introduces its own set of types and everything because you really can’t cram the two into the same box. So if we’re making this parallel API, we might as well do the Really Useful one. It’s not like we haven’t been waiting 3 years to solve this problem already. Might as well wait a few more weeks or whatever to do a better job (and honestly I think this API would land much faster than the ref one, since there would be a strong multi-prong desire for it and it would be less of a historic wart that everyone hates).

Like, I joke that my proposed API is a gross mess, but it’s elegant in its simplicity. It’s also not even that big of an API growth from a conceptual perspective. You have entry and you have the raw_entry builder. Once you finish using the builder it’s almost exactly the same as entry (except VacantEntry::insert and Entry::or_insert are slightly different).

Every time we try to address subset usecases here we just get burned. Let’s stop getting burned.

I also don’t totally agree that the usecase isn’t advanced, in so far as entry is already advanced, and you need to be in a specific situation and actually care about the performance implications.


#6

You make a number of fair points. Two comments:

It’s not like we haven’t been waiting 3 years to solve this problem already. Might as well wait a few more weeks or whatever to do a better job

If it’s weeks, I don’t care. Even months. But as you said, we’ve been waiting 3 years already, and unless someone commits to shepherding the other RFC, we could easily end up a year from now with no further progress on it. That’s what I’m worried about.

I also don’t totally agree that the usecase isn’t advanced, in so far as entry is already advanced, and you need to be in a specific situation and actually care about the performance implications.

*shrug*

For me, performance is partially an aesthetic thing. If some code is doing something obviously wasteful, it really bugs me and I will go out of my way to make it not do that, even if the potential gain is measured in microseconds. This means that I would end up using raw_entry in fairly ordinary situations, and others with the same mindset might too. I admit that means it’s my own fault if I mess something up - I know what Knuth said about premature optimization. :slight_smile: But it’s also aesthetically displeasing to use an unsafe API when a safe one is possible!


#7

How much of the API fussing is caused by ownership? It seems like all of it, but I have a hard time reading highly generic rust code with all the constraint stuff going on.

Would a much simpler api be possible for a hashmap variant where the keys were also bound as Copy and you could just copy all over the place and not think about it so much? Like, personally when I use a HashMap I usually only need integral types and tuple combinations of such.


#8

I like this. One thing I need to do very often is mutate an element of a set in an ordering-preserving way. For example, the set is sorted by some member of a struct, and I need to mutate the other members, which does not change the order of the set in any way.

I have been able to live with removing the element from the set, mutating it, and inserting it back again. But every time I do that a piece of me dies with it.

Being able to mutate it in place is great, and the best part is that it is not something that C++ sets can easily do (without const_casts at least) :smiley:


#9

What are the consequences of misusing this API? I assume that the map can become “corrupted” such as future use of other methods return incorrect results. But there is no memory-safety issue, is there? None of the new methods are unsafe fn.

In other words, how terrified should I be to venture into this godless land?


#10

For this usecase I would envisage something which uses a closure taking ownership of the element, mutating it, and then returning the element.

It’s easy enough upon getting the returned element to check whether it rightly fits where it is. It could be only checked in debug, to avoid any overhead in release.

And if the closure panics, and never returns anything, then the element is evicted from the collection.


#11

It is already easy to “corrupt” a hashmap, e.g. the following code shows how you can create hashmap entries that you can’t find anymore by mutating the keys.

fn main() {
    #[derive(PartialOrd, Ord, PartialEq, Eq)]
    struct Evil<'a>(&'a ::std::cell::Cell<u8>);
    impl<'a> ::std::hash::Hash for Evil<'a> {
        fn hash<H: ::std::hash::Hasher>(&self, state: &mut H) {
            state.write_u8(self.0.get())
        }
    }
    let c = ::std::cell::Cell::new(5);
    let c5 = ::std::cell::Cell::new(5);
    let mut m = ::std::collections::HashMap::new();
    m.insert(Evil(&c), "hai");
    c.set(10);
    println!("{:?}", m.get(&Evil(&c)));
    println!("{:?}", m.get(&Evil(&c5)));
}

#12

Sure, ok. But that’s my point: I want to confirm that these new API don’t do worse than that and don’t introduce memory-safety issues.


#13

Are we currently shipping versions of the std library with debug_assert!ions turned on? If not, then this is not as easy as it sounds. In any case, I wouldn’t really mind turning this into a real assert! if PartialEq is expensive enough for this to matter then the performance of a set is going to be bad independently of whether we check this on this dangerous but uncommon operation or not - uncommon at least when compared to simple lookups.


#14

This is correct. The docs of BTreeSet explicitly say:

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.

This new API makes corrupting the collections easier, but that should not result in undefined behavior, only in unspecified behavior as a consequence of the precondition violation.

For example, if you corrupt a BTreeSet iterating over it might return the elements in an order that does not satisfy Ord and might even not return all the elements, doing a key lookup might not find the key even though it is stored in the set, etc.


#15

No, all debug_asserts in libstd continue to be lies.

I’m genuinely not sure how I would implement this, and it wouldn’t be possible to make bullet-proof, because things like inconsistent orderings just mean the entire collection is chaos. I’d rather just say “you’re on your own” if you use this.


#16

@eddyb has requested the API be called cursor/cursor_mut. The name is fairly meaningless for HashMap, but makes sense for the BTreeMap extensions I suggested. As always I’m pretty ambivalent about naming and would rather focus on the other technical details first.


#17

In that situation the user is modifying an element that is already inserted in the collection. So the way to implement this is to just:

  • for an ordered collection: check, after the modification has completed, that the element still satisfies the order, e.g. by checking that it is greater than the previous element and smaller than the next element. This is as loose as it can be: it allows modifying the element in a way that alters the ordering as long as it doesn’t alter the ordering of the collection being modified.
  • for a hash-based collection: store the hash before the modification, compute the hash after the modification, and compare those two. I don’t know if something can be done about Eq, but this check would already be better than nothing. EDIT: For Eq + Hash one could perform the lookup with the same key after the modification and assert that the element you land on is the same element that was modified.

These two things scream for a debug_assert! instead of an assert! but I could live with an assert! when doing these operations and one could offer …_unchecked methods if the asserts turned to be a huge issue.


#18

I’d like to address two of your concerns:

Entry requires an owned key upfront, even if all you have is a borrowed key and the entry is occupied

I think this problem could be solved by an entry() method that would simply take the borrowed form of the key unconditionally, along with a ToOwned bound, and it would only convert the key to owned if it doesn’t already exist in the map. I’m not sure why the current Entry API doesn’t work like this — is there something in the way of implementing it?

If both APIs existed, it would be possible for the consumer to choose whether s/he wants to move into the entry or let it create an owned copy internally if necessary.

We require K: Eq + Hash to insert keys, like cowards

I’m not entirely sure what you mean by this, or why this is an issue. Doesn’t a key need to be hashable in order to be looked up or inserted in a HashMap?


#19

Sounds good, although it seems appropriate to also have the entry_ref API in addition to the raw API.


#20

If you’re starting with an owned copy of the key that forces a clone.