[Bf-committers] performance variation of BKE_add_object function

[Joshua Leung]

Hi Tamito,

Looks like I missed one other thing in new_id():  check_for_dupid().
Just like the list sorting, it starts by going through the list of
objects at least once to check for duplicate names, and potentially
repeats this process a number of times until all conflicts have been
resolved.

>From the looks of things, it looks to me like it might be worth trying
to create the Blender Internal datastructures directly (i.e. like
convertblender.c does). Sure, this probably does end up coupling the
Freestyle module to the BI internals, but given that you're
practically just creating geometry and assigning some fixed material
properties to these, and then rendering all of this using BI, it might
not be that bad. Brecht might have some better suggestions along these
lines though :)

Regards,
Joshua

On Sun, Oct 7, 2012 at 4:00 AM, Tamito KAJIYAMA
<rd6t-kjym at asahi-net.or.jp> wrote:
> Hi Joshua,
>
> Thanks a lot for the performance analysis of BKE_object_add function.
> That helped me understand the slowness and come up with a temporary
> performance fix.
>
> The Freestyle branch concerns the rendering of 2D storkes (e.g., silhouette and
> crease lines) automatically generated from a given 3D scene and superimposed
> on top of the Combined pass.  For this purpose, a temporary scene populated
> by mesh data representing the 2D strokes is created and rendered with the
> Blender Internal (BI).
>
> Actually individual strokes are translated into distinct mesh objects, resulting
> in a large number of mesh objects.  Freestyle relies on vertex colors and alpha
> transparency, but does not require advanced stuff like modifiers and animation
> functionalities.  Hence I fully agree that for this specific purpose, full Blender
> objects are too heavy and a lightweight representation of 2D strokes would be
> more appropriate.  An option previously considered was to employ an external
> D graphics library for stroke rendering.  There are several reasons why the BI
> was chosen (less dependency on external libraries, native support of color
> management, full sample anti-aliasing, and so forth), but this is a matter of
> future development.
>
> For now, I made an attempt to improve the performance of temporary scene
> generation in the Freestyle branch revision 51114.
> http://lists.blender.org/pipermail/bf-blender-cvs/2012-October/050283.html
> The implemented solution is directly based on the results of your performance
> analysis on BKE_object_add function.  Specifically, the object and mesh names
> are generated so that id_sort_by_name() will terminate in the very beginning
> of sorting.  In addition, object selection was suppressed, since the temporary
> scene is never manipulated by users.
>
> The following plot shows the performance of the implemented solution.
> http://freestyleintegration.files.wordpress.com/2012/10/add_object_perf_fix.png
> Now the average time per mesh object is 15 times shorter than the previous
> timing result.  Still it can be seen that the elapsed time per mesh object tends to
> increase over time.  The function is_dupid (called from new_id -> check_for_dupid)
> goes through all the objects in the scene.  This should be a cause of the slowness.
> Additionally, there is some non-linear time component, which I have no idea at
> the moment and needs further performance analysis.
>
> Another possible direction toward better performance is to reduce the number
> of generated mesh objects.  Combining multiple strokes into one mesh object
> (resulting in many islands) is okay as long as the number of vertices, edges, faces
> and so on does not exceed the upper limits.
>
> That's it for now.  Any further comments and suggestions are of great help.
>
> Regards,
>
> --
> KAJIYAMA, Tamito <rd6t-kjym at asahi-net.or.jp>
>
> -----Original Message-----
> From: Joshua Leung
> Sent: Saturday, October 06, 2012 1:22 AM
> To: bf-blender developers
> Subject: Re: [Bf-committers] performance variation of BKE_add_object function
>
> Hi,
>
> Interesting results, especially those jumps after 1000 and 10000.
> First time I've seen this plotted out.
>
> There seem to be two sources of slowness (without actually profiling
> to confirm):
> 1) BKE_libblock_alloc() will sort the objects so that the newly added
> object is now in alphabetical order relative to the other objects in
> the db. (Actually, it is new_id() -> id_sort_by_name() which does
> this, which does an insertion sort O(n))
>
> 2) BKE_scene_base_deselect_all() needs to go over all items in scene -
> O(m). If all your objects are in the same scene, then m=n.
>
> Now, especially with regards to point 1, this applies to every
> datablock in Blender. This means, it really isn't that nice to go
> around heaps and heaps of these, especially not in any time critical
> loops. Furthermore, creating full "Blender Objects" for quick
> throwaway helpers during rendering (I'm only guessing here) seems
> quite wasteful, as they're not exactly that lightweight and will hang
> around for the rest of the session. Unless there are some capabilities
> provided by Blender Objects (i.e. modifiers, constraints, derivedmesh,
> etc.) that you really need, perhaps it might be worth considering
> checking out a more lightweight approach akin to DupliObjects or so.
>
> Regards,
> Joshua
>
> On Sat, Oct 6, 2012 at 11:07 AM, Tamito KAJIYAMA
> <rd6t-kjym at asahi-net.or.jp> wrote:
>> Hi,
>>
>> BKE_add_object function displays an appreciable performance decrease as the number
>> of objects increases.  The following plot shows the elapsed time per call of the function
>> over 11692 objects successively generated (r50956, Windows Vista 64 bit, VS 2008 64 bit).
>> http://freestyleintegration.files.wordpress.com/2012/10/add_object_perf.png
>> The average time per call is 7.565e-3 seconds, but the time tends to increase over time,
>> with some sudden decreases (e.g., at the calls around the 1000th and 10000th objects).
>> This performance variation effect is quite visible in the Freestyle branch, where a large
>> number of temporary objects are automatically generated for stroke rendering.
>> Any thoughts and suggestions concerning this issue are much appreciated.
>>
>> Regards,
>>
>> --
>> KAJIYAMA, Tamito <rd6t-kjym at asahi-net.or.jp>
> _______________________________________________
> Bf-committers mailing list
> Bf-committers at blender.org
> http://lists.blender.org/mailman/listinfo/bf-committers