[webkit-reviews] review granted: [Bug 15585] speed up sparse arrays by using a custom map : [Attachment 16754] patch with change log

[bugzilla-daemon at webkit.org]

Maciej Stachowiak <mjs at apple.com> has granted Darin Adler <darin at apple.com>'s
request for review:
Bug 15585: speed up sparse arrays by using a custom map
http://bugs.webkit.org/show_bug.cgi?id=15585

Attachment 16754: patch with change log
http://bugs.webkit.org/attachment.cgi?id=16754&action=edit

------- Additional Comments from Maciej Stachowiak <mjs at apple.com>
The code looks good and the speed gain looks good so I'm saying r=me.

However, I don't think any of the current SunSpider test cases create true
sparse arrays. What's happening is that they are making dense arrays which are
bigger than our arbitrary sparse array cutoff. I think we should pick the
storage strategy based on some measure of the density ratio of the array. In
particular, if the array has even a quarter of its slots filled, then the
direct storage is more space-efficient than the overflow map. Indeed it is
probably good to use the dense storage at even as low as 1/8 of slots filled.
We should consider extending storage length so long as this density ratio is
maintained, and perhaps even be able to switch from the overflow map back to
direct array access (and maybe vice versa) at some thresholds of density
change. Would you be interested in that as a follow-up? I bet it would help
even more on the two sunspider tests that are definitely hitting the sparse
array threshold, 3d-morph and access-nsieve.

(Eventually we might have test cases that really do call for a sparse array -
at that point it might be worth doing a more space-efficient implementation
like the sparsetable class from Google's sparse_hash implementation:
http://google-sparsehash.googlecode.com/svn/trunk/doc/sparsetable.html