Home > Archive > VC STL > February 2006 > empty member optimization
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
empty member optimization
|
|
|
| Hi,
Does anyone knows how to support empty member optimization in STL of VS 2003?
Thanks,
Ayal
| |
| Ulrich Eckhardt 2006-02-13, 4:01 am |
| ayal wrote:
> Does anyone knows how to support empty member optimization in STL of VS
> 2003?
What are you talking about? An object, even if empty, still must have a
unique address so it usually gets size 1. Now, there is an optimization
that an empty baseclass doesn't increase the size of the derived class, but
that is something different.
Uli
| |
|
| I'm talking about the technique described by Nathan Myers in Dr. Dobb's
Journal August 1997. See the follwong link:
http://202.179.135.4/data/DDJ/artic...9708b/9708b.htm
Ayal
"Ulrich Eckhardt" wrote:
> ayal wrote:
>
> What are you talking about? An object, even if empty, still must have a
> unique address so it usually gets size 1. Now, there is an optimization
> that an empty baseclass doesn't increase the size of the derived class, but
> that is something different.
>
> Uli
>
>
| |
| Ulrich Eckhardt 2006-02-13, 7:05 pm |
| ayal wrote:
> Does anyone knows how to support empty member optimization in STL
> of VS 2003?
[...]
> I'm talking about the technique described by Nathan Myers in Dr. Dobb's
> Journal August 1997. See the follwong link:
> http://202.179.135.4/data/DDJ/artic...9708b/9708b.htm
>
This technique is pretty old (the article is from 97) and has been
implemented in many standardlibraries I have seen, but in no case was this
something you could turn on or off, if that is what you want to know. If
you want to know whether the standardlibrary of VS2003 supports it, you
could simply look at the code.
Uli
| |
|
| I looked at the code and found out it is not supported.
My question was - does anyi=one knows a god way to add this to the STL of
VS2003
It seems strange that no one did it already since it's quite important.
Ayal
"Ulrich Eckhardt" wrote:
> ayal wrote:
> [...]
>
> This technique is pretty old (the article is from 97) and has been
> implemented in many standardlibraries I have seen, but in no case was this
> something you could turn on or off, if that is what you want to know. If
> you want to know whether the standardlibrary of VS2003 supports it, you
> could simply look at the code.
>
> Uli
>
>
| |
| Stephen Howe 2006-02-13, 7:05 pm |
| > I looked at the code and found out it is not supported.
> My question was - does anyi=one knows a god way to add this to the STL of
> VS2003
> It seems strange that no one did it already since it's quite important.
Surely that is up to the authors of the STL that is bundled with VS2003?
I doubt whether they are unaware of the articles you pointed out.
Stephen Howe
| |
| Tom Widmer [VC++ MVP] 2006-02-13, 7:05 pm |
| ayal wrote:
> I looked at the code and found out it is not supported.
> My question was - does anyi=one knows a god way to add this to the STL of
> VS2003
No, short of switching to the less conforming STLport (www.stlport.com).
Rewriting the standard container headers to support it would be crazy,
though possible of course.
> It seems strange that no one did it already since it's quite important.
It's not particularly important - 4 bytes of extra overhead for a
container is very rarely an issue (4 bytes per element might be of
course). But perhaps Dinkumware would like to comment on why they
haven't implemented it? I also notice that Dinkumware does some strange
inheritence with the node based containers that means that they contain
not one but 3 copies of the allocator - with a non-empty allocator this
means that container sizes really bloat. I would personally have thought
that creating a copy of the allocator on demand (and keeping the most
commonly required allocator around) would be preferred to holding
multiple copies of the allocator.
This thread could have a more descriptive title such as 'Empty allocator
optimization' - you are concerned about the specific application of the
empty base optimization to empty allocators employed in standard containers.
Tom
| |
| Bo Persson 2006-02-13, 7:05 pm |
|
"Tom Widmer [VC++ MVP]" <tom_usenet@hotmail.com> skrev i meddelandet
news:uBKVcuLMGHA.1676@TK2MSFTNGP09.phx.gbl...
> ayal wrote:
>
> No, short of switching to the less conforming STLport
> (www.stlport.com). Rewriting the standard container headers to
> support it would be crazy, though possible of course.
>
>
> It's not particularly important - 4 bytes of extra overhead for a
> container is very rarely an issue (4 bytes per element might be of
> course). But perhaps Dinkumware would like to comment on why they
> haven't implemented it? I also notice that Dinkumware does some
> strange inheritence with the node based containers that means that
> they contain not one but 3 copies of the allocator - with a
> non-empty allocator this means that container sizes really bloat. I
> would personally have thought that creating a copy of the allocator
> on demand (and keeping the most commonly required allocator around)
> would be preferred to holding multiple copies of the allocator.
But with non-empty allocators, it might be important to keep their
contents. :-)
Dinkumware is also trying to support cases where different instances
of the allocators don't compare equal. In that case it is no longer so
easy to create a copy!
They also keep one allocator for creating and destroying pointers, in
the case where allocator::pointer is not just a simple pointer, but
something that has its own constructors and/or destructors.
So compliant that it hurts? :-)
Bo Persson
| |
| Tom Widmer [VC++ MVP] 2006-02-14, 8:01 am |
| Bo Persson wrote:
> "Tom Widmer [VC++ MVP]" <tom_usenet@hotmail.com> skrev i meddelandet
> news:uBKVcuLMGHA.1676@TK2MSFTNGP09.phx.gbl...
>
>
>
> But with non-empty allocators, it might be important to keep their
> contents. :-)
The different typed copies must all compare equal, so as long as you
keep one copy around, you can create the copies with other types on demand.
> Dinkumware is also trying to support cases where different instances
> of the allocators don't compare equal. In that case it is no longer so
> easy to create a copy!
It is always required that copies of the same allocator compare equal
though (from the allocator requirements table):
X a(b); post:Y(a)==b
This implies (at least to me) that if you need a different allocator
type, you can just create it on demand. E.g. to create your pointer
allocator type, to construct one, you do:
ptr_alloc_t(get_allocator()).construct(....);
Allocators will typically at most be reference counted, or often just
have some kind of pool pointer, so copying them is (or should be) very
cheap.
> They also keep one allocator for creating and destroying pointers, in
> the case where allocator::pointer is not just a simple pointer, but
> something that has its own constructors and/or destructors.
Yes, and I agree this is a good thing - I've experimented with bizarre
allocators in the past (e.g. allocator<T>::pointer != T*), and
Dinkumware's is the only library that could cope.
> So compliant that it hurts? :-)
It is still good to optimize as much as possible within the constraints
of the standard though (including non-equal and exotic pointer
allocators, of course)...
Tom
| |
| Pete Becker 2006-02-14, 8:01 am |
| Tom Widmer [VC++ MVP] wrote:
>
> It is always required that copies of the same allocator compare equal
> though (from the allocator requirements table):
> X a(b); post:Y(a)==b
>
That's a statement of what copying means. Like:
int i = 3;
int j(i); // post: j == i
It doesn't mean that they must compare equal for all time.
j = 4; // post: j == i?
And note, too, that some containers require more than one allocator
type, because they allocate more than one type of object. We're talking
here about allocator<Ty>, not a class named allocator.
> This implies (at least to me) that if you need a different allocator
> type, you can just create it on demand. E.g. to create your pointer
> allocator type, to construct one, you do:
>
> ptr_alloc_t(get_allocator()).construct(....);
Sure. Except that this code doesn't copy the allocator back to the
original, so any changes made to its state will be lost.
Also, it gets you an allocator of the same type as the container was
declared to hold, which isn't necessarily the right type for the
allocation you're doing. For example, node-based containers holding
objects of type Elem don't use allocator<Elem>, because they allocate
nodes. So you have to get an allocator<Node>, using
allocator<Elem>::rebind<Node>::other (which breaks most compilers).
There is no guarantee that the allocator you get from rebind compares
equal to the allocator you started with. Indeed, in general, they can't
be compared, because they're different types.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
| |
| Tom Widmer [VC++ MVP] 2006-02-14, 7:06 pm |
| Pete Becker wrote:
> Tom Widmer [VC++ MVP] wrote:
>
>
> That's a statement of what copying means. Like:
>
> int i = 3;
> int j(i); // post: j == i
>
> It doesn't mean that they must compare equal for all time.
>
> j = 4; // post: j == i?
As far as I can tell, allocators need not be assignable, so I don't see
that this is relevent.
> And note, too, that some containers require more than one allocator
> type, because they allocate more than one type of object. We're talking
> here about allocator<Ty>, not a class named allocator.
Are you really suggesting that it is sane for an allocator to become
non-equal to one of its copies, just because allocate or construct has
been called on it? In that case, in your list implementation, you might
end up with 3 member allocators that don't compare equal (when converted
to the same type).
>
>
> Sure. Except that this code doesn't copy the allocator back to the
> original, so any changes made to its state will be lost.
Indeed. But with your version you have 3 independent allocators with
independent state in any case - how is that better? An allocator
implementation that has mutating state should use reference counting,
global state or external state in any case, and that is what happens in
all the allocator implementations I've seen.
> Also, it gets you an allocator of the same type as the container was
> declared to hold, which isn't necessarily the right type for the
> allocation you're doing.
That's why I was copying it to a "ptr_alloc_t", which was meant (overly
subtly) to refer to, e.g., the type of your _Alptr member in <list>.
node_alloc_t would have been clearer I think.
For example, node-based containers holding
> objects of type Elem don't use allocator<Elem>, because they allocate
> nodes. So you have to get an allocator<Node>, using
> allocator<Elem>::rebind<Node>::other (which breaks most compilers).
> There is no guarantee that the allocator you get from rebind compares
> equal to the allocator you started with. Indeed, in general, they can't
> be compared, because they're different types.
Ahh, but they can by converting. For
X a(b); post:Y(a)==b
X and Y are meant to be different allocator types (corresponding to a T
and U rebind respectively).
Anyway, I think it is possible to write a conforming list container
(that works with funny pointer types, and with non-equal allocators)
that includes
1. The empty base optimization, for empty allocators.
2. Only one "copy" of the allocator held in the container (which need
not have the type allocator_type, but might be a rebound type).
Tom
| |
| Pete Becker 2006-02-14, 7:06 pm |
| Tom Widmer [VC++ MVP] wrote:
> Pete Becker wrote:
>
>
>
> As far as I can tell, allocators need not be assignable, so I don't see
> that this is relevent.
Don't be so literal-minded. A member function of an allocator type can
modify its state, which is analogous to modifying a scalar type by
assignment.
>
>
>
> Are you really suggesting that it is sane for an allocator to become
> non-equal to one of its copies, just because allocate or construct has
> been called on it?
Absolutely. But on a more fundamental level, the standard doesn't
prohibit it, so a conforming implementation has to work right with
allocators that do this.
In that case, in your list implementation, you might
> end up with 3 member allocators that don't compare equal (when converted
> to the same type).
Yup. That's allowed by the standard.
>
>
>
> Indeed. But with your version you have 3 independent allocators with
> independent state in any case - how is that better?
It's not a matter of better, but of supporting what the standard allows.
There is no requirement that an allocator and its copy continue to
compare equal when you use them.
> An allocator
> implementation that has mutating state should use reference counting,
> global state or external state in any case, and that is what happens in
> all the allocator implementations I've seen.
Nevertheless, that's not required by the standard.
>
>
>
> That's why I was copying it to a "ptr_alloc_t", which was meant (overly
> subtly) to refer to, e.g., the type of your _Alptr member in <list>.
> node_alloc_t would have been clearer I think.
>
> For example, node-based containers holding
>
>
>
> Ahh, but they can by converting. For
> X a(b); post:Y(a)==b
> X and Y are meant to be different allocator types (corresponding to a T
> and U rebind respectively).
Yup, sorry: I missed that.
Nonetheless, if you create copies and mess with them, there's no
requirement that the changes that result will be reflected in the
original allocator.
>
> Anyway, I think it is possible to write a conforming list container
> (that works with funny pointer types, and with non-equal allocators)
> that includes
> 1. The empty base optimization, for empty allocators.
> 2. Only one "copy" of the allocator held in the container (which need
> not have the type allocator_type, but might be a rebound type).
>
It's certainly possible if you constrain the allocator type to require
that copies all have the same state, regardless of what operations have
been done on them. But, again, the standard doesn't require that.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
| |
| Tom Widmer [VC++ MVP] 2006-02-14, 7:06 pm |
| Pete Becker wrote:
> Tom Widmer [VC++ MVP] wrote:
>
>
> Absolutely. But on a more fundamental level, the standard doesn't
> prohibit it, so a conforming implementation has to work right with
> allocators that do this.
Imagine an allocator that modifies itself every time allocate is called,
to make itself != the the pre call version. Suddenly, your container is
going to die as soon as it calls deallocate, since deallocate has a
precondition that p (the pointer to deallocate) was allocated by an
allocator that compared equal (and doesn't require or even suggest that
it was the same allocator object).
So that's one additional requirement immediately that your
implementation is placing on allocators, but that's fine, as its allowed
by 20.1.5/5:
"Implementors are encouraged to supply libraries that can accept
allocators that encapsulate more general memory models and that support
non-equal instances. In such implementations, any requirements imposed
on allocators by containers beyond those requirements that appear in
Table 32, and the semantics of containers and algorithms when allocator
instances compare non-equal, are implementation-defined."
So, an implementation can place arbitrary additional requirements (and,
realistically, has to do so), and yours has placed at least one - that
allocators cannot mutate while they have any pointers that will need
deallocating.
> In that case, in your list implementation, you might
>
>
>
> Yup. That's allowed by the standard.
Ok, I don't see anything forbidding it.
>
>
> It's not a matter of better, but of supporting what the standard allows.
> There is no requirement that an allocator and its copy continue to
> compare equal when you use them.
Ok, but my point is that self mutating allocators are silly and
impossible to make a container work with, and you don't support them
anyway, so why not forbid them and thus allow yourselves to much better
space-optimize your use of allocators by using on-demand copies?
Tom
| |
| Bo Persson 2006-02-14, 7:06 pm |
|
"Tom Widmer [VC++ MVP]" <tom_usenet@hotmail.com> skrev i meddelandet
news:%23SHC4JVMGHA.2668@tk2msftngp13.phx.gbl...
> Bo Persson wrote:
>
> The different typed copies must all compare equal, so as long as you
> keep one copy around, you can create the copies with other types on
> demand.
That is true only for the default std::allocator. A user defined
allocator, MyAllocator<T>, might behave differently.
Bo Persson
| |
| Tom Widmer [VC++ MVP] 2006-02-14, 7:06 pm |
| Bo Persson wrote:
>
>
> That is true only for the default std::allocator. A user defined
> allocator, MyAllocator<T>, might behave differently.
It's in the allocator requirements that a copy, converted back to the
original type, must compare equal. Pete and I are having a lovely
discussion about the possibility of allocators (copies or otherwise)
becoming != the orginal allocator during the lifetime of a container,
due to member functions being called.
Tom
| |
| Bo Persson 2006-02-14, 7:06 pm |
|
"Tom Widmer [VC++ MVP]" <tom_usenet@hotmail.com> skrev i meddelandet
news:OWh0F3YMGHA.3960@TK2MSFTNGP09.phx.gbl...
> Bo Persson wrote:
>
>
> It's in the allocator requirements that a copy, converted back to
> the original type, must compare equal. Pete and I are having a
> lovely discussion about the possibility of allocators (copies or
> otherwise) becoming != the orginal allocator during the lifetime of
> a container, due to member functions being called.
>
> Tom
In my copy of the standard it says (Table 32):
"a1 == a2 returns true iff storage allocated from each can be
deallocated via the other."
The default std::allocator implements an operator== that always
returns true, but that is not required for non-std allocators.
The relaxation (20.1.5/4) for implementations is that they are
*allowed* to assume that for all allocators, but they are definitely
nor required.
Bo Persson
| |
| Tom Widmer [VC++ MVP] 2006-02-15, 7:58 am |
| Bo Persson wrote:
> In my copy of the standard it says (Table 32):
>
> "a1 == a2 returns true iff storage allocated from each can be
> deallocated via the other."
>
> The default std::allocator implements an operator== that always
> returns true, but that is not required for non-std allocators.
No, and those allocators are the ones we're discussing.
> The relaxation (20.1.5/4) for implementations is that they are
> *allowed* to assume that for all allocators, but they are definitely
> nor required.
Yes, but copies of an allocator (of arbitrarily rebound types) are
required to compare equal to the source allocator:
X a(b); post:Y(a)==b
Tom
|
|
|
|
|