Blender
V3.3
|
Array storage to minimize duplication. More...
#include <stdlib.h>
#include <string.h>
#include "MEM_guardedalloc.h"
#include "BLI_listbase.h"
#include "BLI_mempool.h"
#include "BLI_strict_flags.h"
#include "BLI_array_store.h"
#include "BLI_ghash.h"
Go to the source code of this file.
Classes | |
struct | BArrayInfo |
struct | BArrayMemory |
struct | BArrayStore |
struct | BArrayState |
struct | BChunkList |
struct | BChunk |
struct | BChunkRef |
struct | BTableRef |
Macros | |
#define | data_len_original invalid_usage |
#define | GHASH_PTR_ADD_USER(gh, pt) |
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 4 |
#define | USE_HASH_TABLE_KEY_CACHE |
#define | HASH_TABLE_KEY_UNSET ((uint64_t)-1) |
#define | HASH_TABLE_KEY_FALLBACK ((uint64_t)-2) |
#define | BCHUNK_HASH_TABLE_MUL 3 |
#define | USE_MERGE_CHUNKS |
#define | BCHUNK_SIZE_MIN_DIV 8 |
#define | BCHUNK_SIZE_MAX_MUL 2 |
Typedefs | |
Internal Structs | |
typedef uint64_t | hash_key |
typedef struct BArrayInfo | BArrayInfo |
typedef struct BArrayMemory | BArrayMemory |
typedef struct BChunkList | BChunkList |
typedef struct BChunk | BChunk |
typedef struct BChunkRef | BChunkRef |
typedef struct BTableRef | BTableRef |
Internal BChunkList API | |
#define | ASSERT_CHUNKLIST_SIZE(chunk_list, n) (EXPR_NOP(chunk_list), EXPR_NOP(n)) |
#define | ASSERT_CHUNKLIST_DATA(chunk_list, data) (EXPR_NOP(chunk_list), EXPR_NOP(data)) |
static BChunkList * | bchunk_list_new (BArrayMemory *bs_mem, size_t total_size) |
static void | bchunk_list_decref (BArrayMemory *bs_mem, BChunkList *chunk_list) |
static void | bchunk_list_ensure_min_size_last (const BArrayInfo *info, BArrayMemory *bs_mem, BChunkList *chunk_list) |
static void | 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 | bchunk_list_append_only (BArrayMemory *bs_mem, BChunkList *chunk_list, BChunk *chunk) |
static void | bchunk_list_append_data (const BArrayInfo *info, BArrayMemory *bs_mem, BChunkList *chunk_list, const uchar *data, const size_t data_len) |
static void | bchunk_list_append_data_n (const BArrayInfo *info, BArrayMemory *bs_mem, BChunkList *chunk_list, const uchar *data, size_t data_len) |
static void | bchunk_list_append (const BArrayInfo *info, BArrayMemory *bs_mem, BChunkList *chunk_list, BChunk *chunk) |
static void | 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 | |
#define | HASH_INIT (5381) |
BLI_INLINE uint | hash_data_single (const uchar p) |
static uint | hash_data (const uchar *key, size_t n) |
static void | hash_array_from_data (const BArrayInfo *info, const uchar *data_slice, const size_t data_slice_len, hash_key *hash_array) |
static void | hash_array_from_cref (const BArrayInfo *info, const BChunkRef *cref, const size_t data_len, hash_key *hash_array) |
static void | hash_accum (hash_key *hash_array, const size_t hash_array_len, size_t iter_steps) |
static void | hash_accum_single (hash_key *hash_array, const size_t hash_array_len, size_t iter_steps) |
static hash_key | key_from_chunk_ref (const BArrayInfo *info, const BChunkRef *cref, hash_key *hash_store, const size_t hash_store_len) |
static const BChunkRef * | 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) |
Array storage to minimize duplication.
This is done by splitting arrays into chunks and using copy-on-write (COW), 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.
De<h2>-Duplication
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.c.
Definition at line 408 of file array_store.c.
Definition at line 390 of file array_store.c.
#define BCHUNK_HASH_TABLE_ACCUMULATE_STEPS 4 |
Definition at line 143 of file array_store.c.
#define BCHUNK_HASH_TABLE_MUL 3 |
Definition at line 160 of file array_store.c.
#define BCHUNK_SIZE_MAX_MUL 2 |
Definition at line 184 of file array_store.c.
#define BCHUNK_SIZE_MIN_DIV 8 |
Definition at line 177 of file array_store.c.
#define data_len_original invalid_usage |
#define GHASH_PTR_ADD_USER | ( | gh, | |
pt | |||
) |
#define HASH_INIT (5381) |
Definition at line 735 of file array_store.c.
Definition at line 155 of file array_store.c.
Definition at line 154 of file array_store.c.
#define USE_ALIGN_CHUNKS_TEST |
Definition at line 131 of file array_store.c.
#define USE_FASTPATH_CHUNKS_FIRST |
Definition at line 113 of file array_store.c.
#define USE_FASTPATH_CHUNKS_LAST |
Definition at line 123 of file array_store.c.
#define USE_HASH_TABLE_ACCUMULATE |
Definition at line 136 of file array_store.c.
#define USE_HASH_TABLE_KEY_CACHE |
Definition at line 152 of file array_store.c.
#define USE_MERGE_CHUNKS |
Definition at line 172 of file array_store.c.
typedef struct BArrayInfo BArrayInfo |
typedef struct BArrayMemory BArrayMemory |
typedef struct BChunkList BChunkList |
Links to store BChunk data in BChunkList.chunk_refs.
Definition at line 200 of file array_store.c.
|
static |
Definition at line 1421 of file array_store.c.
References BLI_assert, BLI_mempool_iternew(), BLI_mempool_iterstep(), BArrayMemory::chunk, BChunk::data, ListBase::first, MEM_freeN, BArrayStore::memory, state, BArrayStore::states, and BChunk::users.
Referenced by BLI_array_store_clear(), and BLI_array_store_destroy().
|
static |
Definition at line 339 of file array_store.c.
References BChunk::data, BChunk::data_len, and offset.
Referenced by bchunk_list_from_data_merge(), and table_lookup().
|
static |
Definition at line 327 of file array_store.c.
References BLI_assert, BLI_mempool_free(), BArrayMemory::chunk, BChunk::data, MEM_freeN, and BChunk::users.
Referenced by bchunk_list_append_data(), bchunk_list_decref(), and bchunk_list_ensure_min_size_last().
|
static |
Definition at line 666 of file array_store.c.
References bchunk_list_append_only(), bchunk_list_ensure_min_size_last(), and UNUSED_VARS.
Referenced by bchunk_list_from_data_merge().
|
static |
Definition at line 561 of file array_store.c.
References bchunk_decref(), bchunk_list_append_only(), bchunk_list_ensure_min_size_last(), bchunk_new(), bchunk_new_copydata(), BLI_assert, BLI_listbase_is_empty(), BArrayInfo::chunk_byte_size_min, BChunkList::chunk_refs, BTableRef::cref, BChunk::data, data, BChunk::data_len, ListBase::last, BChunkRef::link, MEM_mallocN, MEM_reallocN, MIN2, UNUSED_VARS, and BChunk::users.
Referenced by bchunk_list_append_data_n(), and bchunk_list_from_data_merge().
|
static |
Similar to bchunk_list_append_data, but handle multiple chunks. Use for adding arrays of arbitrary sized memory at once.
Definition at line 618 of file array_store.c.
References bchunk_list_append_data(), bchunk_list_append_only(), bchunk_list_calc_trim_len(), bchunk_new_copydata(), BLI_assert, BArrayInfo::chunk_byte_size, BArrayInfo::chunk_byte_size_min, BChunkList::chunk_refs, data, and ListBase::last.
Referenced by bchunk_list_from_data_merge().
|
static |
Append and don't manage merging small chunks.
Definition at line 548 of file array_store.c.
References BLI_addtail(), BLI_mempool_alloc(), BArrayMemory::chunk_ref, BChunkList::chunk_refs, BChunkList::chunk_refs_len, BTableRef::cref, BChunkRef::link, and BChunk::users.
Referenced by bchunk_list_append(), bchunk_list_append_data(), bchunk_list_append_data_n(), bchunk_list_fill_from_array(), and bchunk_list_from_data_merge().
|
static |
Split length into 2 values
r_data_trim_len | Length which is aligned to the BArrayInfo.chunk_byte_size |
r_data_last_chunk_len | The remaining bytes. |
Definition at line 506 of file array_store.c.
References BLI_assert, and BArrayInfo::chunk_byte_size.
Referenced by bchunk_list_append_data_n(), and bchunk_list_fill_from_array().
|
static |
Definition at line 367 of file array_store.c.
References bchunk_decref(), BLI_assert, BLI_mempool_free(), BArrayMemory::chunk_list, BArrayMemory::chunk_ref, BChunkList::chunk_refs, BTableRef::cref, ListBase::first, BChunkRef::link, BChunkRef::next, and BChunkList::users.
Referenced by BLI_array_store_state_remove().
|
static |
Definition at line 412 of file array_store.c.
References bchunk_decref(), bchunk_new(), BLI_assert, BLI_mempool_free(), BArrayInfo::chunk_byte_size, BArrayInfo::chunk_byte_size_min, BArrayMemory::chunk_ref, BChunkList::chunk_refs, BChunkList::chunk_refs_len, BTableRef::cref, BChunk::data, BChunk::data_len, ListBase::first, ListBase::last, BChunkRef::link, MEM_mallocN, MIN2, BChunkRef::next, NULL, BChunkRef::prev, blender::io::alembic::split(), and BChunk::users.
Referenced by bchunk_list_append(), bchunk_list_append_data(), and bchunk_list_fill_from_array().
|
static |
Definition at line 680 of file array_store.c.
References ASSERT_CHUNKLIST_DATA, ASSERT_CHUNKLIST_SIZE, bchunk_list_append_only(), bchunk_list_calc_trim_len(), bchunk_list_ensure_min_size_last(), bchunk_new_copydata(), BLI_assert, BLI_listbase_is_empty(), BArrayInfo::chunk_byte_size, BArrayInfo::chunk_byte_size_min, BChunkList::chunk_refs, data, and ListBase::last.
Referenced by BLI_array_store_state_add().
|
static |
data | Data to store in the returned value. |
data_len_original | Length of data in bytes. |
chunk_list_reference | Reuse this list or chunks within it, don't modify its content. |
Definition at line 1009 of file array_store.c.
References BArrayInfo::accum_read_ahead_bytes, BArrayInfo::accum_read_ahead_len, BArrayInfo::accum_steps, ASSERT_CHUNKLIST_DATA, ASSERT_CHUNKLIST_SIZE, bchunk_data_compare(), BCHUNK_HASH_TABLE_MUL, bchunk_list_append(), bchunk_list_append_data(), bchunk_list_append_data_n(), bchunk_list_append_only(), bchunk_list_new(), BLI_assert, BLI_listbase_is_empty(), BArrayInfo::chunk_byte_size, BChunkList::chunk_refs, BChunkList::chunk_refs_len, BArrayInfo::chunk_stride, BTableRef::cref, data, BChunk::data_len, data_len_original, ELEM, ListBase::first, hash_accum(), hash_array_from_data(), key_from_chunk_ref(), ListBase::last, BChunkRef::link, MEM_callocN, MEM_freeN, MEM_mallocN, BChunkRef::next, BTableRef::next, NULL, offset, BChunkRef::prev, table_lookup(), BChunkList::total_size, and USE_HASH_TABLE_ACCUMULATE.
Referenced by BLI_array_store_state_add().
|
static |
Definition at line 356 of file array_store.c.
References BLI_listbase_clear(), BLI_mempool_alloc(), BArrayMemory::chunk_list, BChunkList::chunk_refs, BChunkList::chunk_refs_len, BChunkList::total_size, and BChunkList::users.
Referenced by bchunk_list_from_data_merge(), and BLI_array_store_state_add().
|
static |
Definition at line 1595 of file array_store.c.
References BChunkList::chunk_refs, BTableRef::cref, BChunk::data_len, BChunkRef::link, and LISTBASE_FOREACH.
Referenced by BLI_array_store_is_valid().
|
static |
Definition at line 308 of file array_store.c.
References BLI_mempool_alloc(), BArrayMemory::chunk, BChunk::data, data, BChunk::data_len, HASH_TABLE_KEY_UNSET, BChunk::key, and BChunk::users.
Referenced by bchunk_list_append_data(), bchunk_list_ensure_min_size_last(), and bchunk_new_copydata().
|
static |
Definition at line 320 of file array_store.c.
References bchunk_new(), data, and MEM_mallocN.
Referenced by bchunk_list_append_data(), bchunk_list_append_data_n(), and bchunk_list_fill_from_array().
size_t BLI_array_store_calc_size_compacted_get | ( | const BArrayStore * | bs | ) |
Definition at line 1478 of file array_store.c.
References BLI_assert, BLI_mempool_iternew(), BLI_mempool_iterstep(), BArrayMemory::chunk, BChunk::data_len, BArrayStore::memory, and BChunk::users.
Referenced by BLI_array_store_at_size_calc_memory_usage(), random_chunk_mutate_helper(), TEST(), and text_undosys_step_encode_to_state().
size_t BLI_array_store_calc_size_expanded_get | ( | const BArrayStore * | bs | ) |
Find the memory used by all states (expanded & real).
Definition at line 1469 of file array_store.c.
References LISTBASE_FOREACH, state, and BArrayStore::states.
Referenced by BLI_array_store_at_size_calc_memory_usage(), and TEST().
void BLI_array_store_clear | ( | BArrayStore * | bs | ) |
Clear all contents, allowing reuse of bs.
Definition at line 1452 of file array_store.c.
References array_store_free_data(), BLI_listbase_clear(), BLI_mempool_clear(), BArrayMemory::chunk, BArrayMemory::chunk_list, BArrayMemory::chunk_ref, BArrayStore::memory, and BArrayStore::states.
BArrayStore* BLI_array_store_create | ( | unsigned int | stride, |
unsigned int | chunk_count | ||
) |
Create a new array store, which can store any number of arrays as long as their stride matches.
stride | sizeof() each element, |
1
will always work, its less efficient since duplicate chunks of memory will be searched at positions unaligned with the array data.chunk_count | Number of elements to split each chunk into.
|
Definition at line 1388 of file array_store.c.
References BArrayInfo::accum_read_ahead_bytes, BArrayInfo::accum_read_ahead_len, BArrayInfo::accum_steps, BCHUNK_HASH_TABLE_ACCUMULATE_STEPS, BCHUNK_SIZE_MAX_MUL, BCHUNK_SIZE_MIN_DIV, BLI_MEMPOOL_ALLOW_ITER, BLI_mempool_create(), BLI_MEMPOOL_NOP, BArrayMemory::chunk, BArrayInfo::chunk_byte_size, BArrayInfo::chunk_byte_size_max, BArrayInfo::chunk_byte_size_min, BArrayMemory::chunk_list, BArrayMemory::chunk_ref, BArrayInfo::chunk_stride, BArrayStore::info, MAX2, MEM_callocN, BArrayStore::memory, and stride.
Referenced by BLI_array_store_at_size_ensure(), random_chunk_mutate_helper(), TEST(), testbuffer_run_tests_simple(), and text_undosys_step_encode_to_state().
void BLI_array_store_destroy | ( | BArrayStore * | bs | ) |
Free the BArrayStore, including all states and chunks.
Definition at line 1441 of file array_store.c.
References array_store_free_data(), BLI_mempool_destroy(), BArrayMemory::chunk, BArrayMemory::chunk_list, BArrayMemory::chunk_ref, MEM_freeN, and BArrayStore::memory.
Referenced by BLI_array_store_at_size_clear(), random_chunk_mutate_helper(), TEST(), testbuffer_run_tests_simple(), and text_undosys_step_free().
bool BLI_array_store_is_valid | ( | BArrayStore * | bs | ) |
Definition at line 1604 of file array_store.c.
References bchunk_list_size(), BLI_ghash_free(), BLI_ghash_len(), BLI_ghash_ptr_new(), BLI_ghashIterator_getKey(), BLI_ghashIterator_getValue(), BLI_listbase_count(), BLI_mempool_iternew(), BLI_mempool_iterstep(), BLI_mempool_len(), BArrayMemory::chunk, BArrayInfo::chunk_byte_size_min, BArrayMemory::chunk_list, BArrayMemory::chunk_ref, BChunkList::chunk_refs, BChunkList::chunk_refs_len, BTableRef::cref, BChunk::data, BChunk::data_len, GHASH_ITER, GHASH_PTR_ADD_USER, BArrayStore::info, BChunkRef::link, LISTBASE_FOREACH, MEM_allocN_len, BArrayStore::memory, NULL, POINTER_AS_INT, state, BArrayStore::states, BChunkList::total_size, BChunkList::users, BChunk::users, and users.
Referenced by TEST(), and testbuffer_run_tests_single().
BArrayState* BLI_array_store_state_add | ( | BArrayStore * | bs, |
const void * | data, | ||
size_t | data_len, | ||
const BArrayState * | state_reference | ||
) |
data | Data used to create |
state_reference | The state to use as a reference when adding the new state, typically this is the previous state, however it can be any previously created state from this bs. |
Definition at line 1497 of file array_store.c.
References bchunk_list_fill_from_array(), bchunk_list_from_data_merge(), bchunk_list_new(), BLI_addtail(), BLI_array_store_state_data_get_alloc(), BLI_assert, BLI_findindex(), BArrayState::chunk_list, BArrayInfo::chunk_stride, data, BArrayStore::info, MEM_callocN, MEM_freeN, BArrayStore::memory, state, BArrayStore::states, and BChunkList::users.
Referenced by TEST(), testbuffer_list_store_populate(), text_state_encode(), um_arraystore_cd_compact(), and um_arraystore_compact_ex().
void BLI_array_store_state_data_get | ( | BArrayState * | state, |
void * | data | ||
) |
Fill in existing allocated memory with the contents of state.
Definition at line 1562 of file array_store.c.
References BLI_assert, BTableRef::cref, BChunk::data, data, BChunk::data_len, BChunkRef::link, LISTBASE_FOREACH, state, and BChunk::users.
Referenced by BLI_array_store_state_data_get_alloc().
void* BLI_array_store_state_data_get_alloc | ( | BArrayState * | state, |
size_t * | r_data_len | ||
) |
Allocate an array for state and return it.
Definition at line 1580 of file array_store.c.
References BLI_array_store_state_data_get(), data, MEM_mallocN, and state.
Referenced by BLI_array_store_state_add(), TEST(), testbuffer_item_validate(), text_state_decode(), um_arraystore_cd_expand(), and um_arraystore_expand().
void BLI_array_store_state_remove | ( | BArrayStore * | bs, |
BArrayState * | state | ||
) |
Remove a state and free any unused BChunk data.
The states can be freed in any order.
Definition at line 1545 of file array_store.c.
References bchunk_list_decref(), BLI_assert, BLI_findindex(), BLI_remlink(), MEM_freeN, BArrayStore::memory, state, and BArrayStore::states.
Referenced by TEST(), testbuffer_list_store_clear(), text_undosys_step_free(), um_arraystore_cd_free(), and um_arraystore_free().
size_t BLI_array_store_state_size_get | ( | BArrayState * | state | ) |
Definition at line 1557 of file array_store.c.
References state.
Referenced by TEST().
|
static |
Definition at line 805 of file array_store.c.
References UNLIKELY.
Referenced by bchunk_list_from_data_merge().
|
static |
When we only need a single value, can use a small optimization. we can avoid accumulating the tail of the array a little, each iteration.
Definition at line 826 of file array_store.c.
References BLI_assert, and UNLIKELY.
Referenced by key_from_chunk_ref().
|
static |
Definition at line 780 of file array_store.c.
References BLI_assert, BArrayInfo::chunk_stride, BTableRef::cref, BChunk::data, BChunk::data_len, hash_array_from_data(), BChunkRef::link, BChunkRef::next, and NULL.
Referenced by key_from_chunk_ref().
|
static |
Definition at line 758 of file array_store.c.
References BArrayInfo::chunk_stride, hash_data(), and hash_data_single().
Referenced by bchunk_list_from_data_merge(), and hash_array_from_cref().
Definition at line 743 of file array_store.c.
References HASH_INIT.
Referenced by hash_array_from_data().
BLI_INLINE uint hash_data_single | ( | const uchar | p | ) |
Definition at line 737 of file array_store.c.
References HASH_INIT.
Referenced by hash_array_from_data().
|
static |
Definition at line 848 of file array_store.c.
References BArrayInfo::accum_read_ahead_bytes, BArrayInfo::accum_steps, BLI_assert, BArrayInfo::chunk_stride, BTableRef::cref, BChunk::data_len, hash_accum_single(), hash_array_from_cref(), HASH_TABLE_KEY_FALLBACK, HASH_TABLE_KEY_UNSET, BChunk::key, BChunkRef::link, and UNLIKELY.
Referenced by bchunk_list_from_data_merge().
|
static |
Definition at line 899 of file array_store.c.
References bchunk_data_compare(), BArrayInfo::chunk_stride, BTableRef::cref, data, BChunk::data_len, BChunk::key, BChunkRef::link, BTableRef::next, NULL, and offset.
Referenced by bchunk_list_from_data_merge().