BaseLinkArray's append is too slow

On 21/06/2016 at 02:34, xxxxxxxx wrote:

User Information:
Cinema 4D Version:   R17 
Platform:   Windows  ;   
Language(s) :     C++  ;

---------
Hello.

When I'm about to render in my engine, I have to parse the hierarchy and store some data in stacks.
I also need the object pointers to the original hierarchy nodes, so  I use a BaseLinkArray as stack.

For each child in the hierarchy, I call Append (....) and after the child's children have been processed, I call Remove( GetCounter() - 1).

So, on hierarchy traversal, this data structure starts and ends with 0 objects and the number of appends is exactly the same with the number of removes.

The problem is that this data structure is very slow. In a scene with 10k nodes, the Append call takes 8 seconds (CPU i7-5820k).

Is there anything I can do to make BaseLinkArray work faster ? (Maybe preallocating the baselink memory? )
The other solution would be to create my own structure that handles BaseLink's memory more efficiently by allocating and deleting them all together.

Would that be faster ?

Thank you.

On 21/06/2016 at 05:36, xxxxxxxx wrote:

Howdy,

Just out of curiosity, why do you call Remove()? Could you simply process all of the objects and then call Free() at the end?

Adios,
Cactus Dan

On 21/06/2016 at 11:48, xxxxxxxx wrote:

Originally posted by xxxxxxxx

<ADDRESS>
User Information:
Cinema 4D Version:   R17 
Platform:   Windows  ;   
Language(s) :    
C++  ;

---------
</ADDRESS>

Hello.
When I'm about to render in my engine, I have to parse the hierarchy and store some data in stacks.
<span style="line-height: 16.8px;">I also need the object pointers to the original hierarchy nodes, so  I use a BaseLinkArray as stack.</span>
For each child in the hierarchy, I call Append (....) and after the child's children have been processed, I call Remove( GetCounter() - 1). 
So, on hierarchy traversal, this data structure starts and ends with 0 objects and the number of appends is exactly the same with the number of removes.
The problem is that this data structure is very slow. In a scene with 10k nodes, the Append call takes 8 seconds (CPU i7-5820k). 
Is there anything I can do to make BaseLinkArray work faster ? (Maybe preallocating the baselink memory? )
The other solution would be to create my own structure that handles BaseLink's memory more efficiently by allocating and deleting them all together.
Would that be faster ?
Thank you.

Assuming the timing is based on release code and not debug, I guess your problem isn't due to the append speed of the underlying array or the memory allocation (for that array size all append op. + memory allocations should need less than 600 microseconds), but due to the SetLink() operation that 's called and needed internally for any link goal you add. I'd suggest profiling it to be sure ...

Best regards,

Wilfried

On 21/06/2016 at 11:57, xxxxxxxx wrote:

Unless you're dealing with arbitrary code execution between two stages of the processing that could
potentially free existing nodes, you can use a normal BaseArray that contains BaseObject* (or the like)
pointers (and not BaseLinks). BaseLinks are slow and only necessary when you can't be sure whether
a node is still alive at the point you want to access it.

On 22/06/2016 at 01:32, xxxxxxxx wrote:

Thank you all for your answer.

@wbeh Indeed it seems alloc or free don't cause too much problem and the real issue is the SetLink that is unavoidable.

@NiklasR That is exactly the reason why I use BaseLinkArray. Because in a later time after hierarchy processing, I am not sure if the objects are still alive.