Halide 22.0.0 Halide compiler and libraries

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 {
42 CacheEntry *next;
43 CacheEntry *more_recent;
44 CacheEntry *less_recent;
45 uint8_t *metadata_storage;
46 size_t key_size;
47 uint8_t *key;
48 uint32_t hash;
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;
53 uint8_t *value;
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 = nullptr;
70 more_recent = nullptr;
71 less_recent = nullptr;
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
93 metadata_storage = (uint8_t *)hashmap_malloc(user_context, storage_bytes);
94 if (!metadata_storage) {
95 return false;
96 }
97
98 // Set up the pointers into the allocated metadata space
99 value = metadata_storage;
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
114 inline void CacheEntry::destroy(void *user_context,
115 destroy_value_func destroy_value) {
116 destroy_value(value, value_size);
117 hashmap_free(user_context, metadata_storage);
118}
119
120 struct HashMap {
121 halide_mutex memoization_lock;
122
123 static const size_t kHashTableSize = 256;
124
125 CacheEntry *cache_entries[kHashTableSize];
126
127 CacheEntry *most_recently_used;
128 CacheEntry *least_recently_used;
129
130 uint64_t kDefaultCacheSize;
131 int64_t max_cache_size;
132 int64_t current_cache_size;
133
134 copy_value_func copy_value;
135 destroy_value_func destroy_value;
136
137 void *user_context;
138
139 bool inited;
140
141 bool init(void *user_context, copy_value_func copy_value, destroy_value_func destroy_value);
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 void 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));
152 halide_debug_assert(nullptr, !inited);
153 most_recently_used = nullptr;
154 least_recently_used = nullptr;
155 kDefaultCacheSize = 1 << 20;
156 max_cache_size = kDefaultCacheSize;
157 current_cache_size = 0;
158 for (auto &cache_entry_ref : cache_entries) {
159 cache_entry_ref = nullptr;
160 }
161 halide_debug_assert(nullptr, _copy_value);
162 halide_debug_assert(nullptr, _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;
175 while (current_cache_size > max_cache_size &&
176 prune_candidate != nullptr) {
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 != nullptr && prev_hash_entry->next != prune_candidate) {
189 prev_hash_entry = prev_hash_entry->next;
190 }
191 halide_debug_assert(nullptr, prev_hash_entry != nullptr);
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 != nullptr) {
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 != nullptr) {
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
231 ScopedMutexLock lock(&memoization_lock);
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
243 ScopedMutexLock lock(&memoization_lock);
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 != nullptr) {
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) {
264 halide_debug_assert(user_context, entry->more_recent != nullptr);
265 if (entry->less_recent != nullptr) {
266 entry->less_recent->more_recent = entry->more_recent;
267 } else {
268 halide_debug_assert(user_context, least_recently_used == entry);
269 least_recently_used = entry->more_recent;
270 }
271 halide_debug_assert(user_context, entry->more_recent != nullptr);
272 entry->more_recent->less_recent = entry->less_recent;
273
274 entry->more_recent = nullptr;
275 entry->less_recent = most_recently_used;
276 if (most_recently_used != nullptr) {
277 most_recently_used->more_recent = entry;
278 }
279 most_recently_used = entry;
280 }
281
282 halide_debug_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 void 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
307 ScopedMutexLock lock(&memoization_lock);
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 != nullptr;
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_debug_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;
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);
338 halide_debug_assert(user_context, inited);
339 (void)inited;
340
341 uint64_t added_size = cache_value_size;
342 current_cache_size += added_size;
343 prune();
344
345 new_entry->next = cache_entries[index];
346 new_entry->less_recent = most_recently_used;
347 if (most_recently_used != nullptr) {
348 most_recently_used->more_recent = new_entry;
349 }
350 most_recently_used = new_entry;
351 if (least_recently_used == nullptr) {
352 least_recently_used = new_entry;
353 }
354 cache_entries[index] = new_entry;
355
356 new_entry->in_use_count = 1;
357
358#if CACHE_DEBUGGING
359 validate_cache();
360#endif
361 debug(user_context) << "Exiting halide_memoization_cache_store\n";
362}
363
364 inline void HashMap::release(void *user_context, void *host) {
365 debug(user_context) << "halide_memoization_cache_release\n";
366 // TODO(marcos): this method does not make sense on a generic hashmap... remove it?
367 halide_debug_assert(user_context, false);
368 debug(user_context) << "Exited halide_memoization_cache_release.\n";
369}
370
371 inline void HashMap::cleanup() {
372 debug(nullptr) << "halide_memoization_cache_cleanup\n";
373 for (auto &cache_entry_ref : cache_entries) {
374 CacheEntry *entry = cache_entry_ref;
375 cache_entry_ref = nullptr;
376 while (entry != nullptr) {
377 CacheEntry *next = entry->next;
378 entry->destroy(this->user_context, destroy_value);
379 hashmap_free(this->user_context, entry);
380 entry = next;
381 }
382 }
383 current_cache_size = 0;
384 most_recently_used = nullptr;
385 least_recently_used = nullptr;
386}
387
388// THashMap: a convenience class for using HashMap with actual types
389 template<typename KeyType, typename ValueType>
390 struct THashMap : public HashMap {
391
392 // TODO(marcos): perhaps use KeyType for something useful...
393 // with some generalized interface for keys, we should be able to get rid of
394 // "const uint8_t *cache_key, int32_t key_size" in the 'lookup' and 'store'
395 // member functions below...
396
397 static void copy_value_func(uint8_t *dst, const uint8_t *src, size_t size) {
398 halide_debug_assert(nullptr, sizeof(ValueType) == size);
399 ValueType *D = reinterpret_cast<ValueType *>(dst);
400 const ValueType *S = reinterpret_cast<const ValueType *>(src);
401 *D = *S;
402 }
403
404 static void destroy_value_func(uint8_t *value, size_t size) {
405 halide_debug_assert(nullptr, sizeof(ValueType) == size);
406 ValueType *V = reinterpret_cast<ValueType *>(value);
407 V->~ValueType();
408 }
409
410 bool init(void *user_context) {
411 return HashMap::init(user_context, copy_value_func, destroy_value_func);
412 }
413
414 int lookup(void *user_context, const uint8_t *cache_key, int32_t key_size, ValueType *cache_value) {
415 return HashMap::lookup(user_context, cache_key, key_size, (uint8_t *)cache_value, sizeof(ValueType));
416 }
417
418 void store(void *user_context, const uint8_t *cache_key, int32_t key_size, const ValueType *cache_value) {
419 HashMap::store(user_context, cache_key, key_size, (const uint8_t *)cache_value, sizeof(ValueType));
420 }
421};
422
423} // namespace Internal
424} // namespace Runtime
425} // namespace Halide
426
427#endif // HALIDE_RUNTIME_HASHMAP_H
debug
#define debug(n)
For optional debugging during codegen, use the debug macro as follows:
Definition: Debug.h:52
hashmap_malloc
#define hashmap_malloc(user_context, size)
Definition: hashmap.h:15
hashmap_free
#define hashmap_free(user_context, memory)
Definition: hashmap.h:19
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::copy_value_func
void(* copy_value_func)(uint8_t *dst, const uint8_t *src, size_t size)
Definition: hashmap.h:38
Halide::Runtime::Internal::djb_hash
uint32_t djb_hash(const uint8_t *key, size_t key_size)
Definition: hashmap.h:30
Halide::Runtime::Internal::destroy_value_func
void(* destroy_value_func)(uint8_t *value, size_t size)
Definition: hashmap.h:39
Halide
This file defines the class FunctionDAG, which is our representation of a Halide pipeline,...
Definition: AbstractGenerator.h:19
printer.h
uint64_t
unsigned __INT64_TYPE__ uint64_t
Definition: runtime_internal.h:23
int64_t
signed __INT64_TYPE__ int64_t
Definition: runtime_internal.h:22
halide_debug_assert
#define halide_debug_assert(user_context, cond)
halide_debug_assert() is like halide_assert(), but only expands into a check when DEBUG_RUNTIME is de...
Definition: runtime_internal.h:290
int32_t
signed __INT32_TYPE__ int32_t
Definition: runtime_internal.h:24
uint8_t
unsigned __INT8_TYPE__ uint8_t
Definition: runtime_internal.h:29
memcmp
int memcmp(const void *s1, const void *s2, size_t n)
memset
void * memset(void *s, int val, size_t n)
uint32_t
unsigned __INT32_TYPE__ uint32_t
Definition: runtime_internal.h:25
scoped_mutex_lock.h
Halide::Runtime::Internal::CacheEntry
Definition: hashmap.h:41
Halide::Runtime::Internal::CacheEntry::value
uint8_t * value
Definition: hashmap.h:53
Halide::Runtime::Internal::CacheEntry::key_size
size_t key_size
Definition: hashmap.h:46
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::CacheEntry::metadata_storage
uint8_t * metadata_storage
Definition: hashmap.h:45
Halide::Runtime::Internal::CacheEntry::destroy
void destroy(void *user_context, destroy_value_func destroy_value)
Definition: hashmap.h:114
Halide::Runtime::Internal::CacheEntry::less_recent
CacheEntry * less_recent
Definition: hashmap.h:44
Halide::Runtime::Internal::CacheEntry::key
uint8_t * key
Definition: hashmap.h:47
Halide::Runtime::Internal::CacheEntry::hash
uint32_t hash
Definition: hashmap.h:48
Halide::Runtime::Internal::CacheEntry::in_use_count
uint32_t in_use_count
Definition: hashmap.h:49
Halide::Runtime::Internal::CacheEntry::value_size
size_t value_size
Definition: hashmap.h:52
Halide::Runtime::Internal::CacheEntry::next
CacheEntry * next
Definition: hashmap.h:42
Halide::Runtime::Internal::CacheEntry::more_recent
CacheEntry * more_recent
Definition: hashmap.h:43
Halide::Runtime::Internal::HashMap
Definition: hashmap.h:120
Halide::Runtime::Internal::HashMap::set_size
void set_size(int64_t size)
Definition: hashmap.h:226
Halide::Runtime::Internal::HashMap::destroy_value
destroy_value_func destroy_value
Definition: hashmap.h:135
Halide::Runtime::Internal::HashMap::cache_entries
CacheEntry * cache_entries[kHashTableSize]
Definition: hashmap.h:125
Halide::Runtime::Internal::HashMap::user_context
void * user_context
Definition: hashmap.h:137
Halide::Runtime::Internal::HashMap::memoization_lock
halide_mutex memoization_lock
Definition: hashmap.h:121
Halide::Runtime::Internal::HashMap::max_cache_size
int64_t max_cache_size
Definition: hashmap.h:131
Halide::Runtime::Internal::HashMap::most_recently_used
CacheEntry * most_recently_used
Definition: hashmap.h:127
Halide::Runtime::Internal::HashMap::least_recently_used
CacheEntry * least_recently_used
Definition: hashmap.h:128
Halide::Runtime::Internal::HashMap::cleanup
void cleanup()
Definition: hashmap.h:371
Halide::Runtime::Internal::HashMap::release
void release(void *user_context, void *host)
Definition: hashmap.h:364
Halide::Runtime::Internal::HashMap::current_cache_size
int64_t current_cache_size
Definition: hashmap.h:132
Halide::Runtime::Internal::HashMap::inited
bool inited
Definition: hashmap.h:139
Halide::Runtime::Internal::HashMap::init
bool init(void *user_context, copy_value_func copy_value, destroy_value_func destroy_value)
Definition: hashmap.h:150
Halide::Runtime::Internal::HashMap::copy_value
copy_value_func copy_value
Definition: hashmap.h:134
Halide::Runtime::Internal::HashMap::kHashTableSize
static const size_t kHashTableSize
Definition: hashmap.h:123
Halide::Runtime::Internal::HashMap::prune
void prune()
Definition: hashmap.h:170
Halide::Runtime::Internal::HashMap::kDefaultCacheSize
uint64_t kDefaultCacheSize
Definition: hashmap.h:130
Halide::Runtime::Internal::HashMap::store
void 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::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::ScopedMutexLock
Definition: scoped_mutex_lock.h:11
Halide::Runtime::Internal::THashMap
Definition: hashmap.h:390
Halide::Runtime::Internal::THashMap::destroy_value_func
static void destroy_value_func(uint8_t *value, size_t size)
Definition: hashmap.h:404
Halide::Runtime::Internal::THashMap::init
bool init(void *user_context)
Definition: hashmap.h:410
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:397
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:414
Halide::Runtime::Internal::THashMap::store
void store(void *user_context, const uint8_t *cache_key, int32_t key_size, const ValueType *cache_value)
Definition: hashmap.h:418
halide_buffer_t
The raw representation of an image passed around by generated Halide code.
Definition: HalideRuntime.h:1569
halide_mutex
Cross-platform mutex.
Definition: HalideRuntime.h:191
user_context
void * user_context
Definition: vulkan_resources.h:178