|
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
|
|
|
|
|
This is a tricky issue. Standard allocators are required to compare to true , which means splice , swap and similar operations take constant time. This requirement does not hold for other allocators, though. Why did I decided to implement block_allocator this way? Having all allocators of a given class compare to true is tantamount to saying that these allocators do not hold per-object data, i.e. all internal data are static. In my particular case, having a static list of allocated blocks would have broken the per-container thread safeness usually taken for granted when working with STL. To remedy this I'd have had to include static locking when accessing this list, which I deemed unacceptable for performance reasons. When designing the allocator, I considered implementing these trade offs as a plugglable policy (so that one can decide between per-object data, global data without locking in single-threaded environments, and global, locked data in multithreaded programs), but the design became too complex and I finally settled for the current approach.
Your solution is a valid one, but keep in mind you can run into trouble if your program is multithreaded and there are more than one thread dealing with containers of the same kind.
Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
|
|
|
|
|
I have read that custom block allocators sometimes can decrease the memory necessary for each object in the list.
Does this custom allocator decrease the memory usage of a list(map, or set)?
Thanks, for your help. I'm interested in decreasing size as well as increasing speed.
|
|
|
|
|
Does this custom allocator decrease the memory usage of a list(map, or set)?
On a first approach, no it doesn't. When an allocator is requested n bytes of fresh memory, it has no other option but to provide n bytes of fresh memory, so memory efficiency can only result from second-order effects:- Alignment issues. An allocator reserving memory on a per-object basis can incur a constant alignment overhead (e.g. reserving always 32 bytes when requested 31). IMHO, in release mode this will only happen in very bad designed allocators; I don't think
malloc based allocation suffers from this defect.
- Memory fragmentation. This can actually be an issue. Reserving memory in larger chunks prevents the formation of many unusable little blocks that can fragment memory to the point that the practical limit of total memory seen by the program is much less than theoretically possible. Here, block allocators have a reputation for doing a good job. Furthermore, block allocation improves locality and hence, due to cache considerations, speed.
Anyway, I'd suggest you conduct some tests to see how block_allocator performs with respect to memory efficiency in your particular application.
Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
|
|
|
|
|