Halide 22.0.0 Halide compiler and libraries

block_storage.h
Go to the documentation of this file.
1#ifndef HALIDE_RUNTIME_BLOCK_STORAGE_H
2#define HALIDE_RUNTIME_BLOCK_STORAGE_H
3
4#include "../HalideRuntime.h"
5#include "../printer.h"
6#include "memory_resources.h"
7
8namespace Halide {
9namespace Runtime {
10namespace Internal {
11
12// Dynamically resizable array for block storage (eg plain old data)
13// -- No usage of constructors/destructors for value type
14// -- Assumes all elements stored are uniformly the same fixed size
15// -- Allocations are done in blocks of a fixed size
16// -- Implementation uses memcpy/memmove for copying
17// -- Customizable allocator ... default uses NativeSystemAllocator
18 class BlockStorage {
19public:
20 static constexpr size_t default_capacity = 32; // smallish
21
22 // Configurable parameters
23 struct Config {
24 uint32_t entry_size = 1; // bytes per entry
25 uint32_t block_size = 32; // bytes per each allocation block
26 uint32_t minimum_capacity = default_capacity;
27 };
28
29 BlockStorage(void *user_context, const Config &cfg, const SystemMemoryAllocatorFns &sma = default_allocator());
30 BlockStorage(const BlockStorage &other);
31 ~BlockStorage();
32
33 void initialize(void *user_context, const Config &cfg, const SystemMemoryAllocatorFns &sma = default_allocator());
34
35 BlockStorage &operator=(const BlockStorage &other);
36 bool operator==(const BlockStorage &other) const;
37 bool operator!=(const BlockStorage &other) const;
38
39 void reserve(void *user_context, size_t capacity, bool free_existing = false);
40 void resize(void *user_context, size_t entry_count, bool realloc = true);
41
42 void assign(void *user_context, size_t index, const void *entry_ptr);
43 void insert(void *user_context, size_t index, const void *entry_ptr);
44 void prepend(void *user_context, const void *entry_ptr);
45 void append(void *user_context, const void *entry_ptr);
46 void remove(void *user_context, size_t index);
47
48 void fill(void *user_context, const void *array, size_t array_size);
49 void insert(void *user_context, size_t index, const void *array, size_t array_size);
50 void replace(void *user_context, size_t index, const void *array, size_t array_size);
51 void prepend(void *user_context, const void *array, size_t array_size);
52 void append(void *user_context, const void *array, size_t array_size);
53 void remove(void *user_context, size_t index, size_t entry_count);
54
55 void pop_front(void *user_context);
56 void pop_back(void *user_context);
57 void shrink_to_fit(void *user_context);
58 void clear(void *user_context);
59 void destroy(void *user_context);
60
61 bool empty() const;
62 bool full() const;
63 bool is_valid(size_t index) const;
64 size_t stride() const;
65 size_t size() const;
66
67 void *operator[](size_t index); ///< logical entry index (returns ptr = data() + (index * stride())
68 const void *operator[](size_t index) const;
69
70 void *data();
71 void *front();
72 void *back();
73
74 const void *data() const;
75 const void *front() const;
76 const void *back() const;
77
78 const Config &current_config() const;
79 static const Config &default_config();
80
81 const SystemMemoryAllocatorFns &current_allocator() const;
82 static const SystemMemoryAllocatorFns &default_allocator();
83
84private:
85 void allocate(void *user_context, size_t capacity);
86
87 void *ptr = nullptr;
88 size_t count = 0;
89 size_t capacity = 0;
90 Config config;
91 SystemMemoryAllocatorFns allocator;
92};
93
94BlockStorage::BlockStorage(void *user_context, const Config &cfg, const SystemMemoryAllocatorFns &sma)
95 : config(cfg), allocator(sma) {
96 halide_abort_if_false(user_context, config.entry_size != 0);
97 halide_abort_if_false(user_context, allocator.allocate != nullptr);
98 halide_abort_if_false(user_context, allocator.deallocate != nullptr);
99 if (config.minimum_capacity) {
100 reserve(user_context, config.minimum_capacity);
101 }
102}
103
104 BlockStorage::BlockStorage(const BlockStorage &other)
105 : BlockStorage(nullptr, other.config, other.allocator) {
106 if (other.count) {
107 resize(nullptr, other.count);
108 memcpy(this->ptr, other.ptr, count * config.entry_size);
109 }
110}
111
112BlockStorage::~BlockStorage() {
113 destroy(nullptr);
114}
115
116 void BlockStorage::destroy(void *user_context) {
117 halide_abort_if_false(user_context, allocator.deallocate != nullptr);
118 if (ptr != nullptr) {
119 allocator.deallocate(user_context, ptr);
120 }
121 capacity = count = 0;
122 ptr = nullptr;
123}
124
125 void BlockStorage::initialize(void *user_context, const Config &cfg, const SystemMemoryAllocatorFns &sma) {
126 allocator = sma;
127 config = cfg;
128 capacity = count = 0;
129 ptr = nullptr;
130 if (config.minimum_capacity) {
131 reserve(user_context, config.minimum_capacity);
132 }
133}
134
135 BlockStorage &BlockStorage::operator=(const BlockStorage &other) {
136 if (&other != this) {
137 config = other.config;
138 resize(nullptr, other.count);
139 if (count != 0 && other.ptr != nullptr) {
140 memcpy(ptr, other.ptr, count * config.entry_size);
141 }
142 }
143 return *this;
144}
145
146 bool BlockStorage::operator==(const BlockStorage &other) const {
147 if (config.entry_size != other.config.entry_size) {
148 return false;
149 }
150 if (count != other.count) {
151 return false;
152 }
153 return memcmp(this->ptr, other.ptr, this->size() * config.entry_size) == 0;
154}
155
156 bool BlockStorage::operator!=(const BlockStorage &other) const {
157 return !(*this == other);
158}
159
160 void BlockStorage::fill(void *user_context, const void *array, size_t array_size) {
161 if (array_size != 0) {
162 resize(user_context, array_size);
163 memcpy(this->ptr, array, array_size * config.entry_size);
164 count = array_size;
165 }
166}
167
168 void BlockStorage::assign(void *user_context, size_t index, const void *entry_ptr) {
169 replace(user_context, index, entry_ptr, 1);
170}
171
172 void BlockStorage::prepend(void *user_context, const void *entry_ptr) {
173 insert(user_context, 0, entry_ptr, 1);
174}
175
176 void BlockStorage::append(void *user_context, const void *entry_ptr) {
177 append(user_context, entry_ptr, 1);
178}
179
180 void BlockStorage::pop_front(void *user_context) {
181 halide_abort_if_false(user_context, count > 0);
182 remove(user_context, 0);
183}
184
185 void BlockStorage::pop_back(void *user_context) {
186 halide_abort_if_false(user_context, count > 0);
187 resize(user_context, size() - 1);
188}
189
190 void BlockStorage::clear(void *user_context) {
191 resize(user_context, 0);
192}
193
194 void BlockStorage::reserve(void *user_context, size_t new_capacity, bool free_existing) {
195 new_capacity = max(new_capacity, count);
196
197 if ((new_capacity < capacity) && !free_existing) {
198 new_capacity = capacity;
199 }
200
201 allocate(user_context, new_capacity);
202}
203
204 void BlockStorage::resize(void *user_context, size_t entry_count, bool realloc) {
205 size_t current_size = capacity;
206 size_t requested_size = entry_count;
207 size_t minimum_size = config.minimum_capacity;
208 size_t actual_size = current_size;
209 count = requested_size;
210
211 // increase capacity upto 1.5x existing (or at least min_capacity)
212 if (requested_size > current_size) {
213 actual_size = max(requested_size, max(current_size * 3 / 2, minimum_size));
214 } else if (!realloc) {
215 return;
216 }
217
218#ifdef DEBUG_RUNTIME_INTERNAL
219 debug(user_context) << "BlockStorage: Resize ("
220 << "requested_size=" << (int32_t)requested_size << " "
221 << "current_size=" << (int32_t)current_size << " "
222 << "minimum_size=" << (int32_t)minimum_size << " "
223 << "actual_size=" << (int32_t)actual_size << " "
224 << "entry_size=" << (int32_t)config.entry_size << " "
225 << "realloc=" << (realloc ? "true" : "false") << ")...\n";
226#endif
227
228 allocate(user_context, actual_size);
229}
230
231 void BlockStorage::shrink_to_fit(void *user_context) {
232 if (capacity > count) {
233 void *new_ptr = nullptr;
234 if (count > 0) {
235 size_t actual_bytes = count * config.entry_size;
236 new_ptr = allocator.allocate(user_context, actual_bytes);
237 memcpy(new_ptr, ptr, actual_bytes);
238 }
239 allocator.deallocate(user_context, ptr);
240 capacity = count;
241 ptr = new_ptr;
242 }
243}
244
245 void BlockStorage::insert(void *user_context, size_t index, const void *entry_ptr) {
246 insert(user_context, index, entry_ptr, 1);
247}
248
249 void BlockStorage::remove(void *user_context, size_t index) {
250 remove(user_context, index, 1);
251}
252
253 void BlockStorage::remove(void *user_context, size_t index, size_t entry_count) {
254 halide_abort_if_false(user_context, index < count);
255 const size_t last_index = size();
256 if (index < (last_index - entry_count)) {
257 size_t dst_offset = index * config.entry_size;
258 size_t src_offset = (index + entry_count) * config.entry_size;
259 size_t bytes = (last_index - index - entry_count) * config.entry_size;
260
261#ifdef DEBUG_RUNTIME_INTERNAL
262 debug(user_context) << "BlockStorage: Remove ("
263 << "index=" << (int32_t)index << " "
264 << "entry_count=" << (int32_t)entry_count << " "
265 << "entry_size=" << (int32_t)config.entry_size << " "
266 << "last_index=" << (int32_t)last_index << " "
267 << "src_offset=" << (int32_t)src_offset << " "
268 << "dst_offset=" << (int32_t)dst_offset << " "
269 << "bytes=" << (int32_t)bytes << ")...\n";
270#endif
271 void *dst_ptr = offset_address(ptr, dst_offset);
272 void *src_ptr = offset_address(ptr, src_offset);
273 memmove(dst_ptr, src_ptr, bytes);
274 }
275 resize(user_context, last_index - entry_count);
276}
277
278 void BlockStorage::replace(void *user_context, size_t index, const void *array, size_t array_size) {
279 halide_abort_if_false(user_context, index < count);
280 size_t offset = index * config.entry_size;
281 size_t remaining = count - index;
282
283#if DEBUG
284 debug(user_context) << "BlockStorage: Replace ("
285 << "index=" << (int32_t)index << " "
286 << "array_size=" << (int32_t)array_size << " "
287 << "entry_size=" << (int32_t)config.entry_size << " "
288 << "offset=" << (int32_t)offset << " "
289 << "remaining=" << (int32_t)remaining << " "
290 << "capacity=" << (int32_t)capacity << ")...\n";
291#endif
292
293 halide_abort_if_false(user_context, remaining > 0);
294 size_t copy_count = min(remaining, array_size);
295 void *dst_ptr = offset_address(ptr, offset);
296 memcpy(dst_ptr, array, copy_count * config.entry_size);
297 count = max(count, index + copy_count);
298}
299
300 void BlockStorage::insert(void *user_context, size_t index, const void *array, size_t array_size) {
301 halide_abort_if_false(user_context, index <= count);
302 const size_t last_index = size();
303 resize(user_context, last_index + array_size);
304 if (index < last_index) {
305 size_t src_offset = index * config.entry_size;
306 size_t dst_offset = (index + array_size) * config.entry_size;
307 size_t bytes = (last_index - index) * config.entry_size;
308 void *src_ptr = offset_address(ptr, src_offset);
309 void *dst_ptr = offset_address(ptr, dst_offset);
310 memmove(dst_ptr, src_ptr, bytes);
311 }
312 replace(user_context, index, array, array_size);
313}
314
315 void BlockStorage::prepend(void *user_context, const void *array, size_t array_size) {
316 insert(user_context, 0, array, array_size);
317}
318
319 void BlockStorage::append(void *user_context, const void *array, size_t array_size) {
320 const size_t last_index = size();
321 insert(user_context, last_index, array, array_size);
322}
323
324 bool BlockStorage::empty() const {
325 return count == 0;
326}
327
328 bool BlockStorage::full() const {
329 return (count >= capacity);
330}
331
332 bool BlockStorage::is_valid(size_t index) const {
333 return (index < capacity);
334}
335
336 size_t BlockStorage::size() const {
337 return count;
338}
339
340 size_t BlockStorage::stride() const {
341 return config.entry_size;
342}
343
344 void *BlockStorage::operator[](size_t index) {
345 halide_abort_if_false(nullptr, index < capacity);
346 return offset_address(ptr, index * config.entry_size);
347}
348
349 const void *BlockStorage::operator[](size_t index) const {
350 halide_abort_if_false(nullptr, index < capacity);
351 return offset_address(ptr, index * config.entry_size);
352}
353
354 void *BlockStorage::data() {
355 return ptr;
356}
357
358 void *BlockStorage::front() {
359 halide_abort_if_false(nullptr, count > 0);
360 return ptr;
361}
362
363 void *BlockStorage::back() {
364 halide_abort_if_false(nullptr, count > 0);
365 size_t index = count - 1;
366 return offset_address(ptr, index * config.entry_size);
367}
368
369 const void *BlockStorage::data() const {
370 return ptr;
371}
372
373 const void *BlockStorage::front() const {
374 halide_abort_if_false(nullptr, count > 0);
375 return ptr;
376}
377
378 const void *BlockStorage::back() const {
379 halide_abort_if_false(nullptr, count > 0);
380 size_t index = count - 1;
381 return offset_address(ptr, index * config.entry_size);
382}
383
384void BlockStorage::allocate(void *user_context, size_t new_capacity) {
385 if (new_capacity != capacity) {
386 halide_abort_if_false(user_context, allocator.allocate != nullptr);
387 size_t requested_bytes = new_capacity * config.entry_size;
388 size_t block_size = max(config.block_size, config.entry_size);
389 size_t block_count = (requested_bytes / block_size);
390 block_count += (requested_bytes % block_size) ? 1 : 0;
391 size_t alloc_size = block_count * block_size;
392#ifdef DEBUG_RUNTIME_INTERNAL
393 debug(user_context) << "BlockStorage: Allocating ("
394 << "requested_bytes=" << (int32_t)requested_bytes << " "
395 << "block_size=" << (int32_t)block_size << " "
396 << "block_count=" << (int32_t)block_count << " "
397 << "alloc_size=" << (int32_t)alloc_size << ") ...\n";
398#endif
399 void *new_ptr = alloc_size ? allocator.allocate(user_context, alloc_size) : nullptr;
400 if (count != 0 && ptr != nullptr && new_ptr != nullptr) {
401 memcpy(new_ptr, ptr, count * config.entry_size);
402 }
403 if (ptr != nullptr) {
404 halide_abort_if_false(user_context, allocator.deallocate != nullptr);
405 allocator.deallocate(user_context, ptr);
406 }
407 capacity = new_capacity;
408 ptr = new_ptr;
409 }
410}
411
412const SystemMemoryAllocatorFns &
413BlockStorage::current_allocator() const {
414 return this->allocator;
415}
416
417const BlockStorage::Config &
418BlockStorage::default_config() {
419 static Config default_cfg;
420 return default_cfg;
421}
422
423const BlockStorage::Config &
424BlockStorage::current_config() const {
425 return this->config;
426}
427
428const SystemMemoryAllocatorFns &
429BlockStorage::default_allocator() {
430 static SystemMemoryAllocatorFns native_allocator = {
431 native_system_malloc, native_system_free};
432 return native_allocator;
433}
434
435// --
436
437} // namespace Internal
438} // namespace Runtime
439} // namespace Halide
440
441#endif // HALIDE_RUNTIME_BLOCK_STORAGE_H
debug
#define debug(n)
For optional debugging during codegen, use the debug macro as follows:
Definition: Debug.h:52
Halide::Runtime::Internal::BlockStorage
Definition: block_storage.h:18
Halide::Runtime::Internal::BlockStorage::stride
size_t stride() const
Definition: block_storage.h:340
Halide::Runtime::Internal::BlockStorage::current_config
const Config & current_config() const
Definition: block_storage.h:424
Halide::Runtime::Internal::BlockStorage::operator=
BlockStorage & operator=(const BlockStorage &other)
Definition: block_storage.h:135
Halide::Runtime::Internal::BlockStorage::operator[]
void * operator[](size_t index)
logical entry index (returns ptr = data() + (index * stride())
Definition: block_storage.h:344
Halide::Runtime::Internal::BlockStorage::front
void * front()
Definition: block_storage.h:358
Halide::Runtime::Internal::BlockStorage::full
bool full() const
Definition: block_storage.h:328
Halide::Runtime::Internal::BlockStorage::shrink_to_fit
void shrink_to_fit(void *user_context)
Definition: block_storage.h:231
Halide::Runtime::Internal::BlockStorage::pop_front
void pop_front(void *user_context)
Definition: block_storage.h:180
Halide::Runtime::Internal::BlockStorage::destroy
void destroy(void *user_context)
Definition: block_storage.h:116
Halide::Runtime::Internal::BlockStorage::size
size_t size() const
Definition: block_storage.h:336
Halide::Runtime::Internal::BlockStorage::back
void * back()
Definition: block_storage.h:363
Halide::Runtime::Internal::BlockStorage::clear
void clear(void *user_context)
Definition: block_storage.h:190
Halide::Runtime::Internal::BlockStorage::default_capacity
static constexpr size_t default_capacity
Definition: block_storage.h:20
Halide::Runtime::Internal::BlockStorage::operator!=
bool operator!=(const BlockStorage &other) const
Definition: block_storage.h:156
Halide::Runtime::Internal::BlockStorage::resize
void resize(void *user_context, size_t entry_count, bool realloc=true)
Definition: block_storage.h:204
Halide::Runtime::Internal::BlockStorage::default_config
static const Config & default_config()
Definition: block_storage.h:418
Halide::Runtime::Internal::BlockStorage::replace
void replace(void *user_context, size_t index, const void *array, size_t array_size)
Definition: block_storage.h:278
Halide::Runtime::Internal::BlockStorage::prepend
void prepend(void *user_context, const void *entry_ptr)
Definition: block_storage.h:172
Halide::Runtime::Internal::BlockStorage::remove
void remove(void *user_context, size_t index)
Definition: block_storage.h:249
Halide::Runtime::Internal::BlockStorage::assign
void assign(void *user_context, size_t index, const void *entry_ptr)
Definition: block_storage.h:168
Halide::Runtime::Internal::BlockStorage::data
void * data()
Definition: block_storage.h:354
Halide::Runtime::Internal::BlockStorage::insert
void insert(void *user_context, size_t index, const void *entry_ptr)
Definition: block_storage.h:245
Halide::Runtime::Internal::BlockStorage::initialize
void initialize(void *user_context, const Config &cfg, const SystemMemoryAllocatorFns &sma=default_allocator())
Definition: block_storage.h:125
Halide::Runtime::Internal::BlockStorage::default_allocator
static const SystemMemoryAllocatorFns & default_allocator()
Definition: block_storage.h:429
Halide::Runtime::Internal::BlockStorage::empty
bool empty() const
Definition: block_storage.h:324
Halide::Runtime::Internal::BlockStorage::current_allocator
const SystemMemoryAllocatorFns & current_allocator() const
Definition: block_storage.h:413
Halide::Runtime::Internal::BlockStorage::operator==
bool operator==(const BlockStorage &other) const
Definition: block_storage.h:146
Halide::Runtime::Internal::BlockStorage::~BlockStorage
~BlockStorage()
Definition: block_storage.h:112
Halide::Runtime::Internal::BlockStorage::append
void append(void *user_context, const void *entry_ptr)
Definition: block_storage.h:176
Halide::Runtime::Internal::BlockStorage::BlockStorage
BlockStorage(void *user_context, const Config &cfg, const SystemMemoryAllocatorFns &sma=default_allocator())
Definition: block_storage.h:94
Halide::Runtime::Internal::BlockStorage::is_valid
bool is_valid(size_t index) const
Definition: block_storage.h:332
Halide::Runtime::Internal::BlockStorage::fill
void fill(void *user_context, const void *array, size_t array_size)
Definition: block_storage.h:160
Halide::Runtime::Internal::BlockStorage::reserve
void reserve(void *user_context, size_t capacity, bool free_existing=false)
Definition: block_storage.h:194
Halide::Runtime::Internal::BlockStorage::pop_back
void pop_back(void *user_context)
Definition: block_storage.h:185
memory_resources.h
Halide::Runtime::Internal::native_system_malloc
ALWAYS_INLINE void * native_system_malloc(void *user_context, size_t bytes)
Definition: memory_resources.h:185
Halide::Runtime::Internal::native_system_free
ALWAYS_INLINE void native_system_free(void *user_context, void *ptr)
Definition: memory_resources.h:189
Halide::Runtime::Internal::offset_address
ALWAYS_INLINE const void * offset_address(const void *address, size_t byte_offset)
Definition: memory_resources.h:169
Halide
This file defines the class FunctionDAG, which is our representation of a Halide pipeline,...
Definition: AbstractGenerator.h:19
Halide::LinkageType::Internal
@ Internal
Not visible externally, similar to 'static' linkage in C.
Halide::min
Expr min(const FuncRef &a, const FuncRef &b)
Explicit overloads of min and max for FuncRef.
Definition: Func.h:625
Halide::max
Expr max(const FuncRef &a, const FuncRef &b)
Definition: Func.h:628
memmove
void * memmove(void *dest, const void *src, size_t n)
int32_t
signed __INT32_TYPE__ int32_t
Definition: runtime_internal.h:24
memcpy
void * memcpy(void *s1, const void *s2, size_t n)
memcmp
int memcmp(const void *s1, const void *s2, size_t n)
uint32_t
unsigned __INT32_TYPE__ uint32_t
Definition: runtime_internal.h:25
halide_abort_if_false
#define halide_abort_if_false(user_context, cond)
Definition: runtime_internal.h:271
Halide::Runtime::Internal::BlockStorage::Config
Definition: block_storage.h:23
Halide::Runtime::Internal::BlockStorage::Config::block_size
uint32_t block_size
Definition: block_storage.h:25
Halide::Runtime::Internal::BlockStorage::Config::minimum_capacity
uint32_t minimum_capacity
Definition: block_storage.h:26
Halide::Runtime::Internal::BlockStorage::Config::entry_size
uint32_t entry_size
Definition: block_storage.h:24
Halide::Runtime::Internal::SystemMemoryAllocatorFns
Definition: memory_resources.h:193
Halide::Runtime::Internal::SystemMemoryAllocatorFns::deallocate
DeallocateSystemFn deallocate
Definition: memory_resources.h:195
Halide::Runtime::Internal::SystemMemoryAllocatorFns::allocate
AllocateSystemFn allocate
Definition: memory_resources.h:194
user_context
void * user_context
Definition: vulkan_resources.h:178
allocator
VulkanMemoryAllocator * allocator
Definition: vulkan_resources.h:179