[Haskell-cafe] Announce: Significant performance improvements for
Data.Map
Daniel Fischer
daniel.is.fischer at web.de
Sun Aug 29 20:48:26 EDT 2010
On Sunday 29 August 2010 18:48:32, Johan Tibell wrote:
> On Sun, Aug 29, 2010 at 3:41 PM, Daniel Fischer
<daniel.is.fischer at web.de>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
-------------- next part --------------
Size of map (2^k) 5 6 7 8 9 10 11 12 15 20
alter : 0.5411 0.5249 0.5389 0.5232 0.5357 0.5050 0.4569 0.5153 0.5396 0.5449
delete : 0.6116 0.5936 0.6005 0.5825 0.5902 0.5601 0.5648 0.5632 0.5810 0.5656
foldlWithKey : 0.6243 0.6261 0.6286 0.6109 0.6266 0.6028 0.5867 0.6761 0.6858 0.6810
foldlWithKey' : 0.5359 0.5422 0.4956 0.4761 0.5076 0.4991 0.4024 0.3090 0.0890 0.0085
foldrWithKey : 0.8671 0.8453 0.8300 0.8184 0.8325 0.7933 0.8055 0.7673 0.5367 0.8977
insert : 0.6745 0.6464 0.6136 0.5943 0.5639 0.5208 0.5774 0.5803 0.5656 0.5172
insertLookupWithKey empty : 0.6254 0.6042 0.5912 0.5710 0.5754 0.5947 0.5955 0.6025 0.5735 0.5552
insertLookupWithKey update : 0.6462 0.6656 0.6691 0.6733 0.6667 0.6773 0.7132 0.7115 0.7265 0.7241
insertLookupWithKey' empty : 0.6611 0.6443 0.6197 0.5992 0.5774 0.6115 0.6034 0.5946 0.5935 0.5660
insertLookupWithKey' update : 0.6363 0.6328 0.6427 0.6339 0.6443 0.6071 0.6380 0.6256 0.6298 0.6346
insertWith empty : 0.6505 0.6374 0.5772 0.5686 0.5389 0.5267 0.5668 0.5776 0.5591 0.5163
insertWith update : 0.6295 0.6546 0.6453 0.6558 0.6227 0.5949 0.5358 0.6880 0.7053 0.6822
insertWith' empty : 0.6414 0.5723 0.5575 0.5341 0.5226 0.4839 0.5491 0.5691 0.5409 0.5068
insertWith' update : 0.5848 0.6040 0.5864 0.6075 0.5845 0.5914 0.5571 0.6814 0.7027 0.6880
insertWithKey empty : 0.6542 0.6195 0.5876 0.5650 0.5453 0.5031 0.5695 0.5620 0.5545 0.5098
insertWithKey update : 0.6408 0.6285 0.6335 0.6216 0.6212 0.5963 0.5494 0.7005 0.7283 0.7105
insertWithKey' empty : 0.6354 0.6045 0.5663 0.5584 0.5288 0.5150 0.5530 0.5585 0.5355 0.5057
insertWithKey' update : 0.5887 0.6080 0.5978 0.5945 0.5977 0.5908 0.5638 0.6892 0.6865 0.6814
lookup : 0.6913 0.7070 0.7009 0.6921 0.6966 0.6772 0.6757 0.6834 0.6601 0.7013
lookupIndex : 0.5769 0.5541 0.5540 0.5345 0.5536 0.5225 0.5289 0.5120 0.5270 0.4873
map : 0.8913 0.9036 0.8774 0.9015 0.9010 0.8958 0.8681 0.8544 0.8608 0.8059
mapMaybe : 0.8778 0.8810 0.8555 0.8643 0.8617 0.8654 0.8470 0.8283 0.7799 0.7766
mapMaybeWithKey : 0.8476 0.8810 0.8537 0.8546 0.8541 0.8494 0.8414 0.8181 0.7842 0.7844
mapWithKey : 0.9165 0.9467 0.9431 0.9442 0.9349 0.9263 0.9358 0.8671 0.9236 0.8898
update : 0.5428 0.5416 0.5342 0.5455 0.5323 0.5266 0.4685 0.5305 0.5408 0.5518
updateLookupWithKey : 0.5750 0.5813 0.5754 0.5734 0.5676 0.5511 0.5754 0.5779 0.5904 0.5927
More information about the Haskell-Cafe
mailing list