为什么free()会阻止我的程序？

Question

我正在使用free来释放在递归函数中为一堆临时数组分配的内存.我会发布代码,但它很长.当我注释掉这些free()调用时,程序运行不到一秒钟.但是,当我使用它们时,程序运行大约需要20秒.为什么会发生这种情况,如何解决？这就像100左右的MB所以我宁愿不要只留下内存泄漏.

此外,当我运行包含所有启用了性能分析的free()调用的程序时,它会在不到一秒的时间内运行.我不知道这会产生什么影响,但确实如此.

在仅使用一些free()调用之后,似乎有一些特别会导致程序变慢.其余的似乎没有效果.

好的......这是所要求的代码:

void KDTree::BuildBranch(int height, Mailbox** objs, int nObjects)
{
int dnObjects = nObjects * 2;
int dnmoObjects = dnObjects - 1;

//Check for termination
if(height == -1 || nObjects < minObjectsPerNode)
{
    //Create leaf
    tree[nodeIndex] = KDTreeNode();

    if(nObjects == 1)
        tree[nodeIndex].InitializeLeaf(objs[0], 1);
    else
        tree[nodeIndex].InitializeLeaf(objs, nObjects);

    //Added a node, increment index
    nodeIndex++;

    return;
}

//Save this node's index and increment the current index to save space for this node
int thisNodeIndex = nodeIndex;
nodeIndex++;

//Allocate memory for split options
float* xMins = (float*)malloc(nObjects * sizeof(float));
float* yMins = (float*)malloc(nObjects * sizeof(float));
float* zMins = (float*)malloc(nObjects * sizeof(float));
float* xMaxs = (float*)malloc(nObjects * sizeof(float));
float* yMaxs = (float*)malloc(nObjects * sizeof(float));
float* zMaxs = (float*)malloc(nObjects * sizeof(float));

//Find all possible split locations
int index = 0;
BoundingBox* tempBox = new BoundingBox();
for(int i = 0; i < nObjects; i++)
{
    //Get bounding box
    objs[i]->prim->MakeBoundingBox(tempBox);

    //Add mins to split lists
    xMins[index] = tempBox->x0;
    yMins[index] = tempBox->y0;
    zMins[index] = tempBox->z0;

    //Add maxs
    xMaxs[index] = tempBox->x1;
    yMaxs[index] = tempBox->y1;
    zMaxs[index] = tempBox->z1;
    index++;
}

//Sort lists
Util::sortFloats(xMins, nObjects);
Util::sortFloats(yMins, nObjects);
Util::sortFloats(zMins, nObjects);
Util::sortFloats(xMaxs, nObjects);
Util::sortFloats(yMaxs, nObjects);
Util::sortFloats(zMaxs, nObjects);

//Allocate bin lists
Bin* xLeft = (Bin*)malloc(dnObjects * sizeof(Bin));
Bin* xRight = (Bin*)malloc(dnObjects * sizeof(Bin));
Bin* yLeft = (Bin*)malloc(dnObjects * sizeof(Bin));
Bin* yRight = (Bin*)malloc(dnObjects * sizeof(Bin));
Bin* zLeft = (Bin*)malloc(dnObjects * sizeof(Bin));
Bin* zRight = (Bin*)malloc(dnObjects * sizeof(Bin));

//Initialize all bins
for(int i = 0; i < dnObjects; i++)
{
    xLeft[i] = Bin(0, 0.0f);
    xRight[i] = Bin(0, 0.0f);
    yLeft[i] = Bin(0, 0.0f);
    yRight[i] = Bin(0, 0.0f);
    zLeft[i] = Bin(0, 0.0f);
    zRight[i] = Bin(0, 0.0f);
}

//Construct min and max bins bins from split locations
//Merge min/max lists together for each axis
int minIndex = 0, maxIndex = 0;
for(int i = 0; i < dnObjects; i++)
{
    if(maxIndex == nObjects || (xMins[minIndex] <= xMaxs[maxIndex] && minIndex != nObjects))
    {
        //Add split location to both bin lists
        xLeft[i].rightEdge = xMins[minIndex];
        xRight[i].rightEdge = xMins[minIndex];
        //Add geometry to mins counter
        xLeft[i+1].objectBoundCounter++;

        minIndex++;
    }
    else
    {
        //Add split location to both bin lists
        xLeft[i].rightEdge = xMaxs[maxIndex];
        xRight[i].rightEdge = xMaxs[maxIndex];
        //Add geometry to maxs counter
        xRight[i].objectBoundCounter++;

        maxIndex++;
    }
}

//Repeat for y axis
minIndex = 0, maxIndex = 0;
for(int i = 0; i < dnObjects; i++)
{
    if(maxIndex == nObjects || (yMins[minIndex] <= yMaxs[maxIndex] && minIndex != nObjects))
    {
        //Add split location to both bin lists
        yLeft[i].rightEdge = yMins[minIndex];
        yRight[i].rightEdge = yMins[minIndex];
        //Add geometry to mins counter
        yLeft[i+1].objectBoundCounter++;

        minIndex++;
    }
    else
    {
        //Add split location to both bin lists
        yLeft[i].rightEdge = yMaxs[maxIndex];
        yRight[i].rightEdge = yMaxs[maxIndex];
        //Add geometry to maxs counter
        yRight[i].objectBoundCounter++;

        maxIndex++;
    }
}

//Repeat for z axis
minIndex = 0, maxIndex = 0;
for(int i = 0; i < dnObjects; i++)
{
    if(maxIndex == nObjects || (zMins[minIndex] <= zMaxs[maxIndex] && minIndex != nObjects))
    {
        //Add split location to both bin lists
        zLeft[i].rightEdge = zMins[minIndex];
        zRight[i].rightEdge = zMins[minIndex];
        //Add geometry to mins counter
        zLeft[i+1].objectBoundCounter++;

        minIndex++;
    }
    else
    {
        //Add split location to both bin lists
        zLeft[i].rightEdge = zMaxs[maxIndex];
        zRight[i].rightEdge = zMaxs[maxIndex];
        //Add geometry to maxs counter
        zRight[i].objectBoundCounter++;

        maxIndex++;
    }
}

//Free split memory
free(xMins);
free(xMaxs);
free(yMins);
free(yMaxs);
free(zMins);
free(zMaxs);

//PreCalcs
float voxelL = xRight[dnmoObjects].rightEdge - xLeft[0].rightEdge;
float voxelD = zRight[dnmoObjects].rightEdge - zLeft[0].rightEdge;
float voxelH = yRight[dnmoObjects].rightEdge - yLeft[0].rightEdge;

float voxelSA = 2.0f * voxelL * voxelD + 2.0f * voxelL * voxelH + 2.0f * voxelD * voxelH;

//Minimum cost preset to no split at all
float minCost = (float)nObjects;
float splitLoc;
int minLeftCounter = 0, minRightCounter = 0;
int axis = -1;

 //---------------------------------------------------------------------------------------------
//Check costs of x-axis split planes keeping track of derivative using
//the fact that there is a minimum point on the graph costs vs split location
//Since there is one object per split plane
int splitIndex = 1;
float lastCost = nObjects * voxelL;
float tempCost;
float lastSplit = xLeft[1].rightEdge;
int leftCount = xLeft[1].objectBoundCounter, rightCount = nObjects - xRight[1].objectBoundCounter;
int lastLO = 0, lastRO = nObjects;
//Keep looping while cost is decreasing
while(splitIndex < dnObjects)
{
    tempCost = leftCount * (xLeft[splitIndex].rightEdge - xLeft[0].rightEdge) + rightCount * (xLeft[dnmoObjects].rightEdge - xLeft[splitIndex].rightEdge);
    if(tempCost < lastCost)
    {
        lastCost = tempCost;
        lastSplit = xLeft[splitIndex].rightEdge;
        lastLO = leftCount;
        lastRO = rightCount;
    }

    //Update counters
    splitIndex++;
    leftCount += xLeft[splitIndex].objectBoundCounter;
    rightCount -= xRight[splitIndex].objectBoundCounter;
}

//Calculate full SAH cost
lastCost = ((lastLO * (2 * (lastSplit - xLeft[0].rightEdge) * voxelD + 2 * (lastSplit - xLeft[0].rightEdge) * voxelH + 2 * voxelD * voxelH)) + (lastRO * (2 * (xLeft[dnmoObjects].rightEdge - lastSplit) * voxelD + 2 * (xLeft[dnmoObjects].rightEdge - lastSplit) * voxelH + 2 * voxelD * voxelH))) / voxelSA;

if(lastCost < minCost)
{
    minCost = lastCost;
    splitLoc = lastSplit;
    minLeftCounter = lastLO;
    minRightCounter = lastRO;
    axis = 0;
}

//---------------------------------------------------------------------------------------------
//Repeat for y axis
splitIndex = 1;
lastCost = nObjects * voxelH;
lastSplit = yLeft[1].rightEdge;
leftCount = yLeft[1].objectBoundCounter;
rightCount = nObjects - yRight[1].objectBoundCounter;
lastLO = 0;
lastRO = nObjects;
//Keep looping while cost is decreasing
while(splitIndex < dnObjects)
{
    tempCost = leftCount * (yLeft[splitIndex].rightEdge - yLeft[0].rightEdge) + rightCount * (yLeft[dnmoObjects].rightEdge - yLeft[splitIndex].rightEdge);
    if(tempCost < lastCost)
    {
        lastCost = tempCost;
        lastSplit = yLeft[splitIndex].rightEdge;
        lastLO = leftCount;
        lastRO = rightCount;
    }

    //Update counters
    splitIndex++;
    leftCount += yLeft[splitIndex].objectBoundCounter;
    rightCount -= yRight[splitIndex].objectBoundCounter;
}

//Calculate full SAH cost
lastCost = ((lastLO * (2 * (lastSplit - yLeft[0].rightEdge) * voxelD + 2 * (lastSplit - yLeft[0].rightEdge) * voxelL + 2 * voxelD * voxelL)) + (lastRO * (2 * (yLeft[dnmoObjects].rightEdge - lastSplit) * voxelD + 2 * (yLeft[dnmoObjects].rightEdge - lastSplit) * voxelL + 2 * voxelD * voxelL))) / voxelSA;

if(lastCost < minCost)
{
    minCost = lastCost;
    splitLoc = lastSplit;
    minLeftCounter = lastLO;
    minRightCounter = lastRO;
    axis = 1;
}

//---------------------------------------------------------------------------------------------
//Repeat for z axis
splitIndex = 1;
lastCost = nObjects * voxelD;
lastSplit = zLeft[1].rightEdge;
leftCount = zLeft[1].objectBoundCounter;
rightCount = nObjects - zRight[1].objectBoundCounter;
lastLO = 0;
lastRO = nObjects;
//Keep looping while cost is decreasing
while(splitIndex < dnObjects)
{
    tempCost = leftCount * (zLeft[splitIndex].rightEdge - zLeft[0].rightEdge) + rightCount * (zLeft[dnmoObjects].rightEdge - zLeft[splitIndex].rightEdge);
    if(tempCost < lastCost)
    {
        lastCost = tempCost;
        lastSplit = zLeft[splitIndex].rightEdge;
        lastLO = leftCount;
        lastRO = rightCount;
    }

    //Update counters
    splitIndex++;
    leftCount += zLeft[splitIndex].objectBoundCounter;
    rightCount -= zRight[splitIndex].objectBoundCounter;
}

//Calculate full SAH cost
lastCost = ((lastLO * (2 * (lastSplit - zLeft[0].rightEdge) * voxelL + 2 * (lastSplit - zLeft[0].rightEdge) * voxelH + 2 * voxelH * voxelL)) + (lastRO * (2 * (zLeft[dnmoObjects].rightEdge - lastSplit) * voxelL + 2 * (zLeft[dnmoObjects].rightEdge - lastSplit) * voxelH + 2 * voxelH * voxelL))) / voxelSA;

if(lastCost < minCost)
{
    minCost = lastCost;
    splitLoc = lastSplit;
    minLeftCounter = lastLO;
    minRightCounter = lastRO;
    axis = 2;
}

//Free bin memory
free(xLeft);
free(xRight);
free(yLeft);
free(yRight);
free(zLeft);
free(zRight);

//---------------------------------------------------------------------------------------------
//Make sure a split is in our best interest
if(axis == -1)
{
    //If not decrement the node counter
    nodeIndex--;
    BuildBranch(-1, objs, nObjects);

    return;
}

//Allocate space for left and right lists
Mailbox** leftList = (Mailbox**)malloc(minLeftCounter * sizeof(void*));
Mailbox** rightList = (Mailbox**)malloc(minRightCounter * sizeof(void*));

//Sort objects into lists of those to the left and right of the split plane
int leftIndex = 0, rightIndex = 0;
leftCount = 0;
rightCount = 0;
switch(axis)
{
case 0:
    for(int i = 0; i < nObjects; i++)
    {
        //Get object bounding box
        objs[i]->prim->MakeBoundingBox(tempBox);

        //Add to left and right lists when necessary
        if(tempBox->x0 < splitLoc)
        {
            leftList[leftIndex++] = objs[i];
            leftCount++;
        }

        if(tempBox->x1 > splitLoc)
        {
            rightList[rightIndex++] = objs[i];
            rightCount++;
        }
    }
    break;

case 1:
    for(int i = 0; i < nObjects; i++)
    {
        //Get object bounding box
        objs[i]->prim->MakeBoundingBox(tempBox);

        //Add to left and right lists when necessary
        if(tempBox->y0 < splitLoc)
        {
            leftList[leftIndex++] = objs[i];
            leftCount++;
        }

        if(tempBox->y1 > splitLoc)
        {
            rightList[rightIndex++] = objs[i];
            rightCount++;
        }

    }
    break;

case 2:
    for(int i = 0; i < nObjects; i++)
    {
        //Get object bounding box
        objs[i]->prim->MakeBoundingBox(tempBox);

        //Add to left and right lists when necessary
        if(tempBox->z0 < splitLoc)
        {
            leftList[leftIndex++] = objs[i];
            leftCount++;
        }

        if(tempBox->z1 > splitLoc)
        {
            rightList[rightIndex++] = objs[i];
            rightCount++;
        }

    }
    break;
};

//Delete the bounding box
delete tempBox;

//Delete old objects array
free(objs);

//Construct left and right branches
BuildBranch(height - 1, leftList, leftCount);
BuildBranch(height - 1, rightList, rightCount);

//Build this node
tree[thisNodeIndex] = KDTreeNode();
tree[thisNodeIndex].InitializeInterior(axis, splitLoc, nodeIndex - 1);

return;
}

编辑:好吧我试图用new/delete替换malloc/free,这对速度没有影响.我还发现只有xLeft/xRight数组上的free()似乎会显着影响执行时间.我能够通过在递归调用之后移动free()调用来消除这个问题,虽然我不知道为什么这会产生影响,因为我没有看到任何地方在原始位置之后使用这些数组是免费的( ).至于为什么我使用malloc ...这个程序的某些部分使用缓存对齐的内存,所以我一直在使用_aligned_malloc.虽然可能有一种方法可以获得缓存对齐的新方法,但这是我知道的唯一方法.

Answer 1

您是否有可能链接到运行时库的调试版本,该版本正在执行额外操作,free()例如使用垃圾值填充内存？当你链接过度激进的内存调试库时,我已经看到了这种行为.您发布的代码看起来并不奇怪.我很想知道如果你用std::vector或更换数组会发生什么std::deque.Vector应该具有与数组非常相似的行为,如果数组很大,Deque实际上可以提高速度,因为内存管理器不必保证连续的空间.