Use binary search for querying deform weights.
Spring 02_020_A.anim.blend on Ryzen 1700X goes from 12.4 to 12.7fps.
During profiling it was detected that adding new items to the head was faster than adding to the tail.
Details
Details
Diff Detail
Diff Detail
- Repository
- rB Blender
- Branch
- T78296-mdeformweight-binsearch (branched from master)
- Build Status
Buildable 8720 Build 8720: arc lint + arc unit
Event Timeline
Comment Actions
This is not a finished implementation, right?
I believe there are multiple other places, where def_nr is changed, which would destroy the sorting.
| source/blender/blenkernel/intern/deform.c | ||
|---|---|---|
| 724 | dvert->dw may be null. | |
| 734 | I'd prefer array indexing. | |
| 829 | This shifts the array, right? | |
Comment Actions
Ah yes your right ->def_nr = gives some more results.
| source/blender/blenkernel/intern/deform.c | ||
|---|---|---|
| 734 | Seems MSVC is able to generate the correct code for this as well so will do your preferred way. | |
Comment Actions
Generally looks good.
- We should assert when the groups aren't sorted - see: P1520.
- There are a some places I think sorting may still be needed. layerInterp_mdeformvert, BKE_object_defgroup_index_map_apply, if sorting isn't needed for either of these - there should be an explanation of why since it's not obvious.
- We could make BKE_mesh_validate sort the groups, not urgent though.
- The comment above MDeformWeight.def_nr in the header should note that this is expected to be sorted.
- There could be a fast-path for adding a single group to an existing, sorted array.
Comment Actions
Comments from code review
- We should assert when the groups aren't sorted
- Added sorting to layerInterp_mdeformvert, BKE_object_defgroup_index_map_apply they change def_nr and should be sorted again.
- Added comment of sorting in DNA.