Changeset 49798 in webkit

Timestamp:

Oct 19, 2009 12:11:37 PM (15 years ago)

Author:

eric@webkit.org

Message:

2009-10-19 Jens Alfke <​jens@mooseyard.com>

Reviewed by Darin Adler.

Optimize string upper/lowercasing
​https://bugs.webkit.org/show_bug.cgi?id=30261

• Added AtomicString::upper() and lower()
• Further optimized StringImpl::lower()
• Removed StringImpl::isLower()
• Added QualifiedName::localNameUpper(), which is cached, thereby saving thousands of upper() calls and string allocations.

• dom/Element.cpp: (WebCore::Element::setAttribute): Call AtomicString::lower()
• dom/QualifiedName.cpp: (WebCore::QualifiedName::localNameUpper): New method
• dom/QualifiedName.h: Added localNameUpper() method
• dom/StyledElement.cpp: (WebCore::StyledElement::parseMappedAttribute): Call AtomicString::lower()
• html/HTMLDocument.cpp: (WebCore::HTMLDocument::createElement): Call AtomicString::lower()
• html/HTMLElement.cpp: (WebCore::HTMLElement::nodeName): Call localNameUpper()
• platform/text/AtomicString.cpp: (WebCore::AtomicString::lower): New method (WebCore::AtomicString::upper): New method
• platform/text/AtomicString.h: Added lower() and upper()
• platform/text/StringImpl.cpp: Removed isLower() (WebCore::StringImpl::lower): Further optimization of initial loop
• platform/text/StringImpl.h: Removed isLower()

Location:

trunk/WebCore

Files:

• ChangeLog (modified) (1 diff)
• dom/Element.cpp (modified) (1 diff)
• dom/QualifiedName.cpp (modified) (1 diff)
• dom/QualifiedName.h (modified) (2 diffs)
• dom/StyledElement.cpp (modified) (1 diff)
• html/HTMLDocument.cpp (modified) (1 diff)
• html/HTMLElement.cpp (modified) (1 diff)
• platform/text/AtomicString.cpp (modified) (1 diff)
• platform/text/AtomicString.h (modified) (1 diff)
• platform/text/StringImpl.cpp (modified) (2 diffs)
• platform/text/StringImpl.h (modified) (1 diff)

trunk/WebCore/ChangeLog

@@ +1 @@
+2009-10-19  Jens Alfke  <jens@mooseyard.com>
+
+        Reviewed by Darin Adler.
+
+        Optimize string upper/lowercasing
+        https://bugs.webkit.org/show_bug.cgi?id=30261
+        
+        - Added AtomicString::upper() and lower()
+        - Further optimized StringImpl::lower()
+        - Removed StringImpl::isLower()
+        - Added QualifiedName::localNameUpper(), which is cached, thereby saving
+          thousands of upper() calls and string allocations.
+ 
+         * dom/Element.cpp:
+         (WebCore::Element::setAttribute): Call AtomicString::lower()
+         * dom/QualifiedName.cpp:
+         (WebCore::QualifiedName::localNameUpper): New method
+         * dom/QualifiedName.h: Added localNameUpper() method
+         * dom/StyledElement.cpp:
+         (WebCore::StyledElement::parseMappedAttribute):  Call AtomicString::lower()
+         * html/HTMLDocument.cpp:
+         (WebCore::HTMLDocument::createElement): Call AtomicString::lower()
+         * html/HTMLElement.cpp:
+         (WebCore::HTMLElement::nodeName): Call localNameUpper()
+         * platform/text/AtomicString.cpp:
+         (WebCore::AtomicString::lower): New method
+         (WebCore::AtomicString::upper): New method
+         * platform/text/AtomicString.h: Added lower() and upper()
+         * platform/text/StringImpl.cpp: Removed isLower()
+         (WebCore::StringImpl::lower): Further optimization of initial loop
+         * platform/text/StringImpl.h: Removed isLower()
+ 
 2009-10-19  Nate Chapin  <japhet@chromium.org>
 

trunk/WebCore/dom/Element.cpp

@@ -517 +517 @@
     }
 
-    const AtomicString& localName = (shouldIgnoreAttributeCase(this) && !name.string().impl()->isLower()) ? AtomicString(name.string().lower()) : name;
+    const AtomicString& localName = shouldIgnoreAttributeCase(this) ? name.lower() : name;
 
     // allocate attributemap if necessary

trunk/WebCore/dom/QualifiedName.cpp

@@ -98 +98 @@
 }
 
+const AtomicString& QualifiedName::localNameUpper() const
+{
+    if (!m_impl->m_localNameUpper)
+        m_impl->m_localNameUpper = m_impl->m_localName.upper();
+    return m_impl->m_localNameUpper;
 }
+
+}

trunk/WebCore/dom/QualifiedName.h

@@ -42 +42 @@
         }
 
-        AtomicString m_prefix;
-        AtomicString m_localName;
-        AtomicString m_namespace;
+        const AtomicString m_prefix;
+        const AtomicString m_localName;
+        const AtomicString m_namespace;
+        mutable AtomicString m_localNameUpper;
 
     private:
@@ -76 +77 @@
     const AtomicString& localName() const { return m_impl->m_localName; }
     const AtomicString& namespaceURI() const { return m_impl->m_namespace; }
+
+    // Uppercased localName, cached for efficiency
+    const AtomicString& localNameUpper() const;
 
     String toString() const;

trunk/WebCore/dom/StyledElement.cpp

@@ -241 +241 @@
             if (attr->isNull())
                 namedAttrMap->setID(nullAtom);
-            else if (document()->inCompatMode() && !attr->value().impl()->isLower())
-                namedAttrMap->setID(AtomicString(attr->value().string().lower()));
+            else if (document()->inCompatMode())
+                namedAttrMap->setID(attr->value().lower());
             else
                 namedAttrMap->setID(attr->value());

trunk/WebCore/html/HTMLDocument.cpp

@@ -308 +308 @@
         return 0;
     }
-    AtomicString lowerName = name.string().impl()->isLower() ? name : AtomicString(name.string().lower());
-    return HTMLElementFactory::createHTMLElement(QualifiedName(nullAtom, lowerName, xhtmlNamespaceURI), this, 0, false);
+    return HTMLElementFactory::createHTMLElement(QualifiedName(nullAtom, name.lower(), xhtmlNamespaceURI), this, 0, false);
 }
 

trunk/WebCore/html/HTMLElement.cpp

@@ -68 +68 @@
     // FIXME: We should have a way to detect XHTML elements and replace the hasPrefix() check with it.
     if (document()->isHTMLDocument() && !tagQName().hasPrefix())
-        return tagQName().localName().string().upper();
+        return tagQName().localNameUpper();
     return Element::nodeName();
 }

trunk/WebCore/platform/text/AtomicString.cpp

@@ -229 +229 @@
     stringTable().remove(r);
 }
+    
+AtomicString AtomicString::lower() const
+{
+    // Note: This is a hot function in the Dromaeo benchmark.
+    StringImpl* impl = this->impl();
+    RefPtr<StringImpl> newImpl = impl->lower();
+    if (LIKELY(newImpl == impl))
+        return *this;
+    return AtomicString(newImpl);
+}
 
 #if USE(JSC)

trunk/WebCore/platform/text/AtomicString.h

@@ -84 +84 @@
         { return m_string.endsWith(s, caseSensitive); }
     
+    AtomicString lower() const;
+    AtomicString upper() const { return AtomicString(impl()->upper()); }
+    
     int toInt(bool* ok = 0) const { return m_string.toInt(ok); }
     double toDouble(bool* ok = 0) const { return m_string.toDouble(ok); }

trunk/WebCore/platform/text/StringImpl.cpp

@@ -150 +150 @@
 }
 
-bool StringImpl::isLower()
-{
-    // Do a faster loop for the case where all the characters are ASCII.
-    bool allLower = true;
-    UChar ored = 0;
-    for (unsigned i = 0; i < m_length; i++) {
-        UChar c = m_data[i];
-        allLower = allLower && isASCIILower(c);
-        ored |= c;
-    }
-    if (!(ored & ~0x7F))
-        return allLower;
-
-    // Do a slower check for cases that include non-ASCII characters.
-    allLower = true;
-    unsigned i = 0;
-    while (i < m_length) {
-        UChar32 character;
-        U16_NEXT(m_data, i, m_length, character)
-        allLower = allLower && Unicode::isLower(character);
-    }
-    return allLower;
-}
-
 PassRefPtr<StringImpl> StringImpl::lower()
 {
+    // Note: This is a hot function in the Dromaeo benchmark, specifically the
+    // no-op code path up through the first 'return' statement.
+    
     // First scan the string for uppercase and non-ASCII characters:
-    int32_t length = m_length;
     UChar ored = 0;
     bool noUpper = true;
-    for (int i = 0; i < length; i++) {
-        UChar c = m_data[i];
-        ored |= c;
-        noUpper = noUpper && !isASCIIUpper(c);
+    const UChar *end = m_data + m_length;
+    for (const UChar* chp = m_data; chp != end; chp++) {
+        if (UNLIKELY(isASCIIUpper(*chp)))
+            noUpper = false;
+        ored |= *chp;
     }
     
@@ -190 +169 @@
         return this;
 
+    int32_t length = m_length;
     UChar* data;
     RefPtr<StringImpl> newImpl = createUninitialized(m_length, data);

trunk/WebCore/platform/text/StringImpl.h

@@ -136 +136 @@
     float toFloat(bool* ok = 0);
 
-    bool isLower();
     PassRefPtr<StringImpl> lower();
     PassRefPtr<StringImpl> upper();