|
Blender V5.3
|
Array storage to minimize duplication. More...
#include <algorithm>#include <bit>#include <cstdlib>#include <cstring>#include <type_traits>#include "MEM_guardedalloc.h"#include "BLI_assert.hh"#include "BLI_listbase.hh"#include "BLI_map.hh"#include "BLI_mempool.hh"#include "BLI_utildefines.hh"#include "BLI_array_store.hh"#include "BLI_strict_flags.hh"Go to the source code of this file.
Classes | |
| struct | blender::UInt64_Data |
| struct | blender::UInt96_Data |
| struct | blender::UInt128_Data |
| struct | blender::BArrayInfo |
| struct | blender::BArrayMemory |
| struct | blender::BArrayStore |
| struct | blender::BArrayState |
| struct | blender::BChunkList |
| struct | blender::BChunk |
| struct | blender::BChunkRef |
| struct | blender::BTableRef |
Namespaces | |
| namespace | blender |
| BMesh Iterators. | |
Macros | |
| #define | HASH_ARRAY_FROM_DATA_GENERIC(ty) |
| #define | data_len_original invalid_usage |
Defines | |
Some of the logic for merging is quite involved, support disabling some parts of this. | |
| #define | USE_FASTPATH_CHUNKS_FIRST |
| #define | USE_FASTPATH_CHUNKS_LAST |
| #define | USE_ALIGN_CHUNKS_TEST |
| #define | USE_HASH_TABLE_ACCUMULATE |
| #define | BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_DEFAULT 3 |
| #define | BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_32BITS 4 |
| #define | BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_16BITS 5 |
| #define | BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_8BITS 6 |
| #define | USE_HASH_TABLE_KEY_CACHE |
| #define | HASH_TABLE_KEY_UNSET ((hash_key) - 1) |
| #define | HASH_TABLE_KEY_FALLBACK ((hash_key) - 2) |
| #define | USE_HASH_TABLE_DEDUPLICATE |
| #define | BCHUNK_HASH_TABLE_MUL 3 |
| #define | USE_MERGE_CHUNKS |
| #define | BCHUNK_SIZE_MIN_DIV 8 |
| #define | BCHUNK_SIZE_MAX_MUL 2 |
Functions | |
Debugging API (for testing). | |
| static size_t | blender::bchunk_list_size (const BChunkList *chunk_list) |
| bool | blender::BLI_array_store_is_valid (BArrayStore *bs) |
Internal BChunk API | |
| static BChunk * | blender::bchunk_new (BArrayMemory *bs_mem, const uchar *data, const size_t data_len) |
| static BChunk * | blender::bchunk_new_copydata (BArrayMemory *bs_mem, const uchar *data, const size_t data_len) |
| static void | blender::bchunk_decref (BArrayMemory *bs_mem, BChunk *chunk) |
| BLI_INLINE bool | blender::bchunk_data_compare_unchecked (const BChunk *chunk, const uchar *data_base, const size_t data_base_len, const size_t offset) |
| static bool | blender::bchunk_data_compare (const BChunk *chunk, const uchar *data_base, const size_t data_base_len, const size_t offset) |
Main Data De-Duplication Function | |
| static BChunkList * | blender::bchunk_list_from_data_merge (const BArrayInfo *info, BArrayMemory *bs_mem, const uchar *data, const size_t data_len_original, const BChunkList *chunk_list_reference) |
Main Array Storage API | |
| BArrayStore * | blender::BLI_array_store_create (unsigned int stride, unsigned int chunk_count) |
| static void | blender::array_store_free_data (BArrayStore *bs) |
| void | blender::BLI_array_store_destroy (BArrayStore *bs) |
| void | blender::BLI_array_store_clear (BArrayStore *bs) |
BArrayStore Statistics | |
| size_t | blender::BLI_array_store_calc_size_expanded_get (const BArrayStore *bs) |
| size_t | blender::BLI_array_store_calc_size_compacted_get (const BArrayStore *bs) |
BArrayState Access | |
| BArrayState * | blender::BLI_array_store_state_add (BArrayStore *bs, const void *data, size_t data_len, const BArrayState *state_reference) |
| void | blender::BLI_array_store_state_remove (BArrayStore *bs, BArrayState *state) |
| size_t | blender::BLI_array_store_state_size_get (const BArrayState *state) |
| void | blender::BLI_array_store_state_data_get (const BArrayState *state, void *data) |
| void * | blender::BLI_array_store_state_data_get_alloc (const BArrayState *state, size_t *r_data_len) |
Internal BChunkList API | |
| #define | ASSERT_CHUNKLIST_SIZE(chunk_list, n) |
| #define | ASSERT_CHUNKLIST_DATA(chunk_list, data) |
| static BChunkList * | blender::bchunk_list_new (BArrayMemory *bs_mem, size_t total_expanded_size) |
| static void | blender::bchunk_list_decref (BArrayMemory *bs_mem, BChunkList *chunk_list) |
| static void | blender::bchunk_list_ensure_min_size_last (const BArrayInfo *info, BArrayMemory *bs_mem, BChunkList *chunk_list) |
| static void | blender::bchunk_list_calc_trim_len (const BArrayInfo *info, const size_t data_len, size_t *r_data_trim_len, size_t *r_data_last_chunk_len) |
| static void | blender::bchunk_list_append_only (BArrayMemory *bs_mem, BChunkList *chunk_list, BChunk *chunk) |
| static void | blender::bchunk_list_append_data (const BArrayInfo *info, BArrayMemory *bs_mem, BChunkList *chunk_list, const uchar *data, const size_t data_len) |
| static void | blender::bchunk_list_append_data_n (const BArrayInfo *info, BArrayMemory *bs_mem, BChunkList *chunk_list, const uchar *data, size_t data_len) |
| static void | blender::bchunk_list_append (const BArrayInfo *info, BArrayMemory *bs_mem, BChunkList *chunk_list, BChunk *chunk) |
| static void | blender::bchunk_list_fill_from_array (const BArrayInfo *info, BArrayMemory *bs_mem, BChunkList *chunk_list, const uchar *data, const size_t data_len) |
Internal Hashing/De-Duplication API | |
Only used by #bchunk_list_from_data_merge
For this reason, favor speed over high-quality hashes for each element. (although the hashes are not low quality either). For bytes DJB2 hashing is used. For other integers as variation of bits are not multiplied to account for the range of larger integers being significantly larger than bytes. Instead larger types use addition and XOR to the hash with a single "rotation" for each hash. Alternative hashing could be investigated although take care as this logic needs to hash many small values with low overhead, which can make hashing utility functions such as XXHASH too slow to use. | |
| #define | HASH_INIT (5381) |
| #define | HASH_VALUE_IMPL_ADD_BYTES(h, value) |
| #define | HASH_VALUE_IMPL_ADD(h, value) |
| template<typename T> | |
| BLI_INLINE void | blender::hash_value_generic (hash_key &h, const T &value) |
| template<typename T> | |
| BLI_INLINE hash_key | blender::hash_data_single_generic (const T &value) |
| template<typename T> | |
| static hash_key | blender::hash_data_generic (const T *data, size_t data_len) |
| template<typename T> | |
| static void | blender::hash_array_from_data_generic (const size_t stride, const T *data_slice, const size_t data_slice_len, hash_key *hash_array) |
| static void | blender::hash_array_from_data (const BArrayInfo *info, const uchar *data_slice, const size_t data_slice_len, hash_key *hash_array) |
| static void | blender::hash_array_from_cref (const BArrayInfo *info, const BChunkRef *cref, const size_t data_len, hash_key *hash_array) |
| BLI_INLINE void | blender::hash_accum_impl (hash_key *hash_array, const size_t i_dst, const size_t i_ahead) |
| static void | blender::hash_accum (hash_key *hash_array, const size_t hash_array_len, size_t iter_steps) |
| static void | blender::hash_accum_single (hash_key *hash_array, const size_t hash_array_len, size_t iter_steps) |
| static hash_key | blender::key_from_chunk_ref (const BArrayInfo *info, const BChunkRef *cref, hash_key *hash_store, const size_t hash_store_len) |
| static const BChunkRef * | blender::table_lookup (const BArrayInfo *info, BTableRef **table, const size_t table_len, const size_t i_table_start, const uchar *data, const size_t data_len, const size_t offset, const hash_key *table_hash_array) |
Internal Structs | |
Slow (keep disabled), but handy for debugging. | |
| enum class | blender::HashSize : uint8_t { blender::U8 = sizeof(uint8_t) , blender::U16 = sizeof(uint16_t) , blender::U32 = sizeof(uint32_t) , blender::U64 = sizeof(UInt64_Data) , blender::U96 = sizeof(UInt96_Data) , blender::U128 = sizeof(UInt128_Data) } |
| using | blender::hash_key = uint32_t |
Array storage to minimize duplication.
This is done by splitting arrays into chunks and using copy-on-evaluation, to de-duplicate chunks, from the users perspective this is an implementation detail.
This diagram is an overview of the structure of a single array-store.
<+> #BArrayStore: root data-structure,
| can store many 'states', which share memory.
|
| This can store many arrays, however they must share the same 'stride'.
| Arrays of different types will need to use a new #BArrayStore.
|
+- <+> states (Collection of #BArrayState's):
| | Each represents an array added by the user of this API.
| | and references a chunk_list (each state is a chunk_list user).
| | Note that the list order has no significance.
| |
| +- <+> chunk_list (#BChunkList):
| | The chunks that make up this state.
| | Each state is a chunk_list user,
| | avoids duplicating lists when there is no change between states.
| |
| +- chunk_refs (List of #BChunkRef): Each chunk_ref links to a #BChunk.
| Each reference is a chunk user,
| avoids duplicating smaller chunks of memory found in multiple states.
|
+- info (#BArrayInfo):
| Sizes and offsets for this array-store.
| Also caches some variables for reuse.
|
+- <+> memory (#BArrayMemory):
| Memory pools for storing #BArrayStore data.
|
+- chunk_list (Pool of #BChunkList):
| All chunk_lists, (reference counted, used by #BArrayState).
|
+- chunk_ref (Pool of #BChunkRef):
| All chunk_refs (link between #BChunkList & #BChunk).
|
+- chunks (Pool of #BChunk):
All chunks, (reference counted, used by #BChunkList).
These have their headers hashed for reuse so we can quickly check for duplicates.
When creating a new state, a previous state can be given as a reference, matching chunks from this state are re-used in the new state.
First matches at either end of the array are detected. For identical arrays this is all that's needed.
De-duplication is performed on any remaining chunks, by hashing the first few bytes of the chunk (see: #BCHUNK_HASH_TABLE_ACCUMULATE_STEPS).
An array is created to store hash values at every 'stride', then stepped over to search for matching chunks.
Once a match is found, there is a high chance next chunks match too, so this is checked to avoid performing so many hash-lookups. Otherwise new chunks are created.
Definition in file array_store.cc.
| #define ASSERT_CHUNKLIST_DATA | ( | chunk_list, | |
| data ) |
Definition at line 501 of file array_store.cc.
Referenced by blender::bchunk_list_fill_from_array(), and blender::bchunk_list_from_data_merge().
| #define ASSERT_CHUNKLIST_SIZE | ( | chunk_list, | |
| n ) |
Definition at line 483 of file array_store.cc.
Referenced by blender::bchunk_list_fill_from_array(), and blender::bchunk_list_from_data_merge().
| #define BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_16BITS 5 |
Definition at line 166 of file array_store.cc.
Referenced by blender::BLI_array_store_create().
| #define BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_32BITS 4 |
Definition at line 165 of file array_store.cc.
Referenced by blender::BLI_array_store_create().
| #define BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_8BITS 6 |
Single bytes (or boolean) arrays need a higher number of steps because the resulting values are not unique enough to result in evenly distributed values. Use more accumulation when the size of the structs is small, see: #105046.
With 6 -> 22, one byte each - means an array of booleans can be combined into 22 bits representing 4,194,303 different combinations.
Definition at line 175 of file array_store.cc.
Referenced by blender::BLI_array_store_create().
| #define BCHUNK_HASH_TABLE_ACCUMULATE_STEPS_DEFAULT 3 |
Definition at line 164 of file array_store.cc.
Referenced by blender::BLI_array_store_create().
| #define BCHUNK_HASH_TABLE_MUL 3 |
How much larger the table is then the total number of chunks.
Definition at line 206 of file array_store.cc.
Referenced by blender::bchunk_list_from_data_merge().
| #define BCHUNK_SIZE_MAX_MUL 2 |
Disallow chunks bigger than the regular chunk size scaled by this value.
Definition at line 232 of file array_store.cc.
Referenced by blender::BLI_array_store_create().
| #define BCHUNK_SIZE_MIN_DIV 8 |
Merge chunks smaller then: (#BArrayInfo::chunk_byte_size / BCHUNK_SIZE_MIN_DIV).
Definition at line 223 of file array_store.cc.
Referenced by blender::BLI_array_store_create().
| #define data_len_original invalid_usage |
Referenced by blender::bchunk_list_from_data_merge().
| #define HASH_ARRAY_FROM_DATA_GENERIC | ( | ty | ) |
Referenced by blender::hash_array_from_data().
| #define HASH_INIT (5381) |
Definition at line 842 of file array_store.cc.
Referenced by blender::hash_data_generic(), and blender::hash_data_single_generic().
| #define HASH_TABLE_KEY_FALLBACK ((hash_key) - 2) |
Definition at line 190 of file array_store.cc.
Referenced by blender::key_from_chunk_ref().
| #define HASH_TABLE_KEY_UNSET ((hash_key) - 1) |
Definition at line 189 of file array_store.cc.
Referenced by blender::bchunk_new(), and blender::key_from_chunk_ref().
| #define HASH_VALUE_IMPL_ADD | ( | h, | |
| value ) |
Definition at line 855 of file array_store.cc.
Referenced by blender::hash_value_generic().
| #define HASH_VALUE_IMPL_ADD_BYTES | ( | h, | |
| value ) |
The DJB2 algorithm was originally used for bytes, so it's kept although the rotating method from HASH_VALUE_IMPL_ADD may be acceptable in this case too.
Definition at line 849 of file array_store.cc.
Referenced by blender::hash_value_generic().
| #define USE_ALIGN_CHUNKS_TEST |
For arrays of matching length, test that enough of the chunks are aligned, and simply step over both arrays, using matching chunks. This avoids overhead of using a lookup table for cases when we can assume they're mostly aligned.
Definition at line 147 of file array_store.cc.
| #define USE_FASTPATH_CHUNKS_FIRST |
Scan first chunks (happy path when beginning of the array matches). When the array is a perfect match, we can re-use the entire list.
Note that disabling makes some tests fail that check for output-size.
Definition at line 127 of file array_store.cc.
| #define USE_FASTPATH_CHUNKS_LAST |
Scan last chunks (happy path when end of the array matches). When the end of the array matches, we can quickly add these chunks. note that we will add contiguous matching chunks so this isn't as useful as USE_FASTPATH_CHUNKS_FIRST, however it avoids adding matching chunks into the lookup table, so creating the lookup table won't be as expensive.
Definition at line 138 of file array_store.cc.
| #define USE_HASH_TABLE_ACCUMULATE |
Accumulate hashes from right to left so we can create a hash for the chunk-start. This serves to increase uniqueness and will help when there is many values which are the same.
Definition at line 153 of file array_store.cc.
Referenced by blender::bchunk_list_from_data_merge().
| #define USE_HASH_TABLE_DEDUPLICATE |
Ensure duplicate entries aren't added to temporary hash table needed for arrays where many values match (e.g. an array of booleans all true/false).
Without this, a huge number of duplicates are added a single bucket, making hash lookups slow. While de-duplication adds some cost, it's only performed with other chunks in the same bucket so cases when all chunks are unique will quickly detect and exit the memcmp in most cases.
Definition at line 201 of file array_store.cc.
| #define USE_HASH_TABLE_KEY_CACHE |
Calculate the key once and reuse it.
Definition at line 187 of file array_store.cc.
| #define USE_MERGE_CHUNKS |
Merge too small/large chunks:
Using this means chunks below a threshold will be merged together. Even though short term this uses more memory, long term the overhead of maintaining many small chunks is reduced. This is defined by setting the minimum chunk size (as a fraction of the regular chunk size).
Chunks may also become too large (when incrementally growing an array), this also enables chunk splitting.
Definition at line 219 of file array_store.cc.