Irrlicht Engine

This change reduces memory allocations afterwards from 2.4GB to 1.2GB and everything works well after cycle testing during hours.
I also free the keeptriangles using clear after the memcpy to protect system memory from running out on big meshes.
The mesh alone used in testing takes 380 MB.

Yeah, the set_used will create the memory again. It kinda does something similar like the change I proposed would have done. Except you add a few more re-allocations, but as long as it's not costing you too much time when creating the octree it will be fine.

You don't need the KeepTriangles.clear() by the way - it won't make a difference.
edit: yeah - might reduce intermediate memory usage somewhat - just no difference in the endresult.

So how would you do it, with greater efficiency?

With the line of code I posted earlier. That will only resize the array once at the end.

Reallocate it first, then memcpy, that's what my code does.

The difference is that my code can be at the end of the function. And only be called once.

But the array becomes massive consuming more memory than needed, and for large meshes even exhausting all available memory.

Also reallocate copies all the old and redundant data very inefficiently, whereas clear and set are much faster.

Look at reallocate:


//! Reallocates the array, make it bigger or smaller.
/** \param new_size New size of array. */
00063 void reallocate(u32 new_size)
{
T* old_data = data;

data = allocator.allocate(new_size); //new T[new_size];
allocated = new_size;

// copy old data
s32 end = used < new_size ? used : new_size;

for (s32 i=0; i<end; ++i)
{
// data = old_data;
allocator.construct(&data, old_data);
}

// destruct old data
for (u32 j=0; j<used; ++j)
allocator.destruct(&old_data[j]);

if (allocated < used)
used = allocated;

allocator.deallocate(old_data); //delete [] old_data;
}

reallocate shouldn't be slower (and it would only be called once instead of 8 times).
Memory inside constructOctree will indeed get larger in between when it only cleans up at the end instead of after creating each node. Only end-result would be the same.

Anyway - best solution regarding memory - and avoiding all re-allocation for triangles would be to rewrite it to work with a single array. And all nodes just have range-indices into that array. Wouldn't even be that hard to write. Basically needs a sort function returning numbers for the octet they are in (like 0 for hitting several and 1-8 for some of the others). And that recursively again. But as usual the real work here is not in writing the code but in testing (aka - figuring out test-cases that give realistic speed-comparisons for real situations - and mainly of interest is certainly getTriangles speed and not creation and that might change, thought without profiling I wouldn't even guess if the effect would be positive or negative as there are arguments for both).

Fine if your meshes are small.

Why create another triangle buffer at all, the indices could index directly into the smesh buffers, just add a word in the indices array to indicate sub buffer.

Hm, can't avoid the copy as you need the sorting. One could use sorted indices, but I guess you wouldn't really save much that way.

In the copy in iarray, can't parallel_for be used if the array is larger than a few hundred elements, get those other core working?

Different topic really :-)

Of course, just an idea, as would be an easy boost to employ

Did you ever try if that's really faster? And by try I mean - did you measure it? I didn't so far (I'm not really interested that much in compiler specific stuff usually as that kind of libs tend to get replaced with cross-platform libs). Given how good processors are in processing vectors my first guess would be that this is one of the cases where things would be somewhat tricky to improve easily by processing it parallel. But my knowledge of how multiple cores access shared memory and how caches are handled in that case is somewhat shallow. Guess I should read up on things like hyperthreading some day.