Hello community, reading Elm + Google Summer of Code by Evan in the News section, following links, I ended up to the Data Structure Evaluation Website section of the README of Elm’s projects repository. Since I’m learning Data Structures and Elm at the moment I’m interested to know if anyone is working on it, or which the plan is (if any). In the description of the project, there is no link to the repository of the project like for other listed projects in the file. Thank you!
1 Like
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
Thank you for your prompt answer! I’m for sure interested: not sure if I can set it up by myself but I’ll definitively think about it. Visualgo is a (visual) learning resource for data structures and algorithms I know. Did you have something like this in mind?
Regarding the Aside I’m still compiling it and it will take a while…
Oh, I thought of another thing!
Most data structure performance focuses primarily on speed, but in the browser, it is important to also consider the code size. So a change that (1) improves performance of a certain function and (2) increases code size may not be worthwhile for a “general purpose” implementation. Code size is definitely not a big concern in compiler literature, so I would not be surprised if it’s similar in data structures literature.
That site is pretty cool! I think my personal questions are less about learning the structures and more about evaluating implementation A vs B.
So I’d want to be able to say, my situation is roughly:
- 1,000 inserts
- 100,000 lookups
- 0 union
- 0 intersect
Then get some graphs on how different implementations might handle my particular scenario. For example, the info at the top of Data.IntMap does not comment on the relative performance of lookups, so the fact that all those other operations are faster does not help me. Only if lookups are good too.
And in the context of Elm, even if I find something that is strictly faster, it may still not be worthwhile for my particular scenario if the code is 3x larger or something like that.
So for my particular kinds of questions, I would want to start by giving ranges of estimated uses of map, insert, lookup, intersect, etc. And based on the type of my lookup key, some data structures may not work for me. (E.g. if I have user-given strings, assigning densely packed array indexes may not be worthwhile if I’m getting new values over time.)
I don’t know how niche these questions are though 
I know in browsers performance is almost always dominated by DOM changes, but I wonder if WebGL people using Elm have run into similar kinds of data structure questions as in my compiler work. Not sure!
1 Like
thanks for the awesome information.
This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.