std::vector swap causing memory fragmentation?

Question

I am currently working with very large data sets about 2.5GB worth of memory..

I am currently storing this by using a vector of class Data that contains 1) Meta data 2) boost::ptr_list<MemoryBlock>

The MemoryBlock class contains 1) Meta Data 2) std::vector<XYZ>

When populating, i reserve my std::vector<xyz> in groups of 50,000. If the spatial dimensions of my vector grows to large, i will create a new memoryblock and use std::vector<XYZ>(Points).swap(Points) to shrink the vector to the proper size.

Now the problem... It seems that when I use the swap trick to resize my array, I start to run into std::bad_alloc exceptions after clearing all of my data and loading in a new data set.

The amount of data that I can load in shrinks drastically... It will continue to do so every time I clear my data and load in a new data set... For example, My initial data set will load in 100,000,000 values

next time it will load 70,000,000 values

Next time 50,000,000 values

next time 20,000,000 values etc...

My first thought is a memory leak, but there is nothing I have been able to identify. Every thing in the code except for the swap has been used extensively for a very long time with out any problems.

If I do not use the swap/spatial dimension check, everything continues on and works properly.

any ideas?!?

Edit

bool Check_MemBlock_Size(MemoryBlock &CurrMemblock, XYZ CheckPoint){

    // Set a minimum of 5000 points in each memory block regardless of physical size..
    if(CurrMemblock.PointsArr.size() > 5000){
        XYZ TestMin, TestMax;
        TestMin = CurrMemblock.Min;
        TestMax = CurrMemblock.Max;

        // Check what the bounding box would be if we included the check point..
        if(TestMax.x < CheckPoint.x)
            TestMax.x = CheckPoint.x;
        if(TestMax.y < CheckPoint.y)
            TestMax.y = CheckPoint.y;
        if(TestMax.z < CheckPoint.z)
            TestMax.z = CheckPoint.z;

        if(TestMin.x > CheckPoint.x)
            TestMin.x = CheckPoint.x;
        if(TestMin.y > CheckPoint.y)
            TestMin.y = CheckPoint.y;
        if(TestMin.z > CheckPoint.z)
            TestMin.z = CheckPoint.z;

        // If the new bounding box is too big, lets break it off.
        if(fabs(TestMax.x - TestMin.x) > 100 || fabs(TestMax.y - TestMin.y) > 100 || fabs(TestMax.z - TestMin.z) > 50){

            std::vector<XYZ>(CurrMemblock.PointsArr).swap(CurrMemblock.PointsArr);

            return false;

        }
    }


    return true;
}

Here is the segment of code using this..

                    if(Check_MemBlock_Size(*MemBlock, NewPoint) == false){

                        Data->MemoryBlocks.push_back(MemBlock);

                        try {
                            MemBlock = new MemoryBlock();
                        } catch (std::bad_alloc) {
                            printf("Not enough memory\n");
                            delete Buffer;
                            break;
                        }

                        BlockSize = 0;

                        try{
                            MemBlock->PointsArr.reserve(MaxBlockSize);
                        } catch(std::bad_alloc){
                            delete MemBlock;
                            delete Buffer;
                            printf("Not enough memory\n");
                            break;
                        }

                    }


                    // Push the point to our current memory block
                    BlockSize++;
                    MemBlock->PointsArr.push_back(NewPoint);

                    .... // More stuff going on here.. irrelevant

                    // push a new memory block if we hit the block point limit.
                    if(BlockSize >= MaxBlockSize){

                        Data->MemoryBlocks.push_back(MemBlock);

                        try {
                            MemBlock = new MemoryBlock();
                        } catch (std::bad_alloc) {
                            printf("Not enough memory\n");
                            delete Buffer;
                            break;
                        }

                        BlockSize = 0;

                        try{
                            MemBlock->PointsArr.reserve(MaxBlockSize);
                        } catch(std::bad_alloc){
                            printf("Not enough memory\n");
                            delete MemBlock;
                            delete Buffer;
                            break;
                        }

                    }

Answer 1

This technique seems to guarantee fragmentation if in-between calls to Check_MemBlock_Size() you do some more dynamic allocation. This is because you release your 50K allocation after allocating your smaller chunk, creating a 50K object hole in memory, which can now be partially filled by some more memory, which your next rebuild of your MemoryBlock cannot use.

You could create a global vector instead of a temporary one to hold this 50K object allocation. Then, when you next rebuild a new MemoryBlock, instead of resizing a new 50K object vector, just swap in the global one. When you want to shrink it, swap out with the global one again. Reusing the 50K reserved memory this way will remove any fragmentation to which this allocation may have contributed.

However, there may be other sources of fragmentation in your program if you are sure there are no leaks. Typically, fragmentation is caused by a mix of large and small objects dynamically allocated, each with varying lifetimes. There are many ways to resolve it, but one way to handle it is with pools of memory. A pool in this sense is a collection of objects of the same size and same lifespan, grouped together within a custom allocator. Deallocation of such memory is returned to its pool. If the memory is never returned to the system with delete, the pool combats fragmentation by allowing future allocations to reuse memory that was allocated previously for the same object type. The pools grow to the peak runtime utilization, and the fragmentation is never worse than that.