// Copyright (c) 2007, Google Inc. | |
// 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. | |
// --- | |
// Author: Geoff Pike | |
// | |
// This file provides a minimal cache that can hold a <key, value> pair | |
// with little if any wasted space. The types of the key and value | |
// must be unsigned integral types or at least have unsigned semantics | |
// for >>, casting, and similar operations. | |
// | |
// Synchronization is not provided. However, the cache is implemented | |
// as an array of cache entries whose type is chosen at compile time. | |
// If a[i] is atomic on your hardware for the chosen array type then | |
// raciness will not necessarily lead to bugginess. The cache entries | |
// must be large enough to hold a partial key and a value packed | |
// together. The partial keys are bit strings of length | |
// kKeybits - kHashbits, and the values are bit strings of length kValuebits. | |
// | |
// In an effort to use minimal space, every cache entry represents | |
// some <key, value> pair; the class provides no way to mark a cache | |
// entry as empty or uninitialized. In practice, you may want to have | |
// reserved keys or values to get around this limitation. For example, in | |
// tcmalloc's PageID-to-sizeclass cache, a value of 0 is used as | |
// "unknown sizeclass." | |
// | |
// Usage Considerations | |
// -------------------- | |
// | |
// kHashbits controls the size of the cache. The best value for | |
// kHashbits will of course depend on the application. Perhaps try | |
// tuning the value of kHashbits by measuring different values on your | |
// favorite benchmark. Also remember not to be a pig; other | |
// programs that need resources may suffer if you are. | |
// | |
// The main uses for this class will be when performance is | |
// critical and there's a convenient type to hold the cache's | |
// entries. As described above, the number of bits required | |
// for a cache entry is (kKeybits - kHashbits) + kValuebits. Suppose | |
// kKeybits + kValuebits is 43. Then it probably makes sense to | |
// chose kHashbits >= 11 so that cache entries fit in a uint32. | |
// | |
// On the other hand, suppose kKeybits = kValuebits = 64. Then | |
// using this class may be less worthwhile. You'll probably | |
// be using 128 bits for each entry anyway, so maybe just pick | |
// a hash function, H, and use an array indexed by H(key): | |
// void Put(K key, V value) { a_[H(key)] = pair<K, V>(key, value); } | |
// V GetOrDefault(K key, V default) { const pair<K, V> &p = a_[H(key)]; ... } | |
// etc. | |
// | |
// Further Details | |
// --------------- | |
// | |
// For caches used only by one thread, the following is true: | |
// 1. For a cache c, | |
// (c.Put(key, value), c.GetOrDefault(key, 0)) == value | |
// and | |
// (c.Put(key, value), <...>, c.GetOrDefault(key, 0)) == value | |
// if the elided code contains no c.Put calls. | |
// | |
// 2. Has(key) will return false if no <key, value> pair with that key | |
// has ever been Put. However, a newly initialized cache will have | |
// some <key, value> pairs already present. When you create a new | |
// cache, you must specify an "initial value." The initialization | |
// procedure is equivalent to Clear(initial_value), which is | |
// equivalent to Put(k, initial_value) for all keys k from 0 to | |
// 2^kHashbits - 1. | |
// | |
// 3. If key and key' differ then the only way Put(key, value) may | |
// cause Has(key') to change is that Has(key') may change from true to | |
// false. Furthermore, a Put() call that doesn't change Has(key') | |
// doesn't change GetOrDefault(key', ...) either. | |
// | |
// Implementation details: | |
// | |
// This is a direct-mapped cache with 2^kHashbits entries; | |
// the hash function simply takes the low bits of the key. | |
// So, we don't have to store the low bits of the key in the entries. | |
// Instead, an entry is the high bits of a key and a value, packed | |
// together. E.g., a 20 bit key and a 7 bit value only require | |
// a uint16 for each entry if kHashbits >= 11. | |
// | |
// Alternatives to this scheme will be added as needed. | |
#ifndef TCMALLOC_PACKED_CACHE_INL_H__ | |
#define TCMALLOC_PACKED_CACHE_INL_H__ | |
#ifndef WTF_CHANGES | |
#include "base/basictypes.h" // for COMPILE_ASSERT | |
#include "base/logging.h" // for DCHECK | |
#endif | |
#ifndef DCHECK_EQ | |
#define DCHECK_EQ(val1, val2) ASSERT((val1) == (val2)) | |
#endif | |
// A safe way of doing "(1 << n) - 1" -- without worrying about overflow | |
// Note this will all be resolved to a constant expression at compile-time | |
#define N_ONES_(IntType, N) \ | |
( (N) == 0 ? 0 : ((static_cast<IntType>(1) << ((N)-1))-1 + \ | |
(static_cast<IntType>(1) << ((N)-1))) ) | |
// The types K and V provide upper bounds on the number of valid keys | |
// and values, but we explicitly require the keys to be less than | |
// 2^kKeybits and the values to be less than 2^kValuebits. The size of | |
// the table is controlled by kHashbits, and the type of each entry in | |
// the cache is T. See also the big comment at the top of the file. | |
template <int kKeybits, typename T> | |
class PackedCache { | |
public: | |
typedef uintptr_t K; | |
typedef size_t V; | |
static const size_t kHashbits = 12; | |
static const size_t kValuebits = 8; | |
explicit PackedCache(V initial_value) { | |
COMPILE_ASSERT(kKeybits <= sizeof(K) * 8, key_size); | |
COMPILE_ASSERT(kValuebits <= sizeof(V) * 8, value_size); | |
COMPILE_ASSERT(kHashbits <= kKeybits, hash_function); | |
COMPILE_ASSERT(kKeybits - kHashbits + kValuebits <= kTbits, | |
entry_size_must_be_big_enough); | |
Clear(initial_value); | |
} | |
void Put(K key, V value) { | |
DCHECK_EQ(key, key & kKeyMask); | |
DCHECK_EQ(value, value & kValueMask); | |
array_[Hash(key)] = static_cast<T>(KeyToUpper(key) | value); | |
} | |
bool Has(K key) const { | |
DCHECK_EQ(key, key & kKeyMask); | |
return KeyMatch(array_[Hash(key)], key); | |
} | |
V GetOrDefault(K key, V default_value) const { | |
// As with other code in this class, we touch array_ as few times | |
// as we can. Assuming entries are read atomically (e.g., their | |
// type is uintptr_t on most hardware) then certain races are | |
// harmless. | |
DCHECK_EQ(key, key & kKeyMask); | |
T entry = array_[Hash(key)]; | |
return KeyMatch(entry, key) ? EntryToValue(entry) : default_value; | |
} | |
void Clear(V value) { | |
DCHECK_EQ(value, value & kValueMask); | |
for (int i = 0; i < 1 << kHashbits; i++) { | |
array_[i] = static_cast<T>(value); | |
} | |
} | |
private: | |
// We are going to pack a value and the upper part of a key into | |
// an entry of type T. The UPPER type is for the upper part of a key, | |
// after the key has been masked and shifted for inclusion in an entry. | |
typedef T UPPER; | |
static V EntryToValue(T t) { return t & kValueMask; } | |
static UPPER EntryToUpper(T t) { return t & kUpperMask; } | |
// If v is a V and u is an UPPER then you can create an entry by | |
// doing u | v. kHashbits determines where in a K to find the upper | |
// part of the key, and kValuebits determines where in the entry to put | |
// it. | |
static UPPER KeyToUpper(K k) { | |
const int shift = kHashbits - kValuebits; | |
// Assume kHashbits >= kValuebits. It would be easy to lift this assumption. | |
return static_cast<T>(k >> shift) & kUpperMask; | |
} | |
// This is roughly the inverse of KeyToUpper(). Some of the key has been | |
// thrown away, since KeyToUpper() masks off the low bits of the key. | |
static K UpperToPartialKey(UPPER u) { | |
DCHECK_EQ(u, u & kUpperMask); | |
const int shift = kHashbits - kValuebits; | |
// Assume kHashbits >= kValuebits. It would be easy to lift this assumption. | |
return static_cast<K>(u) << shift; | |
} | |
static size_t Hash(K key) { | |
return static_cast<size_t>(key) & N_ONES_(size_t, kHashbits); | |
} | |
// Does the entry's partial key match the relevant part of the given key? | |
static bool KeyMatch(T entry, K key) { | |
return ((KeyToUpper(key) ^ entry) & kUpperMask) == 0; | |
} | |
static const size_t kTbits = 8 * sizeof(T); | |
static const int kUpperbits = kKeybits - kHashbits; | |
// For masking a K. | |
static const K kKeyMask = N_ONES_(K, kKeybits); | |
// For masking a T. | |
static const T kUpperMask = N_ONES_(T, kUpperbits) << kValuebits; | |
// For masking a V or a T. | |
static const V kValueMask = N_ONES_(V, kValuebits); | |
T array_[1 << kHashbits]; | |
}; | |
#undef N_ONES_ | |
#endif // TCMALLOC_PACKED_CACHE_INL_H__ |