00001 // Copyright (c) 2007, Google Inc. 00002 // All rights reserved. 00003 // 00004 // Redistribution and use in source and binary forms, with or without 00005 // modification, are permitted provided that the following conditions are 00006 // met: 00007 // 00008 // * Redistributions of source code must retain the above copyright 00009 // notice, this list of conditions and the following disclaimer. 00010 // * Redistributions in binary form must reproduce the above 00011 // copyright notice, this list of conditions and the following disclaimer 00012 // in the documentation and/or other materials provided with the 00013 // distribution. 00014 // * Neither the name of Google Inc. nor the names of its 00015 // contributors may be used to endorse or promote products derived from 00016 // this software without specific prior written permission. 00017 // 00018 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 00019 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 00020 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 00021 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 00022 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 00023 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 00024 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 00025 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 00026 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 00027 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 00028 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00029 00030 // --- 00031 // Author: Geoff Pike 00032 // 00033 // This file provides a minimal cache that can hold a <key, value> pair 00034 // with little if any wasted space. The types of the key and value 00035 // must be unsigned integral types or at least have unsigned semantics 00036 // for >>, casting, and similar operations. 00037 // 00038 // Synchronization is not provided. However, the cache is implemented 00039 // as an array of cache entries whose type is chosen at compile time. 00040 // If a[i] is atomic on your hardware for the chosen array type then 00041 // raciness will not necessarily lead to bugginess. The cache entries 00042 // must be large enough to hold a partial key and a value packed 00043 // together. The partial keys are bit strings of length 00044 // kKeybits - kHashbits, and the values are bit strings of length kValuebits. 00045 // 00046 // In an effort to use minimal space, every cache entry represents 00047 // some <key, value> pair; the class provides no way to mark a cache 00048 // entry as empty or uninitialized. In practice, you may want to have 00049 // reserved keys or values to get around this limitation. For example, in 00050 // tcmalloc's PageID-to-sizeclass cache, a value of 0 is used as 00051 // "unknown sizeclass." 00052 // 00053 // Usage Considerations 00054 // -------------------- 00055 // 00056 // kHashbits controls the size of the cache. The best value for 00057 // kHashbits will of course depend on the application. Perhaps try 00058 // tuning the value of kHashbits by measuring different values on your 00059 // favorite benchmark. Also remember not to be a pig; other 00060 // programs that need resources may suffer if you are. 00061 // 00062 // The main uses for this class will be when performance is 00063 // critical and there's a convenient type to hold the cache's 00064 // entries. As described above, the number of bits required 00065 // for a cache entry is (kKeybits - kHashbits) + kValuebits. Suppose 00066 // kKeybits + kValuebits is 43. Then it probably makes sense to 00067 // chose kHashbits >= 11 so that cache entries fit in a uint32. 00068 // 00069 // On the other hand, suppose kKeybits = kValuebits = 64. Then 00070 // using this class may be less worthwhile. You'll probably 00071 // be using 128 bits for each entry anyway, so maybe just pick 00072 // a hash function, H, and use an array indexed by H(key): 00073 // void Put(K key, V value) { a_[H(key)] = pair<K, V>(key, value); } 00074 // V GetOrDefault(K key, V default) { const pair<K, V> &p = a_[H(key)]; ... } 00075 // etc. 00076 // 00077 // Further Details 00078 // --------------- 00079 // 00080 // For caches used only by one thread, the following is true: 00081 // 1. For a cache c, 00082 // (c.Put(key, value), c.GetOrDefault(key, 0)) == value 00083 // and 00084 // (c.Put(key, value), <...>, c.GetOrDefault(key, 0)) == value 00085 // if the elided code contains no c.Put calls. 00086 // 00087 // 2. Has(key) will return false if no <key, value> pair with that key 00088 // has ever been Put. However, a newly initialized cache will have 00089 // some <key, value> pairs already present. When you create a new 00090 // cache, you must specify an "initial value." The initialization 00091 // procedure is equivalent to Clear(initial_value), which is 00092 // equivalent to Put(k, initial_value) for all keys k from 0 to 00093 // 2^kHashbits - 1. 00094 // 00095 // 3. If key and key' differ then the only way Put(key, value) may 00096 // cause Has(key') to change is that Has(key') may change from true to 00097 // false. Furthermore, a Put() call that doesn't change Has(key') 00098 // doesn't change GetOrDefault(key', ...) either. 00099 // 00100 // Implementation details: 00101 // 00102 // This is a direct-mapped cache with 2^kHashbits entries; 00103 // the hash function simply takes the low bits of the key. 00104 // So, we don't have to store the low bits of the key in the entries. 00105 // Instead, an entry is the high bits of a key and a value, packed 00106 // together. E.g., a 20 bit key and a 7 bit value only require 00107 // a uint16 for each entry if kHashbits >= 11. 00108 // 00109 // Alternatives to this scheme will be added as needed. 00110 00111 #ifndef TCMALLOC_PACKED_CACHE_INL_H__ 00112 #define TCMALLOC_PACKED_CACHE_INL_H__ 00113 00114 #include "base/basictypes.h" // for COMPILE_ASSERT 00115 #include "base/logging.h" // for DCHECK 00116 00117 // A safe way of doing "(1 << n) - 1" -- without worrying about overflow 00118 // Note this will all be resolved to a constant expression at compile-time 00119 #define N_ONES_(IntType, N) \ 00120 ( (N) == 0 ? 0 : ((static_cast<IntType>(1) << ((N)-1))-1 + \ 00121 (static_cast<IntType>(1) << ((N)-1))) ) 00122 00123 // The types K and V provide upper bounds on the number of valid keys 00124 // and values, but we explicitly require the keys to be less than 00125 // 2^kKeybits and the values to be less than 2^kValuebits. The size of 00126 // the table is controlled by kHashbits, and the type of each entry in 00127 // the cache is T. See also the big comment at the top of the file. 00128 template <int kKeybits, typename T> 00129 class PackedCache { 00130 public: 00131 typedef uintptr_t K; 00132 typedef size_t V; 00133 static const int kHashbits = 12; 00134 static const int kValuebits = 8; 00135 00136 explicit PackedCache(V initial_value) { 00137 COMPILE_ASSERT(kKeybits <= sizeof(K) * 8, key_size); 00138 COMPILE_ASSERT(kValuebits <= sizeof(V) * 8, value_size); 00139 COMPILE_ASSERT(kHashbits <= kKeybits, hash_function); 00140 COMPILE_ASSERT(kKeybits - kHashbits + kValuebits <= kTbits, 00141 entry_size_must_be_big_enough); 00142 Clear(initial_value); 00143 } 00144 00145 void Put(K key, V value) { 00146 DCHECK_EQ(key, key & kKeyMask); 00147 DCHECK_EQ(value, value & kValueMask); 00148 array_[Hash(key)] = KeyToUpper(key) | value; 00149 } 00150 00151 bool Has(K key) const { 00152 DCHECK_EQ(key, key & kKeyMask); 00153 return KeyMatch(array_[Hash(key)], key); 00154 } 00155 00156 V GetOrDefault(K key, V default_value) const { 00157 // As with other code in this class, we touch array_ as few times 00158 // as we can. Assuming entries are read atomically (e.g., their 00159 // type is uintptr_t on most hardware) then certain races are 00160 // harmless. 00161 DCHECK_EQ(key, key & kKeyMask); 00162 T entry = array_[Hash(key)]; 00163 return KeyMatch(entry, key) ? EntryToValue(entry) : default_value; 00164 } 00165 00166 void Clear(V value) { 00167 DCHECK_EQ(value, value & kValueMask); 00168 for (int i = 0; i < 1 << kHashbits; i++) { 00169 array_[i] = value; 00170 } 00171 } 00172 00173 private: 00174 // We are going to pack a value and the upper part of a key into 00175 // an entry of type T. The UPPER type is for the upper part of a key, 00176 // after the key has been masked and shifted for inclusion in an entry. 00177 typedef T UPPER; 00178 00179 static V EntryToValue(T t) { return t & kValueMask; } 00180 00181 static UPPER EntryToUpper(T t) { return t & kUpperMask; } 00182 00183 // If v is a V and u is an UPPER then you can create an entry by 00184 // doing u | v. kHashbits determines where in a K to find the upper 00185 // part of the key, and kValuebits determines where in the entry to put 00186 // it. 00187 static UPPER KeyToUpper(K k) { 00188 const int shift = kHashbits - kValuebits; 00189 // Assume kHashbits >= kValuebits. It would be easy to lift this assumption. 00190 return static_cast<T>(k >> shift) & kUpperMask; 00191 } 00192 00193 // This is roughly the inverse of KeyToUpper(). Some of the key has been 00194 // thrown away, since KeyToUpper() masks off the low bits of the key. 00195 static K UpperToPartialKey(UPPER u) { 00196 DCHECK_EQ(u, u & kUpperMask); 00197 const int shift = kHashbits - kValuebits; 00198 // Assume kHashbits >= kValuebits. It would be easy to lift this assumption. 00199 return static_cast<K>(u) << shift; 00200 } 00201 00202 static size_t Hash(K key) { 00203 return static_cast<size_t>(key) & N_ONES_(size_t, kHashbits); 00204 } 00205 00206 // Does the entry's partial key match the relevant part of the given key? 00207 static bool KeyMatch(T entry, K key) { 00208 return ((KeyToUpper(key) ^ entry) & kUpperMask) == 0; 00209 } 00210 00211 static const int kTbits = 8 * sizeof(T); 00212 static const int kUpperbits = kKeybits - kHashbits; 00213 00214 // For masking a K. 00215 static const K kKeyMask = N_ONES_(K, kKeybits); 00216 00217 // For masking a T. 00218 static const T kUpperMask = N_ONES_(T, kUpperbits) << kValuebits; 00219 00220 // For masking a V or a T. 00221 static const V kValueMask = N_ONES_(V, kValuebits); 00222 00223 T array_[1 << kHashbits]; 00224 }; 00225 00226 #undef N_ONES_ 00227 00228 #endif // TCMALLOC_PACKED_CACHE_INL_H__