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

Side by Side Diff: src/heap/identity-map.cc

Issue 1105693002: Implement IdentityMap<V>, a robust, GC-safe object-identity HashMap. (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: Created 5 years, 7 months 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 unified diff | Download patch
« no previous file with comments | « src/heap/identity-map.h ('k') | src/objects.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(Empty)
1 // Copyright 2015 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "src/v8.h"
6
7 #include "src/heap/heap.h"
8 #include "src/heap/identity-map.h"
9
10 namespace v8 {
11 namespace internal {
12
13 static const int kInitialIdentityMapSize = 4;
14 static const int kResizeFactor = 4;
15
16 IdentityMapBase::~IdentityMapBase() {
17 if (keys_) {
18 Heap::OptionalRelocationLock lock(heap_, concurrent_);
19 heap_->UnregisterStrongRoots(keys_);
20 }
21 }
22
23
24 IdentityMapBase::RawEntry IdentityMapBase::Lookup(Handle<Object> key) {
25 AllowHandleDereference for_lookup;
26 int index = LookupIndex(*key);
27 return index >= 0 ? &values_[index] : nullptr;
28 }
29
30
31 IdentityMapBase::RawEntry IdentityMapBase::Insert(Handle<Object> key) {
32 AllowHandleDereference for_lookup;
33 int index = InsertIndex(*key);
34 DCHECK_GE(index, 0);
35 return &values_[index];
36 }
37
38
39 int IdentityMapBase::Hash(Object* address) {
40 uintptr_t raw_address = reinterpret_cast<uintptr_t>(address);
41 CHECK_NE(0, raw_address); // Cannot store Smi 0 as a key here, sorry.
42 // Xor some of the upper bits, since the lower 2 or 3 are usually aligned.
43 return static_cast<int>((raw_address >> 11) ^ raw_address);
44 }
45
46
47 int IdentityMapBase::LookupIndex(Object* address) {
48 int start = Hash(address) & mask_;
49 for (int index = start; index < size_; index++) {
50 if (keys_[index] == address) return index; // Found.
51 if (keys_[index] == nullptr) return -1; // Not found.
52 }
53 for (int index = 0; index < start; index++) {
54 if (keys_[index] == address) return index; // Found.
55 if (keys_[index] == nullptr) return -1; // Not found.
56 }
57 return -1;
58 }
59
60
61 int IdentityMapBase::InsertIndex(Object* address) {
62 while (true) {
63 int start = Hash(address) & mask_;
64 int limit = size_ / 2;
65 // Search up to {limit} entries.
66 for (int index = start; --limit > 0; index = (index + 1) & mask_) {
67 if (keys_[index] == address) return index; // Found.
68 if (keys_[index] == nullptr) { // Free entry.
69 keys_[index] = address;
70 return index;
71 }
72 }
73 Resize(); // Should only have to resize once, since we grow 4x.
74 }
75 UNREACHABLE();
76 return -1;
77 }
78
79
80 // Searches this map for the given key using the object's address
81 // as the identity, returning:
82 // found => a pointer to the storage location for the value
83 // not found => a pointer to a new storage location for the value
84 IdentityMapBase::RawEntry IdentityMapBase::GetEntry(Handle<Object> key) {
85 Heap::OptionalRelocationLock lock(heap_, concurrent_);
86 RawEntry result;
87 if (size_ == 0) {
88 // Allocate the initial storage for keys and values.
89 size_ = kInitialIdentityMapSize;
90 mask_ = kInitialIdentityMapSize - 1;
91 gc_counter_ = heap_->gc_count();
92
93 keys_ = zone_->NewArray<Object*>(size_);
94 memset(keys_, 0, sizeof(Object*) * size_);
95 values_ = zone_->NewArray<void*>(size_);
96 memset(values_, 0, sizeof(void*) * size_);
97
98 heap_->RegisterStrongRoots(keys_, keys_ + size_);
99 result = Insert(key);
100 } else {
101 // Perform an optimistic lookup.
102 result = Lookup(key);
103 if (result == nullptr) {
104 // Miss; rehash if there was a GC, then insert.
105 if (gc_counter_ != heap_->gc_count()) Rehash();
106 result = Insert(key);
107 }
108 }
109 return result;
110 }
111
112
113 // Searches this map for the given key using the object's address
114 // as the identity, returning:
115 // found => a pointer to the storage location for the value
116 // not found => {nullptr}
117 IdentityMapBase::RawEntry IdentityMapBase::FindEntry(Handle<Object> key) {
118 if (size_ == 0) return nullptr;
119
120 Heap::OptionalRelocationLock lock(heap_, concurrent_);
121 RawEntry result = Lookup(key);
122 if (result == nullptr && gc_counter_ != heap_->gc_count()) {
123 Rehash(); // Rehash is expensive, so only do it in case of a miss.
124 result = Lookup(key);
125 }
126 return result;
127 }
128
129
130 void IdentityMapBase::Rehash() {
131 // Record the current GC counter.
132 gc_counter_ = heap_->gc_count();
133 // Assume that most objects won't be moved.
134 ZoneVector<std::pair<Object*, void*>> reinsert(zone_);
135 // Search the table looking for keys that wouldn't be found with their
136 // current hashcode and evacuate them.
137 int last_empty = -1;
138 for (int i = 0; i < size_; i++) {
139 if (keys_[i] == nullptr) {
140 last_empty = i;
141 } else {
142 int pos = Hash(keys_[i]) & mask_;
143 if (pos <= last_empty || pos > i) {
144 // Evacuate an entry that is in the wrong place.
145 reinsert.push_back(std::pair<Object*, void*>(keys_[i], values_[i]));
146 keys_[i] = nullptr;
147 values_[i] = nullptr;
148 last_empty = i;
149 }
150 }
151 }
152 // Reinsert all the key/value pairs that were in the wrong place.
153 for (auto pair : reinsert) {
154 int index = InsertIndex(pair.first);
155 DCHECK_GE(index, 0);
156 DCHECK_NULL(values_[index]);
157 values_[index] = pair.second;
158 }
159 }
160
161
162 void IdentityMapBase::Resize() {
163 // Grow the internal storage and reinsert all the key/value pairs.
164 int old_size = size_;
165 Object** old_keys = keys_;
166 void** old_values = values_;
167
168 size_ = size_ * kResizeFactor;
169 mask_ = size_ - 1;
170 gc_counter_ = heap_->gc_count();
171
172 CHECK_LE(size_, (1024 * 1024 * 16)); // that would be extreme...
173
174 keys_ = zone_->NewArray<Object*>(size_);
175 memset(keys_, 0, sizeof(Object*) * size_);
176 values_ = zone_->NewArray<void*>(size_);
177 memset(values_, 0, sizeof(void*) * size_);
178
179 for (int i = 0; i < old_size; i++) {
180 if (old_keys[i] == nullptr) continue;
181 int index = InsertIndex(old_keys[i]);
182 DCHECK_GE(index, 0);
183 values_[index] = old_values[i];
184 }
185
186 // Unregister old keys and register new keys.
187 heap_->UnregisterStrongRoots(old_keys);
188 heap_->RegisterStrongRoots(keys_, keys_ + size_);
189 }
190 }
191 } // namespace v8::internal
OLDNEW
« no previous file with comments | « src/heap/identity-map.h ('k') | src/objects.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698