Click here to Skip to main content
11,718,289 members (88,698 online)
Click here to Skip to main content

A Custom Block Allocator for Speeding Up VC++ STL

, 30 Oct 2006 CPOL 186.6K 1.4K 57
Rate this:
Please Sign up or sign in to vote.
A block allocator for use with STL containers that greatly improves speed in programs doing massive data insertions and extractions.

Introduction

block_allocator is a custom STL allocator for use with STL as implemented in Microsoft VC++. Rather than doing allocations on a per-node basis, block_allocator allocates memory in fixed sized chunks, and delivers portions of these chunks as requested. Typical speed improvements of 40% have been obtained with respect to the default allocator. The size of the chunks, set by the user, should not be too little (reduced speed improvements) nor too large (memory wasted). Experiment and see what sizes fit best to your application.

block_allocator can substitute for the default allocator in the following containers:

  • list,
  • set,
  • multiset,
  • map,
  • multimap,
and WON'T work with other containers such as vector or queue. Note however that vector and queue already perform allocation in chunks. The usage of block_allocator is fairly simple, for instance:
// block allocated list of ints with chunks of 1024 elements
std::list<int,block_allocator<int,1024> > l;
Normal containers and block allocated containers can coexist without problems.

Compatibility mode with MSVC++ 6.0/7.0

Due to limitations of the standard library provided with these compilers, the mode of usage explained above does not work here. To circumvent this problem one must proceed as follows: For each of the containers supported, there's an associated block allocated container derived from it thru use of block_allocator. You have to define an activating macro for each container to be defined prior to the inclusion of blockallocator.h:

  • list -> block_allocated_list (macro DEFINE_BLOCK_ALLOCATED_LIST),
  • set -> block_allocated_set (macro DEFINE_BLOCK_ALLOCATED_SET),
  • multiset -> block_allocated_multiset (macro DEFINE_BLOCK_ALLOCATED_MULTISET),
  • map -> block_allocated_map (macro DEFINE_BLOCK_ALLOCATED_MAP),
  • multimap -> block_allocated_multimap (macro DEFINE_BLOCK_ALLOCATED_MULTIMAP),

To use block allocation based STL in your application, define the corresponding activating macro, include blockallocator.h and then change your declarations as follows:

  • list<type> -> block_allocated_list<type,chunk_size>
  • set<key> -> block_allocated_set<key,chunk_size>
  • multiset<key> -> block_allocated_multiset<key,chunk_size>
  • map<key,type> -> block_allocated_map<key,type,chunk_size>
  • multimap<key,type> -> block_allocated_multimap<key,type,chunk_size>

where chunk_size is the size of the chunks. You can enter too the other optional template parameters (see MSVC++ STL docs for more info).

The MSVC++ 6.0/7.0 compatibility mode can also be used in MSVC++ 7.1, so you need not modify your block_allocator-related code when porting legacy code to 7.1.

Multithreading issues

Each block allocated container instance uses its own block_allocator, so no multithreading problems should arise as long as your program conveniently protects their containers for concurrent access (or if no two threads access the same container instance). This is the same scenario posed by regular STL classes (remember operations on containers are not guarded by CRITICAL_SECTIONs or anything similar), so the moral of it all is: If your program was multithread safe without block_allocator, it'll continue to be with it.

Version history

  • 29th Feb, 2000 - 1.1
    • Initial release in CodeProject.
  • 22nd Mar, 2001 - 1.2
    • Included definitions for operator== and operator!=. The lack of these caused linking errors when invoking list::swap() and similar methods. The funny thing about it is that no one ever reported this seemingly important bug, so either swap() is not that much used or not that many people use block_allocator!
  • 25th Oct, 2006 - 1.3
    • block_allocator now works with MSVC++ 7.1 and 8.0. Thanks to James May for helping with testing this new version of the code.
  • 30th Oct, 2006 - 1.4
    • Fixed some typedefs incorrectly made private in block_allocated_list, block_allocated_set, etc.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

No Biography provided

You may also be interested in...

Comments and Discussions

 
GeneralRe: Free Heap block 347970 modified at 348394 after it was freed Pin
Nyarlatotep19-Dec-06 8:26
memberNyarlatotep19-Dec-06 8:26 
GeneralRe: Free Heap block 347970 modified at 348394 after it was freed Pin
Joaquín M López Muñoz20-Dec-06 2:29
memberJoaquín M López Muñoz20-Dec-06 2:29 
GeneralRe: Free Heap block 347970 modified at 348394 after it was freed Pin
Nyarlatotep20-Dec-06 3:04
memberNyarlatotep20-Dec-06 3:04 
GeneralExcellent! and weird effect Pin
peterchen14-Nov-06 9:20
memberpeterchen14-Nov-06 9:20 
GeneralRe: Excellent! and weird effect Pin
Joaquín M López Muñoz14-Nov-06 10:35
memberJoaquín M López Muñoz14-Nov-06 10:35 
GeneralRe: Excellent! and weird effect Pin
peterchen14-Nov-06 11:49
memberpeterchen14-Nov-06 11:49 
GeneralProblem with block_allocated_list::const_iterator in VS2005 Pin
Wocki26-Oct-06 20:41
memberWocki26-Oct-06 20:41 
AnswerRe: Problem with block_allocated_list::const_iterator in VS2005 Pin
Joaquín M López Muñoz26-Oct-06 21:46
memberJoaquín M López Muñoz26-Oct-06 21:46 
Generalthank you! Pin
wb26-Oct-06 19:28
memberwb26-Oct-06 19:28 
Generalchunk size Pin
slonial17-Feb-06 2:34
memberslonial17-Feb-06 2:34 
Questionwhy do you need to define MSVC_STL_list_node? Pin
Anonymous24-Aug-04 9:07
sussAnonymous24-Aug-04 9:07 
AnswerRe: why do you need to define MSVC_STL_list_node? Pin
Joaquín M López Muñoz24-Aug-04 11:15
memberJoaquín M López Muñoz24-Aug-04 11:15 
GeneralRe: why do you need to define MSVC_STL_list_node? Pin
Anonymous24-Aug-04 20:47
sussAnonymous24-Aug-04 20:47 
GeneralRe: why do you need to define MSVC_STL_list_node? Pin
Joaquín M López Muñoz25-Aug-04 4:11
memberJoaquín M López Muñoz25-Aug-04 4:11 
GeneralRe: why do you need to define MSVC_STL_list_node? Pin
Anonymous26-Aug-04 9:03
sussAnonymous26-Aug-04 9:03 
GeneralRe: why do you need to define MSVC_STL_list_node? Pin
Anonymous26-Aug-04 9:05
sussAnonymous26-Aug-04 9:05 
GeneralRe: why do you need to define MSVC_STL_list_node? Pin
Joaquín M López Muñoz26-Aug-04 9:48
memberJoaquín M López Muñoz26-Aug-04 9:48 
GeneralRe: why do you need to define MSVC_STL_list_node? Pin
Anonymous26-Aug-04 10:51
sussAnonymous26-Aug-04 10:51 
GeneralRe: why do you need to define MSVC_STL_list_node? Pin
Joaquín M López Muñoz26-Aug-04 11:32
memberJoaquín M López Muñoz26-Aug-04 11:32 
GeneralRe: why do you need to define MSVC_STL_list_node? Pin
Anonymous26-Aug-04 20:54
sussAnonymous26-Aug-04 20:54 
GeneralRe: why do you need to define MSVC_STL_list_node? Pin
Joaquín M López Muñoz28-Aug-04 9:45
memberJoaquín M López Muñoz28-Aug-04 9:45 
GeneralRe: why do you need to define MSVC_STL_list_node? Pin
Anonymous7-Sep-04 8:46
sussAnonymous7-Sep-04 8:46 
Generalblock_allocated_list::sort() does not return or produces incorrect result Pin
PeteH16-Apr-03 18:50
sussPeteH16-Apr-03 18:50 
GeneralRe: block_allocated_list::sort() does not return or produces incorrect result Pin
PeteH18-Apr-03 11:47
memberPeteH18-Apr-03 11:47 
GeneralRe: block_allocated_list::sort() does not return or produces incorrect result Pin
Joaquín M López Muñoz20-Apr-03 21:26
memberJoaquín M López Muñoz20-Apr-03 21:26 
QuestionAnyone tried this with VS .net? Pin
bobboberts8-Jan-03 15:10
memberbobboberts8-Jan-03 15:10 
AnswerRe: Anyone tried this with VS .net? Pin
Joaquín M López Muñoz9-Jan-03 9:24
memberJoaquín M López Muñoz9-Jan-03 9:24 
GeneralRe: Anyone tried this with VS .net? Pin
jherico1-May-03 13:31
memberjherico1-May-03 13:31 
GeneralRe: Anyone tried this with VS .net? Pin
Joaquín M López Muñoz4-May-03 9:58
memberJoaquín M López Muñoz4-May-03 9:58 
GeneralRe: Anyone tried this with VS .net? Pin
João Paulo Figueira20-Oct-03 0:10
memberJoão Paulo Figueira20-Oct-03 0:10 
GeneralRe: Anyone tried this with VS .net? Pin
Joaquín M López Muñoz20-Oct-03 0:36
memberJoaquín M López Muñoz20-Oct-03 0:36 
AnswerRe: Anyone tried this with VS .net? Pin
Rajg26-Jun-04 23:40
memberRajg26-Jun-04 23:40 
GeneralRe: Anyone tried this with VS .net? Pin
Anonymous16-Jul-05 2:59
sussAnonymous16-Jul-05 2:59 
GeneralChange in behaviour of list::splice Pin
Brad Davis19-Apr-02 15:31
memberBrad Davis19-Apr-02 15:31 
GeneralRe: Change in behaviour of list::splice Pin
Joaquín M López Muñoz20-Apr-02 6:35
memberJoaquín M López Muñoz20-Apr-02 6:35 
QuestionWill this decrease size? Pin
Rusty19-Feb-02 13:39
memberRusty19-Feb-02 13:39 
AnswerRe: Will this decrease size? Pin
Joaquín M López Muñoz19-Feb-02 20:10
memberJoaquín M López Muñoz19-Feb-02 20:10 
Generalusing with dinkumware library Pin
Thomas George14-Feb-02 10:26
memberThomas George14-Feb-02 10:26 
GeneralRe: using with dinkumware library Pin
Joaquín M López Muñoz14-Feb-02 20:41
memberJoaquín M López Muñoz14-Feb-02 20:41 
QuestionHow can such an allocator be used in a vector? Pin
Thomas George5-Feb-02 5:32
memberThomas George5-Feb-02 5:32 
AnswerRe: How can such an allocator be used in a vector? Pin
Joaquín M López Muñoz5-Feb-02 6:01
memberJoaquín M López Muñoz5-Feb-02 6:01 
Generalblockallocator bug Pin
Ing. Capelli Carlo6-Mar-01 10:20
memberIng. Capelli Carlo6-Mar-01 10:20 
GeneralRe: blockallocator bug Pin
Joaquín M López Muñoz7-Mar-01 21:58
memberJoaquín M López Muñoz7-Mar-01 21:58 
Generalblockallocator bug: closer inspection and proposed workaround Pin
Joaquín M López Muñoz2-Oct-01 0:12
memberJoaquín M López Muñoz2-Oct-01 0:12 
QuestionIs the allocator thread-safe? Pin
Anonymous29-Dec-00 5:52
memberAnonymous29-Dec-00 5:52 
AnswerRe: Is the allocator thread-safe? Pin
Joaquín M López Muñoz2-Oct-01 0:20
memberJoaquín M López Muñoz2-Oct-01 0:20 
General12% map speed improvement achieved by using this approach Pin
Leonid Medvedev26-Nov-00 5:18
memberLeonid Medvedev26-Nov-00 5:18 
QuestionWhere is the speedup? Pin
Jim16-May-00 2:12
sussJim16-May-00 2:12 
AnswerRe: Where is the speedup? Pin
Joaquín M López Muñoz16-May-00 3:18
sussJoaquín M López Muñoz16-May-00 3:18 
AnswerRe: Where is the speedup? Pin
Joaquín M López Muñoz8-Mar-01 21:23
memberJoaquín M López Muñoz8-Mar-01 21:23 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.150901.1 | Last Updated 31 Oct 2006
Article Copyright 2000 by Joaquín M López Muñoz
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid