Solved

STL MAP Allocator

Posted on 2002-06-10
8
740 Views
Last Modified: 2010-05-18
Does anyone know how the STL mapp allocator works?
how much memory does it allocate when it is created? how much does it allocate when it runs out of memory? and what is the algorythm the allocation is based on?
do you know where can i find more information about this?

basically i'm looking for a map allocator that allocates rather small amount of nodes on creation, and aech time it is required to allocate more memory, it doubles the last amount of memory that was allocated on the last time.
do you know or have such an allocator?
Thanks,
Udi
0
Comment
Question by:udibs
8 Comments
 
LVL 9

Accepted Solution

by:
jasonclarke earned 50 total points
Comment Utility
> how much memory does it allocate when it is created?

there is no way to know by default.  An implementation of map is allowed to do whatever it likes.

However, I believe that, at least with the MS implementation, it uses a tree structure to implement the map, and uses a per-pair allocation strategy - that is for each key/value pair memory is allocated.
0
 
LVL 22

Expert Comment

by:nietod
Comment Utility
>> Does anyone know how the STL map allocator works?
As jason said, there is no hard and fast way, it depends on the implimentationand which allocator you are talking about.   But the default allocator in the typical implimenation will just allocates arrays of the required length using the new operator and delete them with the delete opeator.  i.e.

pointer alloctor::allocate(size_type n,pointer *hint)
{
    return new value_type[n];
}

void allocator::deallocate(pointer *p,size_type n)
{
   delete [] p;
}


I would also add there is no speciall STL map allocator.  the STL map, uses an ordinary allocator, just like any other STL container class.

>> how much memory does it allocate when it is created?
Again, as jason said, no one knows.   but most probably allocate no memory when created.   Then allocate memory when it is requested.

>> how much does it allocate when it runs out of memory?
It it runs out of memory it can't allocate memory.  In that case it throws an exception.    It allocates memory when requested (when the allocate() function is called) until it can't allocate memory, then it throws an exceoption.


>> basically i'm looking for a map allocator that allocates rather
>> small amount of nodes on creation, and aech time it is required
>> to allocate more memory, it doubles the last amount of memory
>> that was allocated
That is not the allocator's responsibility.  The map will decide how many nodes it needs.    You could write your own special allocator that does this.   But imagine the problems you would face.   Lets sayt eh idea was to allocate the nodes in large arrays on some requests and then return pointers to those allocated and unsused enties on later requests.   The map will be allocating and freeing nodes in an apparently random order.   So you will find that some of your earlier used entries will become free again.  How will you manage to track which are used and which aren't?    The only efficient way to do this is to write your own heap code.    If you are going to do that, why not just use the standard heap?  i.e. why not just use new and delete.

By the way, in many implimenations, the containers reuse allocated memory rather then freeing it.   For example VC's STL map will save the nodes unused in a linked list so it doesn't have to free the nodes and allocate them again.  It allocates memory only when it runs out of nodes in the list.
0
 

Author Comment

by:udibs
Comment Utility
thanks for your help guys, but i think i didn't give you all the info you need. i'm writing a W2K based application, that is, i will be using the microsoft implementation of the map and allocator. I know it uses a tree, and what i'm looking for is a way to control its allocations. if this means that i'll have to write my own heap, fine, isn't that what writing allocators is all about? it would be better if i had a working one though, or at least some examples.
do you know where can i find a code for such an allocator?
0
 
LVL 22

Expert Comment

by:nietod
Comment Utility
>> 'm looking for is a way to control its allocations.
Why?

The usual answer is that this is to improve either speed or memory use.   Both are the wrong reasons.

It is EXTREMELY unlikely that the allocator will be a bottleneck for your program.   If it isn't a bottleneck then improving its speed will not make any measurable difference in your program's speed.   So its very unlikely that you need to improve its speed.   Besides, the builtin heap functions a fairly well written.  You aren't likely to do significanly better (although you could do some thing they couldn't)

If you want to improve its memory use, you can just about forget it.   The map is still going to buffer its unused nodes just as before.   You don't have any chance for chaning this unless you rewrite map.

This is a guess,b ut your asking for doubling the size on each allocation seems to suggest you are hoping to do something like vector<> does to get amortized constant time efficiency on insertions into the container.   It won't work.  map's efficiency is not governed by the allocator, but instead by its internal structure.  i.e. the allocation is an approximately fixed-time cost, its the searches and reorganizations that must be done in the tree that governs its efficiency.

>>  if this means that i'll have to write my own heap, fine,
>> isn't that what writing allocators is all about? i
Not really.   The main reason is to control other aspects of allocation.    Like perhaps allighment, or the region in memory the data comes from (like in DOS the might be a near heap or far heap, on an embedded system there might be some memory that is set aside for long term allocations etc.)
0
Threat Intelligence Starter Resources

Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

 

Author Comment

by:udibs
Comment Utility
Ok, i see where you getting at.
lets say that this map needs to know how to deal with millions of nodes. today, what we're using is some kind of a heap someone wrote ages ago. all the memory for this heap is allocated in one call to new, and its size is calculated according to the worse case scenario. however,
in most of the times the application doesn't need the whole amount of memory, but rather a small part of it. the nodes should be sorted by their keys, that's why map is good for us. now, the data flows in from a real time source, so we can't risk losing it due to the allocation time of a new bulk. all of that leads me to writing my own allocator, unless you wanna tell me otherwise...
0
 
LVL 22

Expert Comment

by:nietod
Comment Utility
>> so we can't risk losing it due to the allocation time of a new bulk
Do you have any evidenc that the allocation time is a bottleneck?   If not, then you aren't going to acomplish anything.  If you were an INCREADIBLY good programmer and magically made the allocation take no time at all, you probably wouldn't be able to measure any difference in the program speed.   Why?  Its the 80-20 rule.   There is very little--if any--benefit to optimizing a non-bottleneck.


The first thing to do is to see if this is a bottleneck, then if it is is--which is unlikely--then you can consider methods to improve it.   If its not a bottleneck, then no method to improve it is going to do much good for you.


If it really turns out this is a bottleneck, we can write an allocator that uses a vector for storing the data.   Basically it is a simplified heap that uses a vector for storing the data.  The allocator This is likely to be a liffle faster than using the general heap.  The main advantage to this method over the regular heap is that all items on this simplified heap are the same size, so there is no search to find an unused block of the right size i.e.  any unused block is the right size.  

But even though this is simplified, its still likely to be a few hours of programming.   Why spend that time if you don't need it.  Try it with the default allocator first.    Then if things aren't fast enough, then profile the code to find the bottlenecks.  (Note that even if the code with the default allocator is  not fast enough, there is a good chance that fixing the allocator won't make any difference, and instead there is something else you need to improve.)  
0
 
LVL 11

Expert Comment

by:griessh
Comment Utility
Dear udibs

I think you forgot this question. I will ask Community Support to close it unless you finalize it within 7 days. You can always request to keep this question open. But remember, experts can only help you if you provide feedback to their questions.
Unless there is objection or further activity,  I will suggest to split between

     "nietod and jasonclarke"

comment(s) as an answer.

PLEASE DO NOT ACCEPT THIS COMMENT AS AN ANSWER!
======
Werner
0
 
LVL 6

Expert Comment

by:Mindphaser
Comment Utility
Force accepted

** Mindphaser - Community Support Moderator **

nietod, there will be a separate question with points for your help.
0

Featured Post

Enabling OSINT in Activity Based Intelligence

Activity based intelligence (ABI) requires access to all available sources of data. Recorded Future allows analysts to observe structured data on the open, deep, and dark web.

Join & Write a Comment

IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

771 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now