|
|
Comments and Discussions
|
|
 |
|
could it work well with vc2008??
|
|
|
|
|
Have you tried?
Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
Want a Boost forum in Code Project? Vote here[^]!
|
|
|
|
|
Joaquin M Lopez Munoz, Good morning, I added a custom memory allocator modeled off your block_allocator class(http://www.codeproject.com/KB/stl/blockallocator.aspx) to my doubly linked list class. The custom memory allocator functions well for STL set, ,map, list.
However, for my doubly linked class , I have noticed that MapViewOfFile is not functioning properly. Here is an excerpt of the code below. I tried setting a Debug break point in the block_allocator template code but none of the break points get hit when I call MapViewOfFile. Could you please suggest how I may locate or fix this problem.
Here is the block allocator constructor which you wrote:
template
block_allocator(const block_allocator&)
{
head.next=reinterpret_cast(&tail);
tail.previous=reinterpret_cast(&head);
assert(chunk_size>=2);
}
For our doubly doubly link class, do we need to call this constructor? If so, where is the best place for us to call this constructor? Thank you.
template >
class dlist{
public:
Allocator alloc;
class node{
public:
Range value;
node *next;
//pointer to next node
node *prev;
//pointer to previous node
node(){ next = NULL; prev = NULL; }
node(Range r){ value = r; next = NULL; prev = NULL; }
};
node *front; //pointer to front of list
node *back; //pointer to back of list
int size;
dlist(){ front=NULL; back=NULL; size = 0;}
void insertFront(Range value);
void insertBack(Range value);
void removeFront();
void removeBack();
void insertBefore(Range value,node *nodeB);
void insertAfter(Range value,node *nodeA);
void removeBefore(node *nodeB);
void removeAfter(node *nodeA);
int removeNode(node *newNode);
node * getFront(void){ return front; }
node * getBack(void){ return back; }
int getSize(){ return size; }
};
template
void dlist::insertBefore(Range value,node *nodeB)
{ node *newNode;
try {
typename Allocator::rebind::other pointer_alloc;
newNode = pointer_alloc.allocate(1);
}
catch(std::bad_alloc &ba){
printf("Catch exception\n");
}
newNode->prev=nodeB->prev;
newNode->next =nodeB;
newNode->value =value;
if(nodeB->prev==NULL){
this->front=newNode;
}
nodeB->prev=newNode;
}
template
void dlist::removeNode(node *nodeToRemove){
typename Allocator::rebind::other pointer_alloc;
if(nodeToRemove==this->front) {
this->front=this->front->next;
pointer_alloc.destroy(nodeToRemove); // destroy, free erased node
pointer_alloc.deallocate(nodeToRemove,1);
nodeToRemove = NULL;
this->front->prev=NULL;
size -= 1;
}
else if (nodeToRemove==this->back) {
this->back=this->back->prev;
pointer_alloc.destroy(nodeToRemove); // destroy, free erased node
pointer_alloc.deallocate(nodeToRemove,1);
nodeToRemove = NULL;
this->back->next=NULL;
}
else{
nodeToRemove->prev->next=nodeToRemove->next;
nodeToRemove->next->prev=nodeToRemove->prev;
pointer_alloc.destroy(nodeToRemove); // destroy, free erased node
pointer_alloc.deallocate(nodeToRemove,1);
nodeToRemove = NULL;
}
size -= 1;
}
|
|
|
|
|
Hi,
The formatting of your post is ruined by the presence of unescaped <s in your code. Please try using code blocks as provided by the post editor or either replacing appearances of < with <.
As for your question, I don't see how using some allocator or another for your container class can affect the way MapViewOfFile works. Does the function work if you use a standard allocator rather than your own? If so maybe your allocator is somehow corrupting memory. I'm sorry I can't be more helpful than this.
Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
Want a Boost forum in Code Project? Vote here[^]!
|
|
|
|
|
Joaquin M Lopez Munoz, I slightly modified your C++ block allocator class to use it as a custom allocator for my doubly linked list class which does not use STL. So far, the tests show a 30% speed improvement in Windows over the standard allocator.
Now, I would like to port the block allocator to RedHat Linux and Solaris Unix. I was wondering, if I remove the MSVC pragmas, do you think your block allocator class will function properly in Red Hat Linux and Solarix UNIX.
I ran an experiment where I purposely introduced a huge memory leak into the custom block allocator. Somehow, the Windows Kernel page table entries which support virtual address to physical memory mapping got "messed up". Also, MapViewOfFile started to return NULL in the presence of this huge memory leak. This was only a crude experiment and I realize your block allocator class has no memory leaks. Thank you for your help. Frank Chang
|
|
|
|
|
hi Joaquín M López Muñoz :
first thanks for the nice job.
i have tested most of the containers mentioned in your article with its stl counterpart (not including multiset and multimap which i never used).
the facts discovered :
block_allocated_list is about 4x faster than stl::list (un-sorted)
block_allocated_set is about 2x faster than stl::set
block_allocated_map is about 2x faster than stl::map
to test deeper, i sorted the list (both the block_allocated_list and stl::list) then i found that the sort operation for block_allocated_list is about 2x slower than stl::list.
do you have ideas about that? sure i can avoid this in pratice since i have realized the fact but still wonder can this be improved?
thank you.
|
|
|
|
|
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[^]!
|
|
|
|
|
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[^]).
|
|
|
|
|
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.
|
|
|
|
|
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.
|
|
|
|
|
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;
|
|
|
|
|
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[^]!
|
|
|
|
|
|
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  ), 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 ) 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!
|
|
|
|
|
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[^]!
|
|
|
|
|
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  - 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  )
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!
|
|
|
|
|
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.
|
|
|
|
|
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  )
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[^]!
|
|
|
|
|
I just tested your code on VS2005 and I get a speedup by 3.8 compared to the normal STL allocator!! 
|
|
|
|
|
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
|
|
|
|
|
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
|
|
|
|
|
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
|
|
|
|
|
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.
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
|
|
|
|
|
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  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
|
|
|
|
|
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
|
|
|
|
|
|
|
 General  News  Suggestion  Question  Bug  Answer  Joke  Rant  Admin
|
A block allocator for use with STL containers that greatly improves speed in programs doing massive data insertions and extractions.
| Type | Article |
| Licence | CPOL |
| First Posted | 10 May 2000 |
| Views | 168,191 |
| Downloads | 1,172 |
| Bookmarked | 54 times |
|
|
Submit an article or tip
Post your Blog
