Ignore:
Timestamp:
Nov 14, 2008, 3:36:06 PM (17 years ago)
Author:
[email protected]
Message:

2008-11-13 Sam Weinig <​[email protected]>

Reviewed by Darin Adler

Fix for ​https://bugs.webkit.org/show_bug.cgi?id=22269
Reduce PropertyMap usage

From observation of StructureID statistics, it became clear that many
StructureID's were not being used as StructureIDs themselves, but rather
only being necessary as links in the transition chain. Acknowledging this
and that PropertyMaps stored in StructureIDs can be treated as caches, that
is that they can be reconstructed on demand, it became clear that we could
reduce the memory consumption of StructureIDs by only keeping PropertyMaps
for the StructureIDs that need them the most.

The specific strategy used to reduce the number of StructureIDs with
PropertyMaps is to take the previous StructureIDs PropertyMap when initially
transitioning (addPropertyTransition) from it and clearing out the pointer
in the process. The next time we need to do the same transition, for instance
repeated calls to the same constructor, we use the new addPropertyTransitionToExistingStructure
first, which allows us not to need the PropertyMap to determine if the property
exists already, since a transition to that property would require it not already
be present in the StructureID. Should there be no transition, the PropertyMap
can be constructed on demand (via materializePropertyMap) to determine if the put is a
replace or a transition to a new StructureID.

Reduces memory use on Membuster head test (30 pages open) by ~15MB.

  • JavaScriptCore.exp:
  • runtime/JSObject.h: (JSC::JSObject::putDirect): First use addPropertyTransitionToExistingStructure so that we can avoid building the PropertyMap on subsequent similar object creations.
  • runtime/PropertyMapHashTable.h: (JSC::PropertyMapEntry::PropertyMapEntry): Add version of constructor which takes all values to be used when lazily building the PropertyMap.
  • runtime/StructureID.cpp: (JSC::StructureID::dumpStatistics): Add statistics on the number of StructureIDs with PropertyMaps. (JSC::StructureID::StructureID): Rename m_cachedTransistionOffset to m_offset (JSC::isPowerOf2): (JSC::nextPowerOf2): (JSC::sizeForKeyCount): Returns the expected size of a PropertyMap for a key count. (JSC::StructureID::materializePropertyMap): Builds the PropertyMap out of its previous pointer chain. (JSC::StructureID::addPropertyTransitionToExistingStructure): Only transitions if there is a an existing transition. (JSC::StructureID::addPropertyTransition): Instead of always copying the ProperyMap, try and take it from it previous pointer. (JSC::StructureID::removePropertyTransition): Simplify by calling toDictionaryTransition() to do transition work. (JSC::StructureID::changePrototypeTransition): Build the PropertyMap if necessary before transitioning because once you have transitioned, you will not be able to reconstruct it afterwards as there is no previous pointer, pinning the ProperyMap as well. (JSC::StructureID::getterSetterTransition): Ditto. (JSC::StructureID::toDictionaryTransition): Pin the PropertyMap so that it is not destroyed on further transitions. (JSC::StructureID::fromDictionaryTransition): We can only transition back from a dictionary transition if there are no deleted offsets. (JSC::StructureID::addPropertyWithoutTransition): Build PropertyMap on demands and pin. (JSC::StructureID::removePropertyWithoutTransition): Ditto. (JSC::StructureID::get): Build on demand. (JSC::StructureID::createPropertyMapHashTable): Add version of create that takes a size for on demand building. (JSC::StructureID::expandPropertyMapHashTable): (JSC::StructureID::rehashPropertyMapHashTable): (JSC::StructureID::getEnumerablePropertyNamesInternal): Build PropertyMap on demand.
  • runtime/StructureID.h: (JSC::StructureID::propertyStorageSize): Account for StructureIDs without PropertyMaps. (JSC::StructureID::isEmpty): Ditto. (JSC::StructureID::materializePropertyMapIfNecessary): (JSC::StructureID::get): Build PropertyMap on demand
File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/runtime/StructureID.cpp

    r38138 r38407  
    6060static const unsigned tinyMapThreshold = 20;
    6161
     62static const unsigned newTableSize = 16;
     63
    6264#ifndef NDEBUG
    6365static WTF::RefCountedLeakCounter structureIDCounter("StructureID");
    … …  
    8183    unsigned numberUsingSingleSlot = 0;
    8284    unsigned numberSingletons = 0;
     85    unsigned numberWithPropertyMaps = 0;
    8386    unsigned totalPropertyMapsSize = 0;
    8487
    … …  
    9699        }
    97100
    98         if (structureID->m_propertyTable)
     101        if (structureID->m_propertyTable) {
     102            ++numberWithPropertyMaps;
    99103            totalPropertyMapsSize += PropertyMapHashTable::allocationSize(structureID->m_propertyTable->size);
     104        }
    100105    }
    101106
    … …  
    104109    printf("Number of StructureIDs that are leaf nodes: %d\n", numberLeaf);
    105110    printf("Number of StructureIDs that singletons: %d\n", numberSingletons);
     111    printf("Number of StructureIDs with PropertyMaps: %d\n", numberWithPropertyMaps);
    106112
    107113    printf("Size of a single StructureIDs: %d\n", static_cast<unsigned>(sizeof(StructureID)));
    … …  
    122128    , m_propertyTable(0)
    123129    , m_propertyStorageCapacity(JSObject::inlineStorageCapacity)
    124     , m_cachedTransistionOffset(WTF::notFound)
     130    , m_offset(WTF::notFound)
    125131    , m_isDictionary(false)
     132    , m_isPinnedPropertyTable(false)
    126133    , m_hasGetterSetterProperties(false)
    127134    , m_usingSingleTransitionSlot(true)
    … …  
    202209    shouldIgnoreLeaks = false;
    203210#endif
     211}
     212
     213static bool isPowerOf2(unsigned v)
     214{
     215    // Taken from http://www.cs.utk.edu/~vose/c-stuff/bithacks.html
     216   
     217    return !(v & (v - 1)) && v;
     218}
     219
     220static unsigned nextPowerOf2(unsigned v)
     221{
     222    // Taken from http://www.cs.utk.edu/~vose/c-stuff/bithacks.html
     223    // Devised by Sean Anderson, Sepember 14, 2001
     224
     225    v--;
     226    v |= v >> 1;
     227    v |= v >> 2;
     228    v |= v >> 4;
     229    v |= v >> 8;
     230    v |= v >> 16;
     231    v++;
     232
     233    return v;
     234}
     235
     236static unsigned sizeForKeyCount(size_t keyCount)
     237{
     238    if (keyCount == WTF::notFound)
     239        return newTableSize;
     240
     241    if (keyCount < 8)
     242        return newTableSize;
     243
     244    if (isPowerOf2(keyCount))
     245        return keyCount * 4;
     246
     247    return nextPowerOf2(keyCount) * 2;
     248}
     249
     250void StructureID::materializePropertyMap()
     251{
     252    ASSERT(!m_propertyTable);
     253
     254    Vector<StructureID*, 8> structures;
     255    structures.append(this);
     256
     257    StructureID* structure = this;
     258
     259    // Search for the last StructureID with a property table.
     260    while ((structure = structure->previousID())) {
     261        if (structure->m_isPinnedPropertyTable) {
     262            ASSERT(structure->m_propertyTable);
     263            ASSERT(!structure->m_previous);
     264
     265            m_propertyTable = structure->copyPropertyTable();
     266            break;
     267        }
     268
     269        structures.append(structure);
     270    }
     271
     272    if (!m_propertyTable)
     273        createPropertyMapHashTable(sizeForKeyCount(m_offset + 1));
     274    else {
     275        if (sizeForKeyCount(m_offset + 1) > m_propertyTable->size)
     276            rehashPropertyMapHashTable(sizeForKeyCount(m_offset + 1)); // This could be made more efficient by combining with the copy above.
     277    }
     278
     279    for (ptrdiff_t i = structures.size() - 2; i >= 0; --i) {
     280        structure = structures[i];
     281        structure->m_nameInPrevious->ref();
     282        PropertyMapEntry entry(structure->m_nameInPrevious, structure->m_offset, structure->m_attributesInPrevious, ++m_propertyTable->lastIndexUsed);
     283        insertIntoPropertyMapHashTable(entry);
     284    }
    204285}
    205286
    … …  
    267348}
    268349
    269 PassRefPtr<StructureID> StructureID::addPropertyTransition(StructureID* structureID, const Identifier& propertyName, unsigned attributes, size_t& offset)
     350PassRefPtr<StructureID> StructureID::addPropertyTransitionToExistingStructure(StructureID* structureID, const Identifier& propertyName, unsigned attributes, size_t& offset)
    270351{
    271352    ASSERT(!structureID->m_isDictionary);
    … …  
    275356        StructureID* existingTransition = structureID->m_transitions.singleTransition;
    276357        if (existingTransition && existingTransition->m_nameInPrevious == propertyName.ustring().rep() && existingTransition->m_attributesInPrevious == attributes) {
    277             offset = structureID->m_transitions.singleTransition->cachedTransistionOffset();
     358            offset = structureID->m_transitions.singleTransition->m_offset;
    278359            ASSERT(offset != WTF::notFound);
    279360            return existingTransition;
    … …  
    281362    } else {
    282363        if (StructureID* existingTransition = structureID->m_transitions.table->get(make_pair(propertyName.ustring().rep(), attributes))) {
    283             offset = existingTransition->cachedTransistionOffset();
     364            offset = existingTransition->m_offset;
    284365            ASSERT(offset != WTF::notFound);
    285366            return existingTransition;
    286         }       
    287     }
     367        }
     368    }
     369
     370    return 0;
     371}
     372
     373PassRefPtr<StructureID> StructureID::addPropertyTransition(StructureID* structureID, const Identifier& propertyName, unsigned attributes, size_t& offset)
     374{
     375    ASSERT(!structureID->m_isDictionary);
     376    ASSERT(structureID->typeInfo().type() == ObjectType);
     377    ASSERT(structureID->m_deletedOffsets.isEmpty());
     378    ASSERT(!StructureID::addPropertyTransitionToExistingStructure(structureID, propertyName, attributes, offset));
    288379
    289380    if (structureID->m_transitionCount > s_maxTransitionLength) {
    … …  
    301392    transition->m_attributesInPrevious = attributes;
    302393    transition->m_transitionCount = structureID->m_transitionCount + 1;
    303     transition->m_propertyTable = structureID->copyPropertyTable();
    304     transition->m_deletedOffsets = structureID->m_deletedOffsets;
    305394    transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity;
    306395    transition->m_hasGetterSetterProperties = structureID->m_hasGetterSetterProperties;
     396
     397    if (structureID->m_propertyTable) {
     398        if (structureID->m_isPinnedPropertyTable)
     399            transition->m_propertyTable = structureID->copyPropertyTable();
     400        else {
     401            transition->m_propertyTable = structureID->m_propertyTable;
     402            structureID->m_propertyTable = 0;
     403        }
     404    } else {
     405        if (structureID->m_previous)
     406            transition->materializePropertyMap();
     407        else
     408            transition->createPropertyMapHashTable();
     409    }
    307410
    308411    offset = transition->put(propertyName, attributes);
    … …  
    310413        transition->growPropertyStorageCapacity();
    311414
    312     transition->setCachedTransistionOffset(offset);
     415    transition->m_offset = offset;
    313416
    314417    if (structureID->m_usingSingleTransitionSlot) {
    … …  
    332435    ASSERT(!structureID->m_isDictionary);
    333436
    334     RefPtr<StructureID> transition = create(structureID->m_prototype, structureID->typeInfo());
    335     transition->m_isDictionary = true;
    336     transition->m_propertyTable = structureID->copyPropertyTable();
     437    RefPtr<StructureID> transition = toDictionaryTransition(structureID);
     438
     439    offset = transition->remove(propertyName);
     440
     441    return transition.release();
     442}
     443
     444PassRefPtr<StructureID> StructureID::changePrototypeTransition(StructureID* structureID, JSValue* prototype)
     445{
     446    RefPtr<StructureID> transition = create(prototype, structureID->typeInfo());
     447
     448    transition->m_transitionCount = structureID->m_transitionCount + 1;
    337449    transition->m_deletedOffsets = structureID->m_deletedOffsets;
    338450    transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity;
    339451    transition->m_hasGetterSetterProperties = structureID->m_hasGetterSetterProperties;
    340452
    341     offset = transition->remove(propertyName);
     453    // Don't set m_offset, as one can not transition to this.
     454
     455    structureID->materializePropertyMapIfNecessary();
     456    transition->m_propertyTable = structureID->copyPropertyTable();
     457    transition->m_isPinnedPropertyTable = true;
     458
     459    return transition.release();
     460}
     461
     462PassRefPtr<StructureID> StructureID::getterSetterTransition(StructureID* structureID)
     463{
     464    RefPtr<StructureID> transition = create(structureID->storedPrototype(), structureID->typeInfo());
     465    transition->m_transitionCount = structureID->m_transitionCount + 1;
     466    transition->m_deletedOffsets = structureID->m_deletedOffsets;
     467    transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity;
     468    transition->m_hasGetterSetterProperties = transition->m_hasGetterSetterProperties;
     469
     470    // Don't set m_offset, as one can not transition to this.
     471
     472    structureID->materializePropertyMapIfNecessary();
     473    transition->m_propertyTable = structureID->copyPropertyTable();
     474    transition->m_isPinnedPropertyTable = true;
    342475
    343476    return transition.release();
    … …  
    350483    RefPtr<StructureID> transition = create(structureID->m_prototype, structureID->typeInfo());
    351484    transition->m_isDictionary = true;
    352     transition->m_propertyTable = structureID->copyPropertyTable();
    353485    transition->m_deletedOffsets = structureID->m_deletedOffsets;
    354486    transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity;
    355487    transition->m_hasGetterSetterProperties = structureID->m_hasGetterSetterProperties;
     488
     489    structureID->materializePropertyMapIfNecessary();
     490    transition->m_propertyTable = structureID->copyPropertyTable();
     491    transition->m_isPinnedPropertyTable = true;
     492
    356493    return transition.release();
    357494}
    … …  
    364501    // for them, we don't need to allocate a new StructureID when transitioning
    365502    // to non-dictionary status.
    366     structureID->m_isDictionary = false;
     503
     504    // FIMXE: We can make this more efficient by canonicalizing the StructureID (draining the
     505    // deleted offsets vector) before transitioning from dictionary.
     506    if (structureID->m_deletedOffsets.isEmpty())
     507        structureID->m_isDictionary = false;
     508
    367509    return structureID;
    368510}
    369511
    370 PassRefPtr<StructureID> StructureID::changePrototypeTransition(StructureID* structureID, JSValue* prototype)
    371 {
    372     RefPtr<StructureID> transition = create(prototype, structureID->typeInfo());
    373     transition->m_transitionCount = structureID->m_transitionCount + 1;
    374     transition->m_propertyTable = structureID->copyPropertyTable();
    375     transition->m_deletedOffsets = structureID->m_deletedOffsets;
    376     transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity;
    377     transition->m_hasGetterSetterProperties = structureID->m_hasGetterSetterProperties;
    378     return transition.release();
    379 }
    380 
    381 PassRefPtr<StructureID> StructureID::getterSetterTransition(StructureID* structureID)
    382 {
    383     RefPtr<StructureID> transition = create(structureID->storedPrototype(), structureID->typeInfo());
    384     transition->m_transitionCount = structureID->m_transitionCount + 1;
    385     transition->m_propertyTable = structureID->copyPropertyTable();
    386     transition->m_deletedOffsets = structureID->m_deletedOffsets;
    387     transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity;
    388     transition->m_hasGetterSetterProperties = transition->m_hasGetterSetterProperties;
    389     return transition.release();
    390 }
    391 
    392512size_t StructureID::addPropertyWithoutTransition(const Identifier& propertyName, unsigned attributes)
    393513{
     514    ASSERT(!m_transitions.singleTransition);
     515
     516    materializePropertyMapIfNecessary();
     517
     518    m_isPinnedPropertyTable = true;
    394519    size_t offset = put(propertyName, attributes);
    395520    if (propertyStorageSize() > propertyStorageCapacity())
    … …  
    401526size_t StructureID::removePropertyWithoutTransition(const Identifier& propertyName)
    402527{
     528    ASSERT(!m_transitions.singleTransition);
     529    ASSERT(m_isDictionary);
     530
     531    materializePropertyMapIfNecessary();
     532
     533    m_isPinnedPropertyTable = true;
    403534    size_t offset = remove(propertyName);
    404535    clearEnumerationCache();
    … …  
    450581inline void StructureID::checkConsistency()
    451582{
    452 }   
     583}
    453584
    454585#endif
    … …  
    472603}
    473604
    474 size_t StructureID::get(const Identifier& propertyName, unsigned& attributes) const
     605size_t StructureID::get(const Identifier& propertyName, unsigned& attributes)
    475606{
    476607    ASSERT(!propertyName.isNull());
    477608
     609    materializePropertyMapIfNecessary();
    478610    if (!m_propertyTable)
    479611        return WTF::notFound;
    … …  
    713845}
    714846
    715 void StructureID::expandPropertyMapHashTable()
    716 {
    717     ASSERT(m_propertyTable);
    718     rehashPropertyMapHashTable(m_propertyTable->size * 2);
    719 }
    720 
    721847void StructureID::createPropertyMapHashTable()
    722848{
    723     const unsigned newTableSize = 16;
    724 
     849    ASSERT(sizeForKeyCount(7) == newTableSize);
     850    createPropertyMapHashTable(newTableSize);
     851}
     852
     853void StructureID::createPropertyMapHashTable(unsigned newTableSize)
     854{
    725855    ASSERT(!m_propertyTable);
     856    ASSERT(isPowerOf2(newTableSize));
    726857
    727858    checkConsistency();
    … …  
    734865}
    735866
     867void StructureID::expandPropertyMapHashTable()
     868{
     869    ASSERT(m_propertyTable);
     870    rehashPropertyMapHashTable(m_propertyTable->size * 2);
     871}
     872
    736873void StructureID::rehashPropertyMapHashTable()
    737874{
    … …  
    744881{
    745882    ASSERT(m_propertyTable);
     883    ASSERT(isPowerOf2(newTableSize));
    746884
    747885    checkConsistency();
    … …  
    779917}
    780918
    781 void StructureID::getEnumerablePropertyNamesInternal(PropertyNameArray& propertyNames) const
    782 {
     919void StructureID::getEnumerablePropertyNamesInternal(PropertyNameArray& propertyNames)
     920{
     921    materializePropertyMapIfNecessary();
    783922    if (!m_propertyTable)
    784923        return;
    … …  
    842981        return;
    843982
    844     ASSERT(m_propertyTable->size >= 16);
     983    ASSERT(m_propertyTable->size >= newTableSize);
    845984    ASSERT(m_propertyTable->sizeMask);
    846985    ASSERT(m_propertyTable->size == m_propertyTable->sizeMask + 1);
Note: See TracChangeset for help on using the changeset viewer.