Reviewers: danno,
Description:
Replace qsort with std::sort.
std::sort is a template, so it can be inlined more aggressively. Also, it's
O(n log n), while libc's qsort is O(n)
BUG=2639
Please review this at https://codereview.chromium.org/14315005/
SVN Base: https://v8.googlecode.com/svn/branches/bleeding_edge
Affected files:
M src/d8.cc
M src/hydrogen.cc
M src/store-buffer.h
M src/store-buffer.cc
M src/utils.h
Index: src/d8.cc
diff --git a/src/d8.cc b/src/d8.cc
index
e52e9a50a42ef2ca4dab421122722f7f4e35bfd2..938d912a0a6b7783c08b3ef1384a3f729cdc2631
100644
--- a/src/d8.cc
+++ b/src/d8.cc
@@ -42,6 +42,13 @@
#ifdef V8_SHARED
#include <assert.h>
+#endif // V8_SHARED
+
+#ifndef V8_SHARED
+#include <algorithm>
+#endif // !V8_SHARED
+
+#ifdef V8_SHARED
#include "../include/v8-testing.h"
#endif // V8_SHARED
@@ -1561,9 +1568,8 @@ struct CounterAndKey {
};
-int CompareKeys(const void* a, const void* b) {
- return strcmp(static_cast<const CounterAndKey*>(a)->key,
- static_cast<const CounterAndKey*>(b)->key);
+inline bool operator<(const CounterAndKey& lhs, const CounterAndKey& rhs) {
+ return strcmp(lhs.key, rhs.key) < 0;
}
#endif // V8_SHARED
@@ -1583,7 +1589,7 @@ void Shell::OnExit() {
counters[j].counter = i.CurrentValue();
counters[j].key = i.CurrentKey();
}
- qsort(counters, number_of_counters, sizeof(counters[0]), CompareKeys);
+ std::sort(counters, counters + number_of_counters);
printf("+----------------------------------------------------------------+"
"-------------+\n");
printf("|
Name |"
Index: src/hydrogen.cc
diff --git a/src/hydrogen.cc b/src/hydrogen.cc
index
09e3fe9c47310195bc269cc6fa55da7dd9c44acf..1461d0239f0d900cb0c92e38e1c015911ffa9ac8
100644
--- a/src/hydrogen.cc
+++ b/src/hydrogen.cc
@@ -25,9 +25,11 @@
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-#include "v8.h"
#include "hydrogen.h"
+#include <algorithm>
+
+#include "v8.h"
#include "codegen.h"
#include "full-codegen.h"
#include "hashmap.h"
@@ -7884,14 +7886,12 @@ class FunctionSorter {
};
-static int CompareHotness(void const* a, void const* b) {
- FunctionSorter const* function1 = reinterpret_cast<FunctionSorter
const*>(a);
- FunctionSorter const* function2 = reinterpret_cast<FunctionSorter
const*>(b);
- int diff = function1->ticks() - function2->ticks();
- if (diff != 0) return -diff;
- diff = function1->ast_length() - function2->ast_length();
- if (diff != 0) return diff;
- return function1->src_length() - function2->src_length();
+inline bool operator<(const FunctionSorter& lhs, const FunctionSorter&
rhs) {
+ int diff = lhs.ticks() - rhs.ticks();
+ if (diff != 0) return diff > 0;
+ diff = lhs.ast_length() - rhs.ast_length();
+ if (diff != 0) return diff < 0;
+ return lhs.src_length() < rhs.src_length();
}
@@ -7934,10 +7934,7 @@ void
HOptimizedGraphBuilder::HandlePolymorphicCallNamed(
}
}
- qsort(reinterpret_cast<void*>(&order[0]),
- ordered_functions,
- sizeof(order[0]),
- &CompareHotness);
+ std::sort(order, order + ordered_functions);
HBasicBlock* number_block = NULL;
Index: src/store-buffer.cc
diff --git a/src/store-buffer.cc b/src/store-buffer.cc
index
8a69164039c341640241c04745fb6cf8468b6427..7d73dd5ed1be27464640752efc5eb5990a749b4f
100644
--- a/src/store-buffer.cc
+++ b/src/store-buffer.cc
@@ -25,9 +25,11 @@
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-#include "v8.h"
-
#include "store-buffer.h"
+
+#include <algorithm>
+
+#include "v8.h"
#include "store-buffer-inl.h"
#include "v8-counters.h"
@@ -122,33 +124,6 @@ void StoreBuffer::StoreBufferOverflow(Isolate*
isolate) {
}
-#if V8_TARGET_ARCH_X64
-static int CompareAddresses(const void* void_a, const void* void_b) {
- intptr_t a =
- reinterpret_cast<intptr_t>(*reinterpret_cast<const
Address*>(void_a));
- intptr_t b =
- reinterpret_cast<intptr_t>(*reinterpret_cast<const
Address*>(void_b));
- // Unfortunately if int is smaller than intptr_t there is no branch-free
- // way to return a number with the same sign as the difference between
the
- // pointers.
- if (a == b) return 0;
- if (a < b) return -1;
- ASSERT(a > b);
- return 1;
-}
-#else
-static int CompareAddresses(const void* void_a, const void* void_b) {
- intptr_t a =
- reinterpret_cast<intptr_t>(*reinterpret_cast<const
Address*>(void_a));
- intptr_t b =
- reinterpret_cast<intptr_t>(*reinterpret_cast<const
Address*>(void_b));
- ASSERT(sizeof(1) == sizeof(a));
- // Shift down to avoid wraparound.
- return (a >> kPointerSizeLog2) - (b >> kPointerSizeLog2);
-}
-#endif
-
-
void StoreBuffer::Uniq() {
// Remove adjacent duplicates and cells that do not point at new space.
Address previous = NULL;
@@ -283,10 +258,7 @@ void StoreBuffer::Filter(int flag) {
void StoreBuffer::SortUniq() {
Compact();
if (old_buffer_is_sorted_) return;
- qsort(reinterpret_cast<void*>(old_start_),
- old_top_ - old_start_,
- sizeof(*old_top_),
- &CompareAddresses);
+ std::sort(old_start_, old_top_);
Uniq();
old_buffer_is_sorted_ = true;
Index: src/store-buffer.h
diff --git a/src/store-buffer.h b/src/store-buffer.h
index
79046d1540f83f30dcded12e1b3098e571f238b7..514534a1ed72c5af95827ffd3926ad90f497e976
100644
--- a/src/store-buffer.h
+++ b/src/store-buffer.h
@@ -37,6 +37,8 @@
namespace v8 {
namespace internal {
+class Page;
+class PagedSpace;
class StoreBuffer;
typedef void (*ObjectSlotCallback)(HeapObject** from, HeapObject* to);
Index: src/utils.h
diff --git a/src/utils.h b/src/utils.h
index
b84d59238653ce5dad71b3f12d23a2133a9456c8..04f6d297237c6478ca0516b5307d59884a3fb2a3
100644
--- a/src/utils.h
+++ b/src/utils.h
@@ -30,6 +30,7 @@
#include <stdlib.h>
#include <string.h>
+#include <algorithm>
#include <climits>
#include "allocation.h"
@@ -410,11 +411,7 @@ class Vector {
}
void Sort(int (*cmp)(const T*, const T*)) {
- typedef int (*RawComparer)(const void*, const void*);
- qsort(start(),
- length(),
- sizeof(T),
- reinterpret_cast<RawComparer>(cmp));
+ std::sort(start(), start() + length(), RawComparer(cmp));
}
void Sort() {
@@ -454,6 +451,14 @@ class Vector {
private:
T* start_;
int length_;
+
+ struct RawComparer {
+ explicit RawComparer(int (*cmp)(const T*, const T*)) : cmp(cmp) {}
+ bool operator()(const T& a, const T& b) {
+ return cmp(&a, &b) < 0;
+ }
+ int (*cmp)(const T*, const T*);
+ };
};
--
--
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.
