Bug 15606 - make cut-off for sparse vs. dense arrays smarter for speed with large arrays
Summary: make cut-off for sparse vs. dense arrays smarter for speed with large arrays
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: 523.x (Safari 3)
Hardware: Mac OS X 10.4
: P2 Enhancement
Assignee: Darin Adler
Depends on:
Reported: 2007-10-21 22:42 PDT by Darin Adler
Modified: 2007-10-22 06:47 PDT (History)
1 user (show)

See Also:

patch with change log (110.98 KB, patch)
2007-10-21 22:55 PDT, Darin Adler
mjs: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Darin Adler 2007-10-21 22:42:55 PDT
I got 3% speedup on the SunSpider benchmark by doing as Maciej suggested and making arrays smarter about sparse vs. dense.
Comment 1 Darin Adler 2007-10-21 22:55:39 PDT
Created attachment 16784 [details]
patch with change log
Comment 2 Mark Rowe (bdash) 2007-10-21 22:59:47 PDT
Be sure not to introduce bug 15603 with this change :)
Comment 3 Maciej Stachowiak 2007-10-22 00:01:58 PDT
Comment on attachment 16784 [details]
patch with change log

Regarding this FIXME. The extra copy is necessary because mergesort modifies the buffer that you pass it as it works, and there are times when not all values are in the buffer, some are only in auxiliary storage. But the compare function can trigger a garbage collection. If a GC happens while the array's storage pointer points to a buffer that does not contain all the values, then some objects that should be live will be trashed. This led to real crashes before I added the copy, so it's not just a problem in theory. I would suggest replacing the FIXME with a comment that explains this. My apologies for not adding such a comment at the time.

+        // FIXME: Why do we need this copy of the array storage?
+        // I know that mergesort allocates more memory internally,
+        // but I don't see any use of the original m_storage here!
+        size_t size = storageSize(m_vectorLength);
+        ArrayStorage* copy = static_cast<ArrayStorage*>(fastMalloc(size));
+        memcpy(copy, m_storage, size);
+        mergesort(copy->m_vector, lengthNotIncludingUndefined, sizeof(JSValue*), compareWithCompareFunctionForQSort);
+        fastFree(m_storage);
+        m_storage = copy;

Everything else looks good. r=me
Comment 4 Darin Adler 2007-10-22 06:47:30 PDT