Bug in C++ Language or Bug in C++ Compiler?
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 3 123 LastLast
Results 1 to 15 of 32

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

  1. #1
    Join Date
    Jun 2009
    Posts
    31

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

    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!!

  2. #2
    Join Date
    Jul 2002
    Location
    Portsmouth. United Kingdom
    Posts
    2,725

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

    One possible cause is memory fragmentation from interleaved memory allocations in the 132 order.
    "It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
    Richard P. Feynman

  3. #3
    Join Date
    Oct 2006
    Posts
    616

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

    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:
    Code:
    1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 # # # # # #
    =========================================
       Table
    =========================================
    Now, group number 4 finished eating and left:
    Code:
    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:
    Code:
    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

  4. #4
    Join Date
    Jun 2009
    Posts
    31

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

    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?

  5. #5
    Join Date
    Oct 2006
    Posts
    616

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

    For each allocation of 1024 byte block, you allocate and free a pointers block that increases by 4 bytes on each iteration:
    Code:
    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
    Last edited by Zachm; June 16th, 2009 at 08:24 AM.

  6. #6
    Join Date
    Apr 1999
    Posts
    27,433

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

    Quote Originally Posted by pocruadhlaoich View Post
    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

  7. #7
    Join Date
    Jun 2009
    Posts
    31

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

    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?

  8. #8
    Join Date
    Apr 1999
    Posts
    27,433

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

    Quote Originally Posted by pocruadhlaoich View Post
    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

  9. #9
    Join Date
    Oct 2002
    Location
    Austria
    Posts
    1,284

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

    I have modified the testprogram a little
    Code:
    #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

    Code:
    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
    Last edited by ZuK; June 16th, 2009 at 12:39 PM.

  10. #10
    Join Date
    Jun 2009
    Posts
    31

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

    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

  11. #11
    Join Date
    Aug 2000
    Location
    New York, NY, USA
    Posts
    5,527

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

    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:
    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…
    Vlad - MS MVP [2007 - 2012] - www.FeinSoftware.com
    Convenience and productivity tools for Microsoft Visual Studio:
    FeinViewer - an integrated GDI objects viewer for Visual C++ Debugger, and more...

  12. #12
    Join Date
    Jun 2009
    Posts
    31

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

    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?

  13. #13
    Join Date
    Apr 1999
    Posts
    27,433

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

    Quote Originally Posted by pocruadhlaoich View Post
    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

  14. #14
    Join Date
    Oct 2002
    Location
    Austria
    Posts
    1,284

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

    Quote Originally Posted by pocruadhlaoich View Post
    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

  15. #15
    Join Date
    Aug 2000
    Location
    New York, NY, USA
    Posts
    5,527

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

    Quote Originally Posted by ZuK View Post
    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.
    Vlad - MS MVP [2007 - 2012] - www.FeinSoftware.com
    Convenience and productivity tools for Microsoft Visual Studio:
    FeinViewer - an integrated GDI objects viewer for Visual C++ Debugger, and more...

Page 1 of 3 123 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center