Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(186)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: src/heap/mark-compact.cc

Issue 1478623003: [heap] Count bits in markbit cell instead of using a table. (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: Created 5 years, 1 month ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « no previous file | no next file » | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/heap/mark-compact.cc
diff --git a/src/heap/mark-compact.cc b/src/heap/mark-compact.cc
index a58b0678b5fae004175fb8935372c8ee9559d7b4..af366eb1bcb51782da76cea4460b4d9ce81a30b0 100644
--- a/src/heap/mark-compact.cc
+++ b/src/heap/mark-compact.cc
@@ -1488,7 +1488,8 @@ void MarkCompactCollector::DiscoverGreyObjectsWithIterator(T* it) {
}
-static inline int MarkWordToObjectStarts(uint32_t mark_bits, int* starts);
+static inline int MarkWordToObjectStarts(uint32_t mark_bits, Address base,
+ Address* starts);
void MarkCompactCollector::DiscoverGreyObjectsOnPage(MemoryChunk* p) {
@@ -3176,17 +3177,16 @@ bool MarkCompactCollector::EvacuateLiveObjectsFromPage(
AlwaysAllocateScope always_allocate(isolate());
DCHECK(p->IsEvacuationCandidate() && !p->WasSwept());
- int offsets[16];
+ Address starts[16];
for (MarkBitCellIterator it(p); !it.Done(); it.Advance()) {
Address cell_base = it.CurrentCellBase();
MarkBit::CellType* cell = it.CurrentCell();
if (*cell == 0) continue;
- int live_objects = MarkWordToObjectStarts(*cell, offsets);
+ int live_objects = MarkWordToObjectStarts(*cell, cell_base, starts);
for (int i = 0; i < live_objects; i++) {
- Address object_addr = cell_base + offsets[i] * kPointerSize;
- HeapObject* object = HeapObject::FromAddress(object_addr);
+ HeapObject* object = HeapObject::FromAddress(starts[i]);
DCHECK(Marking::IsBlack(Marking::MarkBitFrom(object)));
int size = object->Size();
@@ -3198,7 +3198,7 @@ bool MarkCompactCollector::EvacuateLiveObjectsFromPage(
// the mark bits for objects that have already been migrated.
if (i > 0) {
p->markbits()->ClearRange(p->AddressToMarkbitIndex(p->area_start()),
- p->AddressToMarkbitIndex(object_addr));
+ p->AddressToMarkbitIndex(starts[i]));
}
return false;
}
@@ -3469,7 +3469,7 @@ static int Sweep(PagedSpace* space, FreeList* free_list, Page* p,
Address free_start = p->area_start();
DCHECK(reinterpret_cast<intptr_t>(free_start) % (32 * kPointerSize) == 0);
- int offsets[16];
+ Address starts[16];
// If we use the skip list for code space pages, we have to lock the skip
// list because it could be accessed concurrently by the runtime or the
@@ -3486,10 +3486,10 @@ static int Sweep(PagedSpace* space, FreeList* free_list, Page* p,
for (MarkBitCellIterator it(p); !it.Done(); it.Advance()) {
Address cell_base = it.CurrentCellBase();
MarkBit::CellType* cell = it.CurrentCell();
- int live_objects = MarkWordToObjectStarts(*cell, offsets);
+ int live_objects = MarkWordToObjectStarts(*cell, cell_base, starts);
int live_index = 0;
for (; live_objects != 0; live_objects--) {
- Address free_end = cell_base + offsets[live_index++] * kPointerSize;
+ Address free_end = starts[live_index++];
if (free_end != free_start) {
int size = static_cast<int>(free_end - free_start);
if (free_space_mode == ZAP_FREE_SPACE) {
@@ -3584,15 +3584,14 @@ void MarkCompactCollector::RemoveObjectSlots(Address start_slot,
void MarkCompactCollector::VisitLiveObjects(Page* page,
ObjectVisitor* visitor) {
// First pass on aborted pages.
- int offsets[16];
+ Address starts[16];
for (MarkBitCellIterator it(page); !it.Done(); it.Advance()) {
Address cell_base = it.CurrentCellBase();
MarkBit::CellType* cell = it.CurrentCell();
if (*cell == 0) continue;
- int live_objects = MarkWordToObjectStarts(*cell, offsets);
+ int live_objects = MarkWordToObjectStarts(*cell, cell_base, starts);
for (int i = 0; i < live_objects; i++) {
- Address object_addr = cell_base + offsets[i] * kPointerSize;
- HeapObject* live_object = HeapObject::FromAddress(object_addr);
+ HeapObject* live_object = HeapObject::FromAddress(starts[i]);
DCHECK(Marking::IsBlack(Marking::MarkBitFrom(live_object)));
Map* map = live_object->synchronized_map();
int size = live_object->SizeFromMap(map);
@@ -3829,395 +3828,21 @@ void MarkCompactCollector::ReleaseEvacuationCandidates() {
}
-static const int kStartTableEntriesPerLine = 5;
-static const int kStartTableLines = 171;
-static const int kStartTableInvalidLine = 127;
-static const int kStartTableUnusedEntry = 126;
-
-#define _ kStartTableUnusedEntry
-#define X kStartTableInvalidLine
-// Mark-bit to object start offset table.
-//
-// The line is indexed by the mark bits in a byte. The first number on
-// the line describes the number of live object starts for the line and the
-// other numbers on the line describe the offsets (in words) of the object
-// starts.
-//
-// Since objects are at least 2 words large we don't have entries for two
-// consecutive 1 bits. All entries after 170 have at least 2 consecutive bits.
-char kStartTable[kStartTableLines * kStartTableEntriesPerLine] = {
- 0, _, _,
- _, _, // 0
- 1, 0, _,
- _, _, // 1
- 1, 1, _,
- _, _, // 2
- X, _, _,
- _, _, // 3
- 1, 2, _,
- _, _, // 4
- 2, 0, 2,
- _, _, // 5
- X, _, _,
- _, _, // 6
- X, _, _,
- _, _, // 7
- 1, 3, _,
- _, _, // 8
- 2, 0, 3,
- _, _, // 9
- 2, 1, 3,
- _, _, // 10
- X, _, _,
- _, _, // 11
- X, _, _,
- _, _, // 12
- X, _, _,
- _, _, // 13
- X, _, _,
- _, _, // 14
- X, _, _,
- _, _, // 15
- 1, 4, _,
- _, _, // 16
- 2, 0, 4,
- _, _, // 17
- 2, 1, 4,
- _, _, // 18
- X, _, _,
- _, _, // 19
- 2, 2, 4,
- _, _, // 20
- 3, 0, 2,
- 4, _, // 21
- X, _, _,
- _, _, // 22
- X, _, _,
- _, _, // 23
- X, _, _,
- _, _, // 24
- X, _, _,
- _, _, // 25
- X, _, _,
- _, _, // 26
- X, _, _,
- _, _, // 27
- X, _, _,
- _, _, // 28
- X, _, _,
- _, _, // 29
- X, _, _,
- _, _, // 30
- X, _, _,
- _, _, // 31
- 1, 5, _,
- _, _, // 32
- 2, 0, 5,
- _, _, // 33
- 2, 1, 5,
- _, _, // 34
- X, _, _,
- _, _, // 35
- 2, 2, 5,
- _, _, // 36
- 3, 0, 2,
- 5, _, // 37
- X, _, _,
- _, _, // 38
- X, _, _,
- _, _, // 39
- 2, 3, 5,
- _, _, // 40
- 3, 0, 3,
- 5, _, // 41
- 3, 1, 3,
- 5, _, // 42
- X, _, _,
- _, _, // 43
- X, _, _,
- _, _, // 44
- X, _, _,
- _, _, // 45
- X, _, _,
- _, _, // 46
- X, _, _,
- _, _, // 47
- X, _, _,
- _, _, // 48
- X, _, _,
- _, _, // 49
- X, _, _,
- _, _, // 50
- X, _, _,
- _, _, // 51
- X, _, _,
- _, _, // 52
- X, _, _,
- _, _, // 53
- X, _, _,
- _, _, // 54
- X, _, _,
- _, _, // 55
- X, _, _,
- _, _, // 56
- X, _, _,
- _, _, // 57
- X, _, _,
- _, _, // 58
- X, _, _,
- _, _, // 59
- X, _, _,
- _, _, // 60
- X, _, _,
- _, _, // 61
- X, _, _,
- _, _, // 62
- X, _, _,
- _, _, // 63
- 1, 6, _,
- _, _, // 64
- 2, 0, 6,
- _, _, // 65
- 2, 1, 6,
- _, _, // 66
- X, _, _,
- _, _, // 67
- 2, 2, 6,
- _, _, // 68
- 3, 0, 2,
- 6, _, // 69
- X, _, _,
- _, _, // 70
- X, _, _,
- _, _, // 71
- 2, 3, 6,
- _, _, // 72
- 3, 0, 3,
- 6, _, // 73
- 3, 1, 3,
- 6, _, // 74
- X, _, _,
- _, _, // 75
- X, _, _,
- _, _, // 76
- X, _, _,
- _, _, // 77
- X, _, _,
- _, _, // 78
- X, _, _,
- _, _, // 79
- 2, 4, 6,
- _, _, // 80
- 3, 0, 4,
- 6, _, // 81
- 3, 1, 4,
- 6, _, // 82
- X, _, _,
- _, _, // 83
- 3, 2, 4,
- 6, _, // 84
- 4, 0, 2,
- 4, 6, // 85
- X, _, _,
- _, _, // 86
- X, _, _,
- _, _, // 87
- X, _, _,
- _, _, // 88
- X, _, _,
- _, _, // 89
- X, _, _,
- _, _, // 90
- X, _, _,
- _, _, // 91
- X, _, _,
- _, _, // 92
- X, _, _,
- _, _, // 93
- X, _, _,
- _, _, // 94
- X, _, _,
- _, _, // 95
- X, _, _,
- _, _, // 96
- X, _, _,
- _, _, // 97
- X, _, _,
- _, _, // 98
- X, _, _,
- _, _, // 99
- X, _, _,
- _, _, // 100
- X, _, _,
- _, _, // 101
- X, _, _,
- _, _, // 102
- X, _, _,
- _, _, // 103
- X, _, _,
- _, _, // 104
- X, _, _,
- _, _, // 105
- X, _, _,
- _, _, // 106
- X, _, _,
- _, _, // 107
- X, _, _,
- _, _, // 108
- X, _, _,
- _, _, // 109
- X, _, _,
- _, _, // 110
- X, _, _,
- _, _, // 111
- X, _, _,
- _, _, // 112
- X, _, _,
- _, _, // 113
- X, _, _,
- _, _, // 114
- X, _, _,
- _, _, // 115
- X, _, _,
- _, _, // 116
- X, _, _,
- _, _, // 117
- X, _, _,
- _, _, // 118
- X, _, _,
- _, _, // 119
- X, _, _,
- _, _, // 120
- X, _, _,
- _, _, // 121
- X, _, _,
- _, _, // 122
- X, _, _,
- _, _, // 123
- X, _, _,
- _, _, // 124
- X, _, _,
- _, _, // 125
- X, _, _,
- _, _, // 126
- X, _, _,
- _, _, // 127
- 1, 7, _,
- _, _, // 128
- 2, 0, 7,
- _, _, // 129
- 2, 1, 7,
- _, _, // 130
- X, _, _,
- _, _, // 131
- 2, 2, 7,
- _, _, // 132
- 3, 0, 2,
- 7, _, // 133
- X, _, _,
- _, _, // 134
- X, _, _,
- _, _, // 135
- 2, 3, 7,
- _, _, // 136
- 3, 0, 3,
- 7, _, // 137
- 3, 1, 3,
- 7, _, // 138
- X, _, _,
- _, _, // 139
- X, _, _,
- _, _, // 140
- X, _, _,
- _, _, // 141
- X, _, _,
- _, _, // 142
- X, _, _,
- _, _, // 143
- 2, 4, 7,
- _, _, // 144
- 3, 0, 4,
- 7, _, // 145
- 3, 1, 4,
- 7, _, // 146
- X, _, _,
- _, _, // 147
- 3, 2, 4,
- 7, _, // 148
- 4, 0, 2,
- 4, 7, // 149
- X, _, _,
- _, _, // 150
- X, _, _,
- _, _, // 151
- X, _, _,
- _, _, // 152
- X, _, _,
- _, _, // 153
- X, _, _,
- _, _, // 154
- X, _, _,
- _, _, // 155
- X, _, _,
- _, _, // 156
- X, _, _,
- _, _, // 157
- X, _, _,
- _, _, // 158
- X, _, _,
- _, _, // 159
- 2, 5, 7,
- _, _, // 160
- 3, 0, 5,
- 7, _, // 161
- 3, 1, 5,
- 7, _, // 162
- X, _, _,
- _, _, // 163
- 3, 2, 5,
- 7, _, // 164
- 4, 0, 2,
- 5, 7, // 165
- X, _, _,
- _, _, // 166
- X, _, _,
- _, _, // 167
- 3, 3, 5,
- 7, _, // 168
- 4, 0, 3,
- 5, 7, // 169
- 4, 1, 3,
- 5, 7 // 170
-};
-#undef _
-#undef X
-
-
-// Takes a word of mark bits. Returns the number of objects that start in the
-// range. Puts the offsets of the words in the supplied array.
-static inline int MarkWordToObjectStarts(uint32_t mark_bits, int* starts) {
+// Takes a word of mark bits and a base address. Returns the number of objects
+// that start in the range. Puts the object starts in the supplied array.
+static inline int MarkWordToObjectStarts(uint32_t mark_bits, Address base,
+ Address* starts) {
int objects = 0;
- int offset = 0;
// No consecutive 1 bits.
DCHECK((mark_bits & 0x180) != 0x180);
DCHECK((mark_bits & 0x18000) != 0x18000);
DCHECK((mark_bits & 0x1800000) != 0x1800000);
- while (mark_bits != 0) {
- int byte = (mark_bits & 0xff);
- mark_bits >>= 8;
- if (byte != 0) {
- DCHECK(byte < kStartTableLines); // No consecutive 1 bits.
- char* table = kStartTable + byte * kStartTableEntriesPerLine;
- int objects_in_these_8_words = table[0];
- DCHECK(objects_in_these_8_words != kStartTableInvalidLine);
- DCHECK(objects_in_these_8_words < kStartTableEntriesPerLine);
- for (int i = 0; i < objects_in_these_8_words; i++) {
- starts[objects++] = offset + table[1 + i];
- }
- }
- offset += 8;
+ unsigned index = 0;
+ while ((index = base::bits::CountTrailingZeros32(mark_bits)) != 32) {
+ starts[objects++] = base + kPointerSize * index;
+ mark_bits &= ~(1u << index);
}
return objects;
}
« no previous file with comments | « no previous file | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698