Data structure project

I still think that is a really interesting project!

I recommend giving it a shot if you are interested! Between charting libraries like elm-charts and raw SVG for visualizing certain structures, I personally feel like a really cool interactive learning resource is possible, and I still haven’t seen anything like it before.


Aside: I still run into this kind of question in my compiler programming! A common experience is that I know something like "I need insert and lookup for ~1000 elements, but not union or intersect", but it is tricky to get an idea of whether it’s even worth exploring whether Data.IntMap is an improvement over Data.Map in my scenario.

One of the best compiler performance improvements I found so far came from avoiding many Map.lookup calls in type inference by caching certain information in the AST in an earlier phase! I forget if that was 0.18 or 0.19, but some people were seeing like 10x or 20x better times from that change alone. If I recall correctly, the Map.lookup calls didn’t show in the profiling, but we knew that importing many modules correlated with the outlier cases, so I made an educated guess from there to pursue avoiding O(log(n)) lookups for types from imported modules. Point is, once you have profiled enough to know that something might be costly, it can still be really hard to evaluate which data structures are even worth exploring!

2 Likes