Performance: Building directed graph of game scores (0,0) -> (0,1) etc

[c42f]

@gabiteodoru

But it’s good to know that the dictionary lookup eats a lot of time.

To be clear, Dict is quite amazingly fast when used with types which are cheap to hash; it’s a great simple and robust default. Replacing it in the code above was interesting but I’d say it’s a questionable performance hack unless you really need the speed. You might find the following thread interesting:

IF...ELSEIF...ELSE performance

I need to use an IF…ELSEIF…ELSE statement in a large loop and I therefore did the following test to find the fastest implementation. In the following code a random number between 0 and 5 is chosen. Based on this outcome, the outcome is multiplied by 10. I know this is a silly procedure, but it is purely meant for test purposes. The 0 has the largest occurrence, the 5 the smallest. In the code I implement 3 ways to do so: by a dictionary, by an IF statement that starts testing for the 0 and ends …

@gabiteodoru

using Int16 and Int32 instead of Int64 actually speeds up things (that I found surprising),

The speedup here was relatively minor, but if you have a large dataset and you’re limited by memory bandwidth it can make a huge difference to use smaller width integers. Another related reason to use narrow types would be if your inner loops are naturally data-parallel. In that case the compiler’s SIMD vectorizer might kick in, giving you a speed boost depending on how many elements can fit into your SIMD register at once.

IIRC I got a small benefit out of removing the recursion once I’d optimized some of the other things. I didn’t check in the final version though.

Using sizehint! to avoid rehashing the Dict helped quite a lot. You can sizehint! the arrays as well but that made less of a difference (hence being commented out).

@gabiteodoru

the next parts of my program will be more computationally intensive but will use what I’ve built here, so as long I’m not doing anything wrong, then the next part will make use of the linked nodes, which should be really fast (fingers crossed).

So actually this is the part which you really want to optimize I’d suggest giving LightGraphs.DiGraph a go by feeding it an edge list approximately like the one I’ve built above. I peeked at the light graphs internals and it doesn’t seem to lay out the data quite how I was imagining (ie, in a few big contiguous arrays). Perhaps there’s a different “immutable graph” type you could use which does that. I don’t know a lot about that part of the ecosystem mind you.