|
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 <class t=""> struct MSVC_STL_list_node
{
void *p1 , *p2;
T t;
};
template <class t,="" size_t="" chunk_size="">
class block_allocated_list:
public std::list<t, block_allocator<t,="" msvc_stl_list_node<t=""> , 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<type>
>
class list
you can see, Allocator=allocator<type>, 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<t, block_allocator<t,="" chunk_size=""> >
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 (int s 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 <class u=""> 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<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
|
|
|
|
|
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
|
|
|
|
|
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
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
|
|
|
|
|
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.
|
|
|
|
|
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
|
|
|
|
|
yes. i can't agree with you more.
this afternoon, i set up a project to run the src from codeguru projects.
except the fragmentation issue pointed by you, there are also a lot of logic errors there:
1) its allocate() function and check_consecutive() function is a mess.
2) there is a case of dead_lock, if the ss_allocator's initial size is 4 units,we need to allocate 5 units, the ss_allocator will keep grow() until crash.
3) there are also bugs in pool_allocator ..
I am wondering how could they make that mistakens however wrote such an excellent article. maybe their strength is speeching/writing.
in my opinion, the algorithm of your code is much much better and well implemented. i am thinking of combine your code with src from that article.
BTW, now i implemented a prototype that write some data through STL into
shared memory; i face some challenges here, maybe you can shed some light:
1) how could another process load the data from shared memory into STL by take advantage of our own allocator.
2) if the writer side has some update, how could the reader side effectively gets notified and refresh , but NOT reload the whole STL again.
diffinitely, I will run your program and that codeguru program side by side against some test cases, and post results here.
Happy coding.
jesse
hellojesse@gmail.com
|
|
|
|
|
BTW, now i implemented a prototype that write some data through STL into
shared memory; i face some challenges here, maybe you can shed some light:
1) how could another process load the data from shared memory into STL by take advantage of our own allocator.
2) if the writer side has some update, how could the reader side effectively gets notified and refresh , but NOT reload the whole STL again.
I don't quite get what you are trying to do. Care to explain a little further?
Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
|
|
|
|
|
you have two processes: one is reader , the other is writer.
the writer write some data into shared memory through STL since our allocator is specialized to allocate memory from shared memory;
the reader comes up and try to load date through STL.
challenges:
1) how to re-orgaize the internal tree for STL when reader is started;
2) is there a way for reader to pick up any change made from writer side?
jesse
|
|
|
|
|
This sample code does not return from sort:
<br />
#pragma warning(disable:4786)<br />
#include <iostream><br />
#include <string><br />
#include <list><br />
<br />
using namespace std;<br />
<br />
#define DEFINE_BLOCK_ALLOCATED_LIST<br />
#include "blockallocator.h"<br />
<br />
typedef block_allocated_list<string, 10> ListOfStrings;<br />
typedef ListOfStrings::iterator ListOfStringsItr;<br />
<br />
int main(int argc, char* argv[])<br />
{<br />
ListOfStrings listStrings;<br />
ListOfStringsItr itrStrings;<br />
<br />
<br />
listStrings.push_back(string("zero"));<br />
listStrings.push_back(string("one"));<br />
listStrings.push_back(string("two"));<br />
listStrings.push_back(string("three"));<br />
listStrings.push_back(string("four"));<br />
<br />
cout << endl;<br />
cout << "Before sort: " << endl;<br />
cout << "============ " << endl;<br />
<br />
for (itrStrings = listStrings.begin();<br />
itrStrings != listStrings.end();<br />
itrStrings++)<br />
{<br />
cout << "String: " << (*itrStrings).c_str() << endl;<br />
}<br />
<br />
listStrings.sort();<br />
<br />
cout << endl;<br />
cout << "After sort: " << endl;<br />
cout << "=========== " << endl;<br />
<br />
for (itrStrings = listStrings.begin();<br />
itrStrings != listStrings.end();<br />
itrStrings++)<br />
{<br />
cout << "String: " << (*itrStrings).c_str() << endl;<br />
}<br />
<br />
<br />
return 0;<br />
}<br />
If I add another string to my list at program start, e.g.:
<br />
listStrings.push_back(string("five"));<br />
listStrings.sort() returns, but produces the following output:
Before sort:
============
String: zero
String: one
String: two
String: three
String: four
String: five
After sort:
===========
String: one
String: three
String: four
String: five
String: two
String: zero
It seems to be related to the list::splice() problem. Any idea?
|
|
|
|
|
In the code supplied the typedef of ListOfStrings appears incorrect because the editor removed the template class arguments. Therefore, the line:
typedef block_allocated_list ListOfStrings;<br />
should be replaced with:
typedef block_allocated_list<string, 10> ListOfStrings;<br />
Sorry.
|
|
|
|
|
Hi PeteH,
Thanx for your report. After examining the problem, I've found it to be a bug in the Dinkumware STL implementation for VC++ 6.0. To fix it, replace the implementation of list::splice (if you have the guts to alter a C++ library file): where it reads
void splice(iterator _P, _Myt& _X, iterator _F)
{iterator _L = _F;
if (_P != _F && _P != ++_L)
{_Splice(_P, _X, _F, _L);
++_Size;
--_X._Size; }}
it should be
void splice(iterator _P, _Myt& _X, iterator _F)
{iterator _L = _F;
if (_P != _F && _P != ++_L)
{_Splice(_P, _X, _F, _L);
if(allocator==_X.allocator){
++_Size;
--_X._Size; }}}
This bug does not appear in the official list by Dinkumware, so I guess I'll post it right away. Best regards,
Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
|
|
|
|
|
I use this class all the time in VC++ 6.0, but I just tried to get it working in VS .net, and the new compiler complained about "'rebind' : is not a member of 'block_allocator<t,n,chunk_size>'...".
Does anyone know what this is about? I don't know much about STL allocators, and I have no idea what rebind() is...
Thanks...
-Dan
|
|
|
|
|
Hi Dan,
block_allocator won't work with VS.NET as this compiler's STL implements a different type of allocators (closer to the standard, as it happens). Nevertheless, it is not hard at all to upgrade the library so that it also conforms to this compiler. If I've got some spare time I'll try to write the upgrade, stay tuned.
PS: What do you use block_allocator for? I'm always curious about the use given to the libraries I've posted here at CP.
Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
|
|
|
|
|
Well, I don't know about Dan, but I'm using block_allocator to manage extremely large lists of 3D geometry information (hundreds of thousands of points and vertices). Unfortunately I'm trying to update to VC.Net 2k3 and it STILL has the crappy performance on small allocations that VC6 did. Do you have any suggestions for what I could do, or any plans to port the block allocator to VC.Net?
|
|
|
|
|
Hi jherico,
I'm extremely happy my library is actually being used! I wish I had more time to keep it up to date with new versions of MSVC++, but my spare time is very limited nowadays.
If you volunteer to do the testing and some sort of pair programming over the net, maybe we can port it to MSVC++ 7.x. These compilers have a more standard STL implementation, so things should be simple.
If you're up to the job, drop me a line and I'll send you along some code to test.
Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
|
|
|
|
|
I'm also interested. My present work is an optimizer for cutting plastic rolls (tries to minimize waste). I have to keep a list of all possible combinations of cut sizes and this becomes quite large. At the end of the combinations generation, the list must be sorted. I'm now having performance problems with VC++ 7.x.
Regards,
João Paulo
|
|
|
|
|
I tried to upgrade the library to MSVC 7.x some months ago, but had to do it with a remote peer (I do not have that version of the compiler) and did not complete the porting.
If you have some experience with the compiler and feel like doing some tweaking, I can send you the code as it stood when we left the porting process. The fixings should be (IMHO) simple.
Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
|
|
|
|
|
I want to use the block_allocator for list for VS.NET...I included the rebind allocator into the the block_allocator class like U do for the custom allocators..though it seems I run into another problem of variable matching...are there ne other things that need to be taken into account for changing this class for VS.NET...can ne one help with it...
Thanks in Advance,
Raj
|
|
|
|
|
Hi all and owner,
Do you get any success in compiling the same under VS .NET 2003 or any previous .NET verisons.
Please provide the updates. I wanted this URGENTLY for .NET.
Thanks
|
|
|
|
|
I've been using the block allocator for lists used in my company's code but ran into a serious problem. For a splice operation, a list will simply relink items out of one list into another list, IF the allocators for the two lists compare as the same. By default this is the case with the built in STL and the latest dinkum STL.
However, in a block allocated list, this is not the default. When a block allocated list does a splice, it implements it as an insert followed by an erase. First off, this changes splice from a constant time operation to an order N operation. Second, and more important, it invalidates iterators that pointed to the items in the original list. Now the C++ standard says that items moved from one list to another invalidate iterators pointing to them, but this was not the actual behaviour before I started using block allocated list, and we relied on the existing behaviour.
In case anyone is interested, I've come up with a solution that works in our case. In this we only have one type of list (basically a list of int pointers) that we need to concern ourselves with. So I subclassed block allocated list to a list of the concrete type we used and changed the constructors to always use the same static allocator. This allows the splice operation to return to its behaviour of being a) constant time and b) not invalidating iterators pointing to moved items.
Brad
|
|
|
|
|