Changeset 180908 in webkit


Ignore:
Timestamp:
Mar 2, 2015 4:38:29 PM (9 years ago)
Author:
ggaren@apple.com
Message:

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.

Location:
trunk/Source/bmalloc
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/Source/bmalloc/ChangeLog

    r180806 r180908  
     12015-03-02  Geoffrey Garen  <ggaren@apple.com>
     2
     3        bmalloc: Eagerly remove allocated objects from the free list
     4        https://bugs.webkit.org/show_bug.cgi?id=142194
     5
     6        Reviewed by Andreas Kling.
     7
     8        This reduces the pressure to garbage collect the free list.
     9
     10        Might be a 1% speedup on MallocBench.
     11
     12        * bmalloc/FreeList.cpp: Put this comment at the top of the file instead
     13        of repeating it inside of each function. Tried to clarify the details.
     14
     15        (bmalloc::FreeList::takeGreedy): Matched the other iteration code in this
     16        file for consistency -- even though either direction works fine in this
     17        function.
     18
     19        (bmalloc::FreeList::take): Change to iterate from low to high so that we
     20        can maintain an index into the vector that is not disturbed even if we
     21        pop from the middle (which invalidates the last index in the vector).
     22
     23        Decrement i when popping from the middle to make sure that we don't
     24        skip the next item after popping.
     25
     26        (bmalloc::FreeList::removeInvalidAndDuplicateEntries): Ditto.
     27
    1282015-02-27  Ryosuke Niwa  <rniwa@webkit.org>
    229
  • trunk/Source/bmalloc/bmalloc/FreeList.cpp

    r180797 r180908  
    3030namespace bmalloc {
    3131
     32// We don't eagerly remove invalidated entries from the free list when we merge
     33// large objects. This means that the free list can contain invalid and/or
     34// duplicate entries. (Repeating a merge-and-then-split produces a duplicate.)
     35
     36// To avoid infinite growth in invalid entries, we incrementally remove
     37// invalid entries as we discover them during allocation, and we also garbage
     38// collect the free list as it grows.
     39
    3240LargeObject FreeList::takeGreedy(Owner owner)
    3341{
    34     for (size_t i = m_vector.size(); i-- > 0; ) {
    35         // We don't eagerly remove items when we merge and/or split ranges,
    36         // so we need to validate each free list entry before using it.
     42    for (size_t i = 0; i < m_vector.size(); ++i) {
    3743        LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
    3844        if (!largeObject.isValidAndFree(owner, m_vector[i].size())) {
    39             m_vector.pop(i);
     45            m_vector.pop(i--);
    4046            continue;
    4147        }
    4248
    43         m_vector.pop(i);
     49        m_vector.pop(i--);
    4450        return largeObject;
    4551    }
     
    5056LargeObject FreeList::take(Owner owner, size_t size)
    5157{
    52     LargeObject first;
    53     size_t end = m_vector.size() > freeListSearchDepth ? m_vector.size() - freeListSearchDepth : 0;
    54     for (size_t i = m_vector.size(); i-- > end; ) {
    55         // We don't eagerly remove items when we merge and/or split ranges, so
    56         // we need to validate each free list entry before using it.
     58    LargeObject candidate;
     59    size_t candidateIndex;
     60    size_t begin = m_vector.size() > freeListSearchDepth ? m_vector.size() - freeListSearchDepth : 0;
     61    for (size_t i = begin; i < m_vector.size(); ++i) {
    5762        LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
    5863        if (!largeObject.isValidAndFree(owner, m_vector[i].size())) {
    59             m_vector.pop(i);
     64            m_vector.pop(i--);
    6065            continue;
    6166        }
     
    6469            continue;
    6570
    66         if (!!first && first.begin() < largeObject.begin())
     71        if (!!candidate && candidate.begin() < largeObject.begin())
    6772            continue;
    6873
    69         first = largeObject;
     74        candidate = largeObject;
     75        candidateIndex = i;
    7076    }
    71    
    72     return first;
     77
     78    if (!!candidate)
     79        m_vector.pop(candidateIndex);
     80    return candidate;
    7381}
    7482
     
    7886    size_t alignmentMask = alignment - 1;
    7987
    80     LargeObject first;
    81     size_t end = m_vector.size() > freeListSearchDepth ? m_vector.size() - freeListSearchDepth : 0;
    82     for (size_t i = m_vector.size(); i-- > end; ) {
    83         // We don't eagerly remove items when we merge and/or split ranges, so
    84         // we need to validate each free list entry before using it.
     88    LargeObject candidate;
     89    size_t candidateIndex;
     90    size_t begin = m_vector.size() > freeListSearchDepth ? m_vector.size() - freeListSearchDepth : 0;
     91    for (size_t i = begin; i < m_vector.size(); ++i) {
    8592        LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
    8693        if (!largeObject.isValidAndFree(owner, m_vector[i].size())) {
    87             m_vector.pop(i);
     94            m_vector.pop(i--);
    8895            continue;
    8996        }
     
    95102            continue;
    96103
    97         if (!!first && first.begin() < largeObject.begin())
     104        if (!!candidate && candidate.begin() < largeObject.begin())
    98105            continue;
    99106
    100         first = largeObject;
     107        candidate = largeObject;
     108        candidateIndex = i;
    101109    }
    102110   
    103     return first;
     111    if (!!candidate)
     112        m_vector.pop(candidateIndex);
     113    return candidate;
    104114}
    105115
    106116void FreeList::removeInvalidAndDuplicateEntries(Owner owner)
    107117{
    108     for (size_t i = m_vector.size(); i-- > 0; ) {
     118    for (size_t i = 0; i < m_vector.size(); ++i) {
    109119        LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
    110120        if (!largeObject.isValidAndFree(owner, m_vector[i].size())) {
    111             m_vector.pop(i);
     121            m_vector.pop(i--);
    112122            continue;
    113123        }
     
    116126    }
    117127
    118     for (size_t i = m_vector.size(); i-- > 0; ) {
     128    for (size_t i = 0; i < m_vector.size(); ++i) {
    119129        LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
    120130        if (largeObject.isMarked()) {
    121             m_vector.pop(i);
     131            m_vector.pop(i--);
    122132            continue;
    123133        }
Note: See TracChangeset for help on using the changeset viewer.