Revision: 14406
Author: [email protected]
Date: Wed Apr 24 04:20:16 2013
Log: 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^2)
BUG=2639
Review URL: https://codereview.chromium.org/14315005
Patch from Jochen Eisinger <[email protected]>.
http://code.google.com/p/v8/source/detail?r=14406
Modified:
/branches/bleeding_edge/src/d8.cc
/branches/bleeding_edge/src/hydrogen.cc
/branches/bleeding_edge/src/list-inl.h
/branches/bleeding_edge/src/store-buffer.cc
/branches/bleeding_edge/src/store-buffer.h
/branches/bleeding_edge/src/utils.h
=======================================
--- /branches/bleeding_edge/src/d8.cc Mon Apr 22 04:29:52 2013
+++ /branches/bleeding_edge/src/d8.cc Wed Apr 24 04:20:16 2013
@@ -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
@@ -1573,9 +1580,8 @@
};
-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
@@ -1595,7 +1601,7 @@
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 |"
=======================================
--- /branches/bleeding_edge/src/hydrogen.cc Tue Apr 23 08:28:44 2013
+++ /branches/bleeding_edge/src/hydrogen.cc Wed Apr 24 04:20:16 2013
@@ -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"
@@ -8006,14 +8008,12 @@
};
-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();
}
@@ -8056,10 +8056,7 @@
}
}
- qsort(reinterpret_cast<void*>(&order[0]),
- ordered_functions,
- sizeof(order[0]),
- &CompareHotness);
+ std::sort(order, order + ordered_functions);
HBasicBlock* number_block = NULL;
=======================================
--- /branches/bleeding_edge/src/list-inl.h Tue Apr 16 05:30:51 2013
+++ /branches/bleeding_edge/src/list-inl.h Wed Apr 24 04:20:16 2013
@@ -216,7 +216,7 @@
template<typename T, class P>
void List<T, P>::Sort() {
- Sort(PointerValueCompare<T>);
+ ToVector().Sort();
}
=======================================
--- /branches/bleeding_edge/src/store-buffer.cc Tue Dec 18 02:54:15 2012
+++ /branches/bleeding_edge/src/store-buffer.cc Wed Apr 24 04:20:16 2013
@@ -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 "store-buffer.h"
+
+#include <algorithm>
+
#include "v8.h"
-
-#include "store-buffer.h"
#include "store-buffer-inl.h"
#include "v8-counters.h"
@@ -120,33 +122,6 @@
void StoreBuffer::StoreBufferOverflow(Isolate* isolate) {
isolate->heap()->store_buffer()->Compact();
}
-
-
-#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() {
@@ -283,10 +258,7 @@
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;
=======================================
--- /branches/bleeding_edge/src/store-buffer.h Thu Nov 29 07:13:49 2012
+++ /branches/bleeding_edge/src/store-buffer.h Wed Apr 24 04:20:16 2013
@@ -37,6 +37,8 @@
namespace v8 {
namespace internal {
+class Page;
+class PagedSpace;
class StoreBuffer;
typedef void (*ObjectSlotCallback)(HeapObject** from, HeapObject* to);
=======================================
--- /branches/bleeding_edge/src/utils.h Tue Apr 16 05:30:51 2013
+++ /branches/bleeding_edge/src/utils.h Wed Apr 24 04:20:16 2013
@@ -30,6 +30,7 @@
#include <stdlib.h>
#include <string.h>
+#include <algorithm>
#include <climits>
#include "allocation.h"
@@ -410,15 +411,11 @@
}
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() {
- Sort(PointerValueCompare<T>);
+ std::sort(start(), start() + length());
}
void Truncate(int length) {
@@ -454,6 +451,17 @@
private:
T* start_;
int length_;
+
+ class RawComparer {
+ public:
+ explicit RawComparer(int (*cmp)(const T*, const T*)) : cmp_(cmp) {}
+ bool operator()(const T& a, const T& b) {
+ return cmp_(&a, &b) < 0;
+ }
+
+ private:
+ 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.
