By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
429,557 Members | 1,406 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 429,557 IT Pros & Developers. It's quick & easy.

Can't have stack based STL allocator

P: 18
Although STL container can't support object by reference as a template argument. To make thing worse, allocator can't support stack based allocation.

So:

std::deque<std::string const &>

is impossible to declare.

But, it is also more than impossible to find a workaroung using a custom STL allocator because of the ugly and not object oriented design that was used. Thanks to many STL contributor for this, specially to PJ Plauger where his name is everywhere in the STL header/footer.

This is the reason why this is impossible:

class allocator
{
///...
pointer allocate(size_type _Count, const void _FARQ *)
{ // allocate array of _Count elements, ignore hint
return (allocate(_Count));
}

void construct(pointer _Ptr, const _Ty& _Val)
{ // construct object at _Ptr with value _Val
_Construct(_Ptr, _Val);
}
}

If if was something like this:

class allocator
{
///...
_Ty construct(const _Ty& _Val)
{ // construct object at _Ptr with value _Val
return *(new _Ty( _Val)); //C++ optimizer will get rid of the copy call in the return statement so there is no performance loss with that approach
}
}

Then I could have made this:

class StackbasedAllocator
{
///...
_Ty construct(const _Ty& _Val)
{ // construct object at _Ptr with value _Val
return _Val;
}
}

Which is fully object oriented in C++ and I could have build my allocator to support object by reference in a deque container. The problem with the current implentation is a very major one and implies directly that references CANNOT be used in STL container. So STL container will never be able to meet realtime specs on embedded (even on desktop) computers. Memory heap allocation cost too much on those device specially for small object.

So with this:

pointer allocate(size_type _Count, const void _FARQ *)
{ // allocate array of _Count elements, ignore hint
return (allocate(_Count));
}

You can't do this:

pointer allocate(size_type _Count, const void _FARQ *)
{ // allocate array of _Count elements, ignore hint
return &_Ty(); //Compiler will warn this and most probably reject it
// If _Ty is a reference, then you can't have a pointer on a reference and can't have references uninitialized.
}

So I'm screwed. I can't use STL container in my apps. Though the allocator goal was to abstract the memory allocation, in that case, you can't. The STL allocator is unoptimized regarding memory alloaction and, worse, totally unoptimizable.

In .NET, generics have solve that issue by working either on value types and on reference types. STL have failed that completly. But only simple tricks or having followed object oriented rules form the beginning could have done the same thing.

I was a huge C++ fan and a STL user for long time. But for realtime apps, I can only warn everyone to never try to use it.
Jun 20 '07 #1
Share this Question
Share on Google+
9 Replies


weaknessforcats
Expert Mod 5K+
P: 9,197
Although STL container can't support object by reference as a template argument. To make thing worse, allocator can't support stack based allocation.
If you use the STL then you have to play by STL rules. You use objects or pointers. Most people use handles rather than pointers due to the danger of using pointers in a container that moves things around and might do a delete.

You have to use iterators. You can only have generator, unary or binary functors.

Your objects must be well-behaved. Complete with copy constructors, assignment operators and destructors. And you have solved your deep-copy issues by using handle members.

Finally, in C++ you never, ever, use the stack. The single most dangerous thing in a C++ program is to have the compiler responsible for allocation/deallocation of your assets.
Jun 20 '07 #2

P: 18
STL provides an allocator class. Its purpose is to encapsulate memory allocation. But is done by using a syntax that support only using heap allocation. But it could have been done in a way that both is possible. C++ support that. Even the .NET support that. Because heap allocation is using much more system ressources than the stack.

You can't say: there is a standard (as standard as STL could be) and if your not happy with it, do it by yourself.

Because in realtime apps STL more than useles, it is dangerous. Here's what Kernel tracker showed what it cost using a multimap having std::string as key and value parameters: for at most 100 insertions, it took 162 ms of processing. Most of the processing is done by allocating/freeing object smaller than 100 bytes. For a realtime apps, is totally unacceptable. So, I must go back to C style structure because I can afford the cost.

I don't understand that the allocator was designed that way.

It is not a great advice telling me that I must follow blindlessly the rules because they are the rules. STL fails the realtime most important considerations leaving developper back in the old days of C.
Jun 20 '07 #3

weaknessforcats
Expert Mod 5K+
P: 9,197
For a realtime apps, is totally unacceptable. So, I must go back to C style structure because I can afford the cost.
Yeah, I've heard the Microsoft kernal driver guys say this. In fact, they can't even use C. They wrote their own compiler. All sorts of paging issues arose when calls were made to paged out memory using the Visual Studio compiler. I think they are just about ready to use the Visual Studio C++compiler after some changes there.

Be sure you use a C compiler. Classes in C++ are implemented a structs. That means your structs are subject to the default constructor/copy constructor/assignment operator rules: memberwise not bitwise.

I don't understand that the allocator was designed that way.
I don't either. I wasn't there.

It is not a great advice telling me that I must follow blindlessly the rules because they are the rules.
You have to follow the STL rules or you can't use the STL. Now you can program the STL and write your own allocatoprs, etc. Check out the book "Programming the STL" Addison-Wesley.

STL fails the realtime most important considerations leaving developper back in the old days of C.
Not all C++ features are useable in all environments. STL was not intended for real time. It was intended to avoid having developers rewrite and rewrite and rewrite the same linked list code, tree code, queue code, etc. The template are designed for speed not footprint.

Because heap allocation is using much more system ressources than the stack.
It is?? How are you measuring that?
Jun 20 '07 #4

P: 18
It is?? How are you measuring that?
Kernel tracker shows all the timing inside the processor in microsecond for memory allocation, mutex lock/unlock and so on in a very nice graphical view.

Is was more than easy for me to measure the 162 ms taken to simply manage about 100 strings, maybe less.

The processor is a small Intel XScale 400Mhz with 32 Meg RAM.

The template is an object oriented tool designed to help code reusability and extensibility. Memory footprint and runtime performances are only related to how good an implementation is, not what kind of tool used.

I as said earlier if the allocator Construct method what like this:

Expand|Select|Wrap|Line Numbers
  1.   _Ty construct(const _Ty& _Val)
  2.   {    // construct object at _Ptr with value _Val
  3.     return *allocate(_Val);
  4.   }
instead of

Expand|Select|Wrap|Line Numbers
  1.   pointer allocate(size_type _Count, const void _FARQ *)
  2.   {    // allocate array of _Count elements, ignore hint
  3.     return (allocate(_Count));
  4.   }
  5.  
  6.   void construct(pointer _Ptr, const _Ty& _Val)
  7.   {    // construct object at _Ptr with value _Val
  8.     _Construct(_Ptr, _Val);
  9.   }
Then I would have no problem at all.

By the way, do you know PJ Plauger? If yes, tell him to come by. I have things to discuss with him.
Jun 20 '07 #5

weaknessforcats
Expert Mod 5K+
P: 9,197
I didn't know that. Every time someone like you shows me somthing I don't know, I worry that there's a whole of of things I don't know that I don't know.

No, I do no know Plauger. I have read his book and have been on his Dinkumware site but I never met the man. I did have e-mail with him at one point.

You might ask this question of Plauger yourself and let me know what he says. You got me knid of curious.
Jun 20 '07 #6

P: 18
Its done. As soon as I got something from the STL master, I tell you.
Jun 20 '07 #7

P: 18
[pjp] The issues you raise have been widely discussed. I believe
they have all been addressed in the revison of the C++ Standard
currently under way. Admittedly that doesn't help much for those
who have to live with the current C++ Standard for several more
years...

Best regards,

P.J. Plauger
So far, this doesn't help me much. But at least I was right to worry about that. That what I have feared from the beginning: that I have to wait for the next C++ standard revision to be implemented! This will be done probably in 2-3 years.
From now on, .NET will be far ahead, in both terms of features and advanced concept.
This is bad news for C++ ....
Jun 20 '07 #8

P: 18
487. Allocator::construct is too limiting

http://www.open-std.org/jtc1/sc22/wg...losed.html#487

Discussion:

The standard's version of allocator::construct(pointer, const_reference) severely limits what you can construct using this function. Say you can construct a socket from a file descriptor. Now, using this syntax, I first have to manually construct a socket from the fd, and then pass the constructed socket to the construct() function so it will just to an uninitialized copy of the socket I manually constructed. Now it may not always be possible to copy construct a socket eh! So, I feel that the changes should go in the allocator::construct(), making it:

template<typename T>
struct allocator{
template<typename T1>
void construct(pointer T1 const& rt1);
};
Now, the ctor of the class T which matches the one that takes a T1 can be called! Doesn't that sound great?

Proposed resolution:

Rationale:

NAD. STL uses copying all the time, and making it possible for allocators to construct noncopyable objects is useless in the absence of corresponding container changes. We might consider this as part of a larger redesign of STL.
My idea behind the mistake that was made is that the wanted to allocate the unitialized memory first with a call to allocate(int count) then call the constructor with construct( void *, _Ty const &val ). They go into that direction propably to satisfy some akwards requirements from C users at that point ...
But this is not object oriented. The code of the default allocate looks rather a C hack then a pure C++ function.
Man that annoying ... In a user library I could have understand ... but in STL, i don't. I think that someone doesn't do its job from the beginning ...

I just hope the next version will be much better and far behond exceptation because .NET is getting more and more attractive. Few months ago I couldn't have tought that possible for me to think that way ...
But we have to admit that the 2.0 framework, though still incomplete, is very useful in many ways.
Jun 21 '07 #9

weaknessforcats
Expert Mod 5K+
P: 9,197
There's a lot to be said for .NET.

There is a business opportunity for someone who writes a CLR for Unix and Linux. Since MSIL is public, you could have all this running inthe Unix world in a heartbeat. Maybe except for the "now leaving managed code stuff".

I am sure there were a lotta talks about STL. No one thought about auto_ptr either nor about handle classes (in the next STL this is shared_ptr). vectcor<bool> is still there for the unfortunate few that used it.

Perhaps, you will be heard in the next round of STL standard talks.

(Can I still call it STL?? Or is it now the C++ Standard Library??).
Jun 21 '07 #10

Post your reply

Sign in to post your reply or Sign up for a free account.