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/HashTraits.h

    r31335 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
    … …  
    7877
    7978    template<bool isInteger, typename T> struct GenericHashTraitsBase;
    80     template<typename T> struct GenericHashTraitsBase<true, T> {
    81         typedef T TraitType;
    82         typedef HashTraits<typename IntTypes<sizeof(T)>::SignedType> StorageTraits;
    83         static const bool emptyValueIsZero = true;
    84         static const bool needsDestruction = false;
    85     };
     79
    8680    template<typename T> struct GenericHashTraitsBase<false, T> {
    87         typedef T TraitType;
    88         typedef HashTraits<T> StorageTraits;
    8981        static const bool emptyValueIsZero = false;
    9082        static const bool needsDestruction = true;
    9183    };
    9284
     85    // default integer traits disallow both 0 and -1 as keys (max value instead of -1 for unsigned)
     86    template<typename T> struct GenericHashTraitsBase<true, T> {
     87        static const bool emptyValueIsZero = true;
     88        static const bool needsDestruction = false;
     89        static void constructDeletedValue(T* slot) { *slot = static_cast<T>(-1); }
     90        static bool isDeletedValue(T value) { return value == static_cast<T>(-1); }
     91    };
     92
    9393    template<typename T> struct GenericHashTraits : GenericHashTraitsBase<IsInteger<T>::value, T> {
     94        typedef T TraitType;
     95        typedef HashTraits<T> StorageTraits;
    9496        static T emptyValue() { return T(); }
    9597        static const bool needsRef = false;
    … …  
    98100    template<typename T> struct HashTraits : GenericHashTraits<T> { };
    99101
    100     // signed integer traits may not be appropriate for all uses since they disallow 0 and -1 as keys
    101     template<> struct HashTraits<signed char> : GenericHashTraits<int> {
    102         static signed char deletedValue() { return -1; }
    103     };
    104     template<> struct HashTraits<short> : GenericHashTraits<short> {
    105         static short deletedValue() { return -1; }
    106     };
    107     template<> struct HashTraits<unsigned short> : GenericHashTraits<unsigned short> {
    108         static short deletedValue() { return static_cast<unsigned short>(-1); }
    109     };
    110     template<> struct HashTraits<int> : GenericHashTraits<int> {
    111         static int deletedValue() { return -1; }
    112     };
    113     template<> struct HashTraits<unsigned int> : GenericHashTraits<unsigned int> {
    114         static unsigned int deletedValue() { return static_cast<unsigned int>(-1); }
    115     };
    116     template<> struct HashTraits<long> : GenericHashTraits<long> {
    117         static long deletedValue() { return -1; }
    118     };
    119     template<> struct HashTraits<unsigned long> : GenericHashTraits<unsigned long> {
    120         static unsigned long deletedValue() { return static_cast<unsigned long>(-1); }
    121     };
    122     template<> struct HashTraits<long long> : GenericHashTraits<long long> {
    123         static long long deletedValue() { return -1; }
    124     };
    125     template<> struct HashTraits<unsigned long long> : GenericHashTraits<unsigned long long> {
    126         static unsigned long long deletedValue() { return static_cast<unsigned long long>(-1); }
    127     };
    128    
    129 #if !COMPILER(MSVC) || defined(_NATIVE_WCHAR_T_DEFINED)
    130     template<> struct HashTraits<wchar_t> : GenericHashTraits<wchar_t> {
    131         static wchar_t deletedValue() { return static_cast<wchar_t>(-1); }
    132     };
    133 #endif
    134 
    135     template<typename T> struct FloatHashTraits {
    136         typedef T TraitType;
    137         typedef HashTraits<T> StorageTraits;
     102    template<typename T> struct FloatHashTraits : GenericHashTraits<T> {
     103        static const bool needsDestruction = false;
    138104        static T emptyValue() { return std::numeric_limits<T>::infinity(); }
    139         static T deletedValue() { return -std::numeric_limits<T>::infinity(); }
    140         static const bool emptyValueIsZero = false;
    141         static const bool needsDestruction = false;
    142         static const bool needsRef = false;
    143     };
    144     template<> struct HashTraits<float> : FloatHashTraits<float> {
    145     };
    146     template<> struct HashTraits<double> : FloatHashTraits<double> {
     105        static void constructDeletedValue(T* slot) { *slot = -std::numeric_limits<T>::infinity(); }
     106        static bool isDeletedValue(T value) { return value == -std::numeric_limits<T>::infinity(); }
    147107    };
    148108
     109    template<> struct HashTraits<float> : FloatHashTraits<float> { };
     110    template<> struct HashTraits<double> : FloatHashTraits<double> { };
     111
    149112    template<typename P> struct HashTraits<P*> : GenericHashTraits<P*> {
    150         typedef HashTraits<typename IntTypes<sizeof(P*)>::SignedType> StorageTraits;
    151113        static const bool emptyValueIsZero = true;
    152114        static const bool needsDestruction = false;
    153         static P* deletedValue() { return reinterpret_cast<P*>(-1); }
     115        static void constructDeletedValue(P** slot) { *slot = reinterpret_cast<P*>(-1); }
     116        static bool isDeletedValue(P* value) { return value == reinterpret_cast<P*>(-1); }
    154117    };
    155118
    156119    template<typename P> struct HashTraits<RefPtr<P> > : GenericHashTraits<RefPtr<P> > {
    157         typedef HashTraits<typename IntTypes<sizeof(P*)>::SignedType> StorageTraits;
    158         typedef typename StorageTraits::TraitType StorageType;
    159120        static const bool emptyValueIsZero = true;
    160         static const bool needsRef = true;
    161 
    162         typedef union {
    163             P* m_p;
    164             StorageType m_s;
    165         } UnionType;
    166 
    167         static void ref(const StorageType& s)
    168         {
    169             if (const P* p = reinterpret_cast<const UnionType*>(&s)->m_p)
    170                 const_cast<P*>(p)->ref();
    171         }
    172         static void deref(const StorageType& s)
    173         {
    174             if (const P* p = reinterpret_cast<const UnionType*>(&s)->m_p)
    175                 const_cast<P*>(p)->deref();
    176         }
     121        static void constructDeletedValue(RefPtr<P>* slot) { new (slot) RefPtr<P>(HashTableDeletedValue); }
     122        static bool isDeletedValue(const RefPtr<P>& value) { return value.isHashTableDeletedValue(); }
    177123    };
    178 
    179     // template to set deleted values
    180 
    181     template<typename Traits> struct DeletedValueAssigner {
    182         static void assignDeletedValue(typename Traits::TraitType& location) { location = Traits::deletedValue(); }
    183     };
    184 
    185     template<typename T, typename Traits> inline void assignDeleted(T& location)
    186     {
    187         DeletedValueAssigner<Traits>::assignDeletedValue(location);
    188     }
    189124
    190125    // special traits for pairs, helpful for their use in HashMap implementation
    … …  
    193128
    194129    template<typename FirstTraitsArg, typename SecondTraitsArg>
    195     struct PairBaseHashTraits : GenericHashTraits<pair<typename FirstTraitsArg::TraitType, typename SecondTraitsArg::TraitType> > {
     130    struct PairHashTraits : GenericHashTraits<pair<typename FirstTraitsArg::TraitType, typename SecondTraitsArg::TraitType> > {
    196131        typedef FirstTraitsArg FirstTraits;
    197132        typedef SecondTraitsArg SecondTraits;
    198133        typedef pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> TraitType;
    199134
    200         typedef PairHashTraits<typename FirstTraits::StorageTraits, typename SecondTraits::StorageTraits> StorageTraits;
     135        static const bool emptyValueIsZero = FirstTraits::emptyValueIsZero && SecondTraits::emptyValueIsZero;
     136        static TraitType emptyValue() { return make_pair(FirstTraits::emptyValue(), SecondTraits::emptyValue()); }
    201137
    202         static const bool emptyValueIsZero = FirstTraits::emptyValueIsZero && SecondTraits::emptyValueIsZero;
     138        static const bool needsDestruction = FirstTraits::needsDestruction || SecondTraits::needsDestruction;
    203139
    204         static TraitType emptyValue()
    205         {
    206             return make_pair(FirstTraits::emptyValue(), SecondTraits::emptyValue());
    207         }
     140        static void constructDeletedValue(TraitType* slot) { FirstTraits::constructDeletedValue(&slot->first); }
     141        static bool isDeletedValue(const TraitType& value) { return FirstTraits::isDeletedValue(value.first); }
    208142    };
    209143
    210144    template<typename FirstTraits, typename SecondTraits>
    211     struct PairHashTraits : PairBaseHashTraits<FirstTraits, SecondTraits> {
    212         typedef pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> TraitType;
    213 
    214         static const bool needsDestruction = FirstTraits::needsDestruction || SecondTraits::needsDestruction;
    215 
    216         static TraitType deletedValue()
    217         {
    218             return TraitType(FirstTraits::deletedValue(), SecondTraits::emptyValue());
    219         }
    220 
    221         static void assignDeletedValue(TraitType& location)
    222         {
    223             assignDeleted<typename FirstTraits::TraitType, FirstTraits>(location.first);
    224             location.second = SecondTraits::emptyValue();
    225         }
    226     };
     145    struct PairBaseHashTraits : PairHashTraits<FirstTraits, SecondTraits> { };
    227146
    228147    template<typename First, typename Second>
    229148    struct HashTraits<pair<First, Second> > : public PairHashTraits<HashTraits<First>, HashTraits<Second> > { };
    230149
    231     template<typename FirstTraits, typename SecondTraits>
    232     struct DeletedValueAssigner<PairHashTraits<FirstTraits, SecondTraits> >
    233     {
    234         static void assignDeletedValue(pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType>& location)
    235         {
    236             PairHashTraits<FirstTraits, SecondTraits>::assignDeletedValue(location);
    237         }
    238     };
    239 
    240     template<typename First, typename Second>
    241     struct DeletedValueAssigner<HashTraits<pair<First, Second> > >
    242     {
    243         static void assignDeletedValue(pair<First, Second>& location)
    244         {
    245             HashTraits<pair<First, Second> >::assignDeletedValue(location);
    246         }
    247     };
    248 
    249     // hash functions and traits that are equivalent (for code sharing)
    250 
     150    // obsolete code sharing traits -- to be deleted
    251151    template<typename HashArg, typename TraitsArg> struct HashKeyStorageTraits {
    252152        typedef HashArg Hash;
    253153        typedef TraitsArg Traits;
    254     };
    255     template<typename P> struct HashKeyStorageTraits<PtrHash<P*>, HashTraits<P*> > {
    256         typedef typename IntTypes<sizeof(P*)>::SignedType IntType;
    257         typedef IntHash<IntType> Hash;
    258         typedef HashTraits<IntType> Traits;
    259     };
    260     template<typename P> struct HashKeyStorageTraits<PtrHash<RefPtr<P> >, HashTraits<RefPtr<P> > > {
    261         typedef typename IntTypes<sizeof(P*)>::SignedType IntType;
    262         typedef IntHash<IntType> Hash;
    263         typedef HashTraits<IntType> Traits;
    264154    };
    265155
Note: See TracChangeset for help on using the changeset viewer.