| Map Implementation | Time taken |
| RecordedMapModel | 00:00:00.9722224 |
| ClojureRecordedMapModel | 00:00:04.9654442 |
| Dictionary | 00:00:00.1727407 |
| Copy Dictionary | 00:00:17.3513137 |
| FSharpMap | 00:00:00.7329950 |
| PersistentTreeMap | 00:00:04.4958646 |
Comparing a mutable dictionary directly to an immutable persistent FSharpMap we can see a performance cost of about 5x time, which is a little painful. More than I was hoping for, but well within an order of magnitude. So there is definitely a trade-off here.
Keeping a full history of all previous versions of the map adds very little overhead, less than 50% (RecordedMapModel). Using a copy dictionary approach was about 20x as slow.
The Clojure persistent map did not perform as well as the FSharpMap, but still was much better than the mutable copy approach, and within an order of magnitude from having no history. I am confident that the performance hit here is because I am doing some funky casting and/or reflection because I'm not providing type hints. A true test would use an implementation in Clojure and avoid reflection. I didn't go there as I wanted to keep the tests as similar as possible.
Source code used to test is available here:
https://github.com/timothypratley/timetraveltests
I commented out the Clojure parts as you need to get the dependency to make that work. If you want to, simply add Clojure as a reference and copy the clojure binaries into the output folder. I suggest you build from source and match .NET framework targets.
For a 5x time cost you can have an immutable dictionary with a fully recorded history. Something that would take 20x as long if you had to copy the data around. An important difference here is that the persistent map version uses shared structure and so will take up far less memory. Too bad I don't know a good way to measure this.
Yay for clever data-structures.