Revision: 2790
Author: [email protected]
Date: Tue Sep 1 02:03:58 2009
Log: Cache the results of slow math operations on machines that don't
have hardware fpu instructions to execute them.
Review URL: http://codereview.chromium.org/179059
http://code.google.com/p/v8/source/detail?r=2790
Added:
/branches/bleeding_edge/test/mjsunit/transcendentals.js
Modified:
/branches/bleeding_edge/src/heap.cc
/branches/bleeding_edge/src/heap.h
/branches/bleeding_edge/src/runtime.cc
=======================================
--- /dev/null
+++ /branches/bleeding_edge/test/mjsunit/transcendentals.js Tue Sep 1
02:03:58 2009
@@ -0,0 +1,63 @@
+// Copyright 2009 the V8 project authors. All rights reserved.
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+// * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following
+// disclaimer in the documentation and/or other materials provided
+// with the distribution.
+// * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived
+// from this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+
+// Two fp numbers that have the same hash value (see TranscendentalCache
+// in heap.h).
+var x = 0x123456789ABCD;
+var y = 0x1134567899BCD;
+
+assertEquals(-0.5582508193778007, Math.sin(x));
+assertEquals(-0.7367701055966746, Math.sin(y));
+
+assertEquals(-0.8296722380940645, Math.cos(x));
+assertEquals(-0.6761433365042245, Math.cos(y));
+
+assertEquals(0.6728570557696649, Math.tan(x));
+assertEquals(1.0896655573149632, Math.tan(y));
+
+assertEquals(33.400141709152514, Math.log(x));
+assertEquals(33.343643692997280, Math.log(y));
+
+// These also have the same hash value but they are < 1 so they can be
+// used for the asin and other functions.
+x = 0x123456789ABCD / 0x2000000000000;
+y = 0x1134567899BCD / 0x2000000000000;
+
+assertEquals(0.6051541873165459, Math.asin(x));
+assertEquals(0.5676343396849298, Math.asin(y));
+
+assertEquals(0.9656421394783508, Math.acos(x));
+assertEquals(1.0031619871099668, Math.acos(y));
+
+assertEquals(0.5172294898564562, Math.atan(x));
+assertEquals(0.4933034078249788, Math.atan(y));
+
+assertEquals(1.7663034013841883, Math.exp(x));
+assertEquals(1.7119599587777090, Math.exp(y));
+
+print("OK");
=======================================
--- /branches/bleeding_edge/src/heap.cc Mon Aug 31 05:40:37 2009
+++ /branches/bleeding_edge/src/heap.cc Tue Sep 1 02:03:58 2009
@@ -257,6 +257,7 @@
void Heap::GarbageCollectionPrologue() {
+ TranscendentalCache::Clear();
gc_count_++;
#ifdef DEBUG
ASSERT(allocation_allowed_ && gc_state_ == NOT_IN_GC);
@@ -3986,4 +3987,30 @@
}
#endif
+
+TranscendentalCache::TranscendentalCache(TranscendentalCache::Type t)
+ : type_(t) {
+ uint32_t in0 = 0xffffffffu; // Bit-pattern for a NaN that isn't
+ uint32_t in1 = 0xffffffffu; // generated by the FPU.
+ for (int i = 0; i < kCacheSize; i++) {
+ elements_[i].in[0] = in0;
+ elements_[i].in[1] = in1;
+ elements_[i].output = NULL;
+ }
+}
+
+
+TranscendentalCache* TranscendentalCache::caches_[kNumberOfCaches];
+
+
+void TranscendentalCache::Clear() {
+ for (int i = 0; i < kNumberOfCaches; i++) {
+ if (caches_[i] != NULL) {
+ delete caches_[i];
+ caches_[i] = NULL;
+ }
+ }
+}
+
+
} } // namespace v8::internal
=======================================
--- /branches/bleeding_edge/src/heap.h Mon Aug 31 05:40:37 2009
+++ /branches/bleeding_edge/src/heap.h Tue Sep 1 02:03:58 2009
@@ -28,8 +28,11 @@
#ifndef V8_HEAP_H_
#define V8_HEAP_H_
+#include <math.h>
+
#include "zone-inl.h"
+
namespace v8 {
namespace internal {
@@ -1519,6 +1522,91 @@
int previous_marked_count_;
};
+
+class TranscendentalCache {
+ public:
+ enum Type {ACOS, ASIN, ATAN, COS, EXP, LOG, SIN, TAN, kNumberOfCaches};
+
+ explicit TranscendentalCache(Type t);
+
+ // Returns a heap number with f(input), where f is a math function
specified
+ // by the 'type' argument.
+ static inline Object* Get(Type type, double input) {
+ TranscendentalCache* cache = caches_[type];
+ if (cache == NULL) {
+ caches_[type] = cache = new TranscendentalCache(type);
+ }
+ return cache->Get(input);
+ }
+
+ // The cache contains raw Object pointers. This method disposes of
+ // them before a garbage collection.
+ static void Clear();
+
+ private:
+ inline Object* Get(double input) {
+ Converter c;
+ c.dbl = input;
+ int hash = Hash(c);
+ Element e = elements_[hash];
+ if (e.in[0] == c.integers[0] &&
+ e.in[1] == c.integers[1]) {
+ ASSERT(e.output != NULL);
+ return e.output;
+ }
+ double answer = Calculate(input);
+ Object* heap_number = Heap::AllocateHeapNumber(answer);
+ if (!heap_number->IsFailure()) {
+ elements_[hash].in[0] = c.integers[0];
+ elements_[hash].in[1] = c.integers[1];
+ elements_[hash].output = heap_number;
+ }
+ return heap_number;
+ }
+
+ inline double Calculate(double input) {
+ switch (type_) {
+ case ACOS:
+ return acos(input);
+ case ASIN:
+ return asin(input);
+ case ATAN:
+ return atan(input);
+ case COS:
+ return cos(input);
+ case EXP:
+ return exp(input);
+ case LOG:
+ return log(input);
+ case SIN:
+ return sin(input);
+ case TAN:
+ return tan(input);
+ default:
+ return 0.0; // Never happens.
+ }
+ }
+ static const int kCacheSize = 512;
+ struct Element {
+ uint32_t in[2];
+ Object* output;
+ };
+ union Converter {
+ double dbl;
+ uint32_t integers[2];
+ };
+ inline static int Hash(const Converter& c) {
+ uint32_t hash = (c.integers[0] ^ c.integers[1]);
+ hash ^= hash >> 16;
+ hash ^= hash >> 8;
+ return (hash & (kCacheSize - 1));
+ }
+ static TranscendentalCache* caches_[kNumberOfCaches];
+ Element elements_[kCacheSize];
+ Type type_;
+};
+
+
} } // namespace v8::internal
#endif // V8_HEAP_H_
=======================================
--- /branches/bleeding_edge/src/runtime.cc Wed Aug 26 05:22:44 2009
+++ /branches/bleeding_edge/src/runtime.cc Tue Sep 1 02:03:58 2009
@@ -4058,7 +4058,7 @@
ASSERT(args.length() == 1);
CONVERT_DOUBLE_CHECKED(x, args[0]);
- return Heap::AllocateHeapNumber(acos(x));
+ return TranscendentalCache::Get(TranscendentalCache::ACOS, x);
}
@@ -4067,7 +4067,7 @@
ASSERT(args.length() == 1);
CONVERT_DOUBLE_CHECKED(x, args[0]);
- return Heap::AllocateHeapNumber(asin(x));
+ return TranscendentalCache::Get(TranscendentalCache::ASIN, x);
}
@@ -4076,7 +4076,7 @@
ASSERT(args.length() == 1);
CONVERT_DOUBLE_CHECKED(x, args[0]);
- return Heap::AllocateHeapNumber(atan(x));
+ return TranscendentalCache::Get(TranscendentalCache::ATAN, x);
}
@@ -4117,7 +4117,7 @@
ASSERT(args.length() == 1);
CONVERT_DOUBLE_CHECKED(x, args[0]);
- return Heap::AllocateHeapNumber(cos(x));
+ return TranscendentalCache::Get(TranscendentalCache::COS, x);
}
@@ -4126,7 +4126,7 @@
ASSERT(args.length() == 1);
CONVERT_DOUBLE_CHECKED(x, args[0]);
- return Heap::AllocateHeapNumber(exp(x));
+ return TranscendentalCache::Get(TranscendentalCache::EXP, x);
}
@@ -4144,7 +4144,7 @@
ASSERT(args.length() == 1);
CONVERT_DOUBLE_CHECKED(x, args[0]);
- return Heap::AllocateHeapNumber(log(x));
+ return TranscendentalCache::Get(TranscendentalCache::LOG, x);
}
@@ -4232,7 +4232,7 @@
ASSERT(args.length() == 1);
CONVERT_DOUBLE_CHECKED(x, args[0]);
- return Heap::AllocateHeapNumber(sin(x));
+ return TranscendentalCache::Get(TranscendentalCache::SIN, x);
}
@@ -4250,7 +4250,7 @@
ASSERT(args.length() == 1);
CONVERT_DOUBLE_CHECKED(x, args[0]);
- return Heap::AllocateHeapNumber(tan(x));
+ return TranscendentalCache::Get(TranscendentalCache::TAN, x);
}
--~--~---------~--~----~------------~-------~--~----~
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
-~----------~----~----~----~------~----~------~--~---
