| Age | Commit message (Collapse) | Author |
|---|
|
|
|
|
|
- When returning the number of items in a collection use BLI_*_len()
- Keep _size() for size in bytes.
- Keep _count() for data structures that don't store length
(hint this isn't a simple getter).
See P611 to apply instead of manually resolving conflicts.
|
|
Also some re-indenting.
|
|
|
|
Useful when ghash keys are reallocated.
|
|
|
|
Those are not depsgraph or C++ specific and can be used by everyone.
|
|
This way everyone can benefit from it, not only dependency graph.
|
|
This is an alternative to passing a copy callback which is some times inconvenient.
Instead the caller can write to the key - needed when the key is duplicated memory.
Allows for minor optimization in ghash/gset use.
Also add BLI_gset_ensure_p_ex
|
|
Behavior is similar to python's set.pop(), it removes and returns a 'random' entry from the hash.
Notes:
* Popping will return items in same order as ghash/gset iterators (i.e. increasing
order in internal buckets-based storage), unless ghash/gset is modified in between.
* We are keeping a track of the latest bucket we popped out (through a 'state' parameter),
this allows for similar performances to iterators when iteratively popping a whole hash
(without it, we are roughly O(n!), with it we are roughly O(n)...).
Reviewers: campbellbarton
Differential Revision: https://developer.blender.org/D1808
|
|
Keep index using the outer scope for GHASH iter macros,
while its often nice, in some cases to declare in the for loop,
it means you cant use as a counter after the loop exits, and in some cases signed/unsigned may matter.
API changes should really be split off in their own commits too.
|
|
GPU_buffer no longer has a fallback to client vertex arrays, so remove
comments about it.
Changed a few internal structs/function interfaces to use bool where
appropriate.
Use for-loop scope and flexible declaration placement. PBVH does the
same thing but needs ~150 fewer lines to do it!
The change to BLI_ghashIterator_init is admittedly hackish but makes
GHASH_ITER_INDEX nicer to use.
|
|
|
|
|
|
Needed in cases where the memory from each key is owned by the GHash.
|
|
|
|
Was using pointer hashing when the keys are in fact uint's.
Since they're well distributed from the rangetree,
no need to do bit-shifting tricks. just use int as hash.
Gives ~8% speedup in own tests.
|
|
|
|
utils to API.
This patch is the root of the GHash rework, all other diff will be based on it:
Reduce average load from 3.0 to 0.75
----------------------------------
This is the big performance booster part, e.g. makes tracing a dyntopo stroke between 25% and 30% faster.
Not much to say about it, aside that it obviously increase memory footprint (about 25% - 30% too).
Add optional shrinking
----------------------------------
I.e. ghashes/gsets can now shrink their buckets array when you remove enough entries. This remains optional and OFF by default.
Add code to use masking instead of modulo
----------------------------------
Buckets indices are obtained from hashes by “reducing” the hash value into the valid bucket range. This can be done either by bit-masking, or using modulo operation.
The former is quicker, but requires real hashes, while the later is slower (average 10% impact on ghash operations) but can also be used as a 'fake' hashing on raw values, like e.g. indices.
In Blender currently not all ghash usages actually hash their keys, so we stick to modulo for now (masking is ifdef’ed out), we may however investigate the benefits of switching to masking with systematic very basic hashing later…
Add various missing API helpers
----------------------------------
I.e. a way to deep-copy a ghash/gset, and a way to (re-)reserve entries (i.e. manually grow or shrink the ghash after its creation).
Various code refactoring
----------------------------------
* Get rid of the 'hack' regarding ghash size when used as gset (it’s simpler and safer to have two structs defined here, and cast pointers as needed).
* Various re-shuffle and factorization in low-level internal code.
* Some work on hashing helpers, introducing some murmur2a-based hashing too.
Thanks a bunch to Campbell for the extensive review work. :)
Reviewers: sergey, campbellbarton
Subscribers: psy-fi, lukastoenne
Projects: #bf_blender
Maniphest Tasks: T43766
Differential Revision: https://developer.blender.org/D1178
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Can use to check on improvements to hash functions.
|
|
- ensure GET_INT_FROM_POINTER us only used to get values
- rename STACK_POP_ELSE -> STACK_POP_DEFAULT
|
|
also rename BLI_edgeset_reinsert -> BLI_edgeset_add, in this case its the same.
|
|
Returns a fallback argument when the key isn't found.
|
|
|
|
- BLI_ghashutil_strhash_n takes string length, to avoid terminating the string before hashing.
- BLI_ghashutil_inthash/uinthash take ints, to avoid casting to (void *)
This also showed up incorrect use of inthash, which was using a pointer.
|
|
also remove NULL check, only a few areas made use of this.
|
|
|
|
|
|
takes a key as an arg and isnt popping any element from the hash as you might expect).
add BLI_pophead/tail, since getting the first element from a list and removing it is a common task.
|
|
internally without allocating space for the value).
|
|
|
|
|
|
to try save a few bytes here.
|
|
reserve argument.
|
|
the hash as an arg (avoids resizing in simple cases when the hash is created and filled immediately).
|
|
In previous optimization in outliner I assumed that order in treehash was not important.
But testing outliner in datablocks mode revealed a problem: when user expands multiple recursive levels and then closes any element, it always closed the top level of recursion.
Now it should work fine with recursive trees.
Now treehash contains groups of elements indexed by (id,nr,type). Adding an element with the same (id,nr,type) results in appending it to existing group. No duplicates are possible in treehash.
This commit should also make lookups a little bit faster, because searching in small arrays by "used" is faster than searching in hashtable with duplicates by "id,nr,type,used".
|
|
|
|
avoids remove,insert and only hashes the key once.
|
|
- use single inlined lookup function.
- move comments into source.
- pack iterator vars more efficiently.
|
|
ghash/edgehash.
the outliner does this intentionally, so add a flag to allow this situation optionally.
|
|
|
|
|
|
also added the underlying subdivision as a standalone operator in the edge menu, named: subdivide edge-ring.
http://www.graphicall.org/ftp/ideasman42/bridge_subd.png
|
