Author: [email protected]
Date: Mon Jun 15 01:04:47 2009
New Revision: 2159
Modified:
branches/bleeding_edge/src/api.cc
branches/bleeding_edge/src/arm/codegen-arm.cc
branches/bleeding_edge/src/arm/codegen-arm.h
branches/bleeding_edge/src/assembler.cc
branches/bleeding_edge/src/assembler.h
branches/bleeding_edge/src/codegen.cc
branches/bleeding_edge/src/ia32/codegen-ia32.cc
branches/bleeding_edge/src/ia32/codegen-ia32.h
branches/bleeding_edge/src/math.js
branches/bleeding_edge/src/runtime.cc
branches/bleeding_edge/src/runtime.h
branches/bleeding_edge/src/serialize.cc
branches/bleeding_edge/src/v8.cc
branches/bleeding_edge/src/v8.h
Log:
Change the implementation of Math.random to use George
Marsaglia's multiply-with-carry instead of mixing the
bits obtained from calling the system random() twice.
This seems to be a bit faster and gives a better
distribution than the system random() in particular on
Windows.
Review URL: http://codereview.chromium.org/126113
Modified: branches/bleeding_edge/src/api.cc
==============================================================================
--- branches/bleeding_edge/src/api.cc (original)
+++ branches/bleeding_edge/src/api.cc Mon Jun 15 01:04:47 2009
@@ -2124,7 +2124,9 @@
} else {
int attempts = 0;
do {
- hash_value = random() & i::Smi::kMaxValue; // Limit range to fit a
smi.
+ // Generate a random 32-bit hash value but limit range to fit
+ // within a smi.
+ hash_value = i::V8::Random() & i::Smi::kMaxValue;
attempts++;
} while (hash_value == 0 && attempts < 30);
hash_value = hash_value != 0 ? hash_value : 1; // never return 0
Modified: branches/bleeding_edge/src/arm/codegen-arm.cc
==============================================================================
--- branches/bleeding_edge/src/arm/codegen-arm.cc (original)
+++ branches/bleeding_edge/src/arm/codegen-arm.cc Mon Jun 15 01:04:47 2009
@@ -3405,6 +3405,15 @@
}
+void CodeGenerator::GenerateRandomPositiveSmi(ZoneList<Expression*>* args)
{
+ VirtualFrame::SpilledScope spilled_scope;
+ ASSERT(args->length() == 0);
+ __ Call(ExternalReference::random_positive_smi_function().address(),
+ RelocInfo::RUNTIME_ENTRY);
+ frame_->EmitPush(r0);
+}
+
+
void CodeGenerator::GenerateObjectEquals(ZoneList<Expression*>* args) {
VirtualFrame::SpilledScope spilled_scope;
ASSERT(args->length() == 2);
Modified: branches/bleeding_edge/src/arm/codegen-arm.h
==============================================================================
--- branches/bleeding_edge/src/arm/codegen-arm.h (original)
+++ branches/bleeding_edge/src/arm/codegen-arm.h Mon Jun 15 01:04:47 2009
@@ -349,6 +349,9 @@
void GenerateLog(ZoneList<Expression*>* args);
+ // Fast support for Math.random().
+ void GenerateRandomPositiveSmi(ZoneList<Expression*>* args);
+
// Methods and constants for fast case switch statement support.
//
// Only allow fast-case switch if the range of labels is at most
Modified: branches/bleeding_edge/src/assembler.cc
==============================================================================
--- branches/bleeding_edge/src/assembler.cc (original)
+++ branches/bleeding_edge/src/assembler.cc Mon Jun 15 01:04:47 2009
@@ -553,6 +553,11 @@
}
+ExternalReference ExternalReference::random_positive_smi_function() {
+ return ExternalReference(Redirect(FUNCTION_ADDR(V8::RandomPositiveSmi)));
+}
+
+
ExternalReference ExternalReference::the_hole_value_location() {
return ExternalReference(Factory::the_hole_value().location());
}
Modified: branches/bleeding_edge/src/assembler.h
==============================================================================
--- branches/bleeding_edge/src/assembler.h (original)
+++ branches/bleeding_edge/src/assembler.h Mon Jun 15 01:04:47 2009
@@ -388,8 +388,8 @@
// ExternalReferenceTable in serialize.cc manually.
static ExternalReference perform_gc_function();
-
static ExternalReference builtin_passed_function();
+ static ExternalReference random_positive_smi_function();
// Static variable Factory::the_hole_value.location()
static ExternalReference the_hole_value_location();
Modified: branches/bleeding_edge/src/codegen.cc
==============================================================================
--- branches/bleeding_edge/src/codegen.cc (original)
+++ branches/bleeding_edge/src/codegen.cc Mon Jun 15 01:04:47 2009
@@ -422,7 +422,8 @@
{&CodeGenerator::GenerateSetValueOf, "_SetValueOf"},
{&CodeGenerator::GenerateFastCharCodeAt, "_FastCharCodeAt"},
{&CodeGenerator::GenerateObjectEquals, "_ObjectEquals"},
- {&CodeGenerator::GenerateLog, "_Log"}
+ {&CodeGenerator::GenerateLog, "_Log"},
+ {&CodeGenerator::GenerateRandomPositiveSmi, "_RandomPositiveSmi"}
};
Modified: branches/bleeding_edge/src/ia32/codegen-ia32.cc
==============================================================================
--- branches/bleeding_edge/src/ia32/codegen-ia32.cc (original)
+++ branches/bleeding_edge/src/ia32/codegen-ia32.cc Mon Jun 15 01:04:47 2009
@@ -4934,6 +4934,15 @@
}
+void CodeGenerator::GenerateRandomPositiveSmi(ZoneList<Expression*>* args)
{
+ ASSERT(args->length() == 0);
+ frame_->SpillAll();
+ __ call(FUNCTION_ADDR(V8::RandomPositiveSmi), RelocInfo::RUNTIME_ENTRY);
+ Result result = allocator_->Allocate(eax);
+ frame_->Push(&result);
+}
+
+
void CodeGenerator::VisitCallRuntime(CallRuntime* node) {
if (CheckForInlineRuntimeCall(node)) {
return;
Modified: branches/bleeding_edge/src/ia32/codegen-ia32.h
==============================================================================
--- branches/bleeding_edge/src/ia32/codegen-ia32.h (original)
+++ branches/bleeding_edge/src/ia32/codegen-ia32.h Mon Jun 15 01:04:47 2009
@@ -518,6 +518,9 @@
void GenerateGetFramePointer(ZoneList<Expression*>* args);
+ // Fast support for Math.random().
+ void GenerateRandomPositiveSmi(ZoneList<Expression*>* args);
+
// Methods and constants for fast case switch statement support.
//
// Only allow fast-case switch if the range of labels is at most
Modified: branches/bleeding_edge/src/math.js
==============================================================================
--- branches/bleeding_edge/src/math.js (original)
+++ branches/bleeding_edge/src/math.js Mon Jun 15 01:04:47 2009
@@ -44,39 +44,73 @@
// ECMA 262 - 15.8.2.1
function MathAbs(x) {
- if (%_IsSmi(x)) {
- return x >= 0 ? x : -x;
- } else {
- return %Math_abs(ToNumber(x));
- }
+ if (%_IsSmi(x)) return x >= 0 ? x : -x;
+ if (!IS_NUMBER(x)) x = ToNumber(x);
+ return %Math_abs(x);
}
// ECMA 262 - 15.8.2.2
-function MathAcos(x) { return %Math_acos(ToNumber(x)); }
+function MathAcos(x) {
+ if (!IS_NUMBER(x)) x = ToNumber(x);
+ return %Math_acos(x);
+}
// ECMA 262 - 15.8.2.3
-function MathAsin(x) { return %Math_asin(ToNumber(x)); }
+function MathAsin(x) {
+ if (!IS_NUMBER(x)) x = ToNumber(x);
+ return %Math_asin(x);
+}
// ECMA 262 - 15.8.2.4
-function MathAtan(x) { return %Math_atan(ToNumber(x)); }
+function MathAtan(x) {
+ if (!IS_NUMBER(x)) x = ToNumber(x);
+ return %Math_atan(x);
+}
// ECMA 262 - 15.8.2.5
-function MathAtan2(x, y) { return %Math_atan2(ToNumber(x), ToNumber(y)); }
+function MathAtan2(x, y) {
+ if (!IS_NUMBER(x)) x = ToNumber(x);
+ if (!IS_NUMBER(y)) y = ToNumber(y);
+ return %Math_atan2(x, y);
+}
// ECMA 262 - 15.8.2.6
-function MathCeil(x) { return %Math_ceil(ToNumber(x)); }
+function MathCeil(x) {
+ if (!IS_NUMBER(x)) x = ToNumber(x);
+ return %Math_ceil(x);
+}
// ECMA 262 - 15.8.2.7
-function MathCos(x) { return %Math_cos(ToNumber(x)); }
+function MathCos(x) {
+ if (!IS_NUMBER(x)) x = ToNumber(x);
+ return %Math_cos(x);
+}
// ECMA 262 - 15.8.2.8
-function MathExp(x) { return %Math_exp(ToNumber(x)); }
+function MathExp(x) {
+ if (!IS_NUMBER(x)) x = ToNumber(x);
+ return %Math_exp(x);
+}
// ECMA 262 - 15.8.2.9
-function MathFloor(x) { return %Math_floor(ToNumber(x)); }
+function MathFloor(x) {
+ if (!IS_NUMBER(x)) x = ToNumber(x);
+ if (0 < x && x <= 0xFFFFFFFF) {
+ // Numbers in the range [0, 2^32) can be floored by converting
+ // them to an unsigned 32-bit value using the shift operator.
+ // We avoid doing so for -0, because the result of Math.floor(-0)
+ // has to be -0, which wouldn't be the case with the shift.
+ return x << 0;
+ } else {
+ return %Math_floor(x);
+ }
+}
// ECMA 262 - 15.8.2.10
-function MathLog(x) { return %Math_log(ToNumber(x)); }
+function MathLog(x) {
+ if (!IS_NUMBER(x)) x = ToNumber(x);
+ return %Math_log(x);
+}
// ECMA 262 - 15.8.2.11
function MathMax(arg1, arg2) { // length == 2
@@ -103,22 +137,40 @@
}
// ECMA 262 - 15.8.2.13
-function MathPow(x, y) { return %Math_pow(ToNumber(x), ToNumber(y)); }
+function MathPow(x, y) {
+ if (!IS_NUMBER(x)) x = ToNumber(x);
+ if (!IS_NUMBER(y)) y = ToNumber(y);
+ return %Math_pow(x, y);
+}
// ECMA 262 - 15.8.2.14
-function MathRandom() { return %Math_random(); }
+function MathRandom() {
+ return %_RandomPositiveSmi() / 0x40000000;
+}
// ECMA 262 - 15.8.2.15
-function MathRound(x) { return %Math_round(ToNumber(x)); }
+function MathRound(x) {
+ if (!IS_NUMBER(x)) x = ToNumber(x);
+ return %Math_round(x);
+}
// ECMA 262 - 15.8.2.16
-function MathSin(x) { return %Math_sin(ToNumber(x)); }
+function MathSin(x) {
+ if (!IS_NUMBER(x)) x = ToNumber(x);
+ return %Math_sin(x);
+}
// ECMA 262 - 15.8.2.17
-function MathSqrt(x) { return %Math_sqrt(ToNumber(x)); }
+function MathSqrt(x) {
+ if (!IS_NUMBER(x)) x = ToNumber(x);
+ return %Math_sqrt(x);
+}
// ECMA 262 - 15.8.2.18
-function MathTan(x) { return %Math_tan(ToNumber(x)); }
+function MathTan(x) {
+ if (!IS_NUMBER(x)) x = ToNumber(x);
+ return %Math_tan(x);
+}
// -------------------------------------------------------------------
Modified: branches/bleeding_edge/src/runtime.cc
==============================================================================
--- branches/bleeding_edge/src/runtime.cc (original)
+++ branches/bleeding_edge/src/runtime.cc Mon Jun 15 01:04:47 2009
@@ -4168,24 +4168,6 @@
}
}
-// Returns a number value with positive sign, greater than or equal to
-// 0 but less than 1, chosen randomly.
-static Object* Runtime_Math_random(Arguments args) {
- NoHandleAllocation ha;
- ASSERT(args.length() == 0);
-
- // To get much better precision, we combine the results of two
- // invocations of random(). The result is computed by normalizing a
- // double in the range [0, RAND_MAX + 1) obtained by adding the
- // high-order bits in the range [0, RAND_MAX] with the low-order
- // bits in the range [0, 1).
- double lo = static_cast<double>(random()) * (1.0 / (RAND_MAX + 1.0));
- double hi = static_cast<double>(random());
- double result = (hi + lo) * (1.0 / (RAND_MAX + 1.0));
- ASSERT(result >= 0 && result < 1);
- return Heap::AllocateHeapNumber(result);
-}
-
static Object* Runtime_Math_round(Arguments args) {
NoHandleAllocation ha;
Modified: branches/bleeding_edge/src/runtime.h
==============================================================================
--- branches/bleeding_edge/src/runtime.h (original)
+++ branches/bleeding_edge/src/runtime.h Mon Jun 15 01:04:47 2009
@@ -135,7 +135,6 @@
F(Math_floor, 1) \
F(Math_log, 1) \
F(Math_pow, 2) \
- F(Math_random, 0) \
F(Math_round, 1) \
F(Math_sin, 1) \
F(Math_sqrt, 1) \
Modified: branches/bleeding_edge/src/serialize.cc
==============================================================================
--- branches/bleeding_edge/src/serialize.cc (original)
+++ branches/bleeding_edge/src/serialize.cc Mon Jun 15 01:04:47 2009
@@ -652,6 +652,10 @@
RUNTIME_ENTRY,
1,
"Runtime::PerformGC");
+ Add(ExternalReference::random_positive_smi_function().address(),
+ RUNTIME_ENTRY,
+ 2,
+ "V8::RandomPositiveSmi");
// Miscellaneous
Add(ExternalReference::builtin_passed_function().address(),
Modified: branches/bleeding_edge/src/v8.cc
==============================================================================
--- branches/bleeding_edge/src/v8.cc (original)
+++ branches/bleeding_edge/src/v8.cc Mon Jun 15 01:04:47 2009
@@ -138,4 +138,29 @@
}
+uint32_t V8::Random() {
+ // Random number generator using George Marsaglia's MWC algorithm.
+ static uint32_t hi = 0;
+ static uint32_t lo = 0;
+
+ // Initialize seed using the system random(). If one of the seeds
+ // should ever become zero again, or if random() returns zero, we
+ // avoid getting stuck with zero bits in hi or lo by re-initializing
+ // them on demand.
+ if (hi == 0) hi = random();
+ if (lo == 0) lo = random();
+
+ // Mix the bits.
+ hi = 36969 * (hi & 0xFFFF) + (hi >> 16);
+ lo = 18273 * (lo & 0xFFFF) + (lo >> 16);
+ return (hi << 16) + (lo & 0xFFFF);
+}
+
+
+Smi* V8::RandomPositiveSmi() {
+ uint32_t random = Random();
+ ASSERT(IsPowerOf2(Smi::kMaxValue + 1));
+ return Smi::FromInt(random & Smi::kMaxValue);
+}
+
} } // namespace v8::internal
Modified: branches/bleeding_edge/src/v8.h
==============================================================================
--- branches/bleeding_edge/src/v8.h (original)
+++ branches/bleeding_edge/src/v8.h Mon Jun 15 01:04:47 2009
@@ -80,10 +80,10 @@
public:
// Global actions.
- // If Initialize is called with des == NULL, the
- // initial state is created from scratch. If a non-null Deserializer
- // is given, the initial state is created by reading the
- // deserialized data into an empty heap.
+ // If Initialize is called with des == NULL, the initial state is
+ // created from scratch. If a non-null Deserializer is given, the
+ // initial state is created by reading the deserialized data into an
+ // empty heap.
static bool Initialize(Deserializer* des);
static void TearDown();
static bool IsRunning() { return is_running_; }
@@ -93,6 +93,11 @@
// Report process out of memory. Implementation found in api.cc.
static void FatalProcessOutOfMemory(const char* location);
+
+ // Random number generation support. Not cryptographically safe.
+ static uint32_t Random();
+ static Smi* RandomPositiveSmi();
+
private:
// True if engine is currently running
static bool is_running_;
--~--~---------~--~----~------------~-------~--~----~
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
-~----------~----~----~----~------~----~------~--~---
