Should I define my own allocator?

Hi,

I have a map type such as std::map<int, int>, which I used to manage
many values in a fixed order. But I have thousands of values to be
inserted into the map, and in some case, the action of inserting and
re-building is very frequent, that say, many times per second.

I've made some tests to insert 1500 values into a map, it cost about
30ms in my athlon XP1800+. I think it shouldn't be so expensive. When I
do an inserting action, I think that an operator 'new' is called to
allocate very little memory, so about 1500 times 'new' is called. Maybe
it is the reason which make the action so expensive?

Now my question is: is it worth to implement my own allocator to
allocate memory in such a situation? And if it is worth, could you give
me some advice about how to write an allocator?

Thank you very much for your help :-)

re: Should I define my own allocator?

ddh,

It depends on what you're using this class for, and how big of a delta
you'd expect in performance by writing your own allocator
(unfortunately non-trivial to determine a priori). If this is
something you're using within the context of a larger application local
to you and a small-to-medium sized set of colleagues, I'd say first run
a profiler on the app as a whole to see how much of a bottleneck the
map is. Don't optimize part of a large system if it isn't slowing the
system down appreciably!

On the other hand, if you're publishing this as a standalone library or
something, intended for wide use, a custom allocator is worth
considering. Of course, I wonder why anyone would prefer your
implementation over std::map, but that's for you to answer.

For advice on writing an allocator like this, I recommend that you
check out chapter 4 of Andrei Alexandrescu's "Modern C++ Design." It
discusses, in great detail, the creation of an allocator for large
numbers of small objects. May be just what you need. There's probably
also a fair number of such allocator implementations freely available,
if you look around. If you can use one directly, fantastic. If not,
you may be able to at least temporarily plug it in so you can get some
perf numbers and decide if it's worth the effort to roll your own.

Best of luck,
Luke

re: Should I define my own allocator?

ddh wrote:
[color=blue]
> When I
> do an inserting action, I think that an operator 'new' is called to
> allocate very little memory, so about 1500 times 'new' is called. Maybe
> it is the reason which make the action so expensive?
>
> Now my question is: is it worth to implement my own allocator to
> allocate memory in such a situation? And if it is worth, could you give
> me some advice about how to write an allocator?[/color]

It seems you might be looking for a "pool allocator".
(It's just a class calls new to get batches of say a 1000
items at a time, then hands them over one by one as you request).

You could consider just using a std::vector for your objects
(it doubles the allocated size each time it runs out, but does
reallocation and copying, which may or may not suit you.)

There are also several such libraries available,
so you don't need to write your own.
You could try the pool library in Boost, see
http://www.boost.org/libs/pool/doc/index.html

Look for the pool_alloc or pool_allocator object - it can be
used as a drop-in replacement for std::allocator.

Cheers,

homsan

re: Should I define my own allocator?

ddh wrote:

[]
[color=blue]
> Now my question is: is it worth to implement my own allocator to
> allocate memory in such a situation? And if it is worth, could you give
> me some advice about how to write an allocator?[/color]

Profile your code to find hot spots.

Linux malloc, for example, has fast bins for objects smaller than a
certain limit (64 is a common value), which is essentially a pool
allocator.

re: Should I define my own allocator?

Thank you, and I've read some articles about it. To implement an
allocator is not difficult, but to implement an efficient & bug-free
one is somewhat difficult. So I want to do this after I finish all my
other work.

Thank you


Luke Meyers wrote:[color=blue]
> ddh,
>
> It depends on what you're using this class for, and how big of a delta[/color]

re: Should I define my own allocator?

homsan toft wrote:[color=blue]
>
>
> It seems you might be looking for a "pool allocator".[/color]
Yes, it is what I want.
[color=blue]
>
> You could consider just using a std::vector for your objects[/color]
I must sort the data, so I choice std::map.
[color=blue]
>
> http://www.boost.org/libs/pool/doc/index.html[/color]
Thank you very much, and I will read this document[color=blue]
>[/color]


Thank you :-)