From 9440b885ae4a47155756f8ee9594293e39c3c164 Mon Sep 17 00:00:00 2001 From: "bmeurer@chromium.org" Date: Mon, 6 Oct 2014 12:27:24 +0000 Subject: [PATCH] Add C++11 compatible base::hash function object. Implement NodeCache in terms of base::hash and std::equal_to in preparation for HeapConstant caching. TEST=cctest,unittests R=svenpanne@chromium.org Review URL: https://codereview.chromium.org/624153003 git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@24412 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- BUILD.gn | 2 + src/base/functional.cc | 89 +++++++++++++++++ src/base/functional.h | 154 +++++++++++++++++++++++++++++ src/compiler/node-cache.cc | 103 ++++++++----------- src/compiler/node-cache.h | 42 +++++--- test/unittests/base/functional-unittest.cc | 131 ++++++++++++++++++++++++ test/unittests/test-utils.cc | 20 ++++ test/unittests/test-utils.h | 19 ++++ test/unittests/unittests.gyp | 1 + testing/gtest-support.h | 19 ++-- tools/gyp/v8.gyp | 2 + 11 files changed, 497 insertions(+), 85 deletions(-) create mode 100644 src/base/functional.cc create mode 100644 src/base/functional.h create mode 100644 test/unittests/base/functional-unittest.cc diff --git a/BUILD.gn b/BUILD.gn index 6affb6c..b0a6059 100644 --- a/BUILD.gn +++ b/BUILD.gn @@ -1229,6 +1229,8 @@ source_set("v8_libbase") { "src/base/division-by-constant.cc", "src/base/division-by-constant.h", "src/base/flags.h", + "src/base/functional.cc", + "src/base/functional.h", "src/base/lazy-instance.h", "src/base/logging.cc", "src/base/logging.h", diff --git a/src/base/functional.cc b/src/base/functional.cc new file mode 100644 index 0000000..c4a61ad --- /dev/null +++ b/src/base/functional.cc @@ -0,0 +1,89 @@ +// Copyright 2014 the V8 project authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. +// +// This also contains public domain code from MurmurHash. From the +// MurmurHash header: +// +// MurmurHash3 was written by Austin Appleby, and is placed in the public +// domain. The author hereby disclaims copyright to this source code. + +#include "src/base/functional.h" + +#include + +#include "src/base/bits.h" + +namespace v8 { +namespace base { + +namespace { + +template +inline size_t hash_value_unsigned(T value) { + const unsigned size_t_bits = std::numeric_limits::digits; + // ceiling(std::numeric_limits::digits / size_t_bits) - 1 + const unsigned length = (std::numeric_limits::digits - 1) / size_t_bits; + size_t seed = 0; + // Hopefully, this loop can be unrolled. + for (unsigned i = length * size_t_bits; i > 0; i -= size_t_bits) { + seed ^= static_cast(value >> i) + (seed << 6) + (seed >> 2); + } + seed ^= static_cast(value) + (seed << 6) + (seed >> 2); + return seed; +} + +} // namespace + + +// This code was taken from MurmurHash. +size_t hash_combine(size_t seed, size_t value) { +#if V8_HOST_ARCH_32_BIT + const uint32_t c1 = 0xcc9e2d51; + const uint32_t c2 = 0x1b873593; + + value *= c1; + value = bits::RotateRight32(value, 15); + value *= c2; + + seed ^= value; + seed = bits::RotateRight32(seed, 13); + seed = seed * 5 + 0xe6546b64; +#else + const uint64_t m = V8_UINT64_C(0xc6a4a7935bd1e995); + const uint32_t r = 47; + + value *= m; + value ^= value >> r; + value *= m; + + seed ^= value; + seed *= m; +#endif // V8_HOST_ARCH_32_BIT + return seed; +} + + +size_t hash_value(unsigned long v) { // NOLINT(runtime/int) + return hash_value_unsigned(v); +} + + +size_t hash_value(unsigned long long v) { // NOLINT(runtime/int) + return hash_value_unsigned(v); +} + + +size_t hash_value(float v) { + // 0 and -0 both hash to zero. + return v != 0.0f ? hash_value(bit_cast(v)) : 0; +} + + +size_t hash_value(double v) { + // 0 and -0 both hash to zero. + return v != 0.0 ? hash_value(bit_cast(v)) : 0; +} + +} // namespace base +} // namespace v8 diff --git a/src/base/functional.h b/src/base/functional.h new file mode 100644 index 0000000..60f93dd --- /dev/null +++ b/src/base/functional.h @@ -0,0 +1,154 @@ +// Copyright 2014 the V8 project authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#ifndef V8_BASE_FUNCTIONAL_H_ +#define V8_BASE_FUNCTIONAL_H_ + +#include +#include +#include + +#include "include/v8stdint.h" +#include "src/base/macros.h" + +namespace v8 { +namespace base { + +// base::hash is an implementation of the hash function object specified by +// C++11. It was designed to be compatible with std::hash (in C++11) and +// boost:hash (which in turn is based on the hash function object specified by +// the Draft Technical Report on C++ Library Extensions (TR1)). +// +// base::hash is implemented by calling the hash_value function. The namespace +// isn't specified so that it can detect overloads via argument dependant +// lookup. So if there is a free function hash_value in the same namespace as a +// custom type, it will get called. +// +// If users are asked to implement a hash function for their own types with no +// guidance, they generally write bad hash functions. Instead, we provide a +// simple function base::hash_combine to pass hash-relevant member variables +// into, in order to define a decent hash function. base::hash_combine is +// declared as: +// +// template +// size_t hash_combine(const T& v, const Ts& ...vs); +// +// Consider the following example: +// +// namespace v8 { +// namespace bar { +// struct Point { int x; int y; }; +// size_t hash_value(Point const& p) { +// return base::hash_combine(p.x, p.y); +// } +// } +// +// namespace foo { +// void DoSomeWork(bar::Point const& p) { +// base::hash h; +// ... +// size_t hash_code = h(p); // calls bar::hash_value(Point const&) +// ... +// } +// } +// } +// +// Based on the "Hashing User-Defined Types in C++1y" proposal from Jeffrey +// Yasskin and Chandler Carruth, see +// http://www.open-std.org/Jtc1/sc22/wg21/docs/papers/2012/n3333.html. + +template +struct hash; + + +inline size_t hash_combine() { return 0u; } +inline size_t hash_combine(size_t seed) { return seed; } +size_t hash_combine(size_t seed, size_t value); +template +inline size_t hash_combine(T const& v, Ts const&... vs) { + return hash_combine(hash()(v), hash_combine(vs...)); +} + + +#define V8_BASE_HASH_VALUE_TRIVIAL(type) \ + inline size_t hash_value(type v) { return static_cast(v); } +V8_BASE_HASH_VALUE_TRIVIAL(bool) +V8_BASE_HASH_VALUE_TRIVIAL(unsigned char) +V8_BASE_HASH_VALUE_TRIVIAL(unsigned short) // NOLINT(runtime/int) +V8_BASE_HASH_VALUE_TRIVIAL(unsigned int) +#undef V8_BASE_HASH_VALUE_TRIVIAL + +size_t hash_value(unsigned long v); // NOLINT(runtime/int) +size_t hash_value(unsigned long long v); // NOLINT(runtime/int) + +#define V8_BASE_HASH_VALUE_SIGNED(type) \ + inline size_t hash_value(signed type v) { \ + return hash_value(bit_cast(v)); \ + } +V8_BASE_HASH_VALUE_SIGNED(char) +V8_BASE_HASH_VALUE_SIGNED(short) // NOLINT(runtime/int) +V8_BASE_HASH_VALUE_SIGNED(int) // NOLINT(runtime/int) +V8_BASE_HASH_VALUE_SIGNED(long) // NOLINT(runtime/int) +V8_BASE_HASH_VALUE_SIGNED(long long) // NOLINT(runtime/int) +#undef V8_BASE_HASH_VALUE_SIGNED + +size_t hash_value(float v); +size_t hash_value(double v); + +template +inline size_t hash_value(T* const& v) { + size_t const x = bit_cast(v); + return (x >> 3) + x; +} + +template +inline size_t hash_value(std::pair const& v) { + return hash_combine(v.first, v.second); +} + + +template +struct hash : public std::unary_function { + size_t operator()(T const& v) const { return hash_value(v); } +}; + +#define V8_BASE_HASH_SPECIALIZE(type) \ + template <> \ + struct hash : public std::unary_function { \ + size_t operator()(type const v) const { \ + return ::v8::base::hash_value(v); \ + } \ + }; +V8_BASE_HASH_SPECIALIZE(bool) +V8_BASE_HASH_SPECIALIZE(signed char) +V8_BASE_HASH_SPECIALIZE(unsigned char) +V8_BASE_HASH_SPECIALIZE(short) // NOLINT(runtime/int) +V8_BASE_HASH_SPECIALIZE(unsigned short) // NOLINT(runtime/int) +V8_BASE_HASH_SPECIALIZE(int) +V8_BASE_HASH_SPECIALIZE(unsigned int) +V8_BASE_HASH_SPECIALIZE(long) // NOLINT(runtime/int) +V8_BASE_HASH_SPECIALIZE(unsigned long) // NOLINT(runtime/int) +V8_BASE_HASH_SPECIALIZE(long long) // NOLINT(runtime/int) +V8_BASE_HASH_SPECIALIZE(unsigned long long) // NOLINT(runtime/int) +V8_BASE_HASH_SPECIALIZE(float) +V8_BASE_HASH_SPECIALIZE(double) +#undef V8_BASE_HASH_SPECIALIZE + +template +struct hash : public std::unary_function { + size_t operator()(T* const v) const { return ::v8::base::hash_value(v); } +}; + +template +struct hash > + : public std::unary_function, size_t> { + size_t operator()(std::pair const& v) const { + return ::v8::base::hash_value(v); + } +}; + +} // namespace base +} // namespace v8 + +#endif // V8_BASE_FUNCTIONAL_H_ diff --git a/src/compiler/node-cache.cc b/src/compiler/node-cache.cc index 7cda167..dbf61ac 100644 --- a/src/compiler/node-cache.cc +++ b/src/compiler/node-cache.cc @@ -4,65 +4,43 @@ #include "src/compiler/node-cache.h" +#include + +#include "src/zone.h" + namespace v8 { namespace internal { namespace compiler { -#define INITIAL_SIZE 16 -#define LINEAR_PROBE 5 - -template -int32_t NodeCacheHash(Key key) { - UNIMPLEMENTED(); - return 0; -} - -template <> -inline int32_t NodeCacheHash(int32_t key) { - return ComputeIntegerHash(key, 0); -} - - -template <> -inline int32_t NodeCacheHash(int64_t key) { - return ComputeLongHash(key); -} - - -template <> -inline int32_t NodeCacheHash(double key) { - return ComputeLongHash(bit_cast(key)); -} +template +struct NodeCache::Entry { + Key key_; + Node* value_; +}; -template <> -inline int32_t NodeCacheHash(void* key) { - return ComputePointerHash(key); -} - - -template -bool NodeCache::Resize(Zone* zone) { +template +bool NodeCache::Resize(Zone* zone) { if (size_ >= max_) return false; // Don't grow past the maximum size. // Allocate a new block of entries 4x the size. Entry* old_entries = entries_; - int old_size = size_ + LINEAR_PROBE; - size_ = size_ * 4; - int num_entries = size_ + LINEAR_PROBE; - entries_ = zone->NewArray(num_entries); + size_t old_size = size_ + kLinearProbe; + size_ *= 4; + size_t num_entries = size_ + kLinearProbe; + entries_ = zone->NewArray(static_cast(num_entries)); memset(entries_, 0, sizeof(Entry) * num_entries); // Insert the old entries into the new block. - for (int i = 0; i < old_size; i++) { + for (size_t i = 0; i < old_size; ++i) { Entry* old = &old_entries[i]; - if (old->value_ != NULL) { - int hash = NodeCacheHash(old->key_); - int start = hash & (size_ - 1); - int end = start + LINEAR_PROBE; - for (int j = start; j < end; j++) { + if (old->value_) { + size_t hash = hash_(old->key_); + size_t start = hash & (size_ - 1); + size_t end = start + kLinearProbe; + for (size_t j = start; j < end; ++j) { Entry* entry = &entries_[j]; - if (entry->value_ == NULL) { + if (!entry->value_) { entry->key_ = old->key_; entry->value_ = old->value_; break; @@ -74,28 +52,28 @@ bool NodeCache::Resize(Zone* zone) { } -template -Node** NodeCache::Find(Zone* zone, Key key) { - int32_t hash = NodeCacheHash(key); - if (entries_ == NULL) { +template +Node** NodeCache::Find(Zone* zone, Key key) { + size_t hash = hash_(key); + if (!entries_) { // Allocate the initial entries and insert the first entry. - int num_entries = INITIAL_SIZE + LINEAR_PROBE; - entries_ = zone->NewArray(num_entries); - size_ = INITIAL_SIZE; + size_t num_entries = kInitialSize + kLinearProbe; + entries_ = zone->NewArray(static_cast(num_entries)); + size_ = kInitialSize; memset(entries_, 0, sizeof(Entry) * num_entries); - Entry* entry = &entries_[hash & (INITIAL_SIZE - 1)]; + Entry* entry = &entries_[hash & (kInitialSize - 1)]; entry->key_ = key; return &entry->value_; } - while (true) { + for (;;) { // Search up to N entries after (linear probing). - int start = hash & (size_ - 1); - int end = start + LINEAR_PROBE; - for (int i = start; i < end; i++) { + size_t start = hash & (size_ - 1); + size_t end = start + kLinearProbe; + for (size_t i = start; i < end; i++) { Entry* entry = &entries_[i]; - if (entry->key_ == key) return &entry->value_; - if (entry->value_ == NULL) { + if (pred_(entry->key_, key)) return &entry->value_; + if (!entry->value_) { entry->key_ = key; return &entry->value_; } @@ -107,7 +85,7 @@ Node** NodeCache::Find(Zone* zone, Key key) { // If resized to maximum and still didn't find space, overwrite an entry. Entry* entry = &entries_[hash & (size_ - 1)]; entry->key_ = key; - entry->value_ = NULL; + entry->value_ = nullptr; return &entry->value_; } @@ -115,6 +93,7 @@ Node** NodeCache::Find(Zone* zone, Key key) { template class NodeCache; template class NodeCache; template class NodeCache; -} -} -} // namespace v8::internal::compiler + +} // namespace compiler +} // namespace internal +} // namespace v8 diff --git a/src/compiler/node-cache.h b/src/compiler/node-cache.h index 35352ea..7741e1e 100644 --- a/src/compiler/node-cache.h +++ b/src/compiler/node-cache.h @@ -5,20 +5,30 @@ #ifndef V8_COMPILER_NODE_CACHE_H_ #define V8_COMPILER_NODE_CACHE_H_ -#include "src/v8.h" - -#include "src/compiler/node.h" +#include "src/base/functional.h" +#include "src/base/macros.h" namespace v8 { namespace internal { + +// Forward declarations. +class Zone; + + namespace compiler { +// Forward declarations. +class Node; + + // A cache for nodes based on a key. Useful for implementing canonicalization of // nodes such as constants, parameters, etc. -template -class NodeCache { +template , + typename Pred = std::equal_to > +class NodeCache FINAL { public: - explicit NodeCache(int max = 256) : entries_(NULL), size_(0), max_(max) {} + explicit NodeCache(size_t max = 256) + : entries_(nullptr), size_(0), max_(max) {} // Search for node associated with {key} and return a pointer to a memory // location in this cache that stores an entry for the key. If the location @@ -30,14 +40,15 @@ class NodeCache { Node** Find(Zone* zone, Key key); private: - struct Entry { - Key key_; - Node* value_; - }; + enum { kInitialSize = 16u, kLinearProbe = 5u }; + + struct Entry; Entry* entries_; // lazily-allocated hash entries. - int32_t size_; - int32_t max_; + size_t size_; + size_t max_; + Hash hash_; + Pred pred_; bool Resize(Zone* zone); }; @@ -46,8 +57,9 @@ class NodeCache { typedef NodeCache Int64NodeCache; typedef NodeCache Int32NodeCache; typedef NodeCache PtrNodeCache; -} -} -} // namespace v8::internal::compiler + +} // namespace compiler +} // namespace internal +} // namespace v8 #endif // V8_COMPILER_NODE_CACHE_H_ diff --git a/test/unittests/base/functional-unittest.cc b/test/unittests/base/functional-unittest.cc new file mode 100644 index 0000000..e6f260f --- /dev/null +++ b/test/unittests/base/functional-unittest.cc @@ -0,0 +1,131 @@ +// Copyright 2014 the V8 project authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "src/base/functional.h" + +#include +#include + +#include "test/unittests/test-utils.h" + +namespace v8 { +namespace base { + +TEST(FunctionalTest, HashBool) { + hash h, h1, h2; + EXPECT_EQ(h1(true), h2(true)); + EXPECT_EQ(h1(false), h2(false)); + EXPECT_NE(h(true), h(false)); +} + + +TEST(FunctionalTest, HashFloatZero) { + hash h; + EXPECT_EQ(h(0.0f), h(-0.0f)); +} + + +TEST(FunctionalTest, HashDoubleZero) { + hash h; + EXPECT_EQ(h(0.0), h(-0.0)); +} + + +template +class FunctionalTest : public TestWithRandomNumberGenerator {}; + +typedef ::testing::Types FunctionalTypes; + +TYPED_TEST_CASE(FunctionalTest, FunctionalTypes); + + +TYPED_TEST(FunctionalTest, EqualToImpliesSameHashCode) { + hash h; + std::equal_to e; + TypeParam values[32]; + this->rng()->NextBytes(values, sizeof(values)); + TRACED_FOREACH(TypeParam, v1, values) { + TRACED_FOREACH(TypeParam, v2, values) { + if (e(v1, v2)) EXPECT_EQ(h(v1), h(v2)); + } + } +} + + +TYPED_TEST(FunctionalTest, HashEqualsHashValue) { + for (int i = 0; i < 128; ++i) { + TypeParam v; + this->rng()->NextBytes(&v, sizeof(v)); + hash h; + EXPECT_EQ(h(v), hash_value(v)); + } +} + + +TYPED_TEST(FunctionalTest, HashIsStateless) { + hash h1, h2; + for (int i = 0; i < 128; ++i) { + TypeParam v; + this->rng()->NextBytes(&v, sizeof(v)); + EXPECT_EQ(h1(v), h2(v)); + } +} + + +TYPED_TEST(FunctionalTest, HashIsOkish) { + const size_t kValues = 128; + const size_t kMinHashes = kValues / (sizeof(uint64_t) / sizeof(size_t)); + std::set vs; + while (vs.size() != kValues) { + TypeParam v; + this->rng()->NextBytes(&v, sizeof(v)); + vs.insert(v); + } + std::set hs; + for (const auto& v : vs) { + hash h; + hs.insert(h(v)); + } + EXPECT_LE(kMinHashes, hs.size()); +} + + +namespace { + +struct Foo { + int x; + double y; +}; + + +size_t hash_value(Foo const& v) { return hash_combine(v.x, v.y); } + +} // namespace + + +TEST(FunctionalTest, HashUsesArgumentDependentLookup) { + const int kIntValues[] = {std::numeric_limits::min(), -1, 0, 1, 42, + std::numeric_limits::max()}; + const double kDoubleValues[] = { + std::numeric_limits::min(), -1, -0, 0, 1, + std::numeric_limits::max()}; + TRACED_FOREACH(int, x, kIntValues) { + TRACED_FOREACH(double, y, kDoubleValues) { + hash h; + Foo foo = {x, y}; + EXPECT_EQ(hash_combine(x, y), h(foo)); + } + } +} + +} // namespace base +} // namespace v8 diff --git a/test/unittests/test-utils.cc b/test/unittests/test-utils.cc index a3532dd..e6efef3 100644 --- a/test/unittests/test-utils.cc +++ b/test/unittests/test-utils.cc @@ -4,6 +4,8 @@ #include "test/unittests/test-utils.h" +#include "src/base/platform/time.h" +#include "src/flags.h" #include "src/isolate-inl.h" namespace v8 { @@ -44,6 +46,24 @@ TestWithContext::TestWithContext() TestWithContext::~TestWithContext() {} +namespace base { +namespace { + +inline int64_t GetRandomSeedFromFlag(int random_seed) { + return random_seed ? random_seed : TimeTicks::Now().ToInternalValue(); +} + +} // namespace + +TestWithRandomNumberGenerator::TestWithRandomNumberGenerator() + : rng_(GetRandomSeedFromFlag(internal::FLAG_random_seed)) {} + + +TestWithRandomNumberGenerator::~TestWithRandomNumberGenerator() {} + +} // namespace base + + namespace internal { TestWithIsolate::~TestWithIsolate() {} diff --git a/test/unittests/test-utils.h b/test/unittests/test-utils.h index e08974a..56b9691 100644 --- a/test/unittests/test-utils.h +++ b/test/unittests/test-utils.h @@ -7,6 +7,7 @@ #include "include/v8.h" #include "src/base/macros.h" +#include "src/base/utils/random-number-generator.h" #include "src/zone.h" #include "testing/gtest-support.h" @@ -46,6 +47,24 @@ class TestWithContext : public virtual TestWithIsolate { }; +namespace base { + +class TestWithRandomNumberGenerator : public ::testing::Test { + public: + TestWithRandomNumberGenerator(); + virtual ~TestWithRandomNumberGenerator(); + + RandomNumberGenerator* rng() { return &rng_; } + + private: + RandomNumberGenerator rng_; + + DISALLOW_COPY_AND_ASSIGN(TestWithRandomNumberGenerator); +}; + +} // namespace base + + namespace internal { // Forward declarations. diff --git a/test/unittests/unittests.gyp b/test/unittests/unittests.gyp index e4dadbc..e13eecb 100644 --- a/test/unittests/unittests.gyp +++ b/test/unittests/unittests.gyp @@ -27,6 +27,7 @@ 'base/cpu-unittest.cc', 'base/division-by-constant-unittest.cc', 'base/flags-unittest.cc', + 'base/functional-unittest.cc', 'base/platform/condition-variable-unittest.cc', 'base/platform/mutex-unittest.cc', 'base/platform/platform-unittest.cc', diff --git a/testing/gtest-support.h b/testing/gtest-support.h index 66b1094..7be79b5 100644 --- a/testing/gtest-support.h +++ b/testing/gtest-support.h @@ -16,14 +16,17 @@ namespace internal { inline std::string GetTypeName() { \ return #type; \ } -GET_TYPE_NAME(int8_t) -GET_TYPE_NAME(uint8_t) -GET_TYPE_NAME(int16_t) -GET_TYPE_NAME(uint16_t) -GET_TYPE_NAME(int32_t) -GET_TYPE_NAME(uint32_t) -GET_TYPE_NAME(int64_t) -GET_TYPE_NAME(uint64_t) +GET_TYPE_NAME(bool) +GET_TYPE_NAME(signed char) +GET_TYPE_NAME(unsigned char) +GET_TYPE_NAME(short) +GET_TYPE_NAME(unsigned short) +GET_TYPE_NAME(int) +GET_TYPE_NAME(unsigned int) +GET_TYPE_NAME(long) +GET_TYPE_NAME(unsigned long) +GET_TYPE_NAME(long long) +GET_TYPE_NAME(unsigned long long) GET_TYPE_NAME(float) GET_TYPE_NAME(double) #undef GET_TYPE_NAME diff --git a/tools/gyp/v8.gyp b/tools/gyp/v8.gyp index 0073003..9b85f91 100644 --- a/tools/gyp/v8.gyp +++ b/tools/gyp/v8.gyp @@ -1217,6 +1217,8 @@ '../../src/base/division-by-constant.cc', '../../src/base/division-by-constant.h', '../../src/base/flags.h', + '../../src/base/functional.cc', + '../../src/base/functional.h', '../../src/base/lazy-instance.h', '../../src/base/logging.cc', '../../src/base/logging.h', -- 2.7.4