Ignore:
Timestamp:
Apr 27, 2008, 10:59:07 PM (17 years ago)
Author:
Darin Adler
Message:

JavaScriptCore:

2008-04-25 Darin Adler <Darin Adler>

Reviewed by Maciej.

  • fix <rdar://problem/5657459> REGRESSION: JavaScriptCore no longer builds with GCC 4.2 due to pointer aliasing warnings

Fix this by removing the HashTable optimizations that allowed us to share a back end
implementation between hash tables with integers, pointers, RefPtr, and String objects
as keys. The way it worked was incompatible with strict aliasing.

This increases code size. On Mac OS X we'll have to regenerate .order files to avoid
slowing down Safari startup times.

This creates a slight slowdown in SunSpider, mitigated by the following four speedups:

  • speed up array put slightly by moving a branch (was already done for get)
  • speed up symbol table access by adding a function named inlineGet to HashMap and using that in symbolTableGet/Put
  • speed up PropertyNameArray creation by reducing the amount of reference count churn and uniqueness checking when adding names and not doing any allocation at all when building small arrays
  • speed up conversion of strings to floating point numbers by eliminating the malloc/free of the buffer for the ASCII copy of the string; a way to make things even faster would be to change strtod to take a UTF-16 string

Note that there is considerable unused complexity now in HashSet/Map/Table to support
"storage types", which is no longer used. Will do in a separate patch.

  • API/JSCallbackObjectFunctions.h: (KJS::JSCallbackObject<Base>::getPropertyNames): Removed explicit cast to Identifier to take advantage of the new PropertyNameArray::add overload and avoid reference count churn.
  • API/JSObjectRef.cpp: (JSPropertyNameAccumulatorAddName): Ditto.
  • JavaScriptCore.exp: Updated PropertyNameArray::add entry point name.
  • kjs/JSVariableObject.cpp: Removed now-unneeded IdentifierRepHashTraits::nullRepPtr definition (see below). (KJS::JSVariableObject::getPropertyNames): Removed explicit cast to Identifier.
  • kjs/JSVariableObject.h: (KJS::JSVariableObject::symbolTableGet): Use inlineGet for speed. Also changed to do early exit instead of nesting the body inside an if. (KJS::JSVariableObject::symbolTablePut): Ditto.
  • kjs/PropertyNameArray.cpp: (KJS::PropertyNameArray::add): Changed implementation to take a raw pointer instead of a reference to an identifier. Do uniqueness checking by searching the vector when the vector is short, only building the set once the vector is large enough.
  • kjs/PropertyNameArray.h: Added an overload of add for a raw pointer, and made the old add function call that one. Added an addKnownUnique function for use when the new name is known to be different from any other in the array. Changed the vector to have an inline capacity of 20.
  • kjs/SymbolTable.h: Changed IdentifierRepHash to inherit from the default hash for a RefPtr so we don't have to define so much. Added an overload of the hash function for a raw pointer as required by the new RefPtrHashMap. Got rid of the now-unneeded IdentifierRepHashTraits -- the default traits now work fine. Added a definition of empthValueIsZero to SymbolTableIndexHashTraits; not having it was incorrect, but harmless.
  • kjs/array_instance.cpp: (KJS::ArrayInstance::put): Move the maxArrayIndex check inside the branch that checks the index against the length, as done in the get function.
  • kjs/function.cpp: (KJS::globalFuncKJSPrint): Changed to use the new getCString instead of cstring.
  • kjs/internal.cpp: Removed printInfo debugging function, a client of cstring. If we need a debugging function we can easily make a better one and we haven't used this one in a long time.
  • kjs/internal.h: Ditto.
  • kjs/object.cpp: (KJS::JSObject::getPropertyNames): Removed explicit cast to Identifier.
  • kjs/property_map.cpp: (KJS::PropertyMap::getEnumerablePropertyNames): Ditto. Also added a special case for the case where the propertyNames array is empty -- in that case we know we're adding a set of names that are non-overlapping so we can use addKnownUnique.
  • kjs/ustring.cpp: (KJS::UString::getCString): Replaces cstring. Puts the C string into a CStringBuffer, which is a char Vector with an inline capacity. Also returns a boolean to indicate if the converion was lossy, which eliminates the need for a separate is8Bit call. (KJS::UString::toDouble): Changed to call getCString instead of cstring.
  • kjs/ustring.h: Ditto.
  • wtf/HashFunctions.h: Overload the hash and equal functions for RefPtr's default hash to take raw pointers. This works with the changes to RefPtrHashMap to avoid introducing refcount churn.
  • wtf/HashMap.h: Removed special code to convert the deleted value to the empty value when writing a new value into the map. This is now handled elsewhere. (WTF::HashMap::get): Removed code that checks for an empty hash table before calling HashTable::lookup; it's slightly more efficient to do this check inside lookup.
  • wtf/HashTable.h: (WTF::HashTable::isDeletedBucket): Changed to use isDeletedValue instead of using deletedValue and the equality operator. (WTF::HashTable::deleteBucket): Changed to use constructDeletedValue instead of using deletedValue and the assignment operator. (WTF::HashTable::checkKey): Added. Factors out the check for values that are empty or deleted keys that's used in various functions below. (WTF::HashTable::lookup): Changed to use checkKey, check for a 0 table, and also made public for use by RefPtrHashMap. (WTF::HashTable::lookupForWriting): Changed to use checkKey. (WTF::HashTable::fullLookupForWriting): Changed to use checkKey. (WTF::HashTable::add): Changed to use checkKey, and call initializeBucket on a deleted bucket before putting a new entry into it. (WTF::HashTable::addPassingHashCode): Ditto. (WTF::HashTable::deallocateTable): Check isDeletedBucket before calling ~ValueType.
  • wtf/HashTraits.h: Got ridd of all the HashTraits specialization for the integer types, since GeneicHashTraitsBase already deals with integers separately. Put the deleted value support into GenericHashTraitsBase. Changed FloatHashTraits to inherit from GenericHashTraits, and define construct/isDeletedValue rather than deletedValue. Removed the ref and deref functions from RefPtr's HashTraits, and defined construct/isDeletedValue. Eliminated DeletedValueAssigner. Changed PairHashTraits to define construct/isDeletedValue, and also merged PairBaseHashTraits in with PairHashTraits. Got rid of all specialization of HashKeyStorageTraits. We'll remove that, and the needsRef data member, later.
  • wtf/RefPtr.h: Added HashTableDeletedValueType, an enum type with a single value, HashTableDeletedValue. Used that type to make a new constructor to construct deleted values and also added an isHashTableDeletedValue function.
  • wtf/RefPtrHashMap.h: Added RefPtrHashMapRawKeyTranslator and used it to implement the raw pointer functions. This is a way to continue to avoid refcount thrash. We can't use the old way because it depended on the underlying map using a non-RefPtr type. (WTF::HashMap::find): Use find with RefPtrHashMapRawKeyTranslator. (WTF::HashMap::contains): Use contains with RefPtrHashMapRawKeyTranslator. (WTF::HashMap::inlineAdd): Use add with RefPtrHashMapRawKeyTranslator. (WTF::HashMap::get): Removed code that checks for an empty hash table before calling HashTable::lookup; it's slightly more efficient to do this check inside lookup. (WTF::HashMap::inlineGet): Added. Just like get, but marked inline for use in the symbol table code.

WebCore:

2008-04-25 Darin Adler <Darin Adler>

Reviewed by Maciej.

  • update for compatibility with HashTable that no longer has optimization to share implementation between hash tables with integers, pointers, RefPtr, and String objects as keys
  • bindings/js/JSSVGPODTypeWrapper.h: (WebCore::PODTypeReadWriteHashInfo::PODTypeReadWriteHashInfo): Added constructor for HashTableDeletedValue. (WebCore::PODTypeReadWriteHashInfo::isHashTableDeletedValue): Added. (WebCore::PODTypeReadWriteHashInfoTraits::constructDeletedValue): Added. (WebCore::PODTypeReadWriteHashInfoTraits::isDeletedValue): Added.
  • dom/Document.cpp: Made changedDocuments internal to the file rather than a static data member of Document. (WebCore::FormElementKey::ref): Removed unneeded check for deleted value -- this will never be called on a deleted element. (WebCore::FormElementKey::deref): Ditto.
  • dom/Document.h: Added HashTableDeletedValue constructor and isHashTableDeletedValue to FormElementKey. Changed FormElementKeyHashTraits to use construct/isDeletedValue. Got rid of the changedDocuments data member. Changed iconURL to be an inline that returns a const String&.
  • dom/StyledElement.cpp: Changed MappedAttributeKeyTraits to use construct/isDeletedValue.
  • page/mac/AXObjectCacheMac.mm: (WebCore::AXObjectCache::getAXID): Call isDeletedValue instead of deletedValue.
  • platform/SecurityOriginHash.h: Added overload so that SecurityOriginHash can work with raw pointers as well as RefPt (helpful with the new RefPtrHashMap). Eliminated SecurityOriginTraits, since we can now use the default traits. Changed the value of safeToCompareToEmptyOrDeleted to false, since it's not safe to compare a deleted value using this hash function. I don't think it was safe before either; I'm not sure why it didn't cause a problem before.
  • platform/cf/SchedulePair.h: Removed SchedulePairTraits -- custom traits are no longer needed.
  • platform/graphics/FontCache.cpp: (WebCore::FontPlatformDataCacheKey::FontPlatformDataCacheKey): Added constructor for HashTableDeletedValue. (WebCore::FontPlatformDataCacheKey::isHashTableDeletedValue): Added. (WebCore::FontPlatformDataCacheKey::hashTableDeletedSize): Added. (WebCore::FontPlatformDataCacheKeyTraits::constructDeletedValue): Added. (WebCore::FontPlatformDataCacheKeyTraits::isDeletedValue): Added. (WebCore::FontDataCacheKeyTraits::constructDeletedValue): Added. (WebCore::FontDataCacheKeyTraits::isDeletedValue): Added.
  • platform/graphics/IntSizeHash.h: Changed HashTraits<IntSize> to use construct/isDeletedValue.
  • platform/graphics/mac/FontPlatformData.h: (WebCore::FontPlatformData::FontPlatformData): Added constructor for HashTableDeletedValue. (WebCore::FontPlatformData::isHashTableDeletedValue): Added. (WebCore::FontPlatformData::hashTableDeletedFontValue): Added.
  • platform/text/PlatformString.h: (WebCore::String::swap): Added. Avoids any refcount churn when swapping two strings. (WebCore::String::String): Added constructor for HashTableDeletedValue. (WebCore::String::isHashTableDeletedValue): Added. (WebCore::swap): Added. Avoids any refcount churn when swapping two strings.
  • platform/text/StringHash.h: Changed specialization of HashTraits for WebCore::String to use the deleted value now defined in that class and removed the code to do ref/deref. Removed HashKeyStorageTraits specializations.


  • platform/win/COMPtr.h: Changed specialization of HashTraits for COMPtr to use the deleted value now defined in that class and removed the code to do ref/deref. Removed HashKeyStorageTraits specializations. (COMPtr::COMPtr): Added constructor for HashTableDeletedValue. (COMPtr::isHashTableDeletedValue): Added. (COMPtr::query): Removed inline keyword not needed since functions defined in the class definition are automatically marked inline. (COMPtr::hashTableDeletedValue): Added.
  • storage/DatabaseTracker.h: Removed now-unneeded SecurityOriginTraits.
  • storage/LocalStorage.h: Ditto.
  • storage/OriginQuotaManager.h: Ditto.
  • storage/SessionStorage.h: Ditto.
  • svg/SVGAnimatedTemplate.h: (WebCore::SVGAnimatedTypeWrapperKey::SVGAnimatedTypeWrapperKey): Added constructor for HashTableDeletedValue. (WebCore::SVGAnimatedTypeWrapperKey::isHashTableDeletedValue): Added. (WebCore::SVGAnimatedTypeWrapperKeyHashTraits::constructDeletedValue): Added. (WebCore::SVGAnimatedTypeWrapperKeyHashTraits::isDeletedValue): Added.
File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/wtf/HashTable.h

    r27711 r32609  
    11// -*- mode: c++; c-basic-offset: 4 -*-
    22/*
    3  * This file is part of the KDE libraries
    4  * Copyright (C) 2005, 2006 Apple Computer, Inc.
     3 * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
    54 *
    65 * This library is free software; you can redistribute it and/or
    … …  
    326325
    327326        static bool isEmptyBucket(const ValueType& value) { return Extractor::extract(value) == KeyTraits::emptyValue(); }
    328         static bool isDeletedBucket(const ValueType& value) { return Extractor::extract(value) == KeyTraits::deletedValue(); }
     327        static bool isDeletedBucket(const ValueType& value) { return KeyTraits::isDeletedValue(Extractor::extract(value)); }
    329328        static bool isEmptyOrDeletedBucket(const ValueType& value) { return isEmptyBucket(value) || isDeletedBucket(value); }
    330329
    331330        ValueType* lookup(const Key& key) { return lookup<Key, IdentityTranslatorType>(key); }
     331        template<typename T, typename HashTranslator> ValueType* lookup(const T&);
    332332
    333333#if CHECK_HASHTABLE_CONSISTENCY
    … …  
    344344        typedef pair<LookupType, unsigned> FullLookupType;
    345345
    346         template<typename T, typename HashTranslator> ValueType* lookup(const T&);
    347346        LookupType lookupForWriting(const Key& key) { return lookupForWriting<Key, IdentityTranslatorType>(key); };
    348347        template<typename T, typename HashTranslator> FullLookupType fullLookupForWriting(const T&);
    349348        template<typename T, typename HashTranslator> LookupType lookupForWriting(const T&);
     349
     350        template<typename T, typename HashTranslator> void checkKey(const T&);
    350351
    351352        void removeAndInvalidateWithoutEntryConsistencyCheck(ValueType*);
    … …  
    363364
    364365        static void initializeBucket(ValueType& bucket) { new (&bucket) ValueType(Traits::emptyValue()); }
    365         static void deleteBucket(ValueType& bucket) { assignDeleted<ValueType, Traits>(bucket); }
     366        static void deleteBucket(ValueType& bucket) { bucket.~ValueType(); Traits::constructDeletedValue(&bucket); }
    366367
    367368        FullLookupType makeLookupResult(ValueType* position, bool found, unsigned hash)
    … …  
    424425    }
    425426
     427#if ASSERT_DISABLED
     428
     429    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
     430    template<typename T, typename HashTranslator>
     431    inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T&)
     432    {
     433    }
     434
     435#else
     436
     437    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
     438    template<typename T, typename HashTranslator>
     439    void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T& key)
     440    {
     441        if (!HashFunctions::safeToCompareToEmptyOrDeleted)
     442            return;
     443        ASSERT(!HashTranslator::equal(KeyTraits::emptyValue(), key));
     444        ValueType deletedValue = Traits::emptyValue();
     445        Traits::constructDeletedValue(&deletedValue);
     446        ASSERT(!HashTranslator::equal(Extractor::extract(deletedValue), key));
     447        new (&deletedValue) ValueType(Traits::emptyValue());
     448    }
     449
     450#endif
     451
    426452    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
    427453    template<typename T, typename HashTranslator>
    428454    inline Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookup(const T& key)
    429455    {
    430         ASSERT(m_table);
    431 #if !ASSERT_DISABLED
    432         if (HashFunctions::safeToCompareToEmptyOrDeleted) {
    433             ASSERT(!HashTranslator::equal(KeyTraits::emptyValue(), key));
    434             ASSERT(!HashTranslator::equal(KeyTraits::deletedValue(), key));
    435         }
    436 #endif
     456        checkKey<T, HashTranslator>(key);
    437457
    438458        int k = 0;
    … …  
    441461        unsigned h = HashTranslator::hash(key);
    442462        int i = h & sizeMask;
     463
     464        if (!table)
     465            return 0;
    443466
    444467#if DUMP_HASHTABLE_STATS
    … …  
    479502    {
    480503        ASSERT(m_table);
    481 #if !ASSERT_DISABLED
    482         if (HashFunctions::safeToCompareToEmptyOrDeleted) {
    483             ASSERT(!HashTranslator::equal(KeyTraits::emptyValue(), key));
    484             ASSERT(!HashTranslator::equal(KeyTraits::deletedValue(), key));
    485         }
    486 #endif
     504        checkKey<T, HashTranslator>(key);
    487505
    488506        int k = 0;
    … …  
    536554    {
    537555        ASSERT(m_table);
    538 #if !ASSERT_DISABLED
    539         if (HashFunctions::safeToCompareToEmptyOrDeleted) {
    540             ASSERT(!HashTranslator::equal(KeyTraits::emptyValue(), key));
    541             ASSERT(!HashTranslator::equal(KeyTraits::deletedValue(), key));
    542         }
    543 #endif
     556        checkKey<T, HashTranslator>(key);
    544557
    545558        int k = 0;
    … …  
    592605    inline pair<typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator, bool> HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::add(const T& key, const Extra& extra)
    593606    {
    594 #if !ASSERT_DISABLED
    595         if (HashFunctions::safeToCompareToEmptyOrDeleted) {
    596             ASSERT(!HashTranslator::equal(KeyTraits::emptyValue(), key));
    597             ASSERT(!HashTranslator::equal(KeyTraits::deletedValue(), key));
    598         }
    599 #endif
     607        checkKey<T, HashTranslator>(key);
    600608
    601609        invalidateIterators();
    … …  
    653661
    654662        if (deletedEntry) {
     663            initializeBucket(*deletedEntry);
    655664            entry = deletedEntry;
    656665            --m_deletedCount;
    … …  
    679688    inline pair<typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator, bool> HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::addPassingHashCode(const T& key, const Extra& extra)
    680689    {
     690        checkKey<T, HashTranslator>(key);
     691
    681692        invalidateIterators();
    682693
    … …  
    695706            return std::make_pair(makeKnownGoodIterator(entry), false);
    696707       
    697         if (isDeletedBucket(*entry))
     708        if (isDeletedBucket(*entry)) {
     709            initializeBucket(*entry);
    698710            --m_deletedCount;
     711        }
    699712       
    700713        HashTranslator::translate(*entry, key, extra, h);
    … …  
    837850    void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deallocateTable(ValueType *table, int size)
    838851    {
    839         if (Traits::needsDestruction)
    840             for (int i = 0; i < size; ++i)
    841                 table[i].~ValueType();
     852        if (Traits::needsDestruction) {
     853            for (int i = 0; i < size; ++i) {
     854                if (!isDeletedBucket(table[i]))
     855                    table[i].~ValueType();
     856            }
     857        }
    842858        fastFree(table);
    843859    }
Note: See TracChangeset for help on using the changeset viewer.