[Bf-committers] performance variation of BKE_add_object function

[Tamito KAJIYAMA]

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>