123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239 |
- // -*- Mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*-
- // 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. We store whole keys
- // if a whole key plus a whole value fits in an entry. Otherwise, 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_
- #include "config.h"
- #include <stddef.h> // for size_t
- #ifdef HAVE_STDINT_H
- #include <stdint.h> // for uintptr_t
- #endif
- #include "base/basictypes.h"
- #include "internal_logging.h"
- // 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;
- #ifdef TCMALLOC_SMALL_BUT_SLOW
- // Decrease the size map cache if running in the small memory mode.
- static const int kHashbits = 12;
- #else
- static const int kHashbits = 16;
- #endif
- static const int kValuebits = 7;
- static const bool kUseWholeKeys = kKeybits + kValuebits <= 8 * sizeof(T);
- 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) {
- ASSERT(key == (key & kKeyMask));
- ASSERT(value == (value & kValueMask));
- array_[Hash(key)] = KeyToUpper(key) | value;
- }
- bool Has(K key) const {
- ASSERT(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.
- ASSERT(key == (key & kKeyMask));
- T entry = array_[Hash(key)];
- return KeyMatch(entry, key) ? EntryToValue(entry) : default_value;
- }
- void Clear(V value) {
- ASSERT(value == (value & kValueMask));
- for (int i = 0; i < 1 << kHashbits; i++) {
- ASSERT(kUseWholeKeys || KeyToUpper(i) == 0);
- array_[i] = kUseWholeKeys ? (value | KeyToUpper(i)) : value;
- }
- }
- private:
- // We are going to pack a value and the upper part of a key (or a
- // whole 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; }
- // If we have space for a whole key, we just shift it left.
- // Otherwise 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) {
- if (kUseWholeKeys) {
- return static_cast<T>(k) << kValuebits;
- } else {
- const int shift = kHashbits - kValuebits;
- // Assume kHashbits >= kValuebits. It'd be easy to lift this assumption.
- return static_cast<T>(k >> shift) & kUpperMask;
- }
- }
- static size_t Hash(K key) {
- return static_cast<size_t>(key) & N_ONES_(size_t, kHashbits);
- }
- // Does the entry match the relevant part of the given key?
- static bool KeyMatch(T entry, K key) {
- return kUseWholeKeys ?
- (entry >> kValuebits == key) :
- ((KeyToUpper(key) ^ entry) & kUpperMask) == 0;
- }
- static const int kTbits = 8 * sizeof(T);
- static const int kUpperbits = kUseWholeKeys ? kKeybits : 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);
- // array_ is the cache. Its elements are volatile because any
- // thread can write any array element at any time.
- volatile T array_[1 << kHashbits];
- };
- #undef N_ONES_
- #endif // TCMALLOC_PACKED_CACHE_INL_H_
|