How to implement a buffer (memory?) pool

[Tron Thomas]

As part of applying for a programming position at a company, I
recently I had submitted some code samples to one of the developers
for review.

This is the feedback I received:

One of his concerns was frequent calls to new and delete, which can
cause
memory fragmentation over time. An example is the allocation and
destruction
of a memory buffer for every network packet transmission, vs.
employing a
buffer pool.

I assume a "buffer pool" is the same thing as a memory pool.

Could anyone please direct me to resources that would provide me with
information on how to implement a buffer/memory pool especially for
the use of transmitting network packets.

[c wood]

"Tron Thomas" <tr*********@verizon.net> wrote in message
news:a4**************************@posting.google.c om...

As part of applying for a programming position at a company, I
recently I had submitted some code samples to one of the developers
for review.

This is the feedback I received:

One of his concerns was frequent calls to new and delete, which can
cause
memory fragmentation over time. An example is the allocation and
destruction
of a memory buffer for every network packet transmission, vs.
employing a
buffer pool.

I assume a "buffer pool" is the same thing as a memory pool.

Could anyone please direct me to resources that would provide me with
information on how to implement a buffer/memory pool especially for
the use of transmitting network packets.

Allocate enough memory "once" and then use it each time. If you have a
situation where multiple buffers are needed, then you could create 5 (or
however many) of them, store the address, and store when it's active or not
(being used). It all depends on how many you need at the same time.

Then, when you need a buffer, you call a function which gets a buffer
from this pool, when you are done with it, you call a function that marks
the area as free again. When that all works you can contemplate overriding
new/delete for a specific class of "network buffer" class.

Sometimes you need a variable number of things, with unknown limits.
That can get interesting as your type of storage for the list has to be of a
method that doesn't fragment memory after time (as you resize your
containers that hold the pointers). Of course, it's up to your OS and
implementation on how it does things also. Last time I googled for a
memory pool class I came up with nothing useful (to me)

I believe there is a reason for that:

There's usually a specific type of memory pool that works for a
specific situation, custom code type thing. There may be a blanket
solution these days, but I doubt it would fit every possible use. I must
also mention that this is a very important/core feature of any program that
intends to run very long.

You should write some sample programs (test programs) and see what the
address of things are after new/deleteing a bunch of things: Such as

new a
new b
new c
delete b
new d
.. Keep doing this...

Then see where the object lie. It's interesting to see how garbled it
can get after a while.

Good luck.

[Tron Thomas]

"c wood" <re******@verizon.net> wrote in message news:<ne****************@nwrddc02.gnilink.net>...

Allocate enough memory "once" and then use it each time. If you have a
situation where multiple buffers are needed, then you could create 5 (or
however many) of them, store the address, and store when it's active or not
(being used). It all depends on how many you need at the same time.

Then, when you need a buffer, you call a function which gets a buffer
from this pool, when you are done with it, you call a function that marks
the area as free again. When that all works you can contemplate overriding
new/delete for a specific class of "network buffer" class.

Sometimes you need a variable number of things, with unknown limits.
That can get interesting as your type of storage for the list has to be of a
method that doesn't fragment memory after time (as you resize your
containers that hold the pointers). Of course, it's up to your OS and
implementation on how it does things also. Last time I googled for a
memory pool class I came up with nothing useful (to me)

I believe there is a reason for that:

There's usually a specific type of memory pool that works for a
specific situation, custom code type thing. There may be a blanket
solution these days, but I doubt it would fit every possible use. I must
also mention that this is a very important/core feature of any program that
intends to run very long.

You should write some sample programs (test programs) and see what the
address of things are after new/deleteing a bunch of things: Such as

new a
new b
new c
delete b
new d
.. Keep doing this...

Then see where the object lie. It's interesting to see how garbled it
can get after a while.

Good luck.

I understand the general concept of a memory pool. What I'm not sure
of is how I would want to actually implement one.

Allocating a buffer to instantiate objects doesn't seem to prevent the
problem of fragmentation. The fragmentation will now be localized to
the allocated buffer and not the global heap. This fragmentation
seems to be what the developer who offered feedback I stated in my
original post was most concerned about.

I can appreciate the fact that a memory pool implementation may be
specific to the context it is used. Seeing different implementation
in different contexts would still be useful for letting me know how I
would want to do my implementation.

Where could I find some examples of implemented memory pools?

[Jakob Bieling]

"Tron Thomas" <tr*********@verizon.net> wrote in message
news:a4**************************@posting.google.c om...

"c wood" <re******@verizon.net> wrote in message

news:<ne****************@nwrddc02.gnilink.net>...

Allocate enough memory "once" and then use it each time. If you have a situation where multiple buffers are needed, then you could create 5 (or
however many) of them, store the address, and store when it's active or not (being used). It all depends on how many you need at the same time.

Then, when you need a buffer, you call a function which gets a buffer from this pool, when you are done with it, you call a function that marks the area as free again. When that all works you can contemplate overriding new/delete for a specific class of "network buffer" class.

Sometimes you need a variable number of things, with unknown limits. That can get interesting as your type of storage for the list has to be of a method that doesn't fragment memory after time (as you resize your
containers that hold the pointers). Of course, it's up to your OS and
implementation on how it does things also. Last time I googled for a
memory pool class I came up with nothing useful (to me)

I believe there is a reason for that:

There's usually a specific type of memory pool that works for a
specific situation, custom code type thing. There may be a blanket
solution these days, but I doubt it would fit every possible use. I must also mention that this is a very important/core feature of any program that intends to run very long.

You should write some sample programs (test programs) and see what the address of things are after new/deleteing a bunch of things: Such as

new a
new b
new c
delete b
new d
.. Keep doing this...

Then see where the object lie. It's interesting to see how garbled it can get after a while.

Good luck.

I understand the general concept of a memory pool. What I'm not sure
of is how I would want to actually implement one.

Allocating a buffer to instantiate objects doesn't seem to prevent the
problem of fragmentation. The fragmentation will now be localized to
the allocated buffer and not the global heap. This fragmentation
seems to be what the developer who offered feedback I stated in my
original post was most concerned about.

Well, look at it this way: The memory pool allocates a block of memory
when needed. If a second block is needed, it allocates that one as well. Now
the first one is freed and after that another one is requested. Most of the
time, you would get a completely new block of memory now. Repeat this and
you get the fragmentation. But now, your memory pool manager class (or
whatever) does not allocate a new one, but first checks if a previously
freed block (in your 'pool' of memory blocks) is large enough to fulfill the
allocation request. If so, you can avoid allocating new memory.

hth
--
jb

(replace y with x if you want to reply by e-mail)

[c wood]

"Tron Thomas" <tr*********@verizon.net> wrote in message
news:a4**************************@posting.google.c om...

"c wood" <re******@verizon.net> wrote in message news:<ne****************@nwrddc02.gnilink.net>... I understand the general concept of a memory pool. What I'm not sure
of is how I would want to actually implement one.

Allocating a buffer to instantiate objects doesn't seem to prevent the
problem of fragmentation. The fragmentation will now be localized to
the allocated buffer and not the global heap. This fragmentation
seems to be what the developer who offered feedback I stated in my
original post was most concerned about.

I can appreciate the fact that a memory pool implementation may be
specific to the context it is used. Seeing different implementation
in different contexts would still be useful for letting me know how I
would want to do my implementation.

Where could I find some examples of implemented memory pools?

Try www.google.com with the search for "C++" memory pool

But like I said, there isn't going to be a cure all that fits your
situation unless you tell us the situation.

Answer these:

How many will you need at one time (MAX)?.
How many on average will you need?
What size is the buffer or is it variable, if so, what size range
in bytes?

Your answers to those 3.5 questions make a huge difference on what would
work for you.

You could also google for memory allocation algorithms, but that's
the worst case scenario.

/* OFF TOPIC: Please also note that some OS's have such mechanisms
built into them. */

[lilburne]

Jakob Bieling wrote:

"Tron Thomas" <tr*********@verizon.net> wrote in message
news:a4**************************@posting.google.c om...

"c wood" <re******@verizon.net> wrote in message

Allocating a buffer to instantiate objects doesn't seem to prevent the
problem of fragmentation. The fragmentation will now be localized to
the allocated buffer and not the global heap. This fragmentation
seems to be what the developer who offered feedback I stated in my
original post was most concerned about.

Well, look at it this way: The memory pool allocates a block of memory
when needed. If a second block is needed, it allocates that one as well. Now
the first one is freed and after that another one is requested. Most of the
time, you would get a completely new block of memory now. Repeat this and
you get the fragmentation.

Maybe, maybe not, on some implementations if you deallocate
20 bytes and then allocate 20 bytes you'll get back the same
memory pointer.

But now, your memory pool manager class (or
whatever) does not allocate a new one, but first checks if a previously
freed block (in your 'pool' of memory blocks) is large enough to fulfill the
allocation request. If so, you can avoid allocating new memory.

That is usually how memory allocators are implemented
anyway, they mostly avoid growing the address space
allocated. Fragmentation occurs because memory allocations
are released in between other memory allocations and you end
up with small holes of freed memory:

=== ==== == == ==== == ===== ===== ==== ====

the memory pool doesn't eliminate this fragmentation but
limits its scope:

memory pool
=== ==== == ==-====-==--==== ===== ==== ====

the fragmentation due to the packet allocations doesn't
spread outside of the block set aside for this purpose.

[Jakob Bieling]

"lilburne" <li******@godzilla.net> wrote in message
news:br*************@ID-203936.news.uni-berlin.de...

Jakob Bieling wrote:

But now, your memory pool manager class (or
whatever) does not allocate a new one, but first checks if a previously
freed block (in your 'pool' of memory blocks) is large enough to fulfill the allocation request. If so, you can avoid allocating new memory.

That is usually how memory allocators are implemented
anyway, they mostly avoid growing the address space
allocated. Fragmentation occurs because memory allocations
are released in between other memory allocations and you end
up with small holes of freed memory:

=== ==== == == ==== == ===== ===== ==== ====

the memory pool doesn't eliminate this fragmentation but
limits its scope:

memory pool
=== ==== == ==-====-==--==== ===== ==== ====

the fragmentation due to the packet allocations doesn't
spread outside of the block set aside for this purpose.

The only other solution would be t allocate one llarger block of memory
and return parts of it to the caller. But as the OP pointed out already,
this would only move fragmentation from the heap to the memory pool, unless
the allocation sizes are always the same (which, in the OPs solution is very
unlikely to be the case).

Unless you have a different approach, I do not see why I should go thru
the extra effort of managing my own memory block, when I can let the heap do
this and still end up with the same fragmentation.

regards
--
jb

(replace y with x if you want to reply by e-mail)

[Tron Thomas]

c wood wrote:

Try www.google.com with the search for "C++" memory pool

But like I said, there isn't going to be a cure all that fits your
situation unless you tell us the situation.

Answer these:

How many will you need at one time (MAX)?.
How many on average will you need?
What size is the buffer or is it variable, if so, what size range
in bytes?

Your answers to those 3.5 questions make a huge difference on what would
work for you.

You could also google for memory allocation algorithms, but that's
the worst case scenario.

/* OFF TOPIC: Please also note that some OS's have such mechanisms
built into them. */

I tried the search you suggested on Google, and it didn't reveal
anything that was more useful than any other searches I've already tried

The program I'm working on is a two player networked game that sends
messages between two systems. I modified my code to spit out how much
memory the program was consuming while it was sending messages.

Here are some of the results I got:

0 bytes allocated for message use.
20 bytes allocated for message use.
28 bytes allocated for message use.
8 bytes allocated for message use.
64 bytes allocated for message use.
108 bytes allocated for message use.
52 bytes allocated for message use.
8 bytes allocated for message use.
0 bytes allocated for message use.
44 bytes allocated for message use.
88 bytes allocated for message use.
128 bytes allocated for message use.
88 bytes allocated for message use.
44 bytes allocated for message use.
84 bytes allocated for message use.
44 bytes allocated for message use.
0 bytes allocated for message use.
56 bytes allocated for message use.
100 bytes allocated for message use.
44 bytes allocated for message use.
0 bytes allocated for message use.
44 bytes allocated for message use.
88 bytes allocated for message use.
128 bytes allocated for message use.
88 bytes allocated for message use.
44 bytes allocated for message use.
84 bytes allocated for message use.
44 bytes allocated for message use.
0 bytes allocated for message use.
....
0 bytes allocated for message use.
44 bytes allocated for message use.
88 bytes allocated for message use.
128 bytes allocated for message use.
172 bytes allocated for message use.
216 bytes allocated for message use.
236 bytes allocated for message use.
244 bytes allocated for message use.
224 bytes allocated for message use.
280 bytes allocated for message use.
324 bytes allocated for message use.
268 bytes allocated for message use.
228 bytes allocated for message use.
184 bytes allocated for message use.
224 bytes allocated for message use.
184 bytes allocated for message use.
140 bytes allocated for message use.
180 bytes allocated for message use.
136 bytes allocated for message use.
192 bytes allocated for message use.
236 bytes allocated for message use.
180 bytes allocated for message use.
140 bytes allocated for message use.
96 bytes allocated for message use.
136 bytes allocated for message use.
96 bytes allocated for message use.
52 bytes allocated for message use.
44 bytes allocated for message use.
88 bytes allocated for message use.
132 bytes allocated for message use.
172 bytes allocated for message use.
228 bytes allocated for message use.
272 bytes allocated for message use.
216 bytes allocated for message use.
176 bytes allocated for message use.
132 bytes allocated for message use.
172 bytes allocated for message use.
132 bytes allocated for message use.
88 bytes allocated for message use.
44 bytes allocated for message use.
0 bytes allocated for message use.
....
572 bytes allocated for message use.

The last entry in the results is out of context and it is included
because it was the largest value I found when looking at the output.

Does the output go towards answering the questions you posed in your post?

[Tron Thomas]

I have create an implementation for a memory pool, and it seems to
work. Would it be practical for me to post the implmentation here for
people to review and let me know if it seems like it would be
effective for what I want to accomplish?

tr*********@verizon.net (Tron Thomas) wrote in message news:<a4**************************@posting.google. com>...

As part of applying for a programming position at a company, I
recently I had submitted some code samples to one of the developers
for review.

This is the feedback I received:

One of his concerns was frequent calls to new and delete, which can
cause
memory fragmentation over time. An example is the allocation and
destruction
of a memory buffer for every network packet transmission, vs.
employing a
buffer pool.

I assume a "buffer pool" is the same thing as a memory pool.

Could anyone please direct me to resources that would provide me with
information on how to implement a buffer/memory pool especially for
the use of transmitting network packets.