rust-lang / hashbrown Goto Github PK
View Code? Open in Web Editor NEWRust port of Google's SwissTable hash map
Home Page: https://rust-lang.github.io/hashbrown
License: Apache License 2.0
Rust port of Google's SwissTable hash map
Home Page: https://rust-lang.github.io/hashbrown
License: Apache License 2.0
Presently inside of ss2/generic.rs, the method Group::static_empty() returns the address of a const
value (promoted to 'static
) instead of an explicitly static
variable. As a result, the value ends up being created inside of each consuming dylib instead of having a singular location inside of std
's dylib (or hashbrown's dylib).
In my use case, this is preventing me from reloading a dylib while any empty (HashMap::new()
) instances exist, as their ctrl
pointer ends up pointing to garbage in the unloaded dylib, instead of pointing to a static variable inside of std
.
If people are cool with changing const
-> static
, I'd be happy to prepare the trivial PR.
Code examples:
// if I use hashbrown::HashMap, compiler complains
// if I use std::collections::HashMap instead, it compiles
use hashbrown::HashMap;
//use std::collections::HashMap;
use typed_arena::Arena;
struct A<'a>(HashMap<&'a str, &'a A<'a>>);
struct B<'a>(&'a Arena<A<'a>>);
fn main() {
let alloc: Arena<A> = Arena::new();
let b = B(&alloc);
}
The compiler gives me the following message:
error[E0597]: `alloc` does not live long enough
--> driver/src/main.rs:20:13
|
20 | let b = B(&alloc);
| ^^^^^^ borrowed value does not live long enough
21 | }
| -
| |
| `alloc` dropped here while still borrowed
| borrow might be used here, when `alloc` is dropped and runs the destructor for type `typed_arena::Arena<A<'_>>`
My Cargo.toml:
[dependencies]
typed-arena = "1.4.1"
hashbrown = "0.5"
My rustc version:
rustc 1.37.0-nightly (04a3dd8a8 2019-06-18)
Entry
is Sync
if K
, V
, and S
are all Sync
, and RawVacantEntryMut
is also Sync
in the same way, but I'm not sure why RawOccupiedEntryMut
is always !Sync
?
I ran into this because I'm porting linked-hash-map
to be on top of hashbrown's raw-entry API, and I couldn't figure out why this type would need to be !Sync
(It also makes RawEntryMut
!Sync
).
It's definitely possible I'm missing something, so this is genuinely meant as a question.
I'm a bit confused: since this implementation landed in std
, what's the point of using this crate? I guess the default hash function is different, but apart from that? Would be cool if these things could be explained in the README :)
Is it possible to implement Hash on the hashmap or hashset?
I know that rust stdlib doesn't do this for security reasons. See rust-lang/rust#21182
But as it seems like the goal of this library isn't as focused on security (y'all are using fxhash) as much the stdlib HashSet is, that shouldn't be an issue.
If you look at Cranelift's ScopedHashMap, it (in effect) threads a linked-list of keys through the values of the hash map, and to keep track of scopes, entries are deleted eagerly when a scope is exited by following the list.
Instead of doing the work up-front (deleting when a scope is exited), it is possible to keep track of a "generation number" and lazily delete outdated keys for a given depth while performing other operations such as insertion.
For example, if you have a sequence of operations like:
h.increment_depth();
h.insert("x", "foo");
h.insert("y", "bar");
h.decrement_depth();
h.insert("x", "frob");
Then Cranelift's implementation would have the map evolve like:
{}
{"x" : {"foo", depth = 1}}
{"x" : {"foo", depth = 1}, "y" : {"bar", depth = 1}}
{}
{"x" : {"frob", depth = 1}}
whereas lazily deleting things would give
{}
{"x" : {"foo", depth = 1, gen = 1}}
{"x" : {"foo", depth = 1, gen = 1}, "y" : {"bar", depth = 1, gen = 1}}
{"x" : {"foo", depth = 1, gen = 1}, "y" : {"bar", depth = 1, gen = 1}}
{"x" : {"frob", depth = 1, gen = 2}, "y" : {"bar", depth = 1, gen = 1}}
In this case, I've picked the overwriting key to be identical, but it could very well be something else which just happened to have a hash collision - if the corresponding value is old, we delete the old value.
However, looking at the existing API of the crate, I don't think it is possible to implement such a lazy ScopedHashMap. Is that a fair assessment?
I have recently come aross two different interesting projects that did… well "did something with hashes". meowhash and this crate. Now, I have seen thah hashbrown uses FxHash by default, and that it also uses SIMD tricks to speed up lookup. Meow is a hashing algorithm that also extensively uses SIMD and that is apparently very fast.
I have very limited knowledge of how this all works, so maybe it's obviously stupid. But: Would it be interesting to combine the two?
There is a port of Meow to Rust here but from quickly glancing at it, it doesn't seem to support std::hash::Hasher
and it might also be difficult to do so as it seems to need to reset some internal data when you'd call finish(&self)
.
The README on this repo claims that aHash is not DOS resistant but on the aHash repo it claims that it is DOS resistant.
Goals
AHash is intended to be the fastest DOS resistant hash for use in HashMaps available in the Rust language. Failing in any of these criteria will be treated as a bug.
(ctrl as i8) >= 0
might be faster because might benefit the sign bit already set (if LLVM doesn't perform this optimization automatically).
In the new benchmark suite, for table sizes just under the capacity, inserting and erasing elements leads to frequent resizes and complete table rehashes.
For SIZE=895:
test insert_erase_std_highbits ... bench: 16,548,714 ns/iter (+/- 1,936,585)
test insert_erase_std_random ... bench: 16,376,567 ns/iter (+/- 1,338,857)
test insert_erase_std_serial ... bench: 14,408,640 ns/iter (+/- 2,043,451)
For SIZE=896:
test insert_erase_std_highbits ... bench: 61,495 ns/iter (+/- 6,014)
test insert_erase_std_random ... bench: 63,244 ns/iter (+/- 3,980)
test insert_erase_std_serial ... bench: 60,410 ns/iter (+/- 13,798)
The benchmark is inserting and removing items in a loop keeping it at the given size, and once we generate one DELETED control byte we get pushed over the growth_left limit. We're then forced into a resize for a table of the same size as the one we started with. Ideally the amortized cost of insert/remove should be constant.
As rust-lang/rust#58623 has landed we should probably move this to the rust-lang org. If you add me or @pietroalbini as admins to this repo, we can do this move (I think you need to have admin on rust-lang to move a crate there)
This might seem impertinent, but since this is the HashMap
of the Rust standard library and std
is 1.x, when can this crate become 1.x itself?
Obviously that wouldn't halt development any more than the standard library doesn't develop, but it would mark to direct users of the crate (as the Readme suggests a person might want to do) that they can rely on the direct crate usage not breaking out from under them just as much as they can rely on using this through std
won't break out from under them.
This isn't yet part of std::collections::HashMap
's API, but has a number of features that cannot be done in the current API. It would be extremely nice if these could be done with hashbrown.
For background, see:
This may be an exceptionally niche use-case but I figured I'd bring it up anyway. In Noria, we use a hash table as a sort of cache, and occasionally we want to evict a random element from the map. Unfortunately, there is no good way of getting that efficiently (in hashbrown
or in std::HashMap
). map.keys().skip(rand(map.len()))
for example is far too slow. @fintelia has a fork of std::HashMap
in rahashmap
that we're using, and it:
raw_capacity
remove_element_at_index
at_index
Together, these three operations let us efficiently find a random key/value pair in a map. I realize that this may be fair more internals than you'd like to expose, but some way of getting at/removing a random element would be really handy, as I don't think there's currently a way of doing it through the normally-exposed APIs. Is there any avenue whereby you could imagine a use-case like this being supported? I was toying with the idea of (ab)using RawEntryBuilder::from_hash
, but guessing a hash is very unlikely to yield anything useful, so I think that's out...
The benchmarks should really be using criterion
It would be interesting to benchmark it against bytell-hash-map which I did rust implementation for (Haven't optimised it that much and should really make it usable library).
Disclaimer: This is actually not an issue with hashbrown
but with cargo
.
Topic: no_std support
While hashbrown
itself is able to compile successfully for no_std
targets, and even uses the CI pipeline to verify its compatibility to the thumbv6m-none-eabi
target, it might still trigger issues if used with other dependencies when the default ahash
feature is enabled.
Issue
The dependency tree of ahash
injects the getrandom
crate if the default feature set is enabled. This crate is heavily platform dependent and does not support targets like the thumbv6
or thumbv7
families.
How does this happen?
The underlying issue is an a long standing and well known cargo bug (rust-lang/cargo#5760) which automatically calculates a required feature set for each (sub-)dependency inside the dependency tree regardless of the dependency origin.
If ahash
- with default feature set - is used, it will include the const-random
crate and therefore the proc macro crate const-random-macro
into the dependency tree. This will request the getrandom
feature for the crates rand v^0.7
and indirectly also rand_core v^0.5.1
.
As dependencies of proc macros are compiled for the host and not the target architecture this works fine as long as the host architecture is contained in the following list and the no_std
build should be successful (as you can see inside the CI).
But it is going to fail as soon as one of the following two conditions are true:
The host architecture is not supported.
The target architecture is not supported and the dependency tree contains at least one non proc macro dependency, which requires either rand v^0.7
or rand_core v^0.5.1
, because than the underlying cargo
issue kicks in. Cargo is going to inject the getrandom
feature requirement for these crates, originating from the dependency list of const-random-macro
, into the other dependency so that cargo is trying to compile getrandom
not only for the host architecture but also for the target architecture.
Request
As long as rust-lang/cargo#5760 is still a thing it would be great if at least the hashbrown
documentation could get a warning paragraph explaining this topic including how to work around this issue.
Potential workarounds I can see:
hashbrown
could introduce a way to disable the compile-time-rng
feature of ahash
if default features are disabled.
The relying crate could disable the ahash
feature of hashbrown
and reintroduce another hasher or ahash
without compile-time-rng
feature.
Both might result in ahash
losing the compile time random seed for the hash values.
I find myself in the need of writing a hash map with some custom ownership semantics in regards to keys.
Your internal RawTable
seems to provide exactly the functionality I, with enough flexibility to provide the custom semantics I need.
Would you be open to exposing RawTable
publically, possibly behind a feature flag? I do realize that the API most likely is very unstable and may change, but this is something I would be willing to deal with.
I made a test with the stdlib's hashmap and with this one, hashbrown. The hashbrown version was much faster. In the doc., it's written that the stdlib now uses hashbrown. I guess the stdlib with hashbrown uses a different hash function, which must be slower.
My question: if I want to use the stdlib's hashbrown, how can I configure it to be just as fast as if I had used hashbrown as a dependency?
I don't need DOS-resistance. I just need a very fast hashmap. Thanks.
Hi there!
Yesterday I tried to use this crate as a drop-in replacement for my FnvHashMap
. Surprisingly, it was not faster, but even a bit slower than my previous version. I profiled a bit and noticed that the entry()
API of your implementation is probably suboptimal.
Initially I wrote this:
map.entry(key).or_insert_with(|| produce_value())
To test, I changed it to this:
if map.contains_key(&key) {
map[&key]
} else {
let v = produce_value();
map.insert(key, v);
v
}
In my particular case, the first version runs in 1.96s while the second runs in 1.74s. In my test case, both branches are taken roughly equally often. The code above is executed 3.6 million times and the hashmap ends up with 1.8 million entries. My key is 12 bytes while the value is 4 bytes large.
It's a bit strange that the second version is faster since we have to do two lookups (contains_key
plus either map[&key]
or map.insert(key, v)
). And indeed, FnvHashMap
and the hashmap from std
) get notably slower in the second version. I mean yeah, the memory used for lookup has probably been properly warmed by contains_key
, but we still do unnecessary/duplicate work.
I also wrote this micro benchmark (since my results above are in a bigger codebase). In the micro benchmark, the key is also 4 bytes, but it already shows what I wanted to show.
It's basically only two different benchmarks, which are copied to test them with your hash map, FnvHashMap
and std::collections::HashMap
.
#![feature(test)]
extern crate test;
use hashbrown::HashMap as BrownHashMap;
use fnv::FnvHashMap;
use std::collections::HashMap as StdHashMap;
use self::test::{Bencher, black_box};
const SIZE: usize = 1_000_000;
#[bench]
fn brown_entry(b: &mut Bencher) {
b.iter(|| {
let mut m = BrownHashMap::with_capacity(SIZE / 3);
for i in 0..SIZE as u32 {
black_box(m.entry(i / 3).or_insert(i));
}
})
}
#[bench]
fn brown_manual(b: &mut Bencher) {
b.iter(|| {
let mut m = BrownHashMap::with_capacity(SIZE / 3);
for i in 0..SIZE as u32 {
let key = i / 3;
let v = if m.contains_key(&key) {
m[&key]
} else {
m.insert(key, i);
i
};
black_box(v);
}
})
}
#[bench]
fn fnv_entry(b: &mut Bencher) {
b.iter(|| {
let mut m = FnvHashMap::default();
m.reserve(SIZE / 3);
for i in 0..SIZE as u32 {
black_box(m.entry(i / 3).or_insert(i));
}
})
}
#[bench]
fn fnv_manual(b: &mut Bencher) {
b.iter(|| {
let mut m = FnvHashMap::default();
m.reserve(SIZE / 3);
for i in 0..SIZE as u32 {
let key = i / 3;
let v = if m.contains_key(&key) {
m[&key]
} else {
m.insert(key, i);
i
};
black_box(v);
}
})
}
#[bench]
fn std_entry(b: &mut Bencher) {
b.iter(|| {
let mut m = StdHashMap::with_capacity(SIZE / 3);
for i in 0..SIZE as u32 {
black_box(m.entry(i / 3).or_insert(i));
}
})
}
#[bench]
fn std_manual(b: &mut Bencher) {
b.iter(|| {
let mut m = StdHashMap::with_capacity(SIZE / 3);
for i in 0..SIZE as u32 {
let key = i / 3;
let v = if m.contains_key(&key) {
m[&key]
} else {
m.insert(key, i);
i
};
black_box(v);
}
})
}
The results are:
test brown_entry ... bench: 15,433,281 ns/iter (+/- 6,619,394)
test brown_manual ... bench: 13,233,574 ns/iter (+/- 4,212,542)
test fnv_entry ... bench: 45,841,114 ns/iter (+/- 11,072,757)
test fnv_manual ... bench: 47,913,048 ns/iter (+/- 8,861,713)
test std_entry ... bench: 69,736,423 ns/iter (+/- 14,587,644)
test std_manual ... bench: 84,257,629 ns/iter (+/- 17,948,341)
So only for brownhash
the manual version (without entry()
) is faster, while it's slower for the two other hashmaps (as one would expect).
So it would be awesome if the entry()
API could be improved still. Or is there something about the data structure behind this hashmap that makes it difficult or useless to make the entry APi fast? Thanks!
With the switch to Hashbrow, std::mem::size_of::<std::collections::HashMap<(), ()>>()
on 64-bit platforms grew from 40 bytes to 56. (24 to 40 bytes with BuildHasherDefault
.)
In Servo’s DOM implementation we have types whose size_of
is several hundreds of bytes. Because some not-so-unusual pages can have very many DOM nodes this size can add up to significant memory usage. We have unit tests for size_of
to ensure it does not accidentally grow, which fail in today’s Rust Nightly because several types grew by 16 bytes because they contain a HashMap
.
Hashbrown’s HashMap
contains a RawTable
which has five pointer-sized fields:
Lines 328 to 348 in 7e79b0c
Some of them seem potentially redundant, but I’m not sure. For example there are two pointers that seem to be in the same allocation. How expensive would it be to re-compute the second pointer every time it is needed?
Are bucket_mask
, growth_left
, and len
related such that one of them could be computed from the others?
For my use case I have a worker thread that periodically updates a thread local HashMap and then copies it to another thread. For most iterations no entries are added or removed, only the values change.
I would like to efficiently synchronize the two HashMaps by copying the arrays of control bytes and elements directly to the already allocated arrays of the other HashMap. Basically it would be the same thing that's done in RawTable's clone
function without the extra allocations.
Lines 978 to 1028 in bacb169
I saw that the RawTable was recently exposed in #104 but unless I missed something it is not enough to copy the contents from one map into another. Do you think it would be a good idea to implement clone_from on RawTable which reuses the arrays if possible?
My understanding of the contracts of std::collections::HashMap
is that if a specific capacity is requested through with_capacity()
or reserve()
, then at no point during the lifetime of the map capacity()
would return a quantity that's lower than the requested. This is, however, not the case in the following example:
where for test_with_capacity()
I am seeing the following output:
---- test_with_capacity stdout ----
inserted 1988 capacity = 28
inserted 2666 capacity = 28
inserted 6040 capacity = 28
inserted 25752 capacity = 28
inserted 27146 capacity = 28
inserted 27241 capacity = 28
inserted 27242 capacity = 28
inserted 27243 capacity = 28
inserted 27285 capacity = 28
inserted 27331 capacity = 28
inserted 28712 capacity = 28
inserted 29517 capacity = 28
inserted 32582 capacity = 28
inserted 34410 capacity = 28
inserted 35690 capacity = 28
inserted 38250 capacity = 28
inserted 39274 capacity = 28
inserted 44843 capacity = 28
inserted 48680 capacity = 28
inserted 56389 capacity = 28
inserted 57394 capacity = 28
inserted 61248 capacity = 28
inserted 61510 capacity = 28
inserted 63016 capacity = 28
removed 29517 capacity = 27
thread 'test_with_capacity' panicked at 'assertion failed: `(left == right)`
left: `28`,
right: `27`: map.capacity() != previous_with_capacity', tests/hash_map.rs:65:5
28 is the initial capacity requested.
If you'd like to run the test yourself, do make sure to opt out of the aes
target feature as the test case is based on hashes from the fallback hasher of ahash
.
git clone https://github.com/jakubadamw/hashbrown-capacity-issue-test.git
cd hashbrown-capacity-issue-test
RUSTFLAGS="-C target-feature=-aes" cargo test
Hi,
I'm interested in whether hashbrown can be used for implementing Lua tables for Luster. (Note: I'm not the owner, just someone interested in the project!)
The unusual requirements for Lua's tables are:
next(table, item)
function returns the "next" item in the table, given another.next
has to be stable when removing items during the iteration.I've had a look and think that hashbrown can support this with not much modification, and prototyped it here (a few months ago, so I haven't yet caught up on recent changes; this was before it was moved to rust-lang):
https://github.com/jugglerchris/hashbrown/tree/hash_next
I added a fn next_after(&self, key: Option<&K>) -> Option<(&K, &V)>
which simply steps through hash buckets via a RawIterRange
constructed to point part way through to implement #1, and #2 happens for free by using tombstones when removing (which relies on there not being a resize when shrinking too far; I'm not confident I haven't missed any cases).
I would be interested to know if functionality like this would be considered for hashbrown itself (I could understand not; I can certainly see not wanting to guarantee no resize on removal), or if not whether I've missed any obvious issues if I (or someone else) were to maintain a fork with these changes.
Thanks! I've certainly enjoyed looking through and having a play either way. :-)
Minimal reproducer:
extern crate hashbrown;
fn main() {
hashbrown::HashMap::<(), ()>::new().clear(); // calls `self.table.clear()`
}
When growing a table, hashbrown will start with a table of size 2 (which can hold 1 element due to load factor) and then double every time the load factor is reached.
Table size | Capacity | Memory usage (sizeof(T) = 4 ) |
Memory usage (sizeof(T) = 8 ) |
Memory usage (sizeof(T) = 16 ) |
---|---|---|---|---|
(empty) | 0 | 0 | 0 | 0 |
2 | 1 | 26 (32) | 34 (40) | 50 (56) |
4 | 3 | 36 (40) | 52 (56) | 84 (88) |
8 | 7 | 56 | 88 | 152 |
16 | 14 | 96 | 160 | 288 |
32 | 28 | 176 | 304 | 560 |
(rounded up to 8 for allocator alignment)
In comparison, the current std HashMap starts off empty but then immediately grows to a table size of 32 (capacity 29) as soon as the first element is added.
We want to try to balance memory usage for small tables with the allocation overhead when growing tables up to their final size.
Hi!
It would be useful to have a rough idea about relative memory usage of hashbrown and rustc_hash!
If hashbrown is 2x faster and the same size, it is super cool
If, for example, it is 2x faster but 2x larger, that it is also very cool, but might not fit some projects.
I'm writing a string-interning data structure in a memory-constrained environment. The strings effectively have 'static
lifetime, so I don't need to support deallocation. Therefore, I just append null-terminated strings to a Vec<u8>
buffer and identify a string by its (u32
) offset into this buffer.
Then, we can query a string by its identifier by starting at the given offset and finding the null byte. But, we'd also like to see if a string is already in the buffer and get its offset if so. I'd like to use hashbrown
for maintaining this relation from String
to u32
without duplicating each string in memory twice.
The raw entry API is almost there for supporting this. When looking up a string, we can compute its hash and then use RawEntryBuilder::from_hash
.
struct Offset(u32);
impl Hash for Offset {
fn hash<H: Hasher>(&self, h: &mut H) {
panic!("We shouldn't be hashing the offsets directly!");
}
}
struct InternedTable {
buf: Vec<u8>,
index: HashMap<Offset, ()>,
}
impl InternedTable {
fn lookup(&self, key: &str) -> Option<u32> {
let key_hash = ...;
let result = self.index.raw_entry().from_hash(key_hash, |offset| {
let offset = offset.0 as usize;
key.as_bytes() == &self.buf[offset...min(offset + key.len(), buf.len())]
});
result.map(|(k, v)| k)
}
}
However, doing the same for insertions doesn't quite work. The essential issue is that the raw entry API only lets us control the hash of a single key, and inserting may require recomputing hashes of other keys when resizing.
impl InternedTable {
fn insert(&mut self, key: &str) -> u32 {
let key_hash = ...;
let entry = self.index.raw_entry_mut().from_hash(key_hash, |offset| { ... });
let vacant_entry = match entry {
// String is already in the table, so return its existing offset.
RawEntryMut::Occupied(entry) => return *entry.key(),
RawEntryMut::Vacant(entry) => entry,
};
let offset = self.buf.len() as u32;
self.buf.extend(key.as_bytes());
self.buf.append(0u8);
// Panics here from `Hash` implementation called from `RawTable::resize`
vacant_entry.insert_hashed_nocheck(key_hash, Offset(offset), ());
offset
}
}
Today, I get around this by sneaking in a pointer to buf
via a thread-local to the Hash
implementation. I could also stash a Rc<RefCell<...>>
to the buffer on the hash builder for the same effect. However, both of these solutions are ugly, and given how close it is, it feels to me like the RawEntry
API should support this use case.
Let me know if accommodating this is acceptable and I can submit a PR. It looks like it should be pretty easy since RawTable
already takes in a hasher: impl Fn(&T) -> u64
for many of its methods.
After reviewing the PR unsafe impl
'ing the Send
and Sync
traits I was looking around trying to see if I could trigger unsafe behavior. I didn't find anything with Send
and Sync
, but I think I've found a use-after-free in the pub(crate)
API of RawTable
.
Can someone take a look at this and make sure I'm not crazy? Again, this is in the non-exposed API, so it's not urgent, but it's always good to make unsafety impossible even internally to the codebase.
fn main() {
let table = RawTable::new();
let hash_builder = DefaultHashBuilder::new();
let k = 50;
let v = 500;
let hash = make_hash(&hash_builder, &k);
table.insert(hash, (k, v), |x| make_hash(&hash_builder, &x.0));
let raw_iter = table.iter();
drop(table); /* drops the pointers to data? */
for bad in raw_iter {
/* badness ensues */
}
}
Hi,
I saw the RFC for rust-lang/rust#43244, and was wondering if there was an equivalent need for drain_filter
-esque behaviour with hashmaps? I've thought about using drain and then reconstructing another HashMap, but I would like to avoid the cost of that.
I also thought about using retain and putting items that weren't retained into a Vec
, but I can't take ownership of the items being removed unless I clone/copy them.
In this case, I'm trying to minimize the number of allocations I'm making while taking some items out of a hashmap and putting them into a buffer passed in from elsewhere. The main issue with the retain approach is the inability to not take ownership.
I might be able to dig into the raw
api to get something, but I was wondering if this was common enough to be added to the safe api.
I can't seem to find another RFC for this anywhere, and I'm not sure if this is the relevant place to request this, but I thought since this was the underlying implementation for the hashmap it would be good to request it here.
Thanks!
It seems like hashbrown structures doesn't implement Send making it very hard to use them in multithreaded applications
For example, attempt to return them from thread via join handle:
extern crate hashbrown;
fn main () {
std::thread::spawn(move || { hashbrown::HashSet::new() } );
std::thread::spawn(move || { hashbrown::HashMap::new() } );
}
Wouldn't compile
➜ cargo build
error[E0277]: `std::ptr::NonNull<u8>` cannot be sent between threads safely
--> src/main.rs:4:5
|
4 | std::thread::spawn(move || { hashbrown::HashSet::new() } );
| ^^^^^^^^^^^^^^^^^^ `std::ptr::NonNull<u8>` cannot be sent between threads safely
|
= help: within `hashbrown::HashSet<_>`, the trait `std::marker::Send` is not implemented for `std::ptr::NonNull<u8>`
= note: required because it appears within the type `hashbrown::raw::RawTable<(_, ())>`
= note: required because it appears within the type `hashbrown::HashMap<_, ()>`
= note: required because it appears within the type `hashbrown::HashSet<_>`
= note: required by `std::thread::spawn`
error[E0277]: `std::ptr::NonNull<(_, ())>` cannot be sent between threads safely
--> src/main.rs:4:5
|
4 | std::thread::spawn(move || { hashbrown::HashSet::new() } );
| ^^^^^^^^^^^^^^^^^^ `std::ptr::NonNull<(_, ())>` cannot be sent between threads safely
|
= help: within `hashbrown::HashSet<_>`, the trait `std::marker::Send` is not implemented for `std::ptr::NonNull<(_, ())>`
= note: required because it appears within the type `hashbrown::raw::RawTable<(_, ())>`
.....
Passing ownership of the key to the entry()
function can be costly. Especially if then 'common' case is that an element is found this enforces cloning the key for every lookup.
What I would like is to propose a version of the entry function (so far I've not come up with a good name) that takes a a borrowed key and enforces that the ToOwned trait exists. This way the underlying structure can clone/own the key only when required.
I'm happy to make a PR for this but I wanted to discuss the option first to ensure there is interest, make sure that I didn't overlook something blocking, and to find a good and useful name.
Many thanks for the library!
Unfortunately, library does not work along with the rayon. What am I doing wrong?
use hashbrown::HashMap;
use rayon::prelude::*;
fn main() {
let mut test = HashMap::new();
test.insert("1", 1);
test.insert("2", 2);
test.insert("3", 3);
let vec: Vec<usize> = test.par_iter().map(|(_, val)| *val).collect();
println!("len: {}", vec.len());
}
error[E0599]: no method named `par_iter` found for type `hashbrown::map::HashMap<&str, {integer}>` in the current scope
--> src\main.rs:10:32
|
10 | let vec: Vec<usize> = test.par_iter().map(|(_, val)| *val).collect();
| ^^^^^^^^
|
= note: the method `par_iter` exists but the following trait bounds were not satisfied:
`hashbrown::map::HashMap<&str, {integer}> : rayon::iter::IntoParallelRefIterator`
error: aborting due to previous error
Cargo.toml
[dependencies]
hashbrown = "0.1.8"
rayon = "1.0.3"
cargo 1.34.0-nightly (5c6aa46e6 2019-02-22)
The current code base only has the doctests from the standard library HashMap
. We should add a proper testsuite.
Possible sources of inspiration:
As mentioned briefly in: #71
The benchmarks at present rely on sequential integers. This leads to a serious bias. If the hashmap grows every time it reaches its capacity limit, by the birthday paradox there should be a number of bucket collisions along the way. Hashbrown performs well in this case by storing one byte of the hash code to attempt to resolve the hash collision without having to resort to comparing the keys.
Unfortunately despite the fact that this code path is expected to be common in real life (See footnote) and important to the overall performance of the map, none of the benchmarks presently ever exercise it. (This is because the FxHash is just a single multiplication, so the increasing integers always have evenly spaced low order bits.)
If the benchmarks were changed to instead use random keys, this code path would be exercised and the performance numbers would be more meaningful.
Footnote: (back of the envelope math based on the formula here http://matt.might.net/articles/counting-hash-collisions/ is that as n approaches d and they both get larger the probably of a bucket collisions approaches e^-1 or ~36% when the map is filled. When it is midway between having being resized and needing to be resized again it is ~25%. So we can expect to need to compare the stored byte about a quarter of time.)
I hope I'm not blind and missed the reason as for why this is but I noticed that HashMap
doesn't seem to implement the IndexMut
trait. Is there a specific reason for why this is?
Currently, the README claims that hashbrown is faster than itself 😄
I built a simple memory allocator and set it as global. When I tried to run the test, I got EXC_BAD_ACCESS (code=EXC_I386_GPFLT)
under Mac OS X.
This is the stack
hashbrown::raw::RawTable$LT$T$GT$::reserve_rehash::h89b32432d29be057 0x000000010bba88b1
hashbrown::raw::RawTable$LT$T$GT$::reserve_rehash::h89b32432d29be057 0x000000010bba88b1
hashbrown::raw::RawTable$LT$T$GT$::reserve_rehash::h89b32432d29be057 0x000000010bba88b1
hashbrown::raw::RawTable$LT$T$GT$::reserve_rehash::h89b32432d29be057 0x000000010bba88ac
hashbrown::raw::RawTable$LT$T$GT$::reserve_rehash::h89b32432d29be057 0x000000010bba88a5
hashbrown::raw::RawTable$LT$T$GT$::reserve_rehash::h89b32432d29be057 0x000000010bba886c
term::terminfo::parser::compiled::parse::hbece3b8f1d06cb9e 0x000000010b95a974
This is the what I see in the disassembler
hashbrown::raw::RawTable$LT$T$GT$::reserve_rehash::h89b32432d29be057:
movdqa (%r15), %xmm0
I assume I did not get the alignment right for movdqa
instruction, but content of r15
is 0x000000011355f858
when the mmap returned address is 0x0000000113559000
The code to my allocator is at
https://github.com/ShisoftResearch/Nulloc/blob/a28b93b3647b9628a4c3d247d52257a88a756cd8/src/bump_heap.rs
Hi, I'm very new to rust and just playing around with hash maps and I found that using the code below, the std::collections::HashMap
is significantly faster than hashbrown. I'm wondering if someone could explain this? Is hashbrown only meant to be faster for certain types of data? Or am I doing something wrong?
use hashbrown::HashMap;
//use std::collections::HashMap;
use rand::Rng;
use std::time::Instant;
use numtoa::NumToA;
fn main() {
let mut m = HashMap::new();
let mut rng = rand::thread_rng();
let now = Instant::now();
let mut i = 0;
let mut last_time = now.elapsed().as_millis();
while i < 10000000 {
let mut key_buf = [0u8; 10];
let mut value_buf = [0u8; 10];
let key = rng.gen_range(0, 2u32.pow(31)).numtoa_str(16, &mut key_buf);
let value = rng.gen_range(0, 2u32.pow(31)).numtoa_str(16, &mut value_buf);
m.insert(key.to_owned(), value.to_owned());
i += 1;
if i%1000000 == 0 {
let now_time = now.elapsed().as_millis();
println!("{} {}", i, now_time-last_time);
last_time = now_time;
}
}
}
Here's my laptop's output for hashbrown::HashMap
:
1000000 943
2000000 1749
3000000 1388
4000000 2739
5000000 1433
6000000 1811
7000000 2548
8000000 3885
9000000 1603
10000000 1852
And here's my laptop's output for std::collections::HashMap
:
1000000 709
2000000 738
3000000 513
4000000 1062
5000000 527
6000000 573
7000000 677
8000000 1479
9000000 550
10000000 569
h1
will fail on 32-bit targets if a hasher yields a u64
greater than u32::MAX
:
https://github.com/Amanieu/hashbrown/blob/9068eb7a2268d879dc4453ac72238e8a992f1469/src/raw/mod.rs#L120-L126
The comment in h2
gives some insight to this, but that only applies to FxHash
:
https://github.com/Amanieu/hashbrown/blob/9068eb7a2268d879dc4453ac72238e8a992f1469/src/raw/mod.rs#L131-L138
See also the failure in rust-lang/rust#58623 (comment)
Currently, hashbrown
is only no_std
with the nightly feature enabled. Since alloc
will be stable in 1.36.0, I think it can be no_std
even on stable then.
A feature that enables these Hash{Map,Set}
s to be used with serde (like std::collections
) would be awesome.
I wonder how much of an overhead would be to store hash codes to prevent the worst case [1].
This would be nice as an optin as there's an obvious trade-off with this: memory overhead and insert performance on fully pre allocated tables would be worse.
[1] resizing hash tables which keys are somewhere else in memory (strings) and/or are hard to hash and/or the hasher is slow (like sip).
error[E0599]: no method named `entry` found for type `hashbrown::map::HashMap<rusttype::GlyphId, M>` in the current scope
--> livesplit-core\src\rendering\glyph_cache.rs:31:21
|
31 | self.glyphs.entry(glyph).or_insert_with(|| {
| ^^^^^
|
= note: the method `entry` exists but the following trait bounds were not satisfied:
`hashbrown::map::DefaultHashBuilder : core::hash::BuildHasher`
ed0b240 still builds. So it's either the raw API or more likely AHash that broke it.
First: thanks for your talk last night, very enjoyable!
This morning I tried using this new hashmap implementation in my own code as a replacement for libstd's HashMap.
The following code leads to a crash (extracted from my own code and minimized):
extern crate hashbrown;
use hashbrown::HashMap;
fn main() {
let mut htab = HashMap::new();
htab.insert(51419, 3);
htab.insert(32640, 9);
htab.insert(32475, 22);
}
Error output:
Compiling hashbrown-bug v0.1.0 (/Users/jrediger/projects/rust/hashbrown-bug)
Finished dev [unoptimized + debuginfo] target(s) in 0.96s
Running `target/debug/hashbrown-bug`
thread 'main' panicked at 'assertion failed: is_special(ctrl)', /Users/jrediger/.cargo/registry/src/github.com-1ecc6299db9ec823/hashbrown-0.1.0/src/raw/mod.rs:62:5
stack backtrace:
0: 0x109f0caff - std::sys::unix::backtrace::tracing::imp::unwind_backtrace::hd303b0cd45bccf60
at libstd/sys/unix/backtrace/tracing/gcc_s.rs:49
1: 0x109f0497d - std::sys_common::backtrace::print::hf2fe31942821bdcb
at libstd/sys_common/backtrace.rs:71
at libstd/sys_common/backtrace.rs:59
2: 0x109f0e543 - std::panicking::default_hook::{{closure}}::h748cb38cc840cba6
at libstd/panicking.rs:211
3: 0x109f0e2cc - std::panicking::default_hook::h81d2ef89c2ad110e
at libstd/panicking.rs:227
4: 0x109f0ebb7 - <std::panicking::begin_panic::PanicPayload<A> as core::panic::BoxMeUp>::get::hc265418ddf96c674
at libstd/panicking.rs:477
5: 0x109f0e71c - std::panicking::continue_panic_fmt::h2d9dbf1e069d262d
at libstd/panicking.rs:391
6: 0x109f0e608 - std::panicking::try::do_call::hcfe6ac53944e0624
at libstd/panicking.rs:326
7: 0x109f47931 - core::ptr::drop_in_place::h2136aea44990720c
at libcore/panicking.rs:77
8: 0x109f47866 - core::ptr::drop_in_place::h2136aea44990720c
at libcore/panicking.rs:52
9: 0x109f01020 - hashbrown::raw::special_is_empty::hd3788a278ef6424a
at /Users/jrediger/projects/rust/hashbrown-bug/<::core::macros::panic macros>:3
10: 0x109efe68e - <hashbrown::raw::RawTable<T>>::insert::h3b2c729d59f9a98d
at /Users/jrediger/.cargo/registry/src/github.com-1ecc6299db9ec823/hashbrown-0.1.0/src/raw/mod.rs:614
11: 0x109eff8a2 - <hashbrown::map::HashMap<K, V, S>>::insert::h8ea3dcf9ba9cb1e3
at /Users/jrediger/.cargo/registry/src/github.com-1ecc6299db9ec823/hashbrown-0.1.0/src/map.rs:789
12: 0x109f01571 - hashbrown_bug::main::h8e60525e2e5179d7
at src/main.rs:9
13: 0x109f001e1 - std::rt::lang_start::{{closure}}::hc81fccad58df1a5d
at libstd/rt.rs:74
14: 0x109f0e5e7 - std::panicking::try::do_call::hcfe6ac53944e0624
at libstd/rt.rs:59
at libstd/panicking.rs:310
15: 0x109f1ad6e - macho_symbol_search
at libpanic_unwind/lib.rs:103
16: 0x109f0a49c - std::sys_common::bytestring::debug_fmt_bytestring::h2a45b81d7d291ba2
at libstd/panicking.rs:289
at libstd/panic.rs:392
at libstd/rt.rs:58
17: 0x109f001c1 - std::rt::lang_start::h0cd91951811e88d1
at libstd/rt.rs:74
18: 0x109f015c1 - hashbrown_bug::main::h8e60525e2e5179d7
Hardware: MacBook Pro running macOS High Sierra 10.13.6 on an Intel Core i7
The original raw_hash_set
code assigns the last control byte to a special "sentinel" value: https://github.com/abseil/abseil-cpp/blob/3088e76c597e068479e82508b1770a7ad0c806b6/absl/container/internal/raw_hash_set.h#L1836. I don't understand the purpose, but since I see you don't do this in hashbrown, I suppose that you might have understood. Could you please share the idea?
As I understand the purpose of this crate, the only thing that is different from std::collections::Hash{Map, Set}
and other hash-based data structures from other crates is a different hasher. If that is not true, then what I'm saying below is unapplicable, so feel free to close.
The goal is to eliminate the need to maintain a separate Hash{Map, Set}
and also reuse impls for Hash{Map, Set}
defined in other crates (provided that they are generic over the hasher) so that we don't have to provide them either.
For example, that's how both fxhash
and fnv
do:
FxHashMap
and FnvHashMap
;FxHashSet
and FnvHashSet
;FxBuildHasher
and FnvBuildHasher
.This is technically a breaking change since the semantics of hashbrown::HashMap
and hashbrown::HashSet
might be altered in some ways (that I don't know of, unfortunately).
Solving this issue will help solving https://github.com/Amanieu/hashbrown/issues/6 as well.
We currently use FxHash
as the default hash function, but this function handles aligned values poorly: when hashing an integer, if the low X bits of the input value are 0 then the low X bits of the hash value will also be 0.
One option would be to copy Google's CityHash (used by SwissTable). This uses a long multiple and XORs the top and bottom words of the result together:
impl FxHasher {
#[inline]
#[cfg(target_pointer_width = "32")]
fn add_to_hash(&mut self, i: usize) {
let tmp = self.hash.wrapping_add(i) as u64 * 0xcc9e2d51;
self.hash = (tmp >> 32 ^ tmp) as usize;
}
#[inline]
#[cfg(target_pointer_width = "64")]
fn add_to_hash(&mut self, i: usize) {
let tmp = self.hash.wrapping_add(i) as u128 * 0x9ddfea08eb382d69;
self.hash = (tmp >> 64 ^ tmp) as usize;
}
}
It'd be great to have Rayon compatibility for hashbrown's HashMap
and HashSet
. I think it's a case of implementing IntoParallelIterator
, FromParallelIterator
and ParallelExtend
.
Hi,
I'm still trying to figure out why it happens (it's not easy to get backtrace on a panic without std)
But I'm getting a panic here:
thread panicked at 'Box<Any>', /root/.cargo/registry/src/github.com-1ecc6299db9ec823/hashbrown-0.3.0/src/raw/mod.rs:1078:9
If that's a known thing or if you have any ideas help is welcome :)
Thanks!
Line 1078 in 4368aa4
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.