Inexplicable nondeterministic behavior in scientific computing code

[jw013]

The documentation may be inaccurate by omission - it should be accurate within a single process but across processes the behavior is different. Looking at the underlying code, with_seeds uses the parameters as passed but with_seed mixes in

static SEEDS: OnceBox<[[u64; 4]; 2]> = OnceBox::new();

SEEDS.get_or_init(|| {
        let mut result: [u8; 64] = [0; 64];
        getrandom::getrandom(&mut result).expect("getrandom::getrandom() failed.");
        Box::new(result.convert())
})

[reidprichard]

I'm glad I'm not just a dummy who didn't read the with_seed docs well enough.

But doesn't:

all RandomStates created from the same key will produce identical hashers

Explicitly read that for a given key, you'll get an identical hash function each time (no matter what process, architecture, etc)? Am I misreading that?

Edit: I've apparently reached my message limit for the day (??) so that's all for now.

[jw013]

Writing good documentation is hard. I see that the docs for the top level type have a handy table:

Constructor	Dynamically random?	Seed
new	Each instance unique	RandomSource
generate_with	Each instance unique	u64 x 4 + RandomSource
with_seed	Fixed per process	u64 + static random number
with_seeds	Fixed	u64 x 4

but the wording of the individual methods is legitimately confusing and may have room for improvement.

[ZyX-II]

Vec lookup is essentially ptr + index * element_size, hash is much more work as you need to generate hash from key to get index, then search for actual key location (multiple keys may want to be stored at the same index) and only then you get to see the contained element. While you do get something like constant-time lookup with hashes (note: it can be linear in the worst case of storing multiple different keys with same hashes!) the constant is much bigger.
Linear-time lookup is what you see in case of something like linked lists and Rust does not implement Vecs with them.

[jumpnbrownweasel]

@reidprichard

for key in 0..hashmap.len() {
  let value = &hashmap[&key];
  ...
}

This code indicates that your hashmap keys are just sequentially assigned integers, which is a special case since all you need is an array and your keys are just indexes into that array. Indexing an array is very fast, and in fact a hashmap does indexing also after it hashes your key. So the hashing is extra work that you don't need in this case.

A Rust Vec is just a heap allocated array, although unlike an array it is growable. If you know the length in advance you can preallocate it using Vec::with_capacity so it will never need to grow. Then when you call Vec::push it will add an entry whose index is Vec::len() (before the push), and no memory allocation is performed. I've assumed here that you are sequentially assigning the keys by incrementing a counter.

[ZyX-II]

There are also notable differences in various performance aspects:

1. Hash table generally will not store your keys in order. If you want to iterate with for key in 0..hashmap.len() you may find out that hash stored your data in the 0, 2, 4, …, 1, 3, 5, 7, … and you get cache misses on every single iteration (this is the worst case, of course, but generally do not iterate with for key in 0..hashmap.len(), you may be not too far off from the worst case in practice if you have large number of elements).
2. Hash table is wasting memory storing those keys in first place. And processor cycles and cache accessing stored keys.
3. Hash table is wasting even more memory as hash tables generally work better if there is free space available. (Note: Vec will do the same unless you specified capacity early enough.)

[parasyte]

@reidprichard

Edit 2: I stand corrected - changing the iteration methods as described above fixed the issue even without the fixed hash generator.

It should be pointed out that you can use BTreeMap instead of HashMap for ordered iterations. I provided a suggestion to correctly fix the HashMap seeding, but I doubt it's ideal. An ordered map is purposely designed for use cases like yours.

Note: This presumes that your maps purposely have holes. (e.g. a sparse vector) If you don't have holes, use Vec as recommended by @jumpnbrownweasel.

[reidprichard]

Sorry for the delayed response - apparently there's a post limit within your first day on the forum.

Thank you all for your explanations! Like I said, this is a learning project, so discovering what's going on under the hood is way more important than getting the optimum solution.

I guess I should have done more digging into claims that hashmap is faster. I could not imagine how that would be the case unless the vec needed to be moved around on the heap a lot as it grew. And I guess even that's not the case - good to know that Rust's hashmap ultimately boils down to an array lookup. I assumed it worked like C++'s map, which I believe scatters values all over the place in memory.

I didn't notice a major impact on performance when I switched how I'm iterating over the hashmap elements (e.g. from for (k,_) in values to for k in values.len(), but that makes sense that it would cause cache misses.

I had glanced over BTreeMap but wasn't sure about it. Are there any downsides compared to HashMap? Worse performance when you're accessing elements out of order perhaps?

I switched to vecs, and the program saw an overall 14% performance increase with 8k, 16k, and 32k elements in the three datastructures. That's huge, because last time I ran perf on the program about 70% of the execution time was in a routine that isn't touching the hashmaps (now vecs). That means that on average it's taking <50% the time to access a vec element than it was taking to access a hashmap element.

[kpreid]

@reidprichard

I had glanced over BTreeMap but wasn't sure about it. Are there any downsides compared to HashMap? Worse performance when you're accessing elements out of order perhaps?

A BTreeMap is built on a classic heap-allocated tree data structure: nodes containing pointers to their child nodes. The implementation is like this (with the unsafe extra-cleverness removed):

struct LeafNode<K, V> {
    len: u16,
    keys: [Option<K>; CAPACITY],
    vals: [Option<V>; CAPACITY],
}
struct InternalNode<K, V> {
    data: LeafNode<K, V>,
    edges: [Edge<K, V>>; 2 * B],
}
enum Edge<K, V> {
    None,
    Leaf(Box<LeafNode<K, V>>),
    Internal(Box<InternalNode<K, V>>),
}

So, if you consider the process of finding an arbitrary element in the map, it has to follow several pointers (how many depending on the size of the tree) and load those InternalNodes from main memory, and at each node it has to compare (with Ord) the wanted key to the entries stored in that node, before it knows which edge to follow to continue the search. On the other hand, a HashMap keeps all its entries in a single vector, so the data is more densely packed and more likely to be in cache from a previous lookup, and in the typical case the cost of a lookup is one Hash (to determine where to look in the vector) and some small number of Eqs to confirm that the found entry has the correct key or if it was instead a hash collision.

I don't quite have all the technical details to present a complete justification of this claim myself, but broadly, it's just that a HashMap is flatter in terms of indirections, and therefore works better with modern computer architectures.

But that doesn't mean you always shouldn't use BTreeMap:

• If ordering is useful to your algorithm, then BTreeMap may be the best way to get it, overall.
• In general, all general claims about performance are contingent on characteristics of the specific problem — it is necessary to run benchmarks to be really sure which implementation is better.

[khimru]

@reidprichard

I assumed it worked like C++'s map, which I believe scatters values all over the place in memory

C++ map was created by Stepanov more than 30 years ago. And since C++ ABI ossified it can not be changed. But modern C++ containers, like flat_hash_map work in the exact same way as Rust containers.

@reidprichard

Worse performance when you're accessing elements out of order perhaps?

Indirections. They are very costly on modern hardware.

@reidprichard

That means that on average it's taking <50% the time to access a vec element than it was taking to access a hashmap element.

Yes, accessing memory and calculating hash take similar time. And BTreeMap would need more that two memory access, except if it's very small. That's why usually HashMap is faster. Of course Vec is even faster if, most of the time, you are just processing elements in order.

@kpreid

In general, all general claims about performance are contingent on characteristics of the specific problem — it is necessary to run benchmarks to be really sure which implementation is better.

While true it's also important to remember these Numbers Every Programmer Should Know and be able to do simple “back of the envelope” calculations.

Simply because it's not possible to benchmark all possible combos, you only may compare finite (and small) number of combinations.

[blonk]

@khimru

And since C++ ABI ossified it can not be changed.

From the linked page:

Making std::regex faster (it is currently faster to launch PHP to execute a regex than it is to use std::regex

If only the point here was that PHP launches very fast.

[paramagnetic]

@reidprichard

Correct me if I'm wrong (again, no formal CS background here), but I have read that large hashmaps generally perform better than large vecs

This is why you should think about what you are doing and, more importantly, why you are doing it, instead of just blindly following advice.

What they were probably trying to tell you is a hash map can provide constant-time lookup for arbitrary types of keys, without having to search through all keys using linear search.

But when you already have consecutive integer indices, then all of the hashing gymnastics is entirely useless and in fact makes your code slower. Indexing a regular flat array with an integer index is constant-time (the constant typically being much, much smaller than a hash map), modulo the complications relating to cache locality and pre-fetching.