Reviewers: Yury Semikhatsky, alph,
Description:
HeapSnapshot: replace O(N*ln(N)) algorithm of sorting with O(N) one.
We have HashMap for the strings. They got id sequentially. So we could use
index
sort.
BUG=none
Please review this at https://codereview.chromium.org/24174002/
SVN Base: https://v8.googlecode.com/svn/branches/bleeding_edge
Affected files (+7, -25 lines):
M src/heap-snapshot-generator.h
M src/heap-snapshot-generator.cc
Index: src/heap-snapshot-generator.cc
diff --git a/src/heap-snapshot-generator.cc b/src/heap-snapshot-generator.cc
index
25b1526d98ced35b77bd082d7f4ec414ab8e77c2..d24e4821655327f8d0df3db0c5204e641ee39d6b
100644
--- a/src/heap-snapshot-generator.cc
+++ b/src/heap-snapshot-generator.cc
@@ -2693,10 +2693,14 @@ void
HeapSnapshotJSONSerializer::SerializeString(const unsigned char* s) {
void HeapSnapshotJSONSerializer::SerializeStrings() {
- List<HashMap::Entry*> sorted_strings;
- SortHashMap(&strings_, &sorted_strings);
+ Vector<HashMap::Entry*> sorted_strings =
+ Vector<HashMap::Entry*>::New(strings_.occupancy() + 1);
+ for (HashMap::Entry* entry = strings_.Start();
+ entry != NULL;
+ entry = strings_.Next(entry))
+ sorted_strings[reinterpret_cast<uintptr_t>(entry->value)] = entry;
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));
@@ -2705,25 +2709,4 @@ void HeapSnapshotJSONSerializer::SerializeStrings() {
}
-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
Index: src/heap-snapshot-generator.h
diff --git a/src/heap-snapshot-generator.h b/src/heap-snapshot-generator.h
index
11d094ae793c13445db2c2d37ec01c39695805ad..c323f3cde282de350f88da721630bbbe685d3aee
100644
--- a/src/heap-snapshot-generator.h
+++ b/src/heap-snapshot-generator.h
@@ -658,7 +658,6 @@ class HeapSnapshotJSONSerializer {
void SerializeSnapshot();
void SerializeString(const unsigned char* s);
void SerializeStrings();
- void SortHashMap(HashMap* map, List<HashMap::Entry*>* sorted_entries);
static const int kEdgeFieldsCount;
static const int kNodeFieldsCount;
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
