|
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
|
|
|
|
|
I am using the Dinkumware C++ library. Is this allocator compatible with Dinkumware STL library? I am in a unique situation, where I exactly know the number of items that I want to copy into the set. But, set does not have any member function like reserve. Then, I looked at the block allocator and it was specific to VC++ STL. The problem is that I use the hash_map from Dinkumware also. I cannot switch the library to use this.
I hope I am not bothering you.
Thank you
Thomas
modified 29-Aug-18 21:01pm.
|
|
|
|
|
Well, the STL shipped with VC++ is actually from Dinkumware, so chances are that this improved STL version you're using is allocator-compatible. Why don't you just give it a try?
#define DEFINE_BLOCK_ALLOCATED_SET
#include <blockallocator.h>
int main()
{
block_allocated_set<int,1000> s;
s.insert(5);
return 0;
} If this compiles and works without assertions, then I guess everything's fine. Regards,
Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
|
|
|
|
|
I am using the set_intersection algorithm on two sorted vectors to produce a resultant vector. When I do a reserve on the result vector, the performance increases from 6s to 2s for the same test. The test is a million intersection operations in a loop. But, when I do not know the size of the resultant vector, how can I reserve upwards in blocks? If I cannot do that, each insert operation on the vector from the algorithm will result in memory allocations slowing down the process.
The only other option is to move to another container like list. I was researching options to do this on vector though.
Thomas
modified 29-Aug-18 21:01pm.
|
|
|
|
|
I'm afraid this kind of allocators are useless for vector s, because these containers require that all elements are placed in a contiguous block of memory. When a vector runs out of preallocated space, it asks for more memory and copies the original block to the new, larger block.
My opinion is that the best solution would be (if you're not worried by memory consumption) to preallocate as much memory on the result vector as will ever be needed:
output.reserve(min(input1.capacity(),input2.capacity())) This ensures no reallocations or copyings will occur.
If this is not an option for you (whatever the reason), then switch to a list and give my allocator a try
Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
|
|
|
|
|
I tried the code performance, and found it does good. But the following
example causes a runtime error, somewhat like [HEAP]: block at ... modified after freed...].
void f()
{
typedef block_allocated_map<cstring,int,100> tmap;
tmap *m1 = new tmap, *m2 = new tmap;
delete m1; delete m2;
}
Note the order of calls to deallocate() is not LIFO. I found the cause of the bug is the use of the static _Nil in XTREE, badly deallocated() from a different instance of block_allocator. So I have rewritten the code...
|
|
|
|
|
The actual bug in the code is that allocators may not
contain any instance-specific data, as mine regretably do.
This has implications with thread-safeness too, with regard to
a question some other folk posted several weeks ago.
Currently I'm quite busy, but please look forward for a
new release of the library in a few weeks.
Joaquín M López Muñoz
|
|
|
|
|
This may come a little late months after your post, but now that I had some time to release v1.2 of block_allocator I feel like I can clarify this issue.
The bug you reported is caused (as you pointed out) to the deallocation of an static struct called _Nil by a different block_allocator instance than the one that allocated it. In my opinion, it is the VC++ STL implementation the one to blame for this bug, as it fails to check whether allocators are interchangeable before trying deallocation (however, this check is systematically performed at all other places where it matters).
One simple workaround for this problem is having a static container of the offending type so that both allocation and deallocation of _Nil are carried out by it regardless of the various containers of the same type being constructed and destructed during the life of the program. The following sample code shows the technique:
#define DEFINE_BLOCK_ALLOCATED_MAP
#include "blockallocator.h"
#include <crtdbg.h>
using namespace std;
typedef block_allocated_map<int,int,1024> bmap;
int main(void)
{
_CrtSetDbgFlag(_CRTDBG_DELAY_FREE_MEM_DF|_CrtSetDbgFlag(_CRTDBG_REPORT_FLAG));
bmap *m1=new bmap;
bmap *m2=new bmap;
delete m1;
delete m2;
_CrtCheckMemory();
return 0;
} As for the multithreading issues I mentioned in my first reply to your post, a closer reevaluation of the library shows it is as multithread safe as it can be (more info in the updated article above).
Hope this helps.
Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
|
|
|
|
|
Apparently SGI's STL offers 4 different allocators for use. Three of them are described as being thread-safe, and one is described as fast but only to be used by programs that have one thread. See
http://www.sgi.com/Technology/STL/Allocators.html for more. Is it safe to use the block allocator that you've written in programs with multiple threads?
|
|
|
|
|