Modified: trunk/Source/_javascript_Core/heap/MarkedBlockInlines.h (263251 => 263252)
--- trunk/Source/_javascript_Core/heap/MarkedBlockInlines.h 2020-06-19 01:45:29 UTC (rev 263251)
+++ trunk/Source/_javascript_Core/heap/MarkedBlockInlines.h 2020-06-19 03:30:37 UTC (rev 263252)
@@ -264,6 +264,11 @@
m_directory->setIsDestructible(NoLockingNecessary, this, false);
+ char* startOfLastCell = static_cast<char*>(cellAlign(block.atoms() + m_endAtom - 1));
+ char* payloadEnd = startOfLastCell + cellSize;
+ RELEASE_ASSERT(payloadEnd - MarkedBlock::blockSize <= bitwise_cast<char*>(&block));
+ char* payloadBegin = bitwise_cast<char*>(block.atoms());
+
if (Options::useBumpAllocator()
&& emptyMode == IsEmpty
&& newlyAllocatedMode == DoesNotHaveNewlyAllocated) {
@@ -280,11 +285,6 @@
});
}
- char* startOfLastCell = static_cast<char*>(cellAlign(block.atoms() + m_endAtom - 1));
- char* payloadEnd = startOfLastCell + cellSize;
- RELEASE_ASSERT(payloadEnd - MarkedBlock::blockSize <= bitwise_cast<char*>(&block));
- char* payloadBegin = bitwise_cast<char*>(block.atoms());
-
if (sweepMode == SweepToFreeList)
setIsFreeListed();
if (space()->isMarking())
@@ -304,44 +304,60 @@
}
#if ENABLE(BITMAP_FREELIST)
+ // The code below is an optimized version of the following by merging the
+ // various loops over the bitmaps.
+ //
+ // AtomsBitmap cellLocations;
+ // cellLocations.setEachNthBit(m_atomsPerCell, 0, m_endAtom);
+ //
+ // if (emptyMode == NotEmpty) {
+ // if (marksMode == MarksNotStale) {
+ // freeAtoms = footer.m_marks;
+ // if (newlyAllocatedMode == HasNewlyAllocated)
+ // freeAtoms |= footer.m_newlyAllocated;
+ // } else if (newlyAllocatedMode == HasNewlyAllocated)
+ // freeAtoms = footer.m_newlyAllocated;
+ // // At this point, a set bit in freeAtoms represents live cells.
+ // isEmpty = freeAtoms.isEmpty();
+ //
+ // // Invert the bits at each cell location so that the ones for live cells
+ // // are cleared, and the ones for dead cells are set.
+ // freeAtoms ^= cellLocations;
+ // } else
+ // freeAtoms = cellLocations; // all cells are free.
+
AtomsBitmap localFreeAtoms;
AtomsBitmap& freeAtoms = freeList ? freeList->atomsBitmap() : localFreeAtoms;
- size_t count = 0;
- auto handleDeadCell = [&] (size_t i) {
- HeapCell* cell = reinterpret_cast_ptr<HeapCell*>(atomAt(i));
+ AtomsBitmap::Word* free = freeAtoms.words();
+ AtomsBitmap::Word* marks = footer.m_marks.words();
+ AtomsBitmap::Word* newlyAllocated = footer.m_newlyAllocated.words();
- if (destructionMode != BlockHasNoDestructors)
- destroy(cell);
+ unsigned roundedUpEndAtoms = roundUpToMultipleOf<AtomsBitmap::bitsInWord>(m_endAtom);
+ unsigned endWordIndex = roundedUpEndAtoms / AtomsBitmap::bitsInWord;
+ ASSERT(m_endAtom <= endWordIndex * AtomsBitmap::bitsInWord);
- if (sweepMode == SweepToFreeList) {
- if (scribbleMode == Scribble)
- scribble(cell, cellSize);
- ++count;
- }
- };
+ if (freeList)
+ freeAtoms.clearAll();
+ freeAtoms.setEachNthBit(m_atomsPerCell, 0, m_endAtom);
- bool isEmpty = true;
+ if (emptyMode == NotEmpty) {
+ if (marksMode == MarksNotStale && newlyAllocatedMode == HasNewlyAllocated) {
+ for (unsigned i = 0; i < endWordIndex; ++i)
+ free[i] ^= marks[i] | newlyAllocated[i];
- AtomsBitmap cellLocations;
- cellLocations.setEachNthBit(m_atomsPerCell, 0, m_endAtom);
+ } else if (marksMode == MarksNotStale) {
+ for (unsigned i = 0; i < endWordIndex; ++i)
+ free[i] ^= marks[i];
- if (emptyMode == NotEmpty) {
- if (marksMode == MarksNotStale) {
- freeAtoms = footer.m_marks;
- if (newlyAllocatedMode == HasNewlyAllocated)
- freeAtoms |= footer.m_newlyAllocated;
- } else if (newlyAllocatedMode == HasNewlyAllocated)
- freeAtoms = footer.m_newlyAllocated;
- // At this point, a set bit in freeAtoms represents live cells.
- isEmpty = freeAtoms.isEmpty();
+ } else if (newlyAllocatedMode == HasNewlyAllocated) {
+ for (unsigned i = 0; i < endWordIndex; ++i)
+ free[i] ^= newlyAllocated[i];
+ }
+ }
- // Invert the bits at each cell location so that the ones for live cells
- // are cleared, and the ones for dead cells are set.
- freeAtoms ^= cellLocations;
- } else
- freeAtoms = cellLocations; // all cells are free.
-
+ // At this point, a set bit in freeAtoms represents a dead cell.
+
// We only want to discard the newlyAllocated bits if we're creating a FreeList,
// otherwise we would lose information on what's currently alive.
if (sweepMode == SweepToFreeList && newlyAllocatedMode == HasNewlyAllocated)
@@ -350,11 +366,25 @@
if (space()->isMarking())
footer.m_lock.unlock();
- if (destructionMode != BlockHasNoDestructors)
- freeAtoms.forEachSetBit(handleDeadCell);
+ // Handle dead cells.
+ unsigned deadCellCount = 0;
+ freeAtoms.forEachSetBit([&] (size_t i) {
+ HeapCell* cell = reinterpret_cast_ptr<HeapCell*>(atomAt(i));
+ if (destructionMode != BlockHasNoDestructors)
+ destroy(cell);
+
+ if (sweepMode == SweepToFreeList) {
+ if (scribbleMode == Scribble)
+ scribble(cell, cellSize);
+ }
+ ++deadCellCount;
+ });
+
+ unsigned numberOfCellsInBlock = (payloadEnd - payloadBegin) / cellSize;
+ bool isEmpty = (deadCellCount == numberOfCellsInBlock);
if (sweepMode == SweepToFreeList) {
- freeList->initializeAtomsBitmap(this, freeAtoms, count * cellSize);
+ freeList->initializeAtomsBitmap(this, freeAtoms, deadCellCount * cellSize);
setIsFreeListed();
} else if (isEmpty)
m_directory->setIsEmpty(NoLockingNecessary, this, true);
Modified: trunk/Source/WTF/wtf/Bitmap.h (263251 => 263252)
--- trunk/Source/WTF/wtf/Bitmap.h 2020-06-19 01:45:29 UTC (rev 263251)
+++ trunk/Source/WTF/wtf/Bitmap.h 2020-06-19 03:30:37 UTC (rev 263252)
@@ -135,11 +135,9 @@
static constexpr unsigned bitsInWord = countOfBits<WordType>;
static constexpr unsigned numberOfWords = (bitmapSize + bitsInWord - 1) / bitsInWord;
WordType wordAt(size_t wordIndex) const { return bits[wordIndex]; }
+ Word* words() { return bitwise_cast<Word*>(&bits); }
private:
- static constexpr unsigned wordSize = bitsInWord;
- static constexpr unsigned words = numberOfWords;
-
// the literal '1' is of type signed int. We want to use an unsigned
// version of the correct size when doing the calculations because if
// WordType is larger than int, '1 << 31' will first be sign extended
@@ -147,7 +145,7 @@
// a 64 bit unsigned int would give 0xffff8000
static constexpr WordType _one_ = 1;
- std::array<WordType, words> bits;
+ std::array<WordType, numberOfWords> bits;
};
template<size_t bitmapSize, typename WordType>
@@ -159,13 +157,13 @@
template<size_t bitmapSize, typename WordType>
inline bool Bitmap<bitmapSize, WordType>::get(size_t n, Dependency dependency) const
{
- return !!(dependency.consume(this)->bits[n / wordSize] & (one << (n % wordSize)));
+ return !!(dependency.consume(this)->bits[n / bitsInWord] & (one << (n % bitsInWord)));
}
template<size_t bitmapSize, typename WordType>
inline void Bitmap<bitmapSize, WordType>::set(size_t n)
{
- bits[n / wordSize] |= (one << (n % wordSize));
+ bits[n / bitsInWord] |= (one << (n % bitsInWord));
}
template<size_t bitmapSize, typename WordType>
@@ -180,8 +178,8 @@
template<size_t bitmapSize, typename WordType>
inline bool Bitmap<bitmapSize, WordType>::testAndSet(size_t n)
{
- WordType mask = one << (n % wordSize);
- size_t index = n / wordSize;
+ WordType mask = one << (n % bitsInWord);
+ size_t index = n / bitsInWord;
bool result = bits[index] & mask;
bits[index] |= mask;
return result;
@@ -190,8 +188,8 @@
template<size_t bitmapSize, typename WordType>
inline bool Bitmap<bitmapSize, WordType>::testAndClear(size_t n)
{
- WordType mask = one << (n % wordSize);
- size_t index = n / wordSize;
+ WordType mask = one << (n % bitsInWord);
+ size_t index = n / bitsInWord;
bool result = bits[index] & mask;
bits[index] &= ~mask;
return result;
@@ -200,8 +198,8 @@
template<size_t bitmapSize, typename WordType>
ALWAYS_INLINE bool Bitmap<bitmapSize, WordType>::concurrentTestAndSet(size_t n, Dependency dependency)
{
- WordType mask = one << (n % wordSize);
- size_t index = n / wordSize;
+ WordType mask = one << (n % bitsInWord);
+ size_t index = n / bitsInWord;
WordType* data = "" + index;
return !bitwise_cast<Atomic<WordType>*>(data)->transactionRelaxed(
[&] (WordType& value) -> bool {
@@ -216,8 +214,8 @@
template<size_t bitmapSize, typename WordType>
ALWAYS_INLINE bool Bitmap<bitmapSize, WordType>::concurrentTestAndClear(size_t n, Dependency dependency)
{
- WordType mask = one << (n % wordSize);
- size_t index = n / wordSize;
+ WordType mask = one << (n % bitsInWord);
+ size_t index = n / bitsInWord;
WordType* data = "" + index;
return !bitwise_cast<Atomic<WordType>*>(data)->transactionRelaxed(
[&] (WordType& value) -> bool {
@@ -232,7 +230,7 @@
template<size_t bitmapSize, typename WordType>
inline void Bitmap<bitmapSize, WordType>::clear(size_t n)
{
- bits[n / wordSize] &= ~(one << (n % wordSize));
+ bits[n / bitsInWord] &= ~(one << (n % bitsInWord));
}
template<size_t bitmapSize, typename WordType>
@@ -244,12 +242,12 @@
template<size_t bitmapSize, typename WordType>
inline void Bitmap<bitmapSize, WordType>::invert()
{
- for (size_t i = 0; i < words; ++i)
+ for (size_t i = 0; i < numberOfWords; ++i)
bits[i] = ~bits[i];
- if constexpr (!!(bitmapSize % wordSize)) {
- constexpr size_t remainingBits = bitmapSize % wordSize;
+ if constexpr (!!(bitmapSize % bitsInWord)) {
+ constexpr size_t remainingBits = bitmapSize % bitsInWord;
constexpr WordType mask = (static_cast<WordType>(1) << remainingBits) - 1;
- bits[words - 1] &= mask;
+ bits[numberOfWords - 1] &= mask;
}
}
@@ -256,8 +254,8 @@
template<size_t bitmapSize, typename WordType>
inline size_t Bitmap<bitmapSize, WordType>::nextPossiblyUnset(size_t start) const
{
- if (!~bits[start / wordSize])
- return ((start / wordSize) + 1) * wordSize;
+ if (!~bits[start / bitsInWord])
+ return ((start / bitsInWord) + 1) * bitsInWord;
return start + 1;
}
@@ -288,11 +286,11 @@
inline size_t Bitmap<bitmapSize, WordType>::count(size_t start) const
{
size_t result = 0;
- for ( ; (start % wordSize); ++start) {
+ for ( ; (start % bitsInWord); ++start) {
if (get(start))
++result;
}
- for (size_t i = start / wordSize; i < words; ++i)
+ for (size_t i = start / bitsInWord; i < numberOfWords; ++i)
result += WTF::bitCount(bits[i]);
return result;
}
@@ -300,9 +298,10 @@
template<size_t bitmapSize, typename WordType>
inline bool Bitmap<bitmapSize, WordType>::isEmpty() const
{
- for (size_t i = 0; i < words; ++i)
+ for (size_t i = 0; i < numberOfWords; ++i) {
if (bits[i])
return false;
+ }
return true;
}
@@ -309,11 +308,11 @@
template<size_t bitmapSize, typename WordType>
inline bool Bitmap<bitmapSize, WordType>::isFull() const
{
- for (size_t i = 0; i < words; ++i)
+ for (size_t i = 0; i < numberOfWords; ++i) {
if (~bits[i]) {
- if constexpr (!!(bitmapSize % wordSize)) {
- if (i == words - 1) {
- constexpr size_t remainingBits = bitmapSize % wordSize;
+ if constexpr (!!(bitmapSize % bitsInWord)) {
+ if (i == numberOfWords - 1) {
+ constexpr size_t remainingBits = bitmapSize % bitsInWord;
constexpr WordType mask = (static_cast<WordType>(1) << remainingBits) - 1;
if ((bits[i] & mask) == mask)
return true;
@@ -321,6 +320,7 @@
}
return false;
}
+ }
return true;
}
@@ -327,7 +327,7 @@
template<size_t bitmapSize, typename WordType>
inline void Bitmap<bitmapSize, WordType>::merge(const Bitmap& other)
{
- for (size_t i = 0; i < words; ++i)
+ for (size_t i = 0; i < numberOfWords; ++i)
bits[i] |= other.bits[i];
}
@@ -334,7 +334,7 @@
template<size_t bitmapSize, typename WordType>
inline void Bitmap<bitmapSize, WordType>::filter(const Bitmap& other)
{
- for (size_t i = 0; i < words; ++i)
+ for (size_t i = 0; i < numberOfWords; ++i)
bits[i] &= other.bits[i];
}
@@ -341,7 +341,7 @@
template<size_t bitmapSize, typename WordType>
inline void Bitmap<bitmapSize, WordType>::exclude(const Bitmap& other)
{
- for (size_t i = 0; i < words; ++i)
+ for (size_t i = 0; i < numberOfWords; ++i)
bits[i] &= ~other.bits[i];
}
@@ -348,7 +348,7 @@
template<size_t bitmapSize, typename WordType>
inline void Bitmap<bitmapSize, WordType>::concurrentFilter(const Bitmap& other)
{
- for (size_t i = 0; i < words; ++i) {
+ for (size_t i = 0; i < numberOfWords; ++i) {
for (;;) {
WordType otherBits = other.bits[i];
if (!otherBits) {
@@ -368,7 +368,7 @@
template<size_t bitmapSize, typename WordType>
inline bool Bitmap<bitmapSize, WordType>::subsumes(const Bitmap& other) const
{
- for (size_t i = 0; i < words; ++i) {
+ for (size_t i = 0; i < numberOfWords; ++i) {
WordType myBits = bits[i];
WordType otherBits = other.bits[i];
if ((myBits | otherBits) != myBits)
@@ -381,9 +381,9 @@
template<typename Func>
inline void Bitmap<bitmapSize, WordType>::forEachSetBit(const Func& func) const
{
- for (size_t i = 0; i < words; ++i) {
+ for (size_t i = 0; i < numberOfWords; ++i) {
WordType word = bits[i];
- size_t base = i * wordSize;
+ size_t base = i * bitsInWord;
size_t j = 0;
for (; word; ++j) {
if (word & 1)
@@ -390,7 +390,7 @@
func(base + j);
word >>= 1;
}
- ASSERT(j <= wordSize);
+ ASSERT(j <= bitsInWord);
}
}
@@ -398,15 +398,15 @@
inline size_t Bitmap<bitmapSize, WordType>::findBit(size_t startIndex, bool value) const
{
WordType skipValue = -(static_cast<WordType>(value) ^ 1);
- size_t wordIndex = startIndex / wordSize;
- size_t startIndexInWord = startIndex - wordIndex * wordSize;
+ size_t wordIndex = startIndex / bitsInWord;
+ size_t startIndexInWord = startIndex - wordIndex * bitsInWord;
- while (wordIndex < words) {
+ while (wordIndex < numberOfWords) {
WordType word = bits[wordIndex];
if (word != skipValue) {
size_t index = startIndexInWord;
- if (findBitInWord(word, index, wordSize, value))
- return wordIndex * wordSize + index;
+ if (findBitInWord(word, index, bitsInWord, value))
+ return wordIndex * bitsInWord + index;
}
wordIndex++;
@@ -419,7 +419,7 @@
template<size_t bitmapSize, typename WordType>
inline void Bitmap<bitmapSize, WordType>::mergeAndClear(Bitmap& other)
{
- for (size_t i = 0; i < words; ++i) {
+ for (size_t i = 0; i < numberOfWords; ++i) {
bits[i] |= other.bits[i];
other.bits[i] = 0;
}
@@ -428,7 +428,7 @@
template<size_t bitmapSize, typename WordType>
inline void Bitmap<bitmapSize, WordType>::setAndClear(Bitmap& other)
{
- for (size_t i = 0; i < words; ++i) {
+ for (size_t i = 0; i < numberOfWords; ++i) {
bits[i] = other.bits[i];
other.bits[i] = 0;
}
@@ -440,28 +440,28 @@
ASSERT(start <= end);
ASSERT(end <= bitmapSize);
- size_t wordIndex = start / wordSize;
- size_t endWordIndex = end / wordSize;
- size_t index = start - wordIndex * wordSize;
+ size_t wordIndex = start / bitsInWord;
+ size_t endWordIndex = end / bitsInWord;
+ size_t index = start - wordIndex * bitsInWord;
while (wordIndex < endWordIndex) {
- while (index < wordSize) {
+ while (index < bitsInWord) {
bits[wordIndex] |= (one << index);
index += n;
}
- index -= wordSize;
+ index -= bitsInWord;
wordIndex++;
}
- size_t endIndex = end - endWordIndex * wordSize;
+ size_t endIndex = end - endWordIndex * bitsInWord;
while (index < endIndex) {
bits[wordIndex] |= (one << index);
index += n;
}
- if constexpr (!!(bitmapSize % wordSize)) {
- constexpr size_t remainingBits = bitmapSize % wordSize;
+ if constexpr (!!(bitmapSize % bitsInWord)) {
+ constexpr size_t remainingBits = bitmapSize % bitsInWord;
constexpr WordType mask = (static_cast<WordType>(1) << remainingBits) - 1;
- bits[words - 1] &= mask;
+ bits[numberOfWords - 1] &= mask;
}
}
@@ -468,7 +468,7 @@
template<size_t bitmapSize, typename WordType>
inline bool Bitmap<bitmapSize, WordType>::operator==(const Bitmap& other) const
{
- for (size_t i = 0; i < words; ++i) {
+ for (size_t i = 0; i < numberOfWords; ++i) {
if (bits[i] != other.bits[i])
return false;
}
@@ -484,7 +484,7 @@
template<size_t bitmapSize, typename WordType>
inline void Bitmap<bitmapSize, WordType>::operator|=(const Bitmap& other)
{
- for (size_t i = 0; i < words; ++i)
+ for (size_t i = 0; i < numberOfWords; ++i)
bits[i] |= other.bits[i];
}
@@ -491,7 +491,7 @@
template<size_t bitmapSize, typename WordType>
inline void Bitmap<bitmapSize, WordType>::operator&=(const Bitmap& other)
{
- for (size_t i = 0; i < words; ++i)
+ for (size_t i = 0; i < numberOfWords; ++i)
bits[i] &= other.bits[i];
}
@@ -498,7 +498,7 @@
template<size_t bitmapSize, typename WordType>
inline void Bitmap<bitmapSize, WordType>::operator^=(const Bitmap& other)
{
- for (size_t i = 0; i < words; ++i)
+ for (size_t i = 0; i < numberOfWords; ++i)
bits[i] ^= other.bits[i];
}
@@ -506,7 +506,7 @@
inline unsigned Bitmap<bitmapSize, WordType>::hash() const
{
unsigned result = 0;
- for (size_t i = 0; i < words; ++i)
+ for (size_t i = 0; i < numberOfWords; ++i)
result ^= IntHash<WordType>::hash(bits[i]);
return result;
}
