<deque> and memory allocation

<deque> and memory allocation

Post by Bill Burri » Sat, 26 Jul 2003 20:13:02



When using deque, what happens to the heap if you do a push_back and a
pop_front once per second for a year?

I am just wondering if using deque is appropriate in a program that is
designed to run continuously for extended time periods.

thanks

Bill

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

 
 
 

<deque> and memory allocation

Post by Ben Hutching » Sun, 27 Jul 2003 21:43:18


 > When using deque, what happens to the heap if you do a push_back and a
 > pop_front once per second for a year?

That depends very much on your implementation, and possibly also on what
other memory (de-)allocations are done in-between these.

 > I am just wondering if using deque is appropriate in a program that is
 > designed to run continuously for extended time periods.

That really is a question for the library vendor (or the source code) to
answer.

I expect that you will be OK if you use a custom allocator with its own
memory pool dedicated to the deque.  With the default allocator there
might be a problem of memory fragmentation.

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

 
 
 

<deque> and memory allocation

Post by David Turne » Sun, 27 Jul 2003 21:44:42


Hello


 > When using deque, what happens to the heap if you do a push_back and a
 > pop_front once per second for a year?
 >

There's a simple way to test, you know:

#include <deque>
using namespace std;

int main() {
     deque<int> d;
     for(int i=0; i<356*24*60*60; ++i) {
         d.push_back(i);
         d.pop_front();
     }
     magical_dump_heap_state_function();

Quote:}

Regards
David Turner

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

 
 
 

<deque> and memory allocation

Post by Dhru » Sun, 27 Jul 2003 21:51:56


 > When using deque, what happens to the heap if you do a push_back and a
 > pop_front once per second for a year?
 >
 > I am just wondering if using deque is appropriate in a program that is
 > designed to run continuously for extended time periods.

What happens if you climb down 100 steps and climb them up again and do
this continuously for 10 years. You will get tired. Eaxctly!!!!!! That's
what happens.

But, the deque will run even for 600000 years, provided that the hardare
holds up. I guess the answer is implementation dependant, but ideally, it
should just keep allocating and deallocating memory. And, if the allocator
is good, then it will not ask the OS for more memory each time. Thus,
Ideally, the would operation will make no difference what so ever. If the
deque is multiple node based, then even that operation can be done away
with.

Regards,
-Dhruv.

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

 
 
 

<deque> and memory allocation

Post by Andy Sawye » Sun, 27 Jul 2003 22:43:10



 on 25 Jul 2003 07:13:02 -0400,

Quote:> When using deque, what happens to the heap if you do a push_back and a
> pop_front once per second for a year?

 Depending on the implementations of std::deque, std::allocator and your
heap, you'll probably find it keeps recycling the same block(s). (In
fact, given a literal interpretation of your question, it would be
reasonable for an implementation to only ever allocate a single block :)

Quote:> I am just wondering if using deque is appropriate in a program that is
> designed to run continuously for extended time periods.

 I've certainly used std::deque it in such situations1 and not had any
problems with it. YMMV, however. If this is a great concern, you could
always write an allocator to do (what you consider to be) the right
thing.

Regards,
 Andy S

Footnotes:
1  It didn't have to run continuously for a year (the system admin types
didn't trust the underlying OS to run for that long :), but there were
considerably more than one access per end per second...
--
"Light thinks it travels faster than anything but it is wrong. No matter
 how fast light travels it finds the darkness has always got there first,
 and is waiting for it."                  -- Terry Pratchett, Reaper Man

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

 
 
 

<deque> and memory allocation

Post by Francis Glassboro » Mon, 28 Jul 2003 01:07:42




Quote:>When using deque, what happens to the heap if you do a push_back and a
>pop_front once per second for a year?

>I am just wondering if using deque is appropriate in a program that is
>designed to run continuously for extended time periods.

I suppose that there just might be some horrifically bad implementation
of deque for which there might be a problem but those I am familiar with

ensure that memory is appropriately recovered.

--
ACCU Spring Conference 2003 April 2-5
The Conference you should not have missed
ACCU Spring Conference 2004 Late April
Francis Glassborow      ACCU

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

 
 
 

<deque> and memory allocation

Post by Andy Sawye » Mon, 28 Jul 2003 19:50:45



  on 26 Jul 2003 08:44:42 -0400,

 > Hello
 >


 >  > When using deque, what happens to the heap if you do a push_back and a
 >  > pop_front once per second for a year?
 >  >
 >
 > There's a simple way to test, you know:
 >
 > #include <deque>
 > using namespace std;
 >
 > int main() {
 >      deque<int> d;
 >      for(int i=0; i<356*24*60*60; ++i) {
 >          d.push_back(i);
 >          d.pop_front();
 >      }
 >      magical_dump_heap_state_function();
 > }

#pragma picky(on)
This rather depends on the size of integer on your platform. It
certainly isn't portable. (Of course, a decent compiler will carp about
the integer constant "356*24*60*60" being out of range...)
#pragma picky(off)

Regards,
  Andy S
--
"Light thinks it travels faster than anything but it is wrong. No matter
  how fast light travels it finds the darkness has always got there first,
  and is waiting for it."                  -- Terry Pratchett, Reaper Man

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

 
 
 

<deque> and memory allocation

Post by Bo Persso » Tue, 29 Jul 2003 02:04:22






> >When using deque, what happens to the heap if you do a push_back
and a
> >pop_front once per second for a year?

> >I am just wondering if using deque is appropriate in a program that
is
> >designed to run continuously for extended time periods.

> I suppose that there just might be some horrifically bad
implementation
> of deque for which there might be a problem but those I am familiar
with

> ensure that memory is appropriately recovered.

I guess the problem could lie in the management of the "page map", or
whatever the deque uses for keeping track of its data blocks.

One problem is that a pop_front() must not invalidate iterators and
pointers, so the deque must use some other appropriate time to recover
the left most part of the page map. After a long sequence of pop_fronts,
there will be some empty space a the beginning of the map structure. If
you don't do anything about this, everything will migrate off the other
end.

Fortunately doing a push_back gives such an opportunity. Before
reallocating the page map, empty space from the pop_fronts could be
recovered.

Bo Persson

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

 
 
 

<deque> and memory allocation

Post by Andy Sawye » Tue, 29 Jul 2003 08:34:07



 on 27 Jul 2003 06:50:45 -0400,


>   on 26 Jul 2003 08:44:42 -0400,

>  > int main() {
>  >      deque<int> d;
>  >      for(int i=0; i<356*24*60*60; ++i) {
>  >          d.push_back(i);
>  >          d.pop_front();
>  >      }
>  >      magical_dump_heap_state_function();
>  > }

> #pragma picky(on)
> This rather depends on the size of integer on your platform. It
> certainly isn't portable. (Of course, a decent compiler will carp about
> the integer constant "356*24*60*60" being out of range...)
> #pragma picky(off)

#pragma picky(picky(on))
That should read:
....carp about *it if* the integer...
#pragma picky(picky(off))

Regards,
  Andy S
--
"Light thinks it travels faster than anything but it is wrong. No matter
 how fast light travels it finds the darkness has always got there first,
 and is waiting for it."                  -- Terry Pratchett, Reaper Man

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

 
 
 

<deque> and memory allocation

Post by Bill Burri » Thu, 31 Jul 2003 08:02:47


Quote:>  Depending on the implementations of std::deque, std::allocator and your
> heap, you'll probably find it keeps recycling the same block(s).

Yes, normally all that is needed is one block, but my input thread has
higher priority, so it is possible for the output thread to get behind,
resulting in more then one block of data in the deque.

I was thinking of using more then one deque, each with different size data
structures.  I assume that eventally this would lead to fragmentation of the
heap.

I have decided not to bother using deque, and use an array instead.  I have
my input and output pointers which wrap back to the beginning after reaching
the end.  This way the memory is allocated at program startup and reused
until the end of time.  The threading aspects will also be simple, since the
input & output threads will always be working with different array elements,
the only critical section is the count variable.

Bill

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

 
 
 

<deque> and memory allocation

Post by Francis Glassboro » Fri, 01 Aug 2003 08:56:03




Quote:>I have decided not to bother using deque, and use an array instead.  I have
>my input and output pointers which wrap back to the beginning after reaching
>the end.  This way the memory is allocated at program startup and reused
>until the end of time.  The threading aspects will also be simple, since the
>input & output threads will always be working with different array elements,
>the only critical section is the count variable.

It sounds to me as if what you really need is a circular buffer
container. It isn't that hard to write one yourself that conforms to all
the requirements for and STL container. I think you will even find that
there are already some pretty good implementations around.

--
ACCU Spring Conference 2003 April 2-5
The Conference you should not have missed
ACCU Spring Conference 2004 Late April
Francis Glassborow      ACCU

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

 
 
 

1. HELP >>>>>>>>>>>>> WINAPI <<<<<<<<<<<<<<<<<

   I need help in writting a vb program that will monitor the message
queue of another aplication that is running along with my program. Itried
to use PeekMessage api function but the help file says that it can only
peek the application's own message queue.  My program is similar in
working with SPY or the SPY++ program. Is there an api function that Ican
use. PLEEEEEEEEEZE help.

2. home use

3. >>>>>>>>> PROBLEM WITH MSICPB.EXE <<<<<<<<<<<<<<<<<

4. Windows 98

5. <<<<<<Programmers Needed>>>>>>>

6. Sony TCD-D7 DAT walkman: questions

7. <<>><><><><><><><><><><>

8. Carrier command

9. <><><> www.FotoCD.net <><><>

10. ************************<<<<<<LOTUS CORP.SUCKS>>>>>*****************

11. >>>>>STUCK<<<<<< How to subclass desktop?

12. >>>>> SoftImage Animator - North West UK <<<<<<