A Custom Block Allocator for Speeding Up VC++ STL

Paul Sanders (AlpineSoft)

23:45 27 May '08

Hello,

Can you please read the following thread about sort not behaving properly?

block_allocated_list::sort() does not return or produces incorrect result[^] (bottom of the page)

The reason was a bug in the Dinkumware std lib implementation of list::splice. I guess your problem is different since that was in MSVC++ 6.0 and you most likely are using a more modern compiler, but it doesn't hurt to check.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
Want a Boost forum in Code Project? Vote here[^]!

Low Fragmentation Heap

9:00 26 Oct '07

Another thing you might try to speed up memory allocation in general (not just for STL) is to enable Windows' Low Fragmentation Heap; just add the following at the start of your application:

ULONG HeapFragValue = 2;
HeapSetInformation ((void *) _get_heap_handle (), HeapCompatibilityInformation, &HeapFragValue, sizeof (HeapFragValue));

This works only on Windows XP or later and is convered in more detail here:

http://msdn2.microsoft.com/en-us/library/aa366750.aspx[^]

I am ashamed to say that I have not carried out any benchmarks myself, but I have read that it can make quite a difference (see http://xania.org/200512/crt-heap-fragmentation-in-windows[^]).

Paul Sanders
http://www.alpinesoft.co.uk

Free Heap block 347970 modified at 348394 after it was freed

Re: Free Heap block 347970 modified at 348394 after it was freed

8:33 19 Dec '06

I have used your block allocator with maps under a VC6 project inside two cdialogs (which are both childs of a Control bar and where i can switch from one to the other by a tab control)

in the first cdialog there are these definitions:


typedef block_allocated_map<long, long, 20> LONG2LONG;

LONG2LONG m_mapSrcAO;

in the other one:


typedef block_allocated_map<long, long, 20> LONG2LONG;

LONG2LONG m_mapSrcOP;
LONG2LONG m_mapBrkOP;

when the application is closed I receive the user breakpoint in the subject.

Commenting out the "LONG2LONG m_mapSrcAO;" definition in the first dialog solve the problem.
No one of the maps are modified (inserting or deleting entries). Only if I define the m_mapSrcAO member variable, I obtain the error.

Re: Free Heap block 347970 modified at 348394 after it was freed

8:46 19 Dec '06

Other clues: I 've tried to allocate the map in the heap, in the first dialog only: into the class definition: `typedef block_allocated_map<long, long, 20> LONG2LONG; LONG2LONG *m_mapSrcAO;` into the class constructor `.... m_mapSrcAO = new LONG2LONG; ....` into the class ondestroy handler `.... delete m_mapSrcAO; ....` and no problems arise.
Sign In·View Thread·PermaLink

Re: Free Heap block 347970 modified at 348394 after it was freed

9:26 19 Dec '06

if, in the first cdialog, i change the block size to a different value from the block size used in the second cdialog, all goes right !!! in the first cdialog `typedef block_allocated_map<long, long, 21> LONG2LONG;` in the second cdialog `typedef block_allocated_map<long, long, 20> LONG2LONG;`
Sign In·View Thread·PermaLink

Re: Free Heap block 347970 modified at 348394 after it was freed

3:29 20 Dec '06

Hello Nyarlatotep,

I think the problem you're experiencing is the same that was discussed here[^]. Basically, this is a bug of the Dinkumware's STL library shipping with MSVC++ 6.0 and can be hopefully solved by having (in your case) a LONG2LONG object defined somewhere as a static global.

Does this fix things?

Best regards,

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
Want a Boost forum in Code Project? Vote here[^]!

Excellent! and weird effect

4:04 20 Dec '06

Yes, it fixes !!! Thanks a lot !!! This is a very weird problem, however !!!
Sign In·View Thread·PermaLink

peterchen

10:20 14 Nov '06

First, a very very excellent drop-in replacement!

I'm mainly looking into it to increase memory locality to speed up some data-intense operations.

It works very well in one place (50% faster for a ridiculously oversized data set Smile

), however, in another (for me more interesting) place, I lose performance and wanted to ask if you have an idea what this can be:

The code in question uses a few hundred map[int, {16 byte struct}] instances, each map containing only a few (10..30) items. using block_allocator with small chunk sizes (128) I have about the same performance as std::map. Going to larger chunk sizes, performance radically degrades (half speed at 1024 bytes chunk size)

Speeding this up (instead of slowing it down Smile

) could improve responsiveness of the application notably. So I want to dig deeper. Now that might be memory locality, or another effect with the code (which does many things besides accesing that map). I wanted to ask if you have an idea what this can be.

Q:
Do you know a pathological case with your allcoator that may cause this?

Can your code be modified quickly so all maps of a given type use the same block allocator instance. This way I could test the effect is purely memory locality.

I would be grateful for some ideas.

Developers, Developers, Developers, Developers, Developers, Developers, Velopers, Develprs, Developers!
We are a big screwed up dysfunctional psychotic happy family - some more screwed up, others more happy, but everybody's psychotic joint venture definition of CP
Linkify!|Fold With Us!

Re: Excellent! and weird effect

Re: Excellent! and weird effect

11:35 14 Nov '06

peterchen wrote:
The code in question uses a few hundred map[int, {16 byte struct}] instances, each map containing only a few (10..30) items. using block_allocator with small chunk sizes (128) I have about the same performance as std::map. Going to larger chunk sizes, performance radically degrades (half speed at 1024 bytes chunk size)

If maps sizes top at 30 or so why do you choose a chunk size that high? I'd try setting chunk_size to something closer to 30.

peterchen wrote:
Q:
Do you know a pathological case with your allcoator that may cause this?

No. My hunch about what can be going on is related to the observation above: if you have chunks of 128 elements and each map occupy only around 20% of each associated chunk, you get lots of wasted memory and possibly poor locality. Try lowering the chunk size.

peterchen wrote:
Can your code be modified quickly so all maps of a given type use the same block allocator instance. This way I could test the effect is purely memory locality.

I can't check it right now, but it should be easy to hack this for a try:

In class block_allocator, make the members head and tail static.

Delete all constructors of block_allocator.

Move the head/tail initialization code:
```
      head.next=reinterpret_cast<chunk *>(&tail);
      tail.previous=reinterpret_cast<chunk *>(&head);
```
to some initialization routine of your program (this procedure must be done exactly once).

Please keep me informed about your progress. Hope this helps,

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
Want a Boost forum in Code Project? Vote here[^]!

peterchen

12:49 14 Nov '06

thanks for your quick reply!

Joaquín M López Muñoz wrote:
I'd try setting chunk_size to something closer to 30.

It's "chunks" not "bytes D'Oh!

- sometimes it helps to read documentation!
With chunks that big I'm definitely killing all locality.

I'll try to try the static test tomorrow (gotta get home now Wink

)

Problem with block_allocated_list::const_iterator in VS2005

Wocki

21:41 26 Oct '06

I can't use the const_iterator of the block_allocated_list because the compiler says "No access to private typedef....". If I comment out the const_iterator typedef in block_allocated_list it works.
Sign In·View Thread·PermaLink

Re: Problem with block_allocated_list::const_iterator in VS2005

why do you need to define MSVC_STL_list_node?

22:46 26 Oct '06

Wocki wrote:
I can't use the const_iterator of the block_allocated_list because the compiler says "No access to private typedef....".

If I comment out the const_iterator typedef in block_allocated_list it works.

Hello Wocki,

You're absolutely right, thanks for reporting the problem. A better fix is to make the offending typedef public, rather than commenting it out. I'll be shortly updating the code to solve this long standing bug (seems like it's been there since the very first version six years ago Sniff

)

Anyway, since you're using a modern compiler I suggest you abandon the block_allocated_list stuff, which is really only necessary for MSVC++ 6.0/7.0, and use block_allocator directly as explained in the article.

Best regards,

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
Want a Boost forum in Code Project? Vote here[^]!

thank you!

20:28 26 Oct '06

I just tested your code on VS2005 and I get a speedup by 3.8 compared to the normal STL allocator!!
Sign In·View Thread·PermaLink

chunk size

slonial

3:34 17 Feb '06

What should be the optimal value of chunk size when I am creating 6000 instance of map/list with Custom Block allocator. These 6000 instances are getting created in sequence,if I am keeping chunk size more than 100, the VM of the process shoots up. Thanx, Sumit
Sign In·View Thread·PermaLink

Anonymous

10:07 24 Aug '04

Hi,

I read your lock_allocator on CodeProject website, pretty impressive. however, i feel there is something that dosn't make sense and shouldn't implement like that way, just want to discuss with you.

in your blockallocator.h:

you define

template struct MSVC_STL_list_node
{
void *p1 , *p2;
T t;
};

template
class block_allocated_list:
public std::list , chunk_size>
>
{
...

why do you need to define MSVC_STL_list_node? it should be encapsulated
into the implementation algorithm of microsoft's std::list.

the bellowing is the definitions in MSDN of list:
template <
class Type,
class Allocator=allocator
>
class list

you can see, Allocator=allocator, Microsoft doesn't define an extern
MSVC_STL_list_node explicit. even though, it must be defined and hided in its implementation.

I also checked SGI/HP 's implemenation of STL. same finding.

Thus, I think you don't need to define block_allocated_list,
end user directly use std::list is fine, like:
std::list >

May be i am wrong? if so please correct me.

jesse

hellojesse@gmail.com

12:15 24 Aug '04

May be i am wrong? if so please correct me.

You are not wrong, this mechanism is a workaround to overcome a serious defficiency in MSVC++ 6.0. Let me explain.

Consider the following definition:

typedef std::list<int,funky_allocator<int> > funky_list;

which is the canonical way to use funky_allocator (or any other allocator): the allocator is instantiated to allocate nodes the size of the elements held (ints in the example). But, if you think of it, an STL list needs some additional internal data to maintain its data structure: normally, two pointers to keep the node linked to the prior and following element. So, internally, funky_list cannot just use the allocator as is, because it needs larger nodes.

With this problem in mind, STL designers invented a mechanism called rebinding:

typedef funky_allocator<int> int_allocator;
typedef int_allocator::rebind<double>::other double_allocator;

The oddly defined double_allocator type is exactly the same as

typedef funky_allocator<double> double_allocator;

I don't know how familiar you are with templates: if you don't get the syntax, do not trouble much about it; in essence, the rebinding mechanism allows an STL list to acquire an allocator instantiated for internal nodes from the user provided allocator instantiated for the type of the elements.

Unfortunately, template support in MSVC++ 6.0 is seriously broken so that the rebinding stuff cannot be implemented. For this reason, the implementors of the MSVC version of STL use a different, non-standard, strategy.

I don't want to dive into more details (unless you're curious), but basically, due to the lack of rebinding in MSVC++ 6.0, block_allocator must be instantiated with a type the exact size of the internal nodes used by an STL list (or set, map, etc.), which kinda breaks the encapsulation of the whole scheme. The classes block_allocated_list and family do this dirty work behind the scenes so that at least you've got a decent user interface. Had MSVC++ 6.0 support for allocator rebinding, instead of block_allocated_list you'd simply write:

typedef std::list<type,block_allocator<type,chunk_size> > my_list;

the way STL designers meant it to be.

Hope I've made myself more or less clears. Best,

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo

Anonymous

21:47 24 Aug '04

Joaquín:

thank you very much for your quick reply and your professional knowledge inside STL.
yes, there is rebinding in SGI's STL implementation as you said. now i understand what rebind is. Smile

   since MSVC++ 6.0 doesn't support allocator rebinding, the src code of microsoft's list explictly passes the size of node(with extra left/right pointer) as template parameter. However. MSDN website seems lying,i.e. not conforming to its src code.   please see this link:

         http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vcstdlib/html/vclrfList_class.asp

   please confirm whether my accuse of MSDN is right. thanks in advance!

   P.S.
   I enjoy coding in templates, do you have your own website   to share some topics in templates programming?

jesse
   hellojesse@gmail.com

5:11 25 Aug '04

The URL you refer to applies to MSVC 7.1 (aka .NET), which is conformant in this aspect. block_allocator is meant to be used in MSVC++ 6.0.

I enjoy coding in templates, do you have your own website to share some topics in templates programming?

No, sorry Frown

Thinking of it, that would be an interesting website to have. I don't know of any place devoted to template programing, though this is commonly discussed in newsgroups comp.lang.c++ and comp.lang.c++.moderated.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo

Anonymous

10:03 26 Aug '04

however, i find another nice article and it seems your arguments don't sound right. according to that article, we don't need to define template struct MSVC_STL_list_node by ourself and break the encapsulation.

here is what it said:

======================================================================
.....
VC++ 6.0 does not understand member template classes, so 'template struct rebind { typedef allocator other; };' is useless. Good to know. So, if our allocators have to work with VC++ 6.0 and Dinkumware, we need to implement a member function called '_Charalloc()':

// Begin Dinkumware (VC++ 6.0 SP5):
char *_Charalloc(size_type n) { return static_cast
(mem_.allocate(n)); }
// End Dinkumware
======================================================================
http://www.codeguru.com/Cpp/Cpp/cpp_mfc/stl/article.php/c4079

I also searched my MSDN help that is VC6.0, NOT .NET the std::list class declaration is the same as in .NET.

don't be mad at me, just want the real answer..

regards!

jesse

Anonymous

10:05 26 Aug '04

repost for formating issue.

however, i find another nice article and it seems your arguments don't sound right. according to that article, we don't need to define template struct MSVC_STL_list_node by ourself and break the encapsulation.

here is what it said:

   ======================================================================
   .....
   VC++ 6.0 does not understand member template classes, so 'template <class U> struct rebind { typedef allocator<U> other; };' is useless. Good to know. So, if our allocators have to work with VC++ 6.0 and Dinkumware, we need to implement a member function called '_Charalloc()':

   // Begin Dinkumware (VC++ 6.0 SP5):
   char *_Charalloc(size_type n) { return static_cast<char*>
                           (mem_.allocate(n)); }
   // End Dinkumware
======================================================================
http://www.codeguru.com/Cpp/Cpp/cpp_mfc/stl/article.php/c4079

I also searched my MSDN help that is VC6.0, NOT .NET   the std::list class declaration is the same as in .NET.

   don't be mad at me, just want the real answer..

regards!

jesse

10:48 26 Aug '04

don't be mad at me, just want the real answer..

Not at all, I love discussing this stuff. Please thrash me till you're satisfied Poke tongue

I'll answer in reverse order:

I also searched my MSDN help that is VC6.0, NOT .NET the std::list class declaration is the same as in .NET.

Yes, the interface of std::list is the same, what changes is the internal implementation with respect to how the allocator is used. Please keep reading.

VC++ 6.0 does not understand member template classes, so 'template struct rebind { typedef allocator other; };' is useless. Good to know. So, if our allocators have to work with VC++ 6.0 and Dinkumware, we need to implement a member function called '_Charalloc()'...

This is also correct and it is the key point of this discussion. Consider the definition

typed std::list<int,std::allocator<int> > my_list;

So, according to what the article says, the implementation in MSVC 6.0 of my_list allocates its nodes by calling

Charalloc(n)

where n is not sizeof(int) but rather the size of an internal node. So, the allocator does not know in advance how large the nodes requested will be (though they'll always be the same size for a given container and element). And the problem is that block_allocator needs to know this size at compile-time so that it can arrange its block structure in an efficient manner. To remedy this, the definition

block_allocated_list<type,chunk_size>

is basically the same (it derives from, actually) as

std::list<type,block_allocator<type,MSVC_STL_list_node<type>,chunk_size> >

and block_allocator uses the type MSVC_STL_list_node<type> only to gain knowledge, at compile-time, of the size of the nodes it'll be requested. That's it.

It's a little cumbersome, so if I haven't made myself completely clear please tell me so.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo

Anonymous

11:51 26 Aug '04

now everything clear.

1)your solution is to pass the size of List_Node at compiling time;
pro: speed up
con: break the encapsulation, we need to track whether or when MS change the definition of List_Node. even though the possibility is small.

2)the solution in that article on codeguru
pro: hide the encapsulation.
con: slow down a little bit by caculating the size of List_Node.

To be honest, i like 2) a little bit more.
but your article is well written and organized, you help me a lot
in understaning customzied allocator.
really appreciate.

12:32 26 Aug '04

now everything clear.

Great. Your analysis of the options available is correct, and, to be honest, option 2 looks more attractive to me, too. The article in Codeguru that you mention (I assume it is this[^]) is impressive. But I think there are some problems with its adaptation to _Charalloc:

If you read again the section on _Charalloc again, you'll note that they implement it like this:

  char *_Charalloc(size_type n) { return static_cast<char*>
                   (mem_.allocate(n)); }

Following the thread to the description of ss_storage, it turns out that, when requested a block which is not the default size (that of the element), this class looks for a row of contiguous cells making up for the space required. In our case, no fragmentation will happen (i.e., single cells in between rows), as the container will always be requesting the same size, but the following two problems still remain:

The algorithm is making unnecesary checks to see if there's a contiguos block: given what I said above, the first available cell will be always the beginning of appropriate contiguous row. This extra checks might impact performance.
The allocated memory is not entirely used most of the time, as the contiguous blocks will usually be sligthy large than strictly necessary.

It'd be interesting to benchmark this allocator and mine for time and space efficiency (take the challenge?)

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo