Modified: releases/WebKitGTK/webkit-2.8/Source/bmalloc/ChangeLog (180925 => 180926)
--- releases/WebKitGTK/webkit-2.8/Source/bmalloc/ChangeLog 2015-03-03 08:47:17 UTC (rev 180925)
+++ releases/WebKitGTK/webkit-2.8/Source/bmalloc/ChangeLog 2015-03-03 08:55:14 UTC (rev 180926)
@@ -1,3 +1,30 @@
+2015-03-02 Geoffrey Garen <gga...@apple.com>
+
+ bmalloc: Eagerly remove allocated objects from the free list
+ https://bugs.webkit.org/show_bug.cgi?id=142194
+
+ Reviewed by Andreas Kling.
+
+ This reduces the pressure to garbage collect the free list.
+
+ Might be a 1% speedup on MallocBench.
+
+ * bmalloc/FreeList.cpp: Put this comment at the top of the file instead
+ of repeating it inside of each function. Tried to clarify the details.
+
+ (bmalloc::FreeList::takeGreedy): Matched the other iteration code in this
+ file for consistency -- even though either direction works fine in this
+ function.
+
+ (bmalloc::FreeList::take): Change to iterate from low to high so that we
+ can maintain an index into the vector that is not disturbed even if we
+ pop from the middle (which invalidates the last index in the vector).
+
+ Decrement i when popping from the middle to make sure that we don't
+ skip the next item after popping.
+
+ (bmalloc::FreeList::removeInvalidAndDuplicateEntries): Ditto.
+
2015-02-27 Ryosuke Niwa <rn...@webkit.org>
Fixed a typo in the previous commit.
Modified: releases/WebKitGTK/webkit-2.8/Source/bmalloc/bmalloc/FreeList.cpp (180925 => 180926)
--- releases/WebKitGTK/webkit-2.8/Source/bmalloc/bmalloc/FreeList.cpp 2015-03-03 08:47:17 UTC (rev 180925)
+++ releases/WebKitGTK/webkit-2.8/Source/bmalloc/bmalloc/FreeList.cpp 2015-03-03 08:55:14 UTC (rev 180926)
@@ -29,18 +29,24 @@
namespace bmalloc {
+// We don't eagerly remove invalidated entries from the free list when we merge
+// large objects. This means that the free list can contain invalid and/or
+// duplicate entries. (Repeating a merge-and-then-split produces a duplicate.)
+
+// To avoid infinite growth in invalid entries, we incrementally remove
+// invalid entries as we discover them during allocation, and we also garbage
+// collect the free list as it grows.
+
LargeObject FreeList::takeGreedy(Owner owner)
{
- for (size_t i = m_vector.size(); i-- > 0; ) {
- // We don't eagerly remove items when we merge and/or split ranges,
- // so we need to validate each free list entry before using it.
+ for (size_t i = 0; i < m_vector.size(); ++i) {
LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
if (!largeObject.isValidAndFree(owner, m_vector[i].size())) {
- m_vector.pop(i);
+ m_vector.pop(i--);
continue;
}
- m_vector.pop(i);
+ m_vector.pop(i--);
return largeObject;
}
@@ -49,27 +55,29 @@
LargeObject FreeList::take(Owner owner, size_t size)
{
- LargeObject first;
- size_t end = m_vector.size() > freeListSearchDepth ? m_vector.size() - freeListSearchDepth : 0;
- for (size_t i = m_vector.size(); i-- > end; ) {
- // We don't eagerly remove items when we merge and/or split ranges, so
- // we need to validate each free list entry before using it.
+ LargeObject candidate;
+ size_t candidateIndex;
+ size_t begin = m_vector.size() > freeListSearchDepth ? m_vector.size() - freeListSearchDepth : 0;
+ for (size_t i = begin; i < m_vector.size(); ++i) {
LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
if (!largeObject.isValidAndFree(owner, m_vector[i].size())) {
- m_vector.pop(i);
+ m_vector.pop(i--);
continue;
}
if (largeObject.size() < size)
continue;
- if (!!first && first.begin() < largeObject.begin())
+ if (!!candidate && candidate.begin() < largeObject.begin())
continue;
- first = largeObject;
+ candidate = largeObject;
+ candidateIndex = i;
}
-
- return first;
+
+ if (!!candidate)
+ m_vector.pop(candidateIndex);
+ return candidate;
}
LargeObject FreeList::take(Owner owner, size_t alignment, size_t size, size_t unalignedSize)
@@ -77,14 +85,13 @@
BASSERT(isPowerOfTwo(alignment));
size_t alignmentMask = alignment - 1;
- LargeObject first;
- size_t end = m_vector.size() > freeListSearchDepth ? m_vector.size() - freeListSearchDepth : 0;
- for (size_t i = m_vector.size(); i-- > end; ) {
- // We don't eagerly remove items when we merge and/or split ranges, so
- // we need to validate each free list entry before using it.
+ LargeObject candidate;
+ size_t candidateIndex;
+ size_t begin = m_vector.size() > freeListSearchDepth ? m_vector.size() - freeListSearchDepth : 0;
+ for (size_t i = begin; i < m_vector.size(); ++i) {
LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
if (!largeObject.isValidAndFree(owner, m_vector[i].size())) {
- m_vector.pop(i);
+ m_vector.pop(i--);
continue;
}
@@ -94,31 +101,34 @@
if (test(largeObject.begin(), alignmentMask) && largeObject.size() < unalignedSize)
continue;
- if (!!first && first.begin() < largeObject.begin())
+ if (!!candidate && candidate.begin() < largeObject.begin())
continue;
- first = largeObject;
+ candidate = largeObject;
+ candidateIndex = i;
}
- return first;
+ if (!!candidate)
+ m_vector.pop(candidateIndex);
+ return candidate;
}
void FreeList::removeInvalidAndDuplicateEntries(Owner owner)
{
- for (size_t i = m_vector.size(); i-- > 0; ) {
+ for (size_t i = 0; i < m_vector.size(); ++i) {
LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
if (!largeObject.isValidAndFree(owner, m_vector[i].size())) {
- m_vector.pop(i);
+ m_vector.pop(i--);
continue;
}
largeObject.setMarked(false);
}
- for (size_t i = m_vector.size(); i-- > 0; ) {
+ for (size_t i = 0; i < m_vector.size(); ++i) {
LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
if (largeObject.isMarked()) {
- m_vector.pop(i);
+ m_vector.pop(i--);
continue;
}
