Page MenuHome

Fix T78296: Performance - Use Binary Search for MDeformWeight
Needs ReviewPublic

Authored by Jeroen Bakker (jbakker) on Fri, Jun 26, 12:23 PM.

Details

Summary

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.

Diff Detail

Repository
rB Blender
Branch
arcpatch-D8127 (branched from master)
Build Status
Buildable 8744
Build 8744: arc lint + arc unit

Event Timeline

Jeroen Bakker (jbakker) requested review of this revision.Fri, Jun 26, 12:23 PM
Jeroen Bakker (jbakker) created this revision.

Removed unneeded whiteline

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
764

dvert->dw may be null.
qsort does not explicity allow this, even if most implementations do.

774

I'd prefer array indexing.

838

This shifts the array, right?
Shouldn't it be memmove then?

Jeroen Bakker (jbakker) planned changes to this revision.Fri, Jun 26, 3:00 PM
Jeroen Bakker (jbakker) marked 3 inline comments as done.

Ah yes your right ->def_nr = gives some more results.

source/blender/blenkernel/intern/deform.c
774

Seems MSVC is able to generate the correct code for this as well so will do your preferred way.

Jeroen Bakker (jbakker) marked an inline comment as done.Fri, Jun 26, 3:00 PM
Jeroen Bakker (jbakker) planned changes to this revision.Fri, Jun 26, 3:04 PM
Harbormaster completed remote builds in B8728: Diff 26309.
Jeroen Bakker (jbakker) retitled this revision from Fix T78296: MDeformWeight performance to Fix T78296: Performance - Use Binary Search for MDeformWeight.Mon, Jun 29, 9:14 AM

add sorting to places that changed def_nr directly