Changeset 263252 in webkit


Ignore:
Timestamp:
Jun 18, 2020 8:30:37 PM (4 years ago)
Author:
mark.lam@apple.com
Message:

Unify Bitmap math loops in MarkedBlock::Handle::specializedSweep().
​https://bugs.webkit.org/show_bug.cgi?id=213345

Reviewed by Robin Morisset and Saam Barati.

Source/JavaScriptCore:

This change appears to be performance neutral. However, we'll take the change
because we know that it does less work, and the new way of expressing the Bitmap
math in MarkedBlock::Handle::specializedSweep() does appear to be easier to
understand than the old code.

Also addressed feedback from Robin and Saam in ​https://bugs.webkit.org/show_bug.cgi?id=213071.

Changes made:

  1. Use the new Bitmap::words() API to get direct access to the underlying bits storage. With this, we can do the merging of the marked and newlyAllocated bits with a single pass looping thru the bitmap words.
  1. In MarkedBlock::Handle::specializedSweep()'s Bitmap free list code, moved the implementation of handleDeadCells lambda down to the call to freeAtoms.forEachSetBit() because this is the only place it is used.
  1. Fixed MarkedBlock::Handle::specializedSweep()'s Bitmap free list code to handle the dead cells unconditionally. This condition check was wrongly adapted from the linked list implementation where handleDeadCell() was called in 2 places depending on the destruction mode. With the Bitmap free list, there is only once place to handle the dead cells, and it should be executed unconditionally.

This fixes a bug where the FreeList::originalSize() never gets computed if the
cells in the block does not need destruction.

  1. Renamed FreeList::bitmapRows() to FreeList::bitmapRowsMinusOne(). Renamed FreeList::offsetOfBitmapRows() to FreeList::offsetOfBitmapRowsMinusOne().
  1. Also fixed some typos in comments.
  • heap/FreeList.h:

(JSC::FreeList::bitmapIsEmpty const):
(JSC::FreeList::offsetOfBitmapRowsMinusOne):
(JSC::FreeList::bitmapRowsMinusOne const):
(JSC::FreeList::offsetOfBitmapRows): Deleted.
(JSC::FreeList::bitmapRows const): Deleted.

  • heap/FreeListInlines.h:

(JSC::FreeList::allocate):
(JSC::FreeList::forEach const):

  • heap/MarkedBlockInlines.h:

(JSC::MarkedBlock::Handle::specializedSweep):

  • jit/AssemblyHelpers.cpp:

(JSC::AssemblyHelpers::emitAllocateWithNonNullAllocator):

Source/WTF:

  1. Removed Bitmap::words. Use Bitmap::numberOfWords instead.
  2. Removed Bitmap::wordSize. Use Bitmap::bitsInWord instead.
  3. Added a new Bitmap::words() method which returns the address of the underlying bitmap storage as a Bitmap::Word*. This enables clients to do direct bit manipulation on the Bitmap words if needed.
  • wtf/Bitmap.h:

(WTF::WordType>::get const):
(WTF::WordType>::set):
(WTF::WordType>::testAndSet):
(WTF::WordType>::testAndClear):
(WTF::WordType>::concurrentTestAndSet):
(WTF::WordType>::concurrentTestAndClear):
(WTF::WordType>::clear):
(WTF::WordType>::invert):
(WTF::WordType>::nextPossiblyUnset const):
(WTF::WordType>::count const):
(WTF::WordType>::isEmpty const):
(WTF::WordType>::isFull const):
(WTF::WordType>::merge):
(WTF::WordType>::filter):
(WTF::WordType>::exclude):
(WTF::WordType>::concurrentFilter):
(WTF::WordType>::subsumes const):
(WTF::WordType>::forEachSetBit const):
(WTF::WordType>::findBit const):
(WTF::WordType>::mergeAndClear):
(WTF::WordType>::setAndClear):
(WTF::WordType>::setEachNthBit):
(WTF::= const):
(WTF::=):
(WTF::WordType>::hash const):

Location:
trunk/Source
Files:
7 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ChangeLog

    r263250 r263252  
     12020-06-18  Mark Lam  <mark.lam@apple.com>
     2
     3        Unify Bitmap math loops in MarkedBlock::Handle::specializedSweep().
     4        https://bugs.webkit.org/show_bug.cgi?id=213345
     5
     6        Reviewed by Robin Morisset and Saam Barati.
     7
     8        This change appears to be performance neutral.  However, we'll take the change
     9        because we know that it does less work, and the new way of expressing the Bitmap
     10        math in MarkedBlock::Handle::specializedSweep() does appear to be easier to
     11        understand than the old code.
     12
     13        Also addressed feedback from Robin and Saam in https://bugs.webkit.org/show_bug.cgi?id=213071.
     14
     15        Changes made:
     16
     17        1. Use the new Bitmap::words() API to get direct access to the underlying bits
     18           storage.  With this, we can do the merging of the marked and newlyAllocated
     19           bits with a single pass looping thru the bitmap words.
     20
     21        2. In MarkedBlock::Handle::specializedSweep()'s Bitmap free list code, moved the
     22           implementation of handleDeadCells lambda down to the call to freeAtoms.forEachSetBit()
     23           because this is the only place it is used.
     24
     25        3. Fixed MarkedBlock::Handle::specializedSweep()'s Bitmap free list code to
     26           handle the dead cells unconditionally.  This condition check was wrongly
     27           adapted from the linked list implementation where handleDeadCell() was called
     28           in 2 places depending on the destruction mode.  With the Bitmap free list,
     29           there is only once place to handle the dead cells, and it should be executed
     30           unconditionally.
     31
     32           This fixes a bug where the FreeList::originalSize() never gets computed if the
     33           cells in the block does not need destruction.
     34
     35        4. Renamed FreeList::bitmapRows() to FreeList::bitmapRowsMinusOne().
     36           Renamed FreeList::offsetOfBitmapRows() to FreeList::offsetOfBitmapRowsMinusOne().
     37
     38        5. Also fixed some typos in comments.
     39
     40        * heap/FreeList.h:
     41        (JSC::FreeList::bitmapIsEmpty const):
     42        (JSC::FreeList::offsetOfBitmapRowsMinusOne):
     43        (JSC::FreeList::bitmapRowsMinusOne const):
     44        (JSC::FreeList::offsetOfBitmapRows): Deleted.
     45        (JSC::FreeList::bitmapRows const): Deleted.
     46        * heap/FreeListInlines.h:
     47        (JSC::FreeList::allocate):
     48        (JSC::FreeList::forEach const):
     49        * heap/MarkedBlockInlines.h:
     50        (JSC::MarkedBlock::Handle::specializedSweep):
     51        * jit/AssemblyHelpers.cpp:
     52        (JSC::AssemblyHelpers::emitAllocateWithNonNullAllocator):
     53
    1542020-06-18  Yusuke Suzuki  <ysuzuki@apple.com>
    255
    … …  
    206259        5. On the layout of fields in FreeList (see changes in FreeList.h), we try to
    207260           preserve the positions of the bump allocator fields.  The only change we made
    208            there is n the location of m_cellSize.  It is now moved up next to m_remaining,
     261           there is in the location of m_cellSize.  It is now moved up next to m_remaining,
    209262           and m_originalSize is moved down.  This is because m_originalSize is only
    210263           accessed in the slow path, and m_cellSize is accessed in the bump allocation

  • trunk/Source/JavaScriptCore/heap/FreeList.h

    r263195 r263252  
    106106        // Remember, we don't actually clear the bits in m_bitmap as we allocate
    107107        // the atoms. Instead, m_currentRowBitmap and m_currentRowIndex tells us
    108         // if there atoms still available for allocation. See comment blob below
     108        // if there are atoms still available for allocation. See comment blob below
    109109        // at the declaration of m_currentRowIndex for more details.
    110110        return !m_currentRowBitmap && !m_currentRowIndex;
    … …  
    117117    // we can schedule instructions better i.e. to do a load before decrementing the
    118118    // row index.
    119     static ptrdiff_t offsetOfBitmapRows() { return OBJECT_OFFSETOF(FreeList, m_bitmap) - sizeof(AtomsBitmap::Word); }
     119    static ptrdiff_t offsetOfBitmapRowsMinusOne() { return OBJECT_OFFSETOF(FreeList, m_bitmap) - sizeof(AtomsBitmap::Word); }
    120120
    121121    static ptrdiff_t offsetOfCurrentRowIndex() { return OBJECT_OFFSETOF(FreeList, m_currentRowIndex); }
    … …  
    142142#if ENABLE(BITMAP_FREELIST)
    143143    AtomsBitmap& atomsBitmap() { return m_bitmap; }
    144     AtomsBitmap::Word* bitmapRows() const
    145     {
    146         // See comment about offsetOfBitmapRows().
     144    AtomsBitmap::Word* bitmapRowsMinusOne() const
     145    {
     146        // See comment about offsetOfBitmapRowsMinusOne().
    147147        return bitwise_cast<AtomsBitmap::Word*>(&m_bitmap) - 1;
    148148    }

  • trunk/Source/JavaScriptCore/heap/FreeListInlines.h

    r263195 r263252  
    5757        auto* rowAddress = m_currentMarkedBlockRowAddress;
    5858        while (rowIndex) {
    59             // We load before decrementing rowIndex because bitmapRows() points
    60             // to 1 word before m_bitmap. See comments about offsetOfBitmapRows()
     59            // We load before decrementing rowIndex because bitmapRowsMinusOne() points
     60            // to 1 word before m_bitmap. See comments about offsetOfBitmapRowsMinusOne()
    6161            // for why we do this.
    62             rowBitmap = bitmapRows()[rowIndex--];
     62            rowBitmap = bitmapRowsMinusOne()[rowIndex--];
    6363            rowAddress -= atomsPerRow;
    6464            if (rowBitmap)
    … …  
    107107
    108108            while (rowIndex) {
    109                 // We load before decrementing rowIndex because bitmapRows() points
    110                 // to 1 word before m_bitmap. See comments about offsetOfBitmapRows()
     109                // We load before decrementing rowIndex because bitmapRowsMinusOne() points
     110                // to 1 word before m_bitmap. See comments about offsetOfBitmapRowsMinusOne()
    111111                // for why we do this.
    112                 rowBitmap = bitmapRows()[rowIndex--];
     112                rowBitmap = bitmapRowsMinusOne()[rowIndex--];
    113113                currentMarkedBlockRowAddress -= atomsPerRow;
    114114                if (rowBitmap)

  • trunk/Source/JavaScriptCore/heap/MarkedBlockInlines.h

    r263195 r263252  
    265265    m_directory->setIsDestructible(NoLockingNecessary, this, false);
    266266   
     267    char* startOfLastCell = static_cast<char*>(cellAlign(block.atoms() + m_endAtom - 1));
     268    char* payloadEnd = startOfLastCell + cellSize;
     269    RELEASE_ASSERT(payloadEnd - MarkedBlock::blockSize <= bitwise_cast<char*>(&block));
     270    char* payloadBegin = bitwise_cast<char*>(block.atoms());
     271
    267272    if (Options::useBumpAllocator()
    268273        && emptyMode == IsEmpty
    … …  
    281286        }
    282287       
    283         char* startOfLastCell = static_cast<char*>(cellAlign(block.atoms() + m_endAtom - 1));
    284         char* payloadEnd = startOfLastCell + cellSize;
    285         RELEASE_ASSERT(payloadEnd - MarkedBlock::blockSize <= bitwise_cast<char*>(&block));
    286         char* payloadBegin = bitwise_cast<char*>(block.atoms());
    287        
    288288        if (sweepMode == SweepToFreeList)
    289289            setIsFreeListed();
    … …  
    305305
    306306#if ENABLE(BITMAP_FREELIST)
     307    // The code below is an optimized version of the following by merging the
     308    // various loops over the bitmaps.
     309    //
     310    //    AtomsBitmap cellLocations;
     311    //    cellLocations.setEachNthBit(m_atomsPerCell, 0, m_endAtom);
     312    //
     313    //    if (emptyMode == NotEmpty) {
     314    //        if (marksMode == MarksNotStale) {
     315    //            freeAtoms = footer.m_marks;
     316    //            if (newlyAllocatedMode == HasNewlyAllocated)
     317    //                freeAtoms |= footer.m_newlyAllocated;
     318    //        } else if (newlyAllocatedMode == HasNewlyAllocated)
     319    //            freeAtoms = footer.m_newlyAllocated;
     320    //        // At this point, a set bit in freeAtoms represents live cells.
     321    //        isEmpty = freeAtoms.isEmpty();
     322    //
     323    //        // Invert the bits at each cell location so that the ones for live cells
     324    //        // are cleared, and the ones for dead cells are set.
     325    //        freeAtoms ^= cellLocations;
     326    //    } else
     327    //        freeAtoms = cellLocations; // all cells are free.
     328
    307329    AtomsBitmap localFreeAtoms;
    308330    AtomsBitmap& freeAtoms = freeList ? freeList->atomsBitmap() : localFreeAtoms;
    309     size_t count = 0;
    310 
    311     auto handleDeadCell = [&] (size_t i) {
    312         HeapCell* cell = reinterpret_cast_ptr<HeapCell*>(atomAt(i));
    313 
    314         if (destructionMode != BlockHasNoDestructors)
    315             destroy(cell);
    316 
    317         if (sweepMode == SweepToFreeList) {
    318             if (scribbleMode == Scribble)
    319                 scribble(cell, cellSize);
    320             ++count;
    321         }
    322     };
    323 
    324     bool isEmpty = true;
    325 
    326     AtomsBitmap cellLocations;
    327     cellLocations.setEachNthBit(m_atomsPerCell, 0, m_endAtom);
     331
     332    AtomsBitmap::Word* free = freeAtoms.words();
     333    AtomsBitmap::Word* marks = footer.m_marks.words();
     334    AtomsBitmap::Word* newlyAllocated = footer.m_newlyAllocated.words();
     335
     336    unsigned roundedUpEndAtoms = roundUpToMultipleOf<AtomsBitmap::bitsInWord>(m_endAtom);
     337    unsigned endWordIndex = roundedUpEndAtoms / AtomsBitmap::bitsInWord;
     338    ASSERT(m_endAtom <= endWordIndex * AtomsBitmap::bitsInWord);
     339
     340    if (freeList)
     341        freeAtoms.clearAll();
     342    freeAtoms.setEachNthBit(m_atomsPerCell, 0, m_endAtom);
    328343
    329344    if (emptyMode == NotEmpty) {
    330         if (marksMode == MarksNotStale) {
    331             freeAtoms = footer.m_marks;
    332             if (newlyAllocatedMode == HasNewlyAllocated)
    333                 freeAtoms |= footer.m_newlyAllocated;
    334         } else if (newlyAllocatedMode == HasNewlyAllocated)
    335             freeAtoms = footer.m_newlyAllocated;
    336         // At this point, a set bit in freeAtoms represents live cells.
    337         isEmpty = freeAtoms.isEmpty();
    338 
    339         // Invert the bits at each cell location so that the ones for live cells
    340         // are cleared, and the ones for dead cells are set.
    341         freeAtoms ^= cellLocations;
    342     } else
    343         freeAtoms = cellLocations; // all cells are free.
    344    
     345        if (marksMode == MarksNotStale && newlyAllocatedMode == HasNewlyAllocated) {
     346            for (unsigned i = 0; i < endWordIndex; ++i)
     347                free[i] ^= marks[i] | newlyAllocated[i];
     348
     349        } else if (marksMode == MarksNotStale) {
     350            for (unsigned i = 0; i < endWordIndex; ++i)
     351                free[i] ^= marks[i];
     352
     353        } else if (newlyAllocatedMode == HasNewlyAllocated) {
     354            for (unsigned i = 0; i < endWordIndex; ++i)
     355                free[i] ^= newlyAllocated[i];
     356        }
     357    }
     358
     359    // At this point, a set bit in freeAtoms represents a dead cell.
     360
    345361    // We only want to discard the newlyAllocated bits if we're creating a FreeList,
    346362    // otherwise we would lose information on what's currently alive.
    … …  
    351367        footer.m_lock.unlock();
    352368
    353     if (destructionMode != BlockHasNoDestructors)
    354         freeAtoms.forEachSetBit(handleDeadCell);
    355 
     369    // Handle dead cells.
     370    unsigned deadCellCount = 0;
     371    freeAtoms.forEachSetBit([&] (size_t i) {
     372        HeapCell* cell = reinterpret_cast_ptr<HeapCell*>(atomAt(i));
     373
     374        if (destructionMode != BlockHasNoDestructors)
     375            destroy(cell);
     376
     377        if (sweepMode == SweepToFreeList) {
     378            if (scribbleMode == Scribble)
     379                scribble(cell, cellSize);
     380        }
     381        ++deadCellCount;
     382    });
     383
     384    unsigned numberOfCellsInBlock = (payloadEnd - payloadBegin) / cellSize;
     385    bool isEmpty = (deadCellCount == numberOfCellsInBlock);
    356386    if (sweepMode == SweepToFreeList) {
    357         freeList->initializeAtomsBitmap(this, freeAtoms, count * cellSize);
     387        freeList->initializeAtomsBitmap(this, freeAtoms, deadCellCount * cellSize);
    358388        setIsFreeListed();
    359389    } else if (isEmpty)

  • trunk/Source/JavaScriptCore/jit/AssemblyHelpers.cpp

    r263195 r263252  
    592592        // Load the next row bitmap and point m_currentMarkedBlockRowAddress to the next row.
    593593
    594         // Note: offsetOfBitmapRows() points to 1 word before m_bitmap. We do this
     594        // Note: offsetOfBitmapRowsMinusOne() points to 1 word before m_bitmap. We do this
    595595        // deliberately because it allows us to schedule instructions better and
    596596        // do this load before the decrement below.
    597         load64(BaseIndex(allocatorGPR, rowIndexGPR, TimesEight, LocalAllocator::offsetOfFreeList() + FreeList::offsetOfBitmapRows()), rowBitmapGPR);
     597        load64(BaseIndex(allocatorGPR, rowIndexGPR, TimesEight, LocalAllocator::offsetOfFreeList() + FreeList::offsetOfBitmapRowsMinusOne()), rowBitmapGPR);
    598598
    599599        sub64(TrustedImm32(1), rowIndexGPR);

  • trunk/Source/WTF/ChangeLog

    r263223 r263252  
     12020-06-18  Mark Lam  <mark.lam@apple.com>
     2
     3        Unify Bitmap math loops in MarkedBlock::Handle::specializedSweep().
     4        https://bugs.webkit.org/show_bug.cgi?id=213345
     5
     6        Reviewed by Robin Morisset and Saam Barati.
     7
     8        1. Removed Bitmap::words.  Use Bitmap::numberOfWords instead.
     9        2. Removed Bitmap::wordSize.  Use Bitmap::bitsInWord instead.
     10        3. Added a new Bitmap::words() method which returns the address of the underlying
     11           bitmap storage as a Bitmap::Word*.  This enables clients to do direct bit
     12           manipulation on the Bitmap words if needed.
     13
     14        * wtf/Bitmap.h:
     15        (WTF::WordType>::get const):
     16        (WTF::WordType>::set):
     17        (WTF::WordType>::testAndSet):
     18        (WTF::WordType>::testAndClear):
     19        (WTF::WordType>::concurrentTestAndSet):
     20        (WTF::WordType>::concurrentTestAndClear):
     21        (WTF::WordType>::clear):
     22        (WTF::WordType>::invert):
     23        (WTF::WordType>::nextPossiblyUnset const):
     24        (WTF::WordType>::count const):
     25        (WTF::WordType>::isEmpty const):
     26        (WTF::WordType>::isFull const):
     27        (WTF::WordType>::merge):
     28        (WTF::WordType>::filter):
     29        (WTF::WordType>::exclude):
     30        (WTF::WordType>::concurrentFilter):
     31        (WTF::WordType>::subsumes const):
     32        (WTF::WordType>::forEachSetBit const):
     33        (WTF::WordType>::findBit const):
     34        (WTF::WordType>::mergeAndClear):
     35        (WTF::WordType>::setAndClear):
     36        (WTF::WordType>::setEachNthBit):
     37        (WTF::= const):
     38        (WTF::=):
     39        (WTF::WordType>::hash const):
     40
    1412020-06-18  Geoffrey Garen  <ggaren@apple.com>
    242

  • trunk/Source/WTF/wtf/Bitmap.h

    r263195 r263252  
    136136    static constexpr unsigned numberOfWords = (bitmapSize + bitsInWord - 1) / bitsInWord;
    137137    WordType wordAt(size_t wordIndex) const { return bits[wordIndex]; }
     138    Word* words() { return bitwise_cast<Word*>(&bits); }
    138139
    139140private:
    140     static constexpr unsigned wordSize = bitsInWord;
    141     static constexpr unsigned words = numberOfWords;
    142 
    143141    // the literal '1' is of type signed int.  We want to use an unsigned
    144142    // version of the correct size when doing the calculations because if
    … …  
    148146    static constexpr WordType one = 1;
    149147
    150     std::array<WordType, words> bits;
     148    std::array<WordType, numberOfWords> bits;
    151149};
    152150
    … …  
    160158inline bool Bitmap<bitmapSize, WordType>::get(size_t n, Dependency dependency) const
    161159{
    162     return !!(dependency.consume(this)->bits[n / wordSize] & (one << (n % wordSize)));
     160    return !!(dependency.consume(this)->bits[n / bitsInWord] & (one << (n % bitsInWord)));
    163161}
    164162
    … …  
    166164inline void Bitmap<bitmapSize, WordType>::set(size_t n)
    167165{
    168     bits[n / wordSize] |= (one << (n % wordSize));
     166    bits[n / bitsInWord] |= (one << (n % bitsInWord));
    169167}
    170168
    … …  
    181179inline bool Bitmap<bitmapSize, WordType>::testAndSet(size_t n)
    182180{
    183     WordType mask = one << (n % wordSize);
    184     size_t index = n / wordSize;
     181    WordType mask = one << (n % bitsInWord);
     182    size_t index = n / bitsInWord;
    185183    bool result = bits[index] & mask;
    186184    bits[index] |= mask;
    … …  
    191189inline bool Bitmap<bitmapSize, WordType>::testAndClear(size_t n)
    192190{
    193     WordType mask = one << (n % wordSize);
    194     size_t index = n / wordSize;
     191    WordType mask = one << (n % bitsInWord);
     192    size_t index = n / bitsInWord;
    195193    bool result = bits[index] & mask;
    196194    bits[index] &= ~mask;
    … …  
    201199ALWAYS_INLINE bool Bitmap<bitmapSize, WordType>::concurrentTestAndSet(size_t n, Dependency dependency)
    202200{
    203     WordType mask = one << (n % wordSize);
    204     size_t index = n / wordSize;
     201    WordType mask = one << (n % bitsInWord);
     202    size_t index = n / bitsInWord;
    205203    WordType* data = dependency.consume(bits.data()) + index;
    206204    return !bitwise_cast<Atomic<WordType>*>(data)->transactionRelaxed(
    … …  
    217215ALWAYS_INLINE bool Bitmap<bitmapSize, WordType>::concurrentTestAndClear(size_t n, Dependency dependency)
    218216{
    219     WordType mask = one << (n % wordSize);
    220     size_t index = n / wordSize;
     217    WordType mask = one << (n % bitsInWord);
     218    size_t index = n / bitsInWord;
    221219    WordType* data = dependency.consume(bits.data()) + index;
    222220    return !bitwise_cast<Atomic<WordType>*>(data)->transactionRelaxed(
    … …  
    233231inline void Bitmap<bitmapSize, WordType>::clear(size_t n)
    234232{
    235     bits[n / wordSize] &= ~(one << (n % wordSize));
     233    bits[n / bitsInWord] &= ~(one << (n % bitsInWord));
    236234}
    237235
    … …  
    245243inline void Bitmap<bitmapSize, WordType>::invert()
    246244{
    247     for (size_t i = 0; i < words; ++i)
     245    for (size_t i = 0; i < numberOfWords; ++i)
    248246        bits[i] = ~bits[i];
    249     if constexpr (!!(bitmapSize % wordSize)) {
    250         constexpr size_t remainingBits = bitmapSize % wordSize;
     247    if constexpr (!!(bitmapSize % bitsInWord)) {
     248        constexpr size_t remainingBits = bitmapSize % bitsInWord;
    251249        constexpr WordType mask = (static_cast<WordType>(1) << remainingBits) - 1;
    252         bits[words - 1] &= mask;
     250        bits[numberOfWords - 1] &= mask;
    253251    }
    254252}
    … …  
    257255inline size_t Bitmap<bitmapSize, WordType>::nextPossiblyUnset(size_t start) const
    258256{
    259     if (!~bits[start / wordSize])
    260         return ((start / wordSize) + 1) * wordSize;
     257    if (!~bits[start / bitsInWord])
     258        return ((start / bitsInWord) + 1) * bitsInWord;
    261259    return start + 1;
    262260}
    … …  
    289287{
    290288    size_t result = 0;
    291     for ( ; (start % wordSize); ++start) {
     289    for ( ; (start % bitsInWord); ++start) {
    292290        if (get(start))
    293291            ++result;
    294292    }
    295     for (size_t i = start / wordSize; i < words; ++i)
     293    for (size_t i = start / bitsInWord; i < numberOfWords; ++i)
    296294        result += WTF::bitCount(bits[i]);
    297295    return result;
    … …  
    301299inline bool Bitmap<bitmapSize, WordType>::isEmpty() const
    302300{
    303     for (size_t i = 0; i < words; ++i)
     301    for (size_t i = 0; i < numberOfWords; ++i) {
    304302        if (bits[i])
    305303            return false;
     304    }
    306305    return true;
    307306}
    … …  
    310309inline bool Bitmap<bitmapSize, WordType>::isFull() const
    311310{
    312     for (size_t i = 0; i < words; ++i)
     311    for (size_t i = 0; i < numberOfWords; ++i) {
    313312        if (~bits[i]) {
    314             if constexpr (!!(bitmapSize % wordSize)) {
    315                 if (i == words - 1) {
    316                     constexpr size_t remainingBits = bitmapSize % wordSize;
     313            if constexpr (!!(bitmapSize % bitsInWord)) {
     314                if (i == numberOfWords - 1) {
     315                    constexpr size_t remainingBits = bitmapSize % bitsInWord;
    317316                    constexpr WordType mask = (static_cast<WordType>(1) << remainingBits) - 1;
    318317                    if ((bits[i] & mask) == mask)
    … …  
    322321            return false;
    323322        }
     323    }
    324324    return true;
    325325}
    … …  
    328328inline void Bitmap<bitmapSize, WordType>::merge(const Bitmap& other)
    329329{
    330     for (size_t i = 0; i < words; ++i)
     330    for (size_t i = 0; i < numberOfWords; ++i)
    331331        bits[i] |= other.bits[i];
    332332}
    … …  
    335335inline void Bitmap<bitmapSize, WordType>::filter(const Bitmap& other)
    336336{
    337     for (size_t i = 0; i < words; ++i)
     337    for (size_t i = 0; i < numberOfWords; ++i)
    338338        bits[i] &= other.bits[i];
    339339}
    … …  
    342342inline void Bitmap<bitmapSize, WordType>::exclude(const Bitmap& other)
    343343{
    344     for (size_t i = 0; i < words; ++i)
     344    for (size_t i = 0; i < numberOfWords; ++i)
    345345        bits[i] &= ~other.bits[i];
    346346}
    … …  
    349349inline void Bitmap<bitmapSize, WordType>::concurrentFilter(const Bitmap& other)
    350350{
    351     for (size_t i = 0; i < words; ++i) {
     351    for (size_t i = 0; i < numberOfWords; ++i) {
    352352        for (;;) {
    353353            WordType otherBits = other.bits[i];
    … …  
    369369inline bool Bitmap<bitmapSize, WordType>::subsumes(const Bitmap& other) const
    370370{
    371     for (size_t i = 0; i < words; ++i) {
     371    for (size_t i = 0; i < numberOfWords; ++i) {
    372372        WordType myBits = bits[i];
    373373        WordType otherBits = other.bits[i];
    … …  
    382382inline void Bitmap<bitmapSize, WordType>::forEachSetBit(const Func& func) const
    383383{
    384     for (size_t i = 0; i < words; ++i) {
     384    for (size_t i = 0; i < numberOfWords; ++i) {
    385385        WordType word = bits[i];
    386         size_t base = i * wordSize;
     386        size_t base = i * bitsInWord;
    387387        size_t j = 0;
    388388        for (; word; ++j) {
    … …  
    391391            word >>= 1;
    392392        }
    393         ASSERT(j <= wordSize);
     393        ASSERT(j <= bitsInWord);
    394394    }
    395395}
    … …  
    399399{
    400400    WordType skipValue = -(static_cast<WordType>(value) ^ 1);
    401     size_t wordIndex = startIndex / wordSize;
    402     size_t startIndexInWord = startIndex - wordIndex * wordSize;
    403    
    404     while (wordIndex < words) {
     401    size_t wordIndex = startIndex / bitsInWord;
     402    size_t startIndexInWord = startIndex - wordIndex * bitsInWord;
     403   
     404    while (wordIndex < numberOfWords) {
    405405        WordType word = bits[wordIndex];
    406406        if (word != skipValue) {
    407407            size_t index = startIndexInWord;
    408             if (findBitInWord(word, index, wordSize, value))
    409                 return wordIndex * wordSize + index;
     408            if (findBitInWord(word, index, bitsInWord, value))
     409                return wordIndex * bitsInWord + index;
    410410        }
    411411       
    … …  
    420420inline void Bitmap<bitmapSize, WordType>::mergeAndClear(Bitmap& other)
    421421{
    422     for (size_t i = 0; i < words; ++i) {
     422    for (size_t i = 0; i < numberOfWords; ++i) {
    423423        bits[i] |= other.bits[i];
    424424        other.bits[i] = 0;
    … …  
    429429inline void Bitmap<bitmapSize, WordType>::setAndClear(Bitmap& other)
    430430{
    431     for (size_t i = 0; i < words; ++i) {
     431    for (size_t i = 0; i < numberOfWords; ++i) {
    432432        bits[i] = other.bits[i];
    433433        other.bits[i] = 0;
    … …  
    441441    ASSERT(end <= bitmapSize);
    442442
    443     size_t wordIndex = start / wordSize;
    444     size_t endWordIndex = end / wordSize;
    445     size_t index = start - wordIndex * wordSize;
     443    size_t wordIndex = start / bitsInWord;
     444    size_t endWordIndex = end / bitsInWord;
     445    size_t index = start - wordIndex * bitsInWord;
    446446    while (wordIndex < endWordIndex) {
    447         while (index < wordSize) {
     447        while (index < bitsInWord) {
    448448            bits[wordIndex] |= (one << index);
    449449            index += n;
    450450        }
    451         index -= wordSize;
     451        index -= bitsInWord;
    452452        wordIndex++;
    453453    }
    454454
    455     size_t endIndex = end - endWordIndex * wordSize;
     455    size_t endIndex = end - endWordIndex * bitsInWord;
    456456    while (index < endIndex) {
    457457        bits[wordIndex] |= (one << index);
    … …  
    459459    }
    460460
    461     if constexpr (!!(bitmapSize % wordSize)) {
    462         constexpr size_t remainingBits = bitmapSize % wordSize;
     461    if constexpr (!!(bitmapSize % bitsInWord)) {
     462        constexpr size_t remainingBits = bitmapSize % bitsInWord;
    463463        constexpr WordType mask = (static_cast<WordType>(1) << remainingBits) - 1;
    464         bits[words - 1] &= mask;
     464        bits[numberOfWords - 1] &= mask;
    465465    }
    466466}
    … …  
    469469inline bool Bitmap<bitmapSize, WordType>::operator==(const Bitmap& other) const
    470470{
    471     for (size_t i = 0; i < words; ++i) {
     471    for (size_t i = 0; i < numberOfWords; ++i) {
    472472        if (bits[i] != other.bits[i])
    473473            return false;
    … …  
    485485inline void Bitmap<bitmapSize, WordType>::operator|=(const Bitmap& other)
    486486{
    487     for (size_t i = 0; i < words; ++i)
     487    for (size_t i = 0; i < numberOfWords; ++i)
    488488        bits[i] |= other.bits[i];
    489489}
    … …  
    492492inline void Bitmap<bitmapSize, WordType>::operator&=(const Bitmap& other)
    493493{
    494     for (size_t i = 0; i < words; ++i)
     494    for (size_t i = 0; i < numberOfWords; ++i)
    495495        bits[i] &= other.bits[i];
    496496}
    … …  
    499499inline void Bitmap<bitmapSize, WordType>::operator^=(const Bitmap& other)
    500500{
    501     for (size_t i = 0; i < words; ++i)
     501    for (size_t i = 0; i < numberOfWords; ++i)
    502502        bits[i] ^= other.bits[i];
    503503}
    … …  
    507507{
    508508    unsigned result = 0;
    509     for (size_t i = 0; i < words; ++i)
     509    for (size_t i = 0; i < numberOfWords; ++i)
    510510        result ^= IntHash<WordType>::hash(bits[i]);
    511511    return result;
Note: See TracChangeset for help on using the changeset viewer.