X-Authentication-Warning: delorie.com: mail set sender to djgpp-bounces using -f
Lines: 85
X-Admin: news AT aol DOT com
From: dang2015 AT aol DOT com (DanG2015)
Newsgroups: comp.os.msdos.djgpp
Date: 15 Mar 2004 16:52:04 GMT
Organization: AOL http://www.aol.com
Subject: new / delete efficiency in deque
Message-ID: <20040315115204.08910.00001403@mb-m13.aol.com>
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Reply-To: djgpp AT delorie DOT com

I'm not sure whether to file this under "question" or "curiousity", but here
goes...

I was looking into making a circular list to be able to allocate a fixed chunk
of memory and then push and pop from it in a circular fashion... this would
be done in a real-time system at a fast rate, so minimizing the number of
new / delete calls would be beneficial.  Just for grins, I wanted to see how
often deque would exercise new / delete.

I found it interesting... a deque<int> did a 512-byte block allocation and
then let me push & pop a bunch of times without it calling new / delete again.
Neat.  So then I exercised it a little harder.

Anyway... to cut to the chase, the attached test code and its results got
me curious (although not curious enough to try to read & understand the
deque source ;-)...  I create a deque<int> and then enter a loop to push
an element then pop it.  Goes a bunch of times... then about 3/4 of the
way through a group of 200 iterations, it just "decides" to free its original
512 block and allocate a new one.  It then continues pushing and popping
in that new block.

If I go further, I'd bet this happens at regular intervals based on the size
of what's being pushed, etc.  But it gets me to thinking... are the guts
of deque (or perhaps my underlying call to malloc) leaving a trail of used-up
pointers?  In other words, everytime I do a push/pop pair, the net result
is that I have permanently consumed a pointer somewhere and after a
bunch of these, I need a new block (although it appears that deque is
freeing the previous block)...?

Anyway... I toss this out as a point of curiousity to someone with a little
more time and/or inclination than myself.  Of course it might be that I'm
ignoring something inherently obvious as well ;-)

Regards,

Dan

============source=======================
#include <stdio.h>
#include <new>
#include <memory.h>
#include <deque>
using namespace std;

void* operator new( size_t x ) {
    void* f = malloc(x);
    printf( "malloc (%ld)=%08lX\n", x, (long)f );
    return f;
}

void operator delete( void* x ) {
    printf( "delete %08lX\n", (long)x );
    free(x);
}

int main( void ) {

    deque<int>  D;

    for (int i=0; i<200; i++) {

        printf( "+" );
        D.push_back( 1 );

        printf( "-" );
        D.pop_front();
    }
    printf( "\n" );

    return 0;
}

=============results==========================

malloc (1280)=00095D58
malloc (512)=00096260
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+malloc (512)=00096468
-delete 00096260
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
delete 00096468