New Dict implementation for Elm, now done

[robin.heggelund]

For the last couple of months I’ve been writing a new Dict implementation for Elm. I’m happy to report, that work is now finished.

The previous reports can be read on the old elm-dev mailing list (google groups), but the jist of it is:

get: same performance
insert: 50-150% faster
remove: 95-140% faster
update: -19 to +32% change
fromList: 215% faster (if the list is sorted -> 4100% faster)
filter: 900% faster
partition: 1400% faster
union: 500-870% faster
diff: 500-750% faster
intersect: 600-900% faster

The library is API-compatble (just change the import-statement and you’re ready to go) and available at: http://package.elm-lang.org/packages/Skinney/elm-dict-exploration/latest

Some of you will notice that the numbers are very high, even compared to the last status report. Since last time, @justinmimbs discovered a trick for building up a Dict super quick form a sorted list. That implementation is now used in fromList, filter, partition, union, diff and intersect. And as you can see, it’s working really well. Thank you Justin!

I’ve personally spent some time this past week benchmarking different scenarios, and it seems these numbers scale pretty well regardless of sample size or key-type.

I’d love to hear experience reports from people using this in their own apps. I’d love to hear if people can replicate this benchmark results, and I’ll fix any bugs discovered.

Other than that, I consider this library complete =)

[avh4]

@robin.heggelund

discovered a trick for building up a Dict super quick form a sorted list. That implementation is now used in fromList

(in case this is useful to others)
I was curious about this so I took a look at the code to find that the new fromList works by breaking the list into sorted subsequences, and then inserting each subsequence into the dict. elm-dict-exploration/src/Dict/LLRB.elm at 1.0.4 · robinheghan/elm-dict-exploration · GitHub

[justinmimbs]

@avh4

the new fromList works by breaking the list into sorted subsequences, and then inserting each subsequence into the dict. elm-dict-exploration/src/Dict/LLRB.elm at 1.0.4 · robinheghan/elm-dict-exploration · GitHub

If you’re curious, there’s a function called fromSortedList, and it builds a dict from the bottom up, one level at a time. There’s an illustration of the technique here: B-tree - Wikipedia

In the lines highlighted above, fromList splits the list into its sorted, distinct prefix (if any) and the remainder (if any), so that it can use fromSortedList to quickly build from the sorted part, and then use insert to add the remainder.