Performance testing persistent maps

Persistent maps have the excellent property that they share structure, which enables them to produce copies efficiently. I recently implemented a very simple RecordedMap which keeps a history of all changes that occur so that you can rewind time. Naturally I wanted to know what the overhead I would pay for this feature was, so put together some tests to see:

Map ImplementationTime taken
RecordedMapModel00:00:00.9722224
ClojureRecordedMapModel00:00:04.9654442
Dictionary00:00:00.1727407
Copy Dictionary00:00:17.3513137
FSharpMap00:00:00.7329950
PersistentTreeMap00: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.

No comments:

Post a Comment