aoc-2020 VS hashbrown

I've tried it a few times and solutions were surprisingly elegant! E.g., 2020-01-p2.

Figured I'd post my benches as well, see below. Everything done in Rust (link to source).

Here's my day 24 in Rust, using SIMD as usual :) (and offset coordinate encoding to make a SIMD-friendly 2-D cell grid)

Borrowed both ideas in my version :) On my input your version runs at 3ms, mine in 1.5ms, so it might be faster on some inputs (link). I initially started with something similar to yours but then figured why not use 512-bit ints, so that the notion of 'head' and 'tail' disappears as your head then stays at position 0 (so, e.g., to remove a card, you just right-shift the whole bigint). Also used a tiny bit of simd along the way.

That's because you're looking at a wrapper around the actual implementation (which lives in an external package). Notice "use hashbrown::hash_map as base;" at the top.

There's far more unsafe there: https://github.com/rust-lang/hashbrown/blob/f2e62124cd947b5e...

You might want to check out how popular ecosystem crates do some of these things. Particularly relevant to you are probably crates providing collections, such as smallvec, hashbrown, or indexmap.

https://github.com/topics/swisstable

rust-lang/hashbrown: https://github.com/rust-lang/hashbrown

CuPy has array but not yet hashmaps, or (GPU) SIMD FWICS?

NumPy does SIMD:

Thanks, great point indeed. I am looking into this https://github.com/rust-lang/hashbrown

The way I think about it -- rather naively, I suppose -- is that I care more about the references cells make to each other than the actual grid of cells displayed on a table. The latter feels more like a "view" of the data than an actual data structure?

This also seems to align with the relative priority of (sorted from highest to lowest): figuring out the order of evaluation, calculating those evaluations, and finally displaying the results of the evaluation

updated std's hashbrown dependency to 0.14 which contains some optimizations

The std hashmap is actually very fast and uses state of the art hashmap design, namely because it's implemented by hashbrown

I believe Rust uses hashbrown as the underlying implementation now. This just calculates the number of buckets based on the number of items requested:

https://github.com/rust-lang/hashbrown/blob/009969a860290849...

Is it really the case that rehashing can guarantee that the number of buckets allocated will be sufficient for any given set of keys? In principle you could fail to rehash in a way that reduces collisions after k attempted rehashings.

For example, since the hashbrown crate is marked with #![no_std], it can be used as a dependency for the standard library.

To implement something that cannot be expressed in safe Rust, or at least cannot be expressed succinctly in safe Rust, like fundamental datastructures. The hashbrown crate contains a lot of unsafe code, but it's such high quality that it's now the backing implementation for std::collections::HashMap.