I stum­bled upon this inter­est­ing ques­tion on Stack­Over­flow today, Jon Harrop’s answer men­tions a sig­nif­i­cant over­head in adding and iter­at­ing over a Sorted­Dic­tionary and Map com­pared to using sim­ple arrays.

Think­ing about it, this makes sense, the Sorted­Dic­tionary class sorts its con­stituent key-value pairs by key, which will nat­u­rally incur some per­for­mance overhead.

F#‘s Map con­struct on the other hand, is immutable, and adding an item to a Map returns the result­ing Map – a  new instance of Map which includes all the items from the orig­i­nal Map instance plus the newly added item. As you can imag­ine, this means copy­ing over a lot of data when you’re work­ing with a large map which is an obvi­ous per­for­mance hit.

This is a sim­i­lar prob­lem to using List.append ( or equiv­a­lently using the @ oper­a­tor ) on lists as it also involves copy­ing the data in the first list, more on that on another post.

Any­how, the ques­tion piqued my inter­est and I had to test it out and get some quan­ti­ta­tive num­bers for myself, and I was also inter­ested in see­ing how the stan­dard Dic­tio­nary class does com­pared to the rest. :-)

The test code is very sim­ple, feel free to take a look here and let me know if them are unfair in any way. In short, the test was to add 1,000,000 items and then iter­ate over them with each type of con­struct and record the time each step took.

The results are below, the times are recorded in sec­onds, aver­aged over 5 runs.

image

Aside from the fact that the Map con­struct did par­tic­u­larly poorly in these tests, it was inter­est­ing to see that ini­tial­iz­ing a Dic­tio­nary instance with suf­fi­cient capac­ity to begin with allowed it to per­form twice as fast!

To under­stand where that per­for­mance boost came from, you need to under­stand that a Dic­tio­nary uses an inter­nal array of entry objects (see below) to keep track of what’s in the dictionary:

image

When that inter­nal array fills up, it replaces the array with a big­ger array and the size of the new array is, roughly speak­ing, the small­est prime num­ber that’s >= cur­rent capac­ity times 2, even though the imple­men­ta­tion only uses a cached array of 72 prime num­bers 3, 7, 11, 17, 23, 29, 37, 47, … 7199369.

So when I ini­tial­ized a Dic­tio­nary with­out spec­i­fy­ing its capac­ity (hence capac­ity = 0) and pro­ceed to add 1 mil­lion items it will have had to resize its inter­nal array 18 times, caus­ing more over­head with each resize.

Clos­ing thoughts…

Again, these results should be taken at face value only, it doesn’t mean that you should never use Map because it’s slower than the other struc­tures for addi­tions and iter­a­tions, or that you should start replac­ing your dic­tio­nar­ies with arrays…

Instead, use the right tool for the right job.

If you’ve got a set of sta­tic data (such as con­fig­u­ra­tion data that’s loaded when your appli­ca­tion starts up) you need to look up by key fre­quently, a Map is as good a choice as any, its immutabil­ity in this case ensures that the sta­tic data can­not be mod­i­fied by mis­take and has lit­tle impact to per­for­mance as you never need to mutate it once initialized.

Share

8 Responses to “Performance Test — SortedDictionary vs Dictionary vs Map vs Array”

  1. […] Sim­i­larly, ini­tial­iz­ing an instance of Dictionary<TKey, TValue> with the intended capac­ity allows you to add items to it much more effi­ciently, for more details, see here. […]

  2. JW says:

    It would be nice to show num­bers for smaller cases as well, say for 10, 100, 1000, 10,0000 and 100,000 elements.

  3. Daniel says:

    I just ran a sim­i­lar test myself after run­ning into poor per­for­mance with maps. I was shocked to see how much worse the map was than vir­tu­ally any other col­lec­tion, and I started won­der­ing what niche it fills that dic­tio­nary doesn’t. Oth­er­wise, why wouldn’t the F# team just throw dic­tio­nary code in an immutable wrap­per and call it a day?

    The more I thought about it, the more I began to real­ize exactly how dif­fer­ent map and dic­tio­nary are. Noth­ing can change a map, so any time it’s used, you have a 100% guar­an­tee that it’s exactly as it was when it was cre­ated. That hold true for each iter­a­tion of mod­i­fi­ca­tions (add, remove, etc), so in the­ory one could cre­ate an absurdly ridicu­lous func­tion that keeps a copy of each step of construction.

    With a dic­tio­nary, you would have to copy the entire object with every mod­i­fi­ca­tion in order to achieve the same results, and I have a feel­ing that copy­ing a dic­tio­nary 1,000,000 times dur­ing an iter­a­tive build wouldn’t be very pretty–for you, your mem­ory, or your CPU. Some­thing tells me that map’s red-black trees play a big role in this, but I’ll leave that for oth­ers to test out.

  4. theburningmonk says:

    @Daniel — the prob­lem with Map or other sim­i­lar immutable col­lec­tion is that, when you mod­ify it the exist­ing tree gets copied in its entirety which is what makes it so bad performance-wise.

    Clo­jure solves this prob­lem with its per­sis­tent data struc­tures by using a tech­nique called Path Copy­ing where muta­tion only requires mod­i­fi­ca­tion to a sub­set of the nodes, you should watch this video and find out more about it: http://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey

    Stef­fen Fork­mann is in the process of port­ing them over to F# : http://www.navision-blog.de/2012/05/29/porting-clojures-persistent-data-structures-to-net-part-1-of-n-persistentvector/

    It’s also worth not­ing that they have already been imple­mented in the CLR ver­sion of Clo­jure:
    https://github.com/clojure/clojure-clr/blob/master/Clojure/Clojure/Lib/PersistentTreeMap.cs
    also I haven’t tested them to see how much bet­ter they are.

  5. Daniel says:

    Well, I ran the test I men­tioned last night. Over 100,000 adds, stor­ing an immutable copy of the map at each iter­a­tion, the process com­pleted in around 500 ms on my machine. Total mem­ory usage for the exe­cutable was about 60 MB.

    I did the same thing with a Dic­tio­nary, and the process took longer and caused an out of mem­ory excep­tion at around 1.4 GB mem­ory usage. The exact same data was used for each process, and I tried sev­eral dif­fer­ent ways of copy­ing the dic­tio­nary prior to each add.

    60 MB vs 1.4 GB (and count­ing) is fairly sig­nif­i­cant. Are you sure that map copies the entire tree, or is dic­tio­nary just that inef­fi­cient at resource uti­liza­tion? Is there some other mechanic at work here I’m missing?

  6. theburningmonk says:

    @Daniel — can you put your test code some­where so I can have a look?

  7. Daniel says:

    I’ll post it some­where tonight so you can have a look, but the code is pretty easy to duplicate.

    let val­ues = [0..100000] |> List.map (fun n -> n, n)
    let map = val­ues |> List.scan (fun map (key, value) -> map |> Map.add key value) Map([])
    let dic =
    val­ues |> List.scan (fun last kvAdd -> let next = new Dic­tio­nary()
    [for (kvPair:KeyValuePair) in last do next.Add(kvPair.Key, kvPair.Value)] |> ignore;
    next ) (new Dictionary())

    Some­thing along those lines to gen­er­ate, other func­tions to iter­ate. I had stop­watches run­ning, and added break­points between gen­er­a­tion of each con­struct to check mem­ory usage.

    I do remem­ber read­ing an arti­cle on F# that high­lighted the key dif­fer­ences between it and other .NET lan­guages. It’s been a cou­ple months so my mem­ory is a bit foggy, but IIRC they jus­ti­fied the con­stant churn­ing of mem­ory with F#‘s ten­dency to reuse struc­ture. This would seem to jive with what I saw in the test.

  8. Daniel says:

    (bug: in the sam­ple above, the new kv pair isn’t actu­ally added to the dic­tio­nary. It was in the test.)

Leave a Reply