RE: [boost] Re: circular_buffer?

From: Reid Sweatman (reid_of_diamonds_at_[hidden])
Date: 2001-03-03 22:47:19

Well, the problem is really any generalized homogeneous particle (or generic
object) system.  In the rain example, the rain is created randomly and
killed when it leaves the frame, so I needed to have a storage and lookup
mechanism with practically no overhead and the ability to remove a specific
item from the active object stack.  That's why it had to be a vector; so I
could write an algorithm to move an arbitrary object to the end of the stack
and pop it, with minimum fuss (actually, it just swapped the last element
with the one to be popped).  And you *never* allocate or deallocate from the
object vector until you're totally done with the mechanism; you just move
indices from the available pool stack to the active object stack (these
stacks hold *indices*, not objects; usually just ints).  Very cheap.  If I
needed to access the active elements in a specific order, I could apply a
sort algorithm to the active object stack (another reason to make it out of
a vector, rather than an STL stack).

I can still see the occasional need for circular buffers, say in a compiler
tokenizer, to handle the input stream.  But it shouldn't be too hard to take
the mechanism I described and make it circular.  I'd use a single vector and
wrapping iterators (probably four, to let you handle the wrapping in the
easiest possible manner, and to let you gauge when you're getting close to
needing to perform some iterator updates and data handling (I sort of have
Holub's "Compiler Design in C" in mind, and the implementation of circular
tokenizing buffers given there, which is pretty straight-ahead).  With a
circular buffer of the sort you're talking about you pretty much get the
sliding window automatically, and the ordering will be that of a deque, in
the absence of any dynamic reordering of the buffer contents.

I also experimented with using sets and maps for particle systems and
texture cache management, but I get the most usage out of the SGI hash
templates (not standard, but so long as it compiles and runs efficiently,
who cares?)  I actually got into this list when I needed a dynamic priority
queue, and someone suggested I look here (Seumas McNalley, I think).  When I
posted the request here it prompted Dietmar to update some code he'd written
and submit it to the library (Dietmar being a wiz at graph and network
algorithms--thanks again, Dietmar).

One other nice trick you can pull with the mechanism I described is
specialized lookups into the active object stack; these just take
maintaining secondary data structures (binary trees, sliding windows,
hashing, whatever) to index into the active object stack.  I think you'll
find this mechanism a very fast, versatile way to handle just about any
problem that involves a fixed number of objects that change rapidly and are
all the same type (important for avoiding allocation/deallocation), and that
you want to visit as a group each time.  BTW, I didn't think up this nice,
elegant scheme right away; it's about third iteration, but it's much simpler
than any of my earlier tries, or the code I was handed.  It just took me a
while to identify the core of the problem and figure out the minimum amount
of data and fastest lookup methods required to implement it.

Reid Sweatman
Software Engineer

> -----Original Message-----
> From: Paul Hollingsworth [mailto:boost_at_[hidden]]
> Sent: Tuesday, February 27, 2001 11:50 PM
> To: boost_at_[hidden]
> Subject: Re: [boost] Re: circular_buffer?
>
>
> Hi Reid,
> After puzzling over what you said, I think I understand the problem that
> you're solving.
>
> You're talking about being able to free objects in any order, not just the
> order in which they were "inserted".
>
> I was just talking about a simple sliding window implementation, mandating
> that you pretty much can't delete objects to free up space.
>
> But your mechanism is much more general, and useful for my game ;-)
>
> It is a fantastic solution! Thank you!
>
> Paul Hollingsworth
> http://PaulHollingsworth.com
> ----- Original Message -----
> From: "Reid Sweatman" <reid_of_diamonds_at_[hidden]>
> To: <boost_at_[hidden]>
> Sent: Tuesday, February 27, 2001 3:10 PM
> Subject: RE: [boost] Re: circular_buffer?
>
>
> > In that situation, I usually find it much more efficient to allocate a
> > vector of the size I want (the vector will never change size), and two
> > stacks.  To initialize the mechanism, I create the vector with default
> > objects, then push all the possible vector indices onto one of
> the stacks,
> > which becomes my free pool.  As I actually create real objects in the
> > vector, I pop an index from the pool, assign object data to the
> object in
> > that location using the vector [] operator and the index, then push the
> > index onto the other stack, which is my active object stack.  Killing an
> > object is just the reverse, and you needn't assign default values to the
> > unused vector location, because you're only going to access it when its
> > index comes back off the free pool stack, anyway.  All this is really
> > trivial to do with STL objects.  One fillip:  the "in-use"
> stack I usually
> > implement as a vector instead of a stack, because in some
> usages it can be
> > important to access the objects in a particular order, and the STL stack
> is
> > a little restrictive about that for my taste.
> >
> > This is the fastest way I've found of doing it, so long as you need to
> visit
> > each object currently in use at least once, in which case you
> just use an
> > iterator to traverse the in-use stack.  No allocations, no
> deallocations.
> I
> > was once handed the rain module from a game that gary_at_sierra would
> recognize
> > to incorporate into another game that shall remain nameless due to NDA.
> In
> > the original game the rain was pretty sparse, and it remained so when I
> > incorporated it, no matter how fast I told it to run.  It was
> CPU-bound by
> > the allocation/deallocation and a very brain-dead way of finding active
> > things in the vector.  I rewrote it as I've described, and had so much
> rain
> > you couldn't see anything else in the frame, even with the raindrops'
> alpha
> > set practically transparent.  Give it a shot.  I'd send you the
> pertinent
> > module, but again, unfortunately, NDA, and I don't have the property
> rights,
> > anyway.  But I've described the method, and it's pretty simple.
> >
> > Reid Sweatman
> > Software Engineer
> >
> > > -----Original Message-----
> > > From: boost_at_[hidden] [mailto:boost_at_[hidden]]
> > > Sent: Tuesday, February 27, 2001 11:49 AM
> > > To: boost_at_[hidden]
> > > Subject: [boost] Re: circular_buffer?
> > >
> > >
> > > Actually, neither of these is what I'm looking for.
> > >
> > > Basically, (as a hobby) I am writing yet another shoot-em-up game. The
> > > tried and true technique for managing bullets, ship thrust, bullet
> > > holes etc.  is to have a "ring buffer" or
> > > "circular buffer" with a fixed maximum size.
> > >
> > > You want a maximum of, say, 1000 bullets on the screen. As soon as the
> > > ship fires the 1001st bullet, the 1st bullet "disappears". In terms
> > > of the buffer, asssuming it has a fixed size of "1000". When you add
> > > the 1001st entry, it overwrites the 1st entry.
> > >
> > > The advantages are twofold:
> > > 1. You want to limit the number of artifacts anyway - having more
> > > than 1000 bullets, for example, would slow down the frame rate
> > > 2. It is efficient because it never needs to allocate memory.
> > >
> > > It's pretty easy to do - but I was hoping for an "STL-friendly"
> > > version so that I can write
> > >
> > >
> > > std::for_each(bullets.begin(), bullets.end(), draw_bullet);
> > > std::for_each(bullets.begin(), bullets.end(), animate_bullet);
> > >
> > > etc.
> > >
> > > and
> > >
> > > void ship::fire_bullet()
> > > {
> > >    g_bullets.push_back(bullet(initial_bullet_velocity_));
> > > }
> > >
> > > the idea being that g_bullets.capacity() would never increase unless
> > > you explicitly called reserve().
> > >
> > > So in the above example, I would want the push_back call to just
> > > silently overwrite the oldest bullet, if the buffer was full.
> > >
> > > Of course, a ring buffer like this is also useful for many network
> > > protocols that keep "sliding windows" of messages that might need to
> > > be resent etc. Most protocols define a "maximum" size of such a
> > > window - again, any error would occur only if you couldn't find an
> > > entry in the buffer at a later point, not when you are inserting a
> > > new entry (and thus possibly overwriting the oldest entry).
> > >
> > > These are the type of problem domains a ring_buffer or
> > > circular_buffer would be used in.
> > >
> > > Paul Hollingsworth
> > > http://PaulHollingsworth.com
> > >
> > > --- In boost_at_y..., Howard Hinnant <hinnant_at_t...> wrote:
> > > > There were two ideas floating around:
> > > >
> > > > 1.  A circular_buffer that would extend its capacity when necessary
> > > > (similar to vector and deque).
> > > >
> > > > 2.  A circular_buffer that would throw an exception if the capacity
> > > was
> > > > exceeded.
> > > >
> > > > Which one (or both?) are you interested in?
> > > >
> > > > Personally I'm only interested in #1, and am willing to donate the
> > > > interface to an existing implementatation (taken pretty much from
> > > vector
> > > > and deque).  Unfortunately I can not donate the implementation
> > > itself,
> > > > but I would be happy to participate in and discuss design decisions
> > > on
> > > > such an implementation.
> > > >
> > > > -Howard
> > > >
> > > > boost_at_P... wrote on 2/24/01 6:30 PM
> > > > >Hi everyone,
> > > > >A while back there was a thread talking about a circular_buffer
> > > > >class. Does anyone know what happened?
> > > > >
> > > > >It would find it to be very useful.
> > >
> > >
> > >
> > >
> > > Your use of Yahoo! Groups is subject to
> http://docs.yahoo.com/info/terms/
> > >
> > >
> > >
> >
> >
> >
> >
> > Your use of Yahoo! Groups is subject to
http://docs.yahoo.com/info/terms/
>
>

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/