Reviewed by Maciej.

        - http://bugs.webkit.org/show_bug.cgi?id=15912
          fasta spends a lot of time in qsort

        * kjs/property_map.cpp:
        (KJS::PropertyMap::getEnumerablePropertyNames):
        Use insertion sort instead of qsort for small sets of property names.
        We can probably do some even-better speedups of for/in, but this nets
        0.6% overall and 6.7% on fasta.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@27634 268f45cc-cd09-0410-ab3c-d52691b4dbfc

diff --git a/JavaScriptCore/ChangeLog b/JavaScriptCore/ChangeLog
index ecc65b2c6667053017ea718105058e89ee0e0468..eb9f05f7e756d3f5b7a9b19a97e5c552609ec662 100644 (file)
--- a/JavaScriptCore/ChangeLog
+++ b/JavaScriptCore/ChangeLog
@@ -1,3 +1,16 @@
+2007-11-08  Darin Adler  <darin@apple.com>
+
+        Reviewed by Maciej.
+
+        - http://bugs.webkit.org/show_bug.cgi?id=15912
+          fasta spends a lot of time in qsort
+
+        * kjs/property_map.cpp:
+        (KJS::PropertyMap::getEnumerablePropertyNames):
+        Use insertion sort instead of qsort for small sets of property names.
+        We can probably do some even-better speedups of for/in, but this nets
+        0.6% overall and 6.7% on fasta.
+
 2007-11-08  Darin Adler  <darin@apple.com>
 
         Reviewed by Maciej.

diff --git a/JavaScriptCore/kjs/property_map.cpp b/JavaScriptCore/kjs/property_map.cpp
index f13182156e15543ba35d8c898c8b657fef2d9b59..9b032c57faec506bc67ef2a65922441edf655c82 100644 (file)
--- a/JavaScriptCore/kjs/property_map.cpp
+++ b/JavaScriptCore/kjs/property_map.cpp
@@ -50,7 +50,11 @@ namespace KJS {
 
 // Choose a number for the following so that most property maps are smaller,
 // but it's not going to blow out the stack to allocate this number of pointers.
-const int smallMapThreshold = 1024;
+static const int smallMapThreshold = 1024;
+
+// The point at which the function call overhead of the qsort implementation
+// becomes small compared to the inefficiency of insertion sort.
+static const int tinyMapThreshold = 20;
 
 #if DUMP_PROPERTYMAP_STATS
 
@@ -680,6 +684,25 @@ void PropertyMap::getEnumerablePropertyNames(PropertyNameArray& propertyNames) c
         return;
     }
 
+    if (m_u.table->keyCount < tinyMapThreshold) {
+        Entry* a[tinyMapThreshold];
+        int i = 0;
+        unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
+        for (unsigned k = 1; k <= entryCount; k++) {
+            if (m_u.table->entries()[k].key && !(m_u.table->entries()[k].attributes & DontEnum)) {
+                Entry* value = &m_u.table->entries()[k];
+                int j;
+                for (j = i - 1; j >= 0 && a[j]->index > value->index; --j)
+                    a[j + 1] = a[j];
+                a[j + 1] = value;
+                ++i;
+            }
+        }
+        for (int k = 0; k < i; ++k)
+            propertyNames.add(Identifier(a[k]->key));
+        return;
+    }
+
     // Allocate a buffer to use to sort the keys.
     Vector<Entry*, smallMapThreshold> sortedEnumerables(m_u.table->keyCount);