Page MenuHome

BLI_array_store: array-copy-on-write, array de-duplication library
AbandonedPublic

Authored by Campbell Barton (campbellbarton) on May 24 2016, 12:38 PM.

Details

Reviewers
Bastien Montagne (mont29)
Sergey Sharybin (sergey)
Commits
rBS082865197239: Work in progress array-copy-on-write library
rBS49579f5816aa: Add NULL check, needed in rare cases
rBS4e6057b5a7e3: Correct check for aligned chunks
rBS2e8a673872f9: Add test to check chunk de-duplication is working
rBS5da369a81e2f: Work in progress array-copy-on-write library
rBSfb912676fb6b: Work in progress array-copy-on-write library
rBS04f9fce40ae0: Compact undo steps in a background thread
rBSf93b7361c3f9: Print undo memory saved for a single step
rBS2099384bce8e: minor ifdef tweaks
rBS749cdb7db8cd: Break out of searching for matching blocks once there is a mismatch
rBS27e11a5ef44f: Add support for key-blocks
rBS3c355e9069d3: More unique naming for parts of the undo api relating to array-store usage
rBSfc40b20130b2: Increase chunk size
rBS3a15a8d5f539: print undo memory saving
rBSd35681895050: Add timer for packing, correct release build error
rBS05a2744d4980: Tests Fail, need to check return value of validate
rBS09c7779ed0a0: Initial undo support (as ifdef)
rBS8bd773cee901: Correct ifdef, add paranoid check
rBSef4ec89c8382: Correct user-count freeing for chunk-list
rBScdc24fec6f09: Data was being written incorrectly, correct and add asserts
rBSbf8c19ffbc10: Fix bug using uninitialized memory
rBS19f9cccafbaa: minor simplification
rBSd020d44a75f6: Simplify hash_array_from_cref loop
rBS24b4112b9d26: Add new test based on a bug with mesh undo
rBSd1c1cc13a393: Comments
rBS3d4c60275f2f: Use term `chunk` instead of `block` (was using both)
rBS2ae31bd75638: Fast path hash_array_from_cref for bytes
rBSa170043874ff: Fast-path for hashing bytes (avoid function call per byte)
rBSc57687e7740f: Use size_t for all offset values
rBS315f9b9be992: Remove not-very-useful test
rBSfc2b5314dc04: Add BLI_array_store_clear
rBS892d728a1fbb: Comments
rBS9f29d1f7e2a8: Add tests with different stride values, also optionally shuffle data based on…
rBSbdf2c6562795: Simplify check
rBS647e41fda998: Remove explicit tree structure
rBS9a68d3148216: Support chunk sizes of 1
rBS56fa4ad88de1: Remove asserts left in for debugging purposes
rBSce1faea49e8c: Don't adjust users in bchunk_list_from_data_merge
rBS6fcedc5512e3: Fix rounding error using odd-number for chunk sizes
rBSd46130aa2b4b: Run test on files forward and backwards
rBS9edd239be597: Work in progress array-copy-on-write library
rBS7dc20ed197c1: Fix for overlap check
rBS4736c53a5125: More comprehensive tests
rBSca7ebd58a73f: Work in progress array-copy-on-write library
rBS713dd4b7473e: Increase chunk size
rBS52f53e66c430: Break out of searching for matching blocks once there is a mismatch
rBS06efef414d18: Fix bug using uninitialized memory
rBSce37079c4b58: Initial undo support (as ifdef)
rBS406cc29d9b95: Simplify hash_array_from_cref loop
rBS19292017eff3: Use size_t for all offset values
rBS4b846af92c6f: Remove not-very-useful test
rBS4e4b21c4e058: Fast path hash_array_from_cref for bytes
rBS7000e861236b: minor simplification
rBSf2863ce19504: Fast-path for hashing bytes (avoid function call per byte)
rBS721dd1d50464: Comments
rBSfa859d4f86e9: Add BLI_array_store_clear
rBS4be6daa6ae21: Use term `chunk` instead of `block` (was using both)
rBS7660b6dc8f4e: Comments
rBS25a4522ef4c4: Add tests with different stride values, also optionally shuffle data based on…
rBSb1d2965ef832: Remove explicit tree structure
rBS4c312c2694be: Run test on files forward and backwards
rBSeeedfd487448: Simplify check
rBS7cc4786b6a7b: Don't adjust users in bchunk_list_from_data_merge
rBS07481c890814: Support chunk sizes of 1
rBScb5e3ec7f871: Remove asserts left in for debugging purposes
rBSf38e68430449: More comprehensive tests
rBSad5264e8b68c: Work in progress array-copy-on-write library
rBS859dee82cb27: Fix rounding error using odd-number for chunk sizes
rBS3ef954667bd5: Fix for overlap check
rBSc2307af066aa: Work in progress array-copy-on-write library
rBS5559d2a323ed: Work in progress array-copy-on-write library
rBS73f8356de026: Work in progress array-copy-on-write library
Summary

BLI_array_store API

This adds BLI_array_store for storing many similar arrays.

From users of this API, its only required to add/access/remove data.
Internally the data is de-duplicated.

Currently this patch is finished ~ in that as far as I know there are no bugs to resolve.

This patch also includes ifdef 'd code in editmesh_undo.c to de-duplicate memory for undo storage.

However there are some possible further work:

  • Compare speed of hash lookups with a stride-aligned memstr (in practice this may be faster, since in many cases blocks aren't re-ordered completely).
  • Investigate different methods of hashing blocks.
  • Some of the constants could be tweaked with real-world data, for eg, chunks are hashed based on the first 7 elements (see: BCHUNK_HASH_TABLE_ACCUMULATE_STEPS), it may end up needing to be more.
  • Currently array size is limited to ~4gb (an unsigned it is used for offsets), probably should switch to size_t.
  • Have a fast-path for hashing blocks with a stride of 1 (no need for a function call here).

EditMesh Undo

Note, we may want to split this off into its own diff.

This patch makes use of BLI_array_store to reduce memory usage for edit-mesh undo.

The existing undo code, that stores a mesh data-block for each undo step is kept, however all large arrays are moved into a BLI_array_store,
which handles de-duplication.
Before reading these are temporarily expanded into the mesh, then freed.

Details:

  • Static array-store and task-pool are kept allocated as long as there is at least one edit-mesh undo state.
  • An array-store is created for each struct size, as needed.
  • All arrays are stored in the array-store (vert/edge/loop/poly customdata, keyblocks and selection history).
  • Array-store and array-store thread can be disabled by ifdef's.

Memory use:

  • For reading a single undo step this doubles memory use (since it uses memory for the array-store and the expanded arrays).
  • For writing a single undo step the memory is moved into the array-store and freed along the way. So peak memory will only increase by the size of the largest array.
  • The array-stores themselves have some minimal overhead which isn't taken into account when printing statistics (states themselves, storage for chunks), none are very big and they use memory pools.
  • The data for each chunk don't use a memory pool. however their size is set to use the nearest power-of-two (taking guarded-alloc overhead into account), so they will use minimal slop-space.
  • While single peak memory usage for a single undo is higher, overall memory usage drops for many steps, though exact numbers depend a lot on the use-case. In own testing anywhere from 25% to 10% of the expanded memory use is quite common.

Performance:

  • Currently the compacting is done in a single, background thread, since it does add some lag and theres no reason this task needs to block.
  • The compacting its self could be multi-threaded however its not so slow and would complicate code.
  • There is potential to introduce user noticeable lag if the user either does 2x actions very fast (where adding the second undo state waits for the first to finish). Or when undo is called immediately after performing the action.
  • In practice, I don't think this is something users will notice, for example, a destructive edits on the dragon_adult.blend take around 0.02 seconds, non-destructive edit (dragging vertices/UV/weight-paint/selection changes) ~0.005 seconds (both in a background thread).
  • Expanding the array-store adds some overhead to each undo step, but not much since its just copying memory (~ 0.004 seconds on the dragon_adult.blend, for both destructive and non-destructive edits).

Diff Detail

Repository
rBS Blender Staging
Branch
temp-array-copy_on_write

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
  • Fix for overlap check
  • Added test for all sentences from words10k (test data).

More comprehensive tests

Check all words from 10k words, forward, backwards, and at different chunk sizes, split into words and sentences

  • Don't adjust users in bchunk_list_from_data_merge
  • Simplify check
  • Support chunk sizes of 1
  • Remove explicit tree structure
  • Add tests with different stride values, also optionally shuffle data based on a random seed
  • Use term chunk instead of block (was using both)
  • Add BLI_array_store_clear
Campbell Barton (campbellbarton) retitled this revision from Work in progress array-copy-on-write library to BLI_array_store: array-copy-on-write, array de-duplication library.May 25 2016, 7:47 AM
  • Fast-path for hashing bytes (avoid function call per byte)
  • Remove not-very-useful test

Use hash_array_from_data from hash_array_from_cref

Did only quick skim over the code, API looks good to me, simple and easy to use. Did you have time to make some tests with undo system already?

Re details, size limitation should be removed imho, though probably not top priority in practice. As for performance investigations, think would be nice to have already an idea how current lib behaves with undo first of all.

  • Use size_t for all offset values (should allow for >4gig arrays, but need to add a disabled-by-default gtest for this).

@Bastien Montagne (mont29), Yes, next step is to test this with editmesh undo.
Then some more tests to ensure complete code-coverage, though current tests are fairly comprehensive.

  • Fix bug using uninitialized memory hashing the last chunks that didnt have enough bytes
  • Initial undo support (as ifdef)
  • Correct user-count freeing for chunk-list
  • Add new test based on a bug with mesh undo
  • Correct ifdef, add paranoid check
  • Data was being written incorrectly, correct and add asserts
  • Tests Fail, need to check return value of validate
  • Initial undo support (as ifdef)
  • Add timer for packing, correct release build error
  • print undo memory saving
  • Print undo memory saved for a single step
  • Break out of searching for matching blocks once there is a mismatch
  • Add support for key-blocks, (completing initial editmesh undo support)
  • Split array_store_for_size in two, since when freeing we never need to create
  • More unique naming for parts of the undo api relating to array-store usage
  • Compact undo step in a background thread

(updated main description with details)

  • Optimize chunk-count for power-of-two allocations
  • Expand array-store into the mesh before freeing so we don't attempt to free an invalid mesh, and free any allocations within the custom-data.
  • Assume reference customdata is aligned with current, only do full lookup when its not
  • Remove test, turns out this wasn't the cause of a bug afterall, and isn't worth keeping
  • Remove redundant MIN2
  • Fix missing ChunkRef free & simplify user-reference count
  • Add user-count validation
  • Add checks for unreachable memory
  • Fix memcpy commands
  • Add test for random data, where minor modifications are made each step
Bastien Montagne (mont29) edited edge metadata.

Only did quick read, but code lgtm. Nice improvement on mem usage. :)

This revision is now accepted and ready to land.May 29 2016, 4:54 PM
Campbell Barton (campbellbarton) edited edge metadata.
  • Add NULL check, needed in rare cases
  • Correct check for aligned chunks
  • Add test to check chunk de-duplication is working
  • Quiet warnings in debug mode
  • Quiet warnings w/ test
  • Comments and cleanup