1
// Copyright (c) 2007, Google Inc.
2
// All rights reserved.
4
// Redistribution and use in source and binary forms, with or without
5
// modification, are permitted provided that the following conditions are
8
// * Redistributions of source code must retain the above copyright
9
// notice, this list of conditions and the following disclaimer.
10
// * Redistributions in binary form must reproduce the above
11
// copyright notice, this list of conditions and the following disclaimer
12
// in the documentation and/or other materials provided with the
14
// * Neither the name of Google Inc. nor the names of its
15
// contributors may be used to endorse or promote products derived from
16
// this software without specific prior written permission.
18
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
33
// This file provides a minimal cache that can hold a <key, value> pair
34
// with little if any wasted space. The types of the key and value
35
// must be unsigned integral types or at least have unsigned semantics
36
// for >>, casting, and similar operations.
38
// Synchronization is not provided. However, the cache is implemented
39
// as an array of cache entries whose type is chosen at compile time.
40
// If a[i] is atomic on your hardware for the chosen array type then
41
// raciness will not necessarily lead to bugginess. The cache entries
42
// must be large enough to hold a partial key and a value packed
43
// together. The partial keys are bit strings of length
44
// kKeybits - kHashbits, and the values are bit strings of length kValuebits.
46
// In an effort to use minimal space, every cache entry represents
47
// some <key, value> pair; the class provides no way to mark a cache
48
// entry as empty or uninitialized. In practice, you may want to have
49
// reserved keys or values to get around this limitation. For example, in
50
// tcmalloc's PageID-to-sizeclass cache, a value of 0 is used as
51
// "unknown sizeclass."
53
// Usage Considerations
54
// --------------------
56
// kHashbits controls the size of the cache. The best value for
57
// kHashbits will of course depend on the application. Perhaps try
58
// tuning the value of kHashbits by measuring different values on your
59
// favorite benchmark. Also remember not to be a pig; other
60
// programs that need resources may suffer if you are.
62
// The main uses for this class will be when performance is
63
// critical and there's a convenient type to hold the cache's
64
// entries. As described above, the number of bits required
65
// for a cache entry is (kKeybits - kHashbits) + kValuebits. Suppose
66
// kKeybits + kValuebits is 43. Then it probably makes sense to
67
// chose kHashbits >= 11 so that cache entries fit in a uint32.
69
// On the other hand, suppose kKeybits = kValuebits = 64. Then
70
// using this class may be less worthwhile. You'll probably
71
// be using 128 bits for each entry anyway, so maybe just pick
72
// a hash function, H, and use an array indexed by H(key):
73
// void Put(K key, V value) { a_[H(key)] = pair<K, V>(key, value); }
74
// V GetOrDefault(K key, V default) { const pair<K, V> &p = a_[H(key)]; ... }
80
// For caches used only by one thread, the following is true:
82
// (c.Put(key, value), c.GetOrDefault(key, 0)) == value
84
// (c.Put(key, value), <...>, c.GetOrDefault(key, 0)) == value
85
// if the elided code contains no c.Put calls.
87
// 2. Has(key) will return false if no <key, value> pair with that key
88
// has ever been Put. However, a newly initialized cache will have
89
// some <key, value> pairs already present. When you create a new
90
// cache, you must specify an "initial value." The initialization
91
// procedure is equivalent to Clear(initial_value), which is
92
// equivalent to Put(k, initial_value) for all keys k from 0 to
95
// 3. If key and key' differ then the only way Put(key, value) may
96
// cause Has(key') to change is that Has(key') may change from true to
97
// false. Furthermore, a Put() call that doesn't change Has(key')
98
// doesn't change GetOrDefault(key', ...) either.
100
// Implementation details:
102
// This is a direct-mapped cache with 2^kHashbits entries; the hash
103
// function simply takes the low bits of the key. We store whole keys
104
// if a whole key plus a whole value fits in an entry. Otherwise, an
105
// entry is the high bits of a key and a value, packed together.
106
// E.g., a 20 bit key and a 7 bit value only require a uint16 for each
107
// entry if kHashbits >= 11.
109
// Alternatives to this scheme will be added as needed.
111
#ifndef TCMALLOC_PACKED_CACHE_INL_H_
112
#define TCMALLOC_PACKED_CACHE_INL_H_
114
#include "base/basictypes.h" // for COMPILE_ASSERT
115
#include "base/logging.h" // for DCHECK
117
// A safe way of doing "(1 << n) - 1" -- without worrying about overflow
118
// Note this will all be resolved to a constant expression at compile-time
119
#define N_ONES_(IntType, N) \
120
( (N) == 0 ? 0 : ((static_cast<IntType>(1) << ((N)-1))-1 + \
121
(static_cast<IntType>(1) << ((N)-1))) )
123
// The types K and V provide upper bounds on the number of valid keys
124
// and values, but we explicitly require the keys to be less than
125
// 2^kKeybits and the values to be less than 2^kValuebits. The size of
126
// the table is controlled by kHashbits, and the type of each entry in
127
// the cache is T. See also the big comment at the top of the file.
128
template <int kKeybits, typename T>
133
static const int kHashbits = 12;
134
static const int kValuebits = 7;
135
static const bool kUseWholeKeys = kKeybits + kValuebits <= 8 * sizeof(T);
137
explicit PackedCache(V initial_value) {
138
COMPILE_ASSERT(kKeybits <= sizeof(K) * 8, key_size);
139
COMPILE_ASSERT(kValuebits <= sizeof(V) * 8, value_size);
140
COMPILE_ASSERT(kHashbits <= kKeybits, hash_function);
141
COMPILE_ASSERT(kKeybits - kHashbits + kValuebits <= kTbits,
142
entry_size_must_be_big_enough);
143
Clear(initial_value);
146
void Put(K key, V value) {
147
DCHECK_EQ(key, key & kKeyMask);
148
DCHECK_EQ(value, value & kValueMask);
149
array_[Hash(key)] = KeyToUpper(key) | value;
152
bool Has(K key) const {
153
DCHECK_EQ(key, key & kKeyMask);
154
return KeyMatch(array_[Hash(key)], key);
157
V GetOrDefault(K key, V default_value) const {
158
// As with other code in this class, we touch array_ as few times
159
// as we can. Assuming entries are read atomically (e.g., their
160
// type is uintptr_t on most hardware) then certain races are
162
DCHECK_EQ(key, key & kKeyMask);
163
T entry = array_[Hash(key)];
164
return KeyMatch(entry, key) ? EntryToValue(entry) : default_value;
167
void Clear(V value) {
168
DCHECK_EQ(value, value & kValueMask);
169
for (int i = 0; i < 1 << kHashbits; i++) {
170
RAW_DCHECK(kUseWholeKeys || KeyToUpper(i) == 0, "KeyToUpper failure");
171
array_[i] = kUseWholeKeys ? (value | KeyToUpper(i)) : value;
176
// We are going to pack a value and the upper part of a key (or a
177
// whole key) into an entry of type T. The UPPER type is for the
178
// upper part of a key, after the key has been masked and shifted
179
// for inclusion in an entry.
182
static V EntryToValue(T t) { return t & kValueMask; }
184
// If we have space for a whole key, we just shift it left.
185
// Otherwise kHashbits determines where in a K to find the upper
186
// part of the key, and kValuebits determines where in the entry to
188
static UPPER KeyToUpper(K k) {
190
return static_cast<T>(k) << kValuebits;
192
const int shift = kHashbits - kValuebits;
193
// Assume kHashbits >= kValuebits. It'd be easy to lift this assumption.
194
return static_cast<T>(k >> shift) & kUpperMask;
198
static size_t Hash(K key) {
199
return static_cast<size_t>(key) & N_ONES_(size_t, kHashbits);
202
// Does the entry match the relevant part of the given key?
203
static bool KeyMatch(T entry, K key) {
204
return kUseWholeKeys ?
205
(entry >> kValuebits == key) :
206
((KeyToUpper(key) ^ entry) & kUpperMask) == 0;
209
static const int kTbits = 8 * sizeof(T);
210
static const int kUpperbits = kUseWholeKeys ? kKeybits : kKeybits - kHashbits;
213
static const K kKeyMask = N_ONES_(K, kKeybits);
216
static const T kUpperMask = N_ONES_(T, kUpperbits) << kValuebits;
218
// For masking a V or a T.
219
static const V kValueMask = N_ONES_(V, kValuebits);
221
// array_ is the cache. Its elements are volatile because any
222
// thread can write any array element at any time.
223
volatile T array_[1 << kHashbits];
228
#endif // TCMALLOC_PACKED_CACHE_INL_H_
added
removed
src/packed-cache-inl.h
