Chromium Code Reviews

Unified Diff: src/heap-snapshot-generator.cc

Issue 24174002: HeapSnapshot: replace O(N*ln(N)) algorithm of sorting with O(N) one. (Closed) Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge
Patch Set: comments addressed Created 7 years, 3 months ago
Use n/p to move between diff chunks; N/P to move between comments.
Jump to:
View side-by-side diff with in-line comments
« no previous file with comments | « src/heap-snapshot-generator.h ('k') | no next file » | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/heap-snapshot-generator.cc
diff --git a/src/heap-snapshot-generator.cc b/src/heap-snapshot-generator.cc
index 25b1526d98ced35b77bd082d7f4ec414ab8e77c2..7844d32677fa461c8fc2542c494333702dcc989d 100644
--- a/src/heap-snapshot-generator.cc
+++ b/src/heap-snapshot-generator.cc
@@ -2693,37 +2693,20 @@ void HeapSnapshotJSONSerializer::SerializeString(const unsigned char* s) {
void HeapSnapshotJSONSerializer::SerializeStrings() {
- List<HashMap::Entry*> sorted_strings;
- SortHashMap(&strings_, &sorted_strings);
+ ScopedVector<const unsigned char*> sorted_strings(
+ strings_.occupancy() + 1);
+ for (HashMap::Entry* entry = strings_.Start();
+ entry != NULL; entry = strings_.Next(entry)) {
+ sorted_strings[reinterpret_cast<uintptr_t>(entry->value)] =
+ reinterpret_cast<const unsigned char*>(entry->key);
+ }
writer_->AddString("\"<dummy>\"");
- for (int i = 0; i < sorted_strings.length(); ++i) {
+ for (int i = 1; i < sorted_strings.length(); ++i) {
writer_->AddCharacter(',');
- SerializeString(
- reinterpret_cast<const unsigned char*>(sorted_strings[i]->key));
+ SerializeString(sorted_strings[i]);
if (writer_->aborted()) return;
}
}
-template<typename T>
-inline static int SortUsingEntryValue(const T* x, const T* y) {
- uintptr_t x_uint = reinterpret_cast<uintptr_t>((*x)->value);
- uintptr_t y_uint = reinterpret_cast<uintptr_t>((*y)->value);
- if (x_uint > y_uint) {
- return 1;
- } else if (x_uint == y_uint) {
- return 0;
- } else {
- return -1;
- }
-}
-
-
-void HeapSnapshotJSONSerializer::SortHashMap(
- HashMap* map, List<HashMap::Entry*>* sorted_entries) {
- for (HashMap::Entry* p = map->Start(); p != NULL; p = map->Next(p))
- sorted_entries->Add(p);
- sorted_entries->Sort(SortUsingEntryValue);
-}
-
} } // namespace v8::internal
« no previous file with comments | « src/heap-snapshot-generator.h ('k') | no next file » | no next file with comments »

Powered by Google App Engine