Bug in C++ Language or Bug in C++ Compiler?

[pocruadhlaoich]

Hi,
I was writing some code involving arrays of pointers and I noticed some extremely strange behavior.
Is there a problem with my C++, the C++ language or is this an error in the compiler (its tested on VS2005/2003).

The following code keeps declaring memory on the heap until it runs out of memory, in Windows 32 bit, this is at around 2 Gigabyte. However when I change the order of one line of code it inexplicably runs out of memory at about 72Megs!

First I define a structure, its just a block of memory

struct TestMemBlock
{
char MemBlock[1024];
};

Then I create a function which is just an infinite while loop

void CMyClass::InfiniteWhileLoop()
{

bool go = true;
long NoAdded = 0;
long TotalMemoryDeclared = 0;

while( go == true )
{
AddItemTest( NoAdded );
TotalMemoryDeclared += sizeof(TestMemBlock);
}

}

In the next function I do 3 things.
1. Declare an Array of Pointers on the heap.
2. Delete the Array of Pointers from the heap.
3. Declare an object on the heap.

If I do them in this order 1,2,3, by setting the "MakeStrangenessHappen = false" the code works as expected and I run out of memory at 2Gig. If I do them in this order 1,3,2 by setting the "MakeStrangenessHappen = true" the code runs out of memory at around 72Meg (or much less than 2Gig).
I KNOW THAT THERE IS A MEMORY LEAK HERE, its an intentional memory leak to see how much memory I can declare before I run out of memory.

int CMemoryTestAppDlg::AddItemTest(long& NoAdded)
{
bool MakeStrangenessHappen = true;
++NoAdded;
TestMemBlock** ppListBuff = new TestMemBlock*[NoAdded];

if( MakeStrangenessHappen == true )
TestMemBlock* pNewType = new TestMemBlock; // we will hit a ~72Meg limit, strange!

delete[] ppListBuff;

if( MakeStrangenessHappen == false )
TestMemBlock* pNewType = new TestMemBlock; // we will reach 2 Gig Limit, OK
return 1;
}


Can anyone explain why the order of items 1,2 & 3 would have such a massive impact on the available memory, the compiler shows no leaks, the code looks functionally the same, so is it a problem in the compiler, my c++ or the c++ language itself!!

[JohnW@Wessex]

One possible cause is memory fragmentation from interleaved memory allocations in the 132 order.

[Zachm]

What you are experiencing is a small phenomena known as memory fragmentation, or more specifically, external fragmentation.
To understand this problem, you must become a heap manger for a second, or in other words, a table organizer at a restaurant:
Imagine you are organizing tables at a restaurant, i.e. telling people who come where to sit, and all your restaurant has is one long table(or bar) where everybody, friend of foe, sit at. You would like to sit people who are friends next to each other, otherwise they would be angry.
Now, let's say people come to your restaurant in groups, the first group has only 1 person, the second 2 persons, the 3rd - 3 persons and so on until group of 5 persons:

1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 # # # # # #
=========================================
   Table
=========================================

Now, group number 4 finished eating and left:

1 2 2 3 3 3 # # # # 5 5 5 5 5 # # # # # #
=========================================
   Table
=========================================

Now, group number 6 arrived, notice that you can't put them in between groups 3 and 5 since there are only 4 seats in between, so your table seating would look like:

1 2 2 3 3 3 # # # # 5 5 5 5 5 6 6 6 6 6 6
=========================================
   Table
=========================================

The result - even if some of the groups have finished eating and left, you can't put new groups in their seats because you don't have enough seats in a row, unless the newly arriving group is at most the size of a group that already left.

The heap manager behaves much the same way and this is not a bug of any compiler - this is the defined behavior.
To avoid fragmentation - you usually need to change your memory management scheme - if you MUST allocate ever increasing memory blocks - consider implementing some sort of memory pool, or search the web for "avoiding memory fragmentation".

Regards,
Zachm

[pocruadhlaoich]

Hi Zachm and JohnW,

many thanks, this sounds interesting, and I cant think of a better explanation...
However should the memory management software not fill in the gaps...

so for example
X = new Item
P = new Pointer array
- = Empty space/deleted item

Step 1) I declare an array of Pointer/s
P
Step 2) then I declare an Item
PX
Step 3) then I delete the Pointer array
- X

Step 1.
- XPP
Step 2.
XXPP
Step 3.
XX--

Step 1.
XXPPP
Step 2.
XXPPPX
Step 3.
XX - - - X

Step 1.
XX - - - XPPPP
Step 2.
XXX- - XPPPP
Step 3.
XXX- - X - - - -

Step 1.
XXX - - XPPPPP
Step 2.
XXXX - X - - - - -

And so on....
As you can see the memory isnt getting that fragmented at all. And when I look at the addresses of the items being declared, they seem to match the theory above, i.e. that items are being slotted into the available slots of memory.

However, clearly something IS happening or I would be getting more than 72 meg. Indeed if I do some maths...

I have 2 Gig of available memory
I get 72,000 items of 1k in size.
If they are all evenly distributed in memory to make the memory as INefficient as possible, the largest run of memory would be about 28k.
If each pointer is 4 bytes and I have an array of 72000 pointers that would equal 288k of contiguous memory required to create the array of pointers.

So whatever way the memory manager has been designed we are not far away maximal INefficiency? Can this really be true?

[Zachm]

For each allocation of 1024 byte block, you allocate and free a pointers block that increases by 4 bytes on each iteration:

Heap memory layout, each number represents a block size in bytes,
-(x) represents a free block of size x:

1	4
2	4,1024
3	-(4),1024
1	-(4),1024,8
2	-(4),1024,8,1024
3	-(4),1024,-(8),1024
1	-(4),1024,-(8),1024,12
2	-(4),1024,-(8),1024,12,1024
3	-(4),1024,-(8),1024,-(12),1024
1	-(4),1024,-(8),1024,-(12),1024,16
2	-(4),1024,-(8),1024,-(12),1024,16,1024
3	-(4),1024,-(8),1024,-(12),1024,-(16),1024
1	-(4),1024,-(8),1024,-(12),1024,-(16),1024,22
2	-(4),1024,-(8),1024,-(12),1024,-(16),1024,22,1024
3	-(4),1024,-(8),1024,-(12),1024,-(16),1024,-(22),1024
	.
	.
	.

As you can see, you can never reuse the freed blocks in order to allocate a new pointer block, so, when you reach 72 Meg block, you effectively cause external fragmentation of ~72 Meg in at least one continuous block, and the next allocation will not be able to use this block as well so it will allocate a new block of ~72 Meg, and so on, you quickly reach 2 GB limit without effectively using more than 72 Megs...

Regards,
Zachm

[Paul McKenzie]

Can anyone explain why the order of items 1,2 & 3 would have such a massive impact on the available memory,

Google "first fit" and "best fit" memory allocation schemes.

Regards,

Paul McKenzie

[pocruadhlaoich]

Hi Zachm

thanks for the reply, I REALLY appreciate the help here.

I take your point. However I dont think it can explain the level of fragmentation I am seeing.

I have done some calculations and at line 256 of your diagram we declare 1024 of memory and only have a slot 1020 available to put it in, so at that line we have 50% loss due to fragmentation.

However if you extend this to much larger numbers, so you declare and delete an array of 10,000 pointers at 4 bytes = 40k.
You can then insert about 40 x 1k blocks before you leave a maximum unusable space of 1020 bytes.
So the efficiency increases logarithmically as the array of pointers get larger.

At any rate the fragmentation level will not get any worse than 50%. In reality it could be much much less than this.

However I have 2Gig of addressable memory available, so even in the worst case I should be getting 1Gig of usable memory, but I am actually getting about 75Meg, which is obviously a massive shortfall.

There must be some other much more significant factors?

[Paul McKenzie]

Hi Zachm

thanks for the reply, I REALLY appreciate the help here.

I take your point. However I dont think it can explain the level of fragmentation I am seeing.

Have you verified that the heap manager uses the algorithm that ZachM described?

There is "first fit", "best fit" and "worst fit" and probably other algorithms used for heap management. That's why I mentioned that you should google or research these algorithms.

Regards,

Paul McKenzie

[ZuK]

I have modified the testprogram a little

#include <iostream>
#include <string>

using namespace std;

struct TestMemBlock {
    char MemBlock[1024];
};

long NoAdded = 0;
unsigned long TotalMemoryDeclared = 0;
bool MakeStrangenessHappen = false;


int AddItemTest(long& NoAdded) {
    TestMemBlock* pNewType;
    ++NoAdded;
    TestMemBlock** ppListBuff = new TestMemBlock*[NoAdded];

    if( MakeStrangenessHappen == true )
        pNewType = new TestMemBlock;

    delete[] ppListBuff;

    if( MakeStrangenessHappen == false )
        pNewType = new TestMemBlock;

    TotalMemoryDeclared += sizeof(TestMemBlock);

    return 1;
}

void InfiniteWhileLoop() {

    bool go = true;

    NoAdded = 0;
    TotalMemoryDeclared = 0;

    cout << "MakeStrangenessHappen = " <<  MakeStrangenessHappen << endl;

    try {
        while( go == true ) {
            AddItemTest( NoAdded );
        }
    }
    catch (std::bad_alloc a ) {
        cout << NoAdded << " allocations,  " << TotalMemoryDeclared << " bytes allocated." << endl;
    }
}

int main( int argc, char ** argv ) {
    if ( argc == 2 ) {
        string s( argv[1] );
        MakeStrangenessHappen = ( s == "1" );
        InfiniteWhileLoop();
    }
}

Running under Linux I get this output

kurt@power:~$ g++ tfrag.cc
kurt@power:~$ ./a.out 0
MakeStrangenessHappen = 0
3100885 allocations,  3175305216 bytes allocated.
kurt@power:~$ ./a.out 1
MakeStrangenessHappen = 1
3087358 allocations,  3161453568 bytes allocated.

No strange things happen.

Kurt

[pocruadhlaoich]

Paul - Yes I looked briefly into first fit and best fit earlier, thanks for the hint. The above code is a simplfication of a problem I am trying to solve. I am coding this in VS2005, whatever heap management algorithm that uses.

ZuK - thanks very much for the code tweaks! I will test, compare and post my results using VS2005 when I get back into work tomorrow morning.

Thanks all!
Patrick

[VladimirF]

Since you are using Visual Studio, I can safely assume that we are talking about Windows platform.
According to MSDN, there currently are only TWO modes for heap allocations: “standard” and “Low-fragmentation Heap” (LFH).
Try to use HeapSetInformation() API to switch to LFH and see if that helps.

Unfortunately, my experiment failed. Here is the code:

HEAP_INFORMATION_CLASS hic = HeapCompatibilityInformation;
ULONG HeapFragValue(0);
HANDLE h = GetProcessHeap();
SIZE_T ReturnLength(0);

HeapQueryInformation(h, hic, &HeapFragValue, sizeof(HeapFragValue), &ReturnLength);
HeapFragValue = 2;
HeapSetInformation(h, hic, &HeapFragValue, sizeof(HeapFragValue));

HeapQueryInformation() sets HeapFragValue to 1.
HeapSetInformation() failes with the error code 0x0000001f (“A device attached to the system is not functioning.”)
Rather misterious error…

[pocruadhlaoich]

Hey all,
I ran ZuK's exact same code using Visual Studio 2005 in Windows XP and get a surprising difference from what he saw:

fragmentation.exe 0
MakeStrangenessHappen = 0
1936489 allocations, 1982963712 bytes allocated. ( total time = 4+ hours )

fragmentation.exe 1
MakeStrangenessHappen = 1
72022 allocations, 73749504 bytes allocated. ( total time = 15 seconds )

Sooooooo... out of interest, could it be gcc vs Visual Studio compiler that is causing the difference, or could it be Windows vs Linux and its ability for a process to use more than 2GB of memory?

[Paul McKenzie]

Sooooooo... out of interest, could it be gcc vs Visual Studio compiler that is causing the difference,

Every compiler vendor has created their own heap manager, so it is a given that there are differences.

How about bypassing the heap manager, and instead call the low-level OS functions (HeapAlloc, GlobalAlloc) in the same loop? Then you've eliminated the compiler implementation being a reason for any differences.

Regards,

Paul McKenzie

[ZuK]

1936489 allocations, 1982963712 bytes allocated. ( total time = 4+ hours )

4 Hours. That seems to be a debug build. It runs a couple of minutes to allocate 3GB for me.
Kurt

[VladimirF]

4 Hours. That seems to be a debug build. It runs a couple of minutes to allocate 3GB for me.
Kurt

Don't think so. My debug build doesn't take long at all.
If you wouldn't have enough RAM installed and have to go to the swap file all the time - don't know how long that might take.