Halide
hashmap.h
Go to the documentation of this file.
1 #ifndef HALIDE_RUNTIME_HASHMAP_H
2 #define HALIDE_RUNTIME_HASHMAP_H
3 
4 // the bulk of this hashmap implementation is based on 'cache.cpp'
5 
6 #include "printer.h"
7 #include "scoped_mutex_lock.h"
8 
9 // By default, hashmap_malloc() and hashmap_free() simply wrap around
10 // halide_malloc() and halide_free(), respectively. It is possible to
11 // override the implementation by providing the corresponding #define
12 // prior to including "hashmap.h":
13 //
14 #ifndef hashmap_malloc
15 #define hashmap_malloc(user_context, size) halide_malloc(user_context, size)
16 #endif // hashmap_malloc
17 //
18 #ifndef hashmap_free
19 #define hashmap_free(user_context, memory) halide_free(user_context, memory)
20 #endif // hashmap_free
21 
22 namespace Halide {
23 namespace Runtime {
24 namespace Internal {
25 
26 inline bool keys_equal(const uint8_t *key1, const uint8_t *key2, size_t key_size) {
27  return memcmp(key1, key2, key_size) == 0;
28 }
29 
30 inline uint32_t djb_hash(const uint8_t *key, size_t key_size) {
31  uint32_t h = 5381;
32  for (size_t i = 0; i < key_size; i++) {
33  h = (h << 5) + h + key[i];
34  }
35  return h;
36 }
37 
38 typedef void (*copy_value_func)(uint8_t *dst, const uint8_t *src, size_t size);
39 typedef void (*destroy_value_func)(uint8_t *value, size_t size);
40 
41 struct CacheEntry {
46  size_t key_size;
49  uint32_t in_use_count; // 0 if none returned from halide_cache_lookup
50 
51  // The actual stored data.
52  size_t value_size;
54 
55  bool init(void *user_context,
56  const uint8_t *cache_key, size_t cache_key_size,
57  uint32_t key_hash,
58  const uint8_t *cache_value, size_t cache_value_size,
59  copy_value_func copy_value);
60  void destroy(void *user_context,
61  destroy_value_func destroy_value);
62 };
63 
64 inline bool CacheEntry::init(void *user_context,
65  const uint8_t *cache_key, size_t cache_key_size,
66  uint32_t key_hash,
67  const uint8_t *cache_value, size_t cache_value_size,
68  copy_value_func copy_value) {
69  next = NULL;
70  more_recent = NULL;
71  less_recent = NULL;
72  key_size = cache_key_size;
73  hash = key_hash;
74  in_use_count = 0;
75 
76  // Allocate all the necessary space (or die)
77  size_t storage_bytes = 0;
78 
79  // First storage for value:
80  storage_bytes += cache_value_size;
81 
82  // Enforce some alignment between value and key:
83  const size_t alignment = 8;
84  storage_bytes += (alignment - 1);
85  storage_bytes /= alignment; // positive integer division (floor)
86  storage_bytes *= alignment;
87 
88  // Then storage for the key, starting immediately after the (aligned) value:
89  const size_t key_offset = storage_bytes;
90  storage_bytes += key_size;
91 
92  // Do the single malloc call
94  if (!metadata_storage) {
95  return false;
96  }
97 
98  // Set up the pointers into the allocated metadata space
100  key = metadata_storage + key_offset;
101 
102  // Copy over the key
103  for (size_t i = 0; i < key_size; i++) {
104  key[i] = cache_key[i];
105  }
106 
107  // Copy the value:
108  copy_value(value, cache_value, cache_value_size);
109  value_size = cache_value_size;
110 
111  return true;
112 }
113 
115  destroy_value_func destroy_value) {
116  destroy_value(value, value_size);
118 }
119 
120 struct HashMap {
122 
123  static const size_t kHashTableSize = 256;
124 
126 
129 
133 
136 
138 
139  bool inited;
140 
142  void prune();
143  void set_size(int64_t size);
144  int lookup(void *user_context, const uint8_t *cache_key, int32_t size, uint8_t *cache_value, size_t cache_value_size);
145  int store(void *user_context, const uint8_t *cache_key, int32_t size, const uint8_t *cache_value, size_t cache_value_size);
146  void release(void *user_context, void *host);
147  void cleanup();
148 };
149 
150 inline bool HashMap::init(void *user_context, copy_value_func _copy_value, destroy_value_func _destroy_value) {
151  memset(&memoization_lock, 0, sizeof(halide_mutex));
155  kDefaultCacheSize = 1 << 20;
157  current_cache_size = 0;
158  for (size_t i = 0; i < kHashTableSize; ++i) {
159  cache_entries[i] = NULL;
160  }
161  halide_assert(NULL, _copy_value);
162  halide_assert(NULL, _destroy_value);
163  this->copy_value = _copy_value;
164  this->destroy_value = _destroy_value;
165  inited = true;
166  this->user_context = user_context;
167  return true;
168 }
169 
170 inline void HashMap::prune() {
171 #if CACHE_DEBUGGING
172  validate_cache();
173 #endif
174  CacheEntry *prune_candidate = least_recently_used;
176  prune_candidate != NULL) {
177  CacheEntry *more_recent = prune_candidate->more_recent;
178 
179  if (prune_candidate->in_use_count == 0) {
180  uint32_t h = prune_candidate->hash;
181  uint32_t index = h % kHashTableSize;
182 
183  // Remove from hash table
184  CacheEntry *prev_hash_entry = cache_entries[index];
185  if (prev_hash_entry == prune_candidate) {
186  cache_entries[index] = prune_candidate->next;
187  } else {
188  while (prev_hash_entry != NULL && prev_hash_entry->next != prune_candidate) {
189  prev_hash_entry = prev_hash_entry->next;
190  }
191  halide_assert(NULL, prev_hash_entry != NULL);
192  prev_hash_entry->next = prune_candidate->next;
193  }
194 
195  // Remove from less recent chain.
196  if (least_recently_used == prune_candidate) {
197  least_recently_used = more_recent;
198  }
199  if (more_recent != NULL) {
200  more_recent->less_recent = prune_candidate->less_recent;
201  }
202 
203  // Remove from more recent chain.
204  if (most_recently_used == prune_candidate) {
205  most_recently_used = prune_candidate->less_recent;
206  }
207  if (prune_candidate->less_recent != NULL) {
208  prune_candidate->less_recent = more_recent;
209  }
210 
211  // Decrease cache used amount.
212  current_cache_size -= prune_candidate->value_size;
213 
214  // Deallocate the entry.
215  prune_candidate->destroy(this->user_context, destroy_value);
216  hashmap_free(this->user_context, prune_candidate);
217  }
218 
219  prune_candidate = more_recent;
220  }
221 #if CACHE_DEBUGGING
222  validate_cache();
223 #endif
224 }
225 
226 inline void HashMap::set_size(int64_t size) {
227  if (size == 0) {
228  size = kDefaultCacheSize;
229  }
230 
232 
233  max_cache_size = size;
234  prune();
235 }
236 
237 inline int HashMap::lookup(void *user_context,
238  const uint8_t *cache_key, int32_t size,
239  uint8_t *cache_value, size_t cache_value_size) {
240  uint32_t h = djb_hash(cache_key, size);
241  uint32_t index = h % kHashTableSize;
242 
244 
245 #if CACHE_DEBUGGING
246  debug_print_key(user_context, "halide_memoization_cache_lookup", cache_key, size);
247 
248  debug_print_buffer(user_context, "computed_bounds", *computed_bounds);
249 
250  {
251  for (int32_t i = 0; i < tuple_count; i++) {
252  halide_buffer_t *buf = tuple_buffers[i];
253  debug_print_buffer(user_context, "Allocation bounds", *buf);
254  }
255  }
256 #endif
257 
258  CacheEntry *entry = cache_entries[index];
259  while (entry != NULL) {
260  if (entry->hash == h && entry->key_size == (size_t)size &&
261  keys_equal(entry->key, cache_key, size)) {
262 
263  if (entry != most_recently_used) {
265  if (entry->less_recent != NULL) {
266  entry->less_recent->more_recent = entry->more_recent;
267  } else {
270  }
272  entry->more_recent->less_recent = entry->less_recent;
273 
274  entry->more_recent = NULL;
276  if (most_recently_used != NULL) {
278  }
279  most_recently_used = entry;
280  }
281 
282  halide_assert(user_context, (cache_value_size == entry->value_size));
283  copy_value(cache_value, entry->value, entry->value_size);
284 
285  entry->in_use_count += 1;
286 
287  return 0;
288  }
289  entry = entry->next;
290  }
291 
292 #if CACHE_DEBUGGING
293  validate_cache();
294 #endif
295 
296  return 1;
297 }
298 
299 inline int HashMap::store(void *user_context,
300  const uint8_t *cache_key, int32_t size,
301  const uint8_t *cache_value, size_t cache_value_size) {
302  debug(user_context) << "halide_memoization_cache_store\n";
303 
304  uint32_t h = djb_hash(cache_key, size);
305  uint32_t index = h % kHashTableSize;
306 
308 
309 #if CACHE_DEBUGGING
310  debug_print_key(user_context, "halide_memoization_cache_store", cache_key, size);
311 
312  debug_print_buffer(user_context, "computed_bounds", *computed_bounds);
313 
314  {
315  for (int32_t i = 0; i < tuple_count; i++) {
316  halide_buffer_t *buf = tuple_buffers[i];
317  debug_print_buffer(user_context, "Allocation bounds", *buf);
318  }
319  }
320 #endif
321 
322  // key is already present in the hashmap: overwrite value
323  for (CacheEntry *entry = cache_entries[index];
324  entry != NULL;
325  entry = entry->next) {
326  if (entry->hash == h && entry->key_size == (size_t)size &&
327  keys_equal(entry->key, cache_key, size)) {
328  halide_assert(user_context, (cache_value_size == entry->value_size));
329  destroy_value(entry->value, entry->value_size);
330  copy_value(entry->value, cache_value, entry->value_size);
331  return (0);
332  }
333  }
334 
335  // key not found: create new entry
336  CacheEntry *new_entry = (CacheEntry *)hashmap_malloc(user_context, sizeof(CacheEntry));
337  bool inited = new_entry->init(user_context, cache_key, size, h, cache_value, cache_value_size, copy_value);
339 
340  uint64_t added_size = cache_value_size;
341  current_cache_size += added_size;
342  prune();
343 
344  new_entry->next = cache_entries[index];
345  new_entry->less_recent = most_recently_used;
346  if (most_recently_used != NULL) {
347  most_recently_used->more_recent = new_entry;
348  }
349  most_recently_used = new_entry;
350  if (least_recently_used == NULL) {
351  least_recently_used = new_entry;
352  }
353  cache_entries[index] = new_entry;
354 
355  new_entry->in_use_count = 1;
356 
357 #if CACHE_DEBUGGING
358  validate_cache();
359 #endif
360  debug(user_context) << "Exiting halide_memoization_cache_store\n";
361 
362  return 0;
363 }
364 
365 inline void HashMap::release(void *user_context, void *host) {
366  debug(user_context) << "halide_memoization_cache_release\n";
367  // TODO(marcos): this method does not make sense on a generic hashmap... remove it?
368  halide_assert(user_context, false);
369  debug(user_context) << "Exited halide_memoization_cache_release.\n";
370 }
371 
372 inline void HashMap::cleanup() {
373  debug(NULL) << "halide_memoization_cache_cleanup\n";
374  for (size_t i = 0; i < kHashTableSize; i++) {
375  CacheEntry *entry = cache_entries[i];
376  cache_entries[i] = NULL;
377  while (entry != NULL) {
378  CacheEntry *next = entry->next;
379  entry->destroy(this->user_context, destroy_value);
380  hashmap_free(this->user_context, entry);
381  entry = next;
382  }
383  }
384  current_cache_size = 0;
387 }
388 
389 // THashMap: a convenience class for using HashMap with actual types
390 template<typename KeyType, typename ValueType>
391 struct THashMap : public HashMap {
392 
393  // TODO(marcos): perhaps use KeyType for something useful...
394  // with some generalized interface for keys, we should be able to get rid of
395  // "const uint8_t *cache_key, int32_t key_size" in the 'lookup' and 'store'
396  // member functions below...
397 
398  static void copy_value_func(uint8_t *dst, const uint8_t *src, size_t size) {
399  halide_assert(NULL, sizeof(ValueType) == size);
400  ValueType *D = reinterpret_cast<ValueType *>(dst);
401  const ValueType *S = reinterpret_cast<const ValueType *>(src);
402  *D = *S;
403  }
404 
405  static void destroy_value_func(uint8_t *value, size_t size) {
406  halide_assert(NULL, sizeof(ValueType) == size);
407  ValueType *V = reinterpret_cast<ValueType *>(value);
408  V->~ValueType();
409  }
410 
411  bool init(void *user_context) {
413  }
414 
415  int lookup(void *user_context, const uint8_t *cache_key, int32_t key_size, ValueType *cache_value) {
416  return HashMap::lookup(user_context, cache_key, key_size, (uint8_t *)cache_value, sizeof(ValueType));
417  }
418 
419  int store(void *user_context, const uint8_t *cache_key, int32_t key_size, const ValueType *cache_value) {
420  return HashMap::store(user_context, cache_key, key_size, (const uint8_t *)cache_value, sizeof(ValueType));
421  }
422 };
423 
424 } // namespace Internal
425 } // namespace Runtime
426 } // namespace Halide
427 
428 #endif //HALIDE_RUNTIME_HASHMAP_H
int32_t
signed __INT32_TYPE__ int32_t
Definition: runtime_internal.h:20
Halide::Runtime::Internal::CacheEntry::destroy
void destroy(void *user_context, destroy_value_func destroy_value)
Definition: hashmap.h:114
hashmap_malloc
#define hashmap_malloc(user_context, size)
Definition: hashmap.h:15
NULL
#define NULL
Definition: runtime_internal.h:32
Halide::Runtime::Internal::djb_hash
uint32_t djb_hash(const uint8_t *key, size_t key_size)
Definition: hashmap.h:30
uint8_t
unsigned __INT8_TYPE__ uint8_t
Definition: runtime_internal.h:25
Halide::Runtime::Internal::CacheEntry::more_recent
CacheEntry * more_recent
Definition: hashmap.h:43
Halide::Runtime::Internal::CacheEntry::next
CacheEntry * next
Definition: hashmap.h:42
Halide::Runtime::Internal::CacheEntry::key_size
size_t key_size
Definition: hashmap.h:46
Halide::Runtime::Internal::THashMap::store
int store(void *user_context, const uint8_t *cache_key, int32_t key_size, const ValueType *cache_value)
Definition: hashmap.h:419
Halide::Runtime::Internal::HashMap::user_context
void * user_context
Definition: hashmap.h:137
memcmp
int memcmp(const void *s1, const void *s2, size_t n)
Halide::Runtime::Internal::CacheEntry
Definition: hashmap.h:41
Halide::Runtime::Internal::THashMap::destroy_value_func
static void destroy_value_func(uint8_t *value, size_t size)
Definition: hashmap.h:405
Halide::Runtime::Internal::HashMap::max_cache_size
int64_t max_cache_size
Definition: hashmap.h:131
Halide::Runtime::Internal::HashMap::kHashTableSize
static const size_t kHashTableSize
Definition: hashmap.h:123
Halide::Runtime::Internal::THashMap::copy_value_func
static void copy_value_func(uint8_t *dst, const uint8_t *src, size_t size)
Definition: hashmap.h:398
Halide::Runtime::Internal::CacheEntry::init
bool init(void *user_context, const uint8_t *cache_key, size_t cache_key_size, uint32_t key_hash, const uint8_t *cache_value, size_t cache_value_size, copy_value_func copy_value)
Definition: hashmap.h:64
Halide::Runtime::Internal::HashMap::release
void release(void *user_context, void *host)
Definition: hashmap.h:365
scoped_mutex_lock.h
uint64_t
unsigned __INT64_TYPE__ uint64_t
Definition: runtime_internal.h:19
Halide::Runtime::Internal::HashMap::destroy_value
destroy_value_func destroy_value
Definition: hashmap.h:135
Halide::Runtime::Internal::keys_equal
bool keys_equal(const uint8_t *key1, const uint8_t *key2, size_t key_size)
Definition: hashmap.h:26
Halide::Runtime::Internal::THashMap
Definition: hashmap.h:391
Halide::Runtime::Internal::CacheEntry::key
uint8_t * key
Definition: hashmap.h:47
Halide
This file defines the class FunctionDAG, which is our representation of a Halide pipeline,...
Definition: AddAtomicMutex.h:21
memset
void * memset(void *s, int val, size_t n)
Halide::Runtime::Internal::HashMap::set_size
void set_size(int64_t size)
Definition: hashmap.h:226
halide_assert
#define halide_assert(user_context, cond)
Definition: runtime_internal.h:240
Halide::Runtime::Internal::CacheEntry::value
uint8_t * value
Definition: hashmap.h:53
Halide::Runtime::Internal::HashMap::copy_value
copy_value_func copy_value
Definition: hashmap.h:134
printer.h
Halide::Runtime::Internal::destroy_value_func
void(* destroy_value_func)(uint8_t *value, size_t size)
Definition: hashmap.h:39
Halide::Runtime::Internal::HashMap::most_recently_used
CacheEntry * most_recently_used
Definition: hashmap.h:127
hashmap_free
#define hashmap_free(user_context, memory)
Definition: hashmap.h:19
Halide::Runtime::Internal::CacheEntry::in_use_count
uint32_t in_use_count
Definition: hashmap.h:49
Halide::Runtime::Internal::HashMap
Definition: hashmap.h:120
int64_t
signed __INT64_TYPE__ int64_t
Definition: runtime_internal.h:18
Halide::Runtime::Internal::HashMap::current_cache_size
int64_t current_cache_size
Definition: hashmap.h:132
Halide::Runtime::Internal::copy_value_func
void(* copy_value_func)(uint8_t *dst, const uint8_t *src, size_t size)
Definition: hashmap.h:38
Halide::Runtime::Internal::HashMap::prune
void prune()
Definition: hashmap.h:170
Halide::Runtime::Internal::HashMap::least_recently_used
CacheEntry * least_recently_used
Definition: hashmap.h:128
Halide::Runtime::Internal::HashMap::kDefaultCacheSize
uint64_t kDefaultCacheSize
Definition: hashmap.h:130
halide_mutex
Cross-platform mutex.
Definition: HalideRuntime.h:114
Halide::Runtime::Internal::CacheEntry::hash
uint32_t hash
Definition: hashmap.h:48
Halide::Runtime::Internal::HashMap::store
int store(void *user_context, const uint8_t *cache_key, int32_t size, const uint8_t *cache_value, size_t cache_value_size)
Definition: hashmap.h:299
Halide::Runtime::Internal::THashMap::lookup
int lookup(void *user_context, const uint8_t *cache_key, int32_t key_size, ValueType *cache_value)
Definition: hashmap.h:415
Halide::Runtime::Internal::CacheEntry::value_size
size_t value_size
Definition: hashmap.h:52
Halide::Runtime::Internal::HashMap::lookup
int lookup(void *user_context, const uint8_t *cache_key, int32_t size, uint8_t *cache_value, size_t cache_value_size)
Definition: hashmap.h:237
Halide::Runtime::Internal::THashMap::init
bool init(void *user_context)
Definition: hashmap.h:411
dst
char * dst
Definition: printer.h:32
Halide::Runtime::Internal::HashMap::inited
bool inited
Definition: hashmap.h:139
halide_buffer_t
The raw representation of an image passed around by generated Halide code.
Definition: HalideRuntime.h:1404
Halide::Runtime::Internal::CacheEntry::less_recent
CacheEntry * less_recent
Definition: hashmap.h:44
buf
char * buf
Definition: printer.h:32
Halide::Runtime::Internal::CacheEntry::metadata_storage
uint8_t * metadata_storage
Definition: hashmap.h:45
uint32_t
unsigned __INT32_TYPE__ uint32_t
Definition: runtime_internal.h:21
Halide::Runtime::Internal::HashMap::init
bool init(void *user_context, copy_value_func copy_value, destroy_value_func destroy_value)
Definition: hashmap.h:150
user_context
void * user_context
Definition: printer.h:33
Halide::Runtime::Internal::ScopedMutexLock
Definition: scoped_mutex_lock.h:11
Halide::Runtime::Internal::HashMap::cleanup
void cleanup()
Definition: hashmap.h:372
Halide::Runtime::Internal::HashMap::cache_entries
CacheEntry * cache_entries[kHashTableSize]
Definition: hashmap.h:125
Halide::Runtime::Internal::HashMap::memoization_lock
halide_mutex memoization_lock
Definition: hashmap.h:121