Day 23

Feelings

Part 1 ➟ Yay, let's do VecDeque again!

Part 2 ➟ Why did I make this with VecDeque? FUUUUU~~

VecDeque is absolutely useless in part 2, way too slow to do it like that. Damnit.

So for part 2 I ported the whole thing to HashMap. Thought that if you need to look up a value and find next value you could do this kinda single linked list-ish way, but with good speed for lookups.

Well yeah. It manages to find the solution in about 5 seconds so I guess there's much improvement to do.

Improvement ideas

Good old perf and look at that

I still haven't got cargo flamegraph working for me at all, it just doesn't produce correct results (shows only the module). Maybe it's because of my workspace build?

perf record -g --call-graph dwarf or perf record -g --call-graph fp and then perf report | rustfilt | less work pretty well and I've been using those to figure out performance issues.

Lazy create

Should the whole structure be created before starting to run through it or would it be ok to just lazily populate it?

All of the values above 10 (to 1_000_000) are initially same as the position and the next value is +1 of it. Maybe that can be used as optimization of some kind?

What's the real access pattern anyway?

Try out flat memory structure

First thing is to is to try what happens if, instead of having HashMap, there would just be a vec or just mutable slice. As numbers are unique it should be quite simple to port hashmap version to this very simple flat memory structure with pointers. (even more like a linked list. uhh.)

Something like let mut v: Vec<u32> and having something like v[value] = next_value would be exactly as I have with HashMap, but without hashing. Facepalmed a bit too hard when I understood that. :|

This + compile time constant initializer should be pretty damn fast. Maybe.

Compile time constants

Try to set up some structures beforehand (at compile time). For example array of u32 from 1..1_000_000 that would just get loaded when the binary is loaded could be kinda nice maybe.

This might be nice to try out: compile time static arrays - dev.to