Our great sponsors
-
robin-hood-hashing
Discontinued Fast & memory efficient hashtable based on robin hood hashing for C++11/14/17/20
The standard library sets have somewhat poor performance characteristics because the C++ standard pretty much requires them to be implemented as chaining hashtables, so iterating them can cause a lot of cache misses. You could try a drop in* replacement like robin_hood::unordered_flat_set or look at some benchmarks for possibly better replacements. Again, re-use these instead of returning them.
-
Also, choose a good hash function! A poor one can reduce hashtable performance dramatically, but especially with chaining hashtables since hashing all elements to a couple buckets mean massive linked lists to traverse. I recommend not rolling your own, use a good quality one like xxHash. xxHash also allows you to hash an entire block of bytes at one time.
-
InfluxDB
Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.
-
I got to 120ms for both parts (10 + 110) in C++ with the standard library data structures: https://github.com/nutki/adventofcode/blob/master/2021/23.cpp
-
Mine (rust)runs for 50ms for both parts. I've used just a regular bruteforce approach, so nothing fancy. There are several things I did that reduced the execution time:
-
WorkOS
The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.
