Re: [Haskell-cafe] Announce: Significant performance improvements for Data.Map

On Sunday 29 August 2010 18:48:32, Johan Tibell wrote:

On Sun, Aug 29, 2010 at 3:41 PM, Daniel Fischer wrote:

...

That is great. Have you any data about the speedup relative to map sizes? Milan Straka's benchmarks ran only on very small maps (<= 2^10 elements), I'd be interested in whether size plays a significant role in the effect.

I just ran an ad-hoc test to get an indication of of the performance gains scale with the map size. I ran the lookup benchmark, which looks up all the elements in a map, and I got a 37% improvement running with a map size of 2^22 elements. Compare this to the 42% gain I get on the same benchmark with a map of 2^10 elements. This is just an indication as I didn't really investigate where the time went. It's something I'd like to look into in the future.

For what it's worth, I ran the benchmarks for various sizes up to 2^20. Since the old Data.Map doesn't have foldlWithKey' and insertLookupWithKey', I used the unprimed versions of those for the old Data.Map. That doesn't have much impact on the insertLookupWithKey' tests, but the foldlWithKey' test is of course terrible with a large map, so that shows atypical behaviour. In general, from just looking at the numbers without statistical analysis, it seems that the size of the map doesn't matter much. For most benchmarks, the speedup doesn't show a clear trend of growing or shrinking with the map size. The numbers in the table are (mean of new Map) / (mean of old Map). A file with a few more sizes is attached. Size of map (2^k) 8 10 12 15 20 alter : 0.5232 0.5050 0.5153 0.5396 0.5449 delete : 0.5825 0.5601 0.5632 0.5810 0.5656 foldlWithKey : 0.6109 0.6028 0.6761 0.6858 0.6810 foldlWithKey' : 0.4761 0.4991 0.3090 0.0890 0.0085 foldrWithKey : 0.8184 0.7933 0.7673 0.5367 0.8977 insert : 0.5943 0.5208 0.5803 0.5656 0.5172 insertLookupWithKey empty : 0.5710 0.5947 0.6025 0.5735 0.5552 insertLookupWithKey update : 0.6733 0.6773 0.7115 0.7265 0.7241 insertLookupWithKey' empty : 0.5992 0.6115 0.5946 0.5935 0.5660 insertLookupWithKey' update : 0.6339 0.6071 0.6256 0.6298 0.6346 insertWith empty : 0.5686 0.5267 0.5776 0.5591 0.5163 insertWith update : 0.6558 0.5949 0.6880 0.7053 0.6822 insertWith' empty : 0.5341 0.4839 0.5691 0.5409 0.5068 insertWith' update : 0.6075 0.5914 0.6814 0.7027 0.6880 insertWithKey empty : 0.5650 0.5031 0.5620 0.5545 0.5098 insertWithKey update : 0.6216 0.5963 0.7005 0.7283 0.7105 insertWithKey' empty : 0.5584 0.5150 0.5585 0.5355 0.5057 insertWithKey' update : 0.5945 0.5908 0.6892 0.6865 0.6814 lookup : 0.6921 0.6772 0.6834 0.6601 0.7013 lookupIndex : 0.5345 0.5225 0.5120 0.5270 0.4873 map : 0.9015 0.8958 0.8544 0.8608 0.8059 mapMaybe : 0.8643 0.8654 0.8283 0.7799 0.7766 mapMaybeWithKey : 0.8546 0.8494 0.8181 0.7842 0.7844 mapWithKey : 0.9442 0.9263 0.8671 0.9236 0.8898 update : 0.5455 0.5266 0.5305 0.5408 0.5518 updateLookupWithKey : 0.5734 0.5511 0.5779 0.5904 0.5927