[Bf-committers] Faster listbase lookups

[Campbell Barton]

Hey Ed,

a Hash table could be an interesting way to do name lookups, and worth 
researching...

one way to speed up object operations is to have a way to know if an 
object is in the current scene or not
getting the base for an object also takes a fair ammount of time,

I think is to make objects link back to their last used scene and base-
so an object would have  a Base* and a Scene* added to the struct,

Heres how it would work
* on initializing or changing a scenes, ob->scene and ob->base would be 
set to that scene, and its base in that scnen.
* when removing an object from the current scene ob->scene and ob->base 
would be set to NULL

So you could always know, without a loop
* is the object in the current scene
* the object base in the active scene (if above is true)

At worst, you wont know weather the object is in a scene other then the 
active scene, but thats only if the object is in more then 1 scene at a 
time.
in that case youd still need to to a full loop but In my experience, 
objects used in multiple scenes is useually limited to a smaller number 
and most lookups deal with the active scenes.




Ed Halley wrote:
>
> Hrm, this sounds a lot like the complaints I raised in December of 
> last year, in that the O(n) searches in lists was really getting 
> unworkable at about n = 5000 ~ 6000.  I think the real solution is to 
> find O(log n) searches where possible, even if this requires a heavier 
> data structure.  Not all of the searches can be improved, but many 
> searches seemed to be to find single things by name, which is a 
> classic case where a hashtable (like Python dicts) wins.
>
> On Oct 21, 2006, at 8:33 AM, Campbell Barton wrote:
>
>> Hey Guys
>>
>> Iv been using scenes with a large number of objects recently, - 
>> groups and scnene-sets has helped me bring object counts down from 
>> 50,000 to about ~5000 per scene but even with 5000 objects, it can 
>> still be noticeably slow to duplicate, parent and unparent objects. - 
>> a few seconds.,
>>
>> My understanding of threads is limited, but I was thinking
>> one thing that could improve performance on large ListBases is a way 
>> to thread ListBase searches so 2 threads would search starting at 
>> each end of the listBase and check up with (eachother every ~50 or so 
>> iterations to see if they have found the item thats being searched for)
>>
>> Im not sure weather youd want this all the time, because it could be 
>> slower for smaller listbases, but in that case it may be woth the 
>> small slowdown....
>>
>> Talking to Emil, he thaught it would be possible.
>>
>> first Id like to know what others think, then if thats ok, if anyone 
>> would like to do this (would be a paid job).
>>
>> - Cam
>>
>> -- 
>> Campbell J Barton
>>
>> 133 Hope Street
>> Geelong West, Victoria 3218 Australia
>>
>> URL:    http://www.metavr.com
>> e-mail: cbarton at metavr.com
>> phone: AU (03) 5229 0241
>>
>> _______________________________________________
>> Bf-committers mailing list
>> Bf-committers at projects.blender.org
>> http://projects.blender.org/mailman/listinfo/bf-committers
>>
>>
>
> -- 
> [ e d @ h a l l e y . c c ]
>
>
>
>
> _______________________________________________
> Bf-committers mailing list
> Bf-committers at projects.blender.org
> http://projects.blender.org/mailman/listinfo/bf-committers
>


-- 
Campbell J Barton

133 Hope Street
Geelong West, Victoria 3218 Australia

URL:    http://www.metavr.com
e-mail: cbarton at metavr.com
phone: AU (03) 5229 0241