CODEWITHSUNDEEP
c++performancememory-managementheap-memory
bofjas
bofjas

Reputation: 1206

Why recursive memory deallocation so slow?

I've made a Octree to match 3 dimensional points fast. And it is fast! However, deleting the octree takes 100 folds more time than building it. I don't understand why this is happening. This is my class:

#pragma once
#include "LeakCheck.h"
#include "vec3.h"

namespace Geometry 
{

static const float tolerance = 1.0e-30f;

class VertexOctree
{
private:
    float halfSize;
    vec3 center;
    VertexOctree *subTrees;
    int vertexIndex;
    void CreateSubTree()
    {
        subTrees = news VertexOctree[8];
        subTrees[0] = VertexOctree(center+(vec3(-1.0f,-1.0f,-1.0f)*halfSize),halfSize*0.5f);
        subTrees[1] = VertexOctree(center+(vec3(+1.0f,-1.0f,-1.0f)*halfSize),halfSize*0.5f);
        subTrees[2] = VertexOctree(center+(vec3(-1.0f,+1.0f,-1.0f)*halfSize),halfSize*0.5f);
        subTrees[3] = VertexOctree(center+(vec3(+1.0f,+1.0f,-1.0f)*halfSize),halfSize*0.5f);
        subTrees[4] = VertexOctree(center+(vec3(-1.0f,-1.0f,+1.0f)*halfSize),halfSize*0.5f);
        subTrees[5] = VertexOctree(center+(vec3(+1.0f,-1.0f,+1.0f)*halfSize),halfSize*0.5f);
        subTrees[6] = VertexOctree(center+(vec3(-1.0f,+1.0f,+1.0f)*halfSize),halfSize*0.5f);
        subTrees[7] = VertexOctree(center+(vec3(+1.0f,+1.0f,+1.0f)*halfSize),halfSize*0.5f);
    }
public:
    int AddVertex(std::vector<vec3> &VertexList, const vec3& Point)
    {
        if (vertexIndex == -1) {
            vertexIndex = VertexList.size();
            VertexList.push_back(Point);
            return vertexIndex;
        }
        if ((VertexList[vertexIndex]-Point).lengthSq() < tolerance) {
            return vertexIndex;
        }
        if (subTrees == NULL)
            CreateSubTree();

        return subTrees[(Point.x>center.x)+(2*(Point.y>center.y))+(4*(Point.z>center.z))].AddVertex(VertexList, Point);
    }
    VertexOctree()
    {
        subTrees = NULL;
        vertexIndex = -1;
    }
    VertexOctree(vec3 Center, float HalfSize)
    {
        subTrees = NULL;
        center = Center;
        halfSize = HalfSize;
        vertexIndex = -1;
    }
    ~VertexOctree()
    {
        if (subTrees)
            delete[] subTrees;
    }
};

};

When deleting a VertexOctree it takes a LONG time. Much longer than creating the trees which also has to do floating point operations to compare points and allocate the memory. Why is it so slow to delete it? I use Visual Studio 2012 and compile in release mode.

Upvotes: 3

Views: 856

Answers (1)

Neil Kirk
Neil Kirk

Reputation: 21803

When you press F5 to run your program, it uses a special, slower debug heap, even in release mode. If you press ctrl+F5, it uses the regular heap, even in debug mode. Try that and if it speeds it up, then in your project's debugging properties, in the environment box put _NO_DEBUG_HEAP=1 to always use the fast heap.

Upvotes: 4

Related Questions