Avoiding STL bloat with a variation of "the void* trick"
Donovan Rebbechi
of STL containers (mostly map and list) and template instances seem
to make up a lot of the code.
One idea was to roll my own, and implement pointer containers by using
private inheritence and inheriting from container<void*>. The idea is
that a template instance acts as some sort of type safety wrapper.
Then it occurred to me that I could just reuse the STL containers void*
instance
eg
template<class T> class ptrList : private std::list<void*>
{
public:
typedef std::list<void*> base_class;
inline void push_back(T* x){ base_class::push_back(x); }
inline void push_front(T* x){ base_class::push_front(x); }
...
// key needs working comparison operators, so just use pointers for values
template<class key, class value> ptrMap : private std::map<key, void*>
{
.....
// more extreme ...
template <class key> my_compare
{
public:
bool operator()(void* left, void* right)
{
return *(key*)left < *(key*)right;
}
template <class key, class value> ptrMap :
private std::map<void*, void*, my_compare<key> >
{
This seems to work quite well, the upfront "cost" is quite large, but
the marginal cost of adding instances is very low. I'm curious as to
whether anyone else has tried something like this ? Are there any pitfalls
with deriving from standard container classes ?
Is it possible/practical to use a void* container to implement a value-based
container (which is something my second map example comes close to doing)?
--
Donovan
Andre Kostur
<slrn9mo5ki....@panix6.panix.com>:
> // more extreme ...
> template <class key> my_compare
> {
> public:
> bool operator()(void* left, void* right)
> {
> return *(key*)left < *(key*)right;
> }
You can't dereference a void pointer. (OK, strictly speaking you can, but
the this your pointing at has no type...)
> template <class key, class value> ptrMap :
> private std::map<void*, void*, my_compare<key> >
> {
>
>
> This seems to work quite well, the upfront "cost" is quite large, but
> the marginal cost of adding instances is very low. I'm curious as to
> whether anyone else has tried something like this ? Are there any
> pitfalls with deriving from standard container classes ?
Yes. As I recall, none of them have a virtual destructor.
> Is it possible/practical to use a void* container to implement a
> value-based container (which is something my second map example comes
> close to doing)?
IMHO: you're defeating the entire type safety features of the language. If
I had a programmer who thought that this was a good idea, and didn't have
_a lot_ of proof that it was absolutely required, I'd rip his/her lungs
out.
I can't see how your comparison operator can work for any type.
I guess one big question: you refer to code bloat. Is this code bloat
actually causing you problems?
Howard Hinnant
<elf...@panix.com> wrote:
| Hi. I've been working on a library which uses a number of instances
| of STL containers (mostly map and list) and template instances seem
| to make up a lot of the code.
|
| One idea was to roll my own, and implement pointer containers by using
| private inheritence and inheriting from container<void*>. The idea is
| that a template instance acts as some sort of type safety wrapper.
|
| Then it occurred to me that I could just reuse the STL containers void*
| instance
|
| eg
|
| template<class T> class ptrList : private std::list<void*>
| {
| public:
| typedef std::list<void*> base_class;
| inline void push_back(T* x){ base_class::push_back(x); }
| inline void push_front(T* x){ base_class::push_front(x); }
| ...
The Metrowerks implementation of std::vector, std::list, std::deque,
and the non-standard container Metrowerks::cdeque does this for you
automatically (Windows, Mac, several embedded enivronments including
Palm). We haven't done this optimization with set/map, though that
remains a possibility for the future. The feedback that we've gotten
from some of our customers (from some of the largest, to some of the
smallest) has been consistently positive. I had one major customer
tell me that this feature saved them about 3/4 Mb in the code size of
their application, though I don't know what the overall size of the app
was. I've had other customers say "So what, don't all STL's do this?".
Um... nope, no one else currently does. We've had it for a couple
years though.
So yes, this approach can be a significant win. And although generally
easy to implement, watch out for the member template methods. You
really have to be careful with those to avoid some nasty bugs. And you
might want an easy way to turn this feature off. It's a pain to try to
view the contents of your container in a debugger when it is full of
void*'s.
In article <Xns90F36533BDC93...@209.53.75.21>, Andre
Kostur <An...@incognito.com> wrote:
| If
| I had a programmer who thought that this was a good idea, and didn't have
| _a lot_ of proof that it was absolutely required, I'd rip his/her lungs
| out.
Ouch! I guess the workplace can be quite hazardous. :-)
--
Howard Hinnant
Metrowerks
Donovan Rebbechi
> elf...@panix.com (Donovan Rebbechi) wrote in
><slrn9mo5ki....@panix6.panix.com>:
>
>> // more extreme ...
>> template <class key> my_compare
>> {
>> public:
>> bool operator()(void* left, void* right)
>> {
>> return *(key*)left < *(key*)right;
>> }
>
> You can't dereference a void pointer. (OK, strictly speaking you can, but
> the this your pointing at has no type...)
You can only do it if you know something about the pointer in question.
But I do know something about it -- namely that it points to something
that was inserted through the exposed public interface, and that
interface gaurantees that only things of type std::pair<key,value*> get
inserted.
>> This seems to work quite well, the upfront "cost" is quite large, but
>> the marginal cost of adding instances is very low. I'm curious as to
>> whether anyone else has tried something like this ? Are there any
>> pitfalls with deriving from standard container classes ?
>
> Yes. As I recall, none of them have a virtual destructor.
But this is not a problem here, because I am not adding any data to the
classes.
>> Is it possible/practical to use a void* container to implement a
>> value-based container (which is something my second map example comes
>> close to doing)?
>
> IMHO: you're defeating the entire type safety features of the language. If
I disagree. On the contrary, other containers that impose pseudo
single-rooted heirarchies (as well as the java containers) defeat
type safety features, by failing to distinguish between different types.
Using base class pointers and having list<Base*> instead of
list<Derived1*>, list<Derived2*>, list<Derived3*> also throws away type
safety.
My code on the other hand provides type-safe generic containers. For
example, you can implement a ptrlist<Derived1> and even though it shares
code with ptrlist<Base>, it has the advantage that you can't put Base
class pointers into it.
The intermediate code itself is, as you've observed, not safe (unsafe
casts are performed), but it has the redeeming feature that it is
extremely simple and not terribly error prone. All of the functions are
inlined one-liners that delegate to the base class, stripping or
re-attaching type information. If the class actually did anything
non-trivial, I'd think you'd have a valid point, but the adaptors that
I'm writing are extremely simple.
> I had a programmer who thought that this was a good idea, and didn't
> have
> _a lot_ of proof that it was absolutely required, I'd rip his/her lungs
> out.
This basic idiom is something that Stroustrup mentions in "The C++
Programming Language". It's also used by toolkit implementors to
write generic containers. (see for example Qt)
> I can't see how your comparison operator can work for any type.
The comparison operator only works for types for which operator< is
defined. This is a requirement for any map class. The requirement will
be enforced *at compile time*.
Note that the comparison operator should absolutely not be used directly,
it's only to be used indirectly by the map container. There is an
assurance that any pointer in the key field of a pair inside map container
does indeed point to type key, because the map interface enforces this.
> I guess one big question: you refer to code bloat. Is this code bloat
> actually causing you problems?
Yes, it is. A map class on my implementation costs 90kb *per instance*.
Instances of the list class are about 45kb *per instance*.
That means that a large program could produce an enormous executable.
The library I'm working on is getting larger, and resulting in larger
executables. This is a genuine problem. Another problem is
compile times -- template code when used without discipline, is a
disaster as far as compile dependencies are concerned, because the
amount of work that the compiler has to do expands combinatorially along
with the code.
I would like to be able to create several different instances of a
template class rather than creating one instance of an artificially
generic base class precisely because I *do* want type-safety, but I
want it without template bloat.
Indeed, there are instances of projects that ended up dumping
technologies because the template bloat ended up producing enormous
executables (example in point: Mico, a CORBA orb which uses STL)
--
Donovan
Donovan Rebbechi
wrote:
> In article <slrn9mo5ki....@panix6.panix.com>, Donovan Rebbechi
><elf...@panix.com> wrote:
> The Metrowerks implementation of std::vector, std::list, std::deque,
> and the non-standard container Metrowerks::cdeque does this for you
> automatically (Windows, Mac, several embedded enivronments including
> Palm).
This is interesting. The fact that this wasn't done in my STL version
led me to believe it wasn't possible.
Question -- do you do this sort of thing with *all* types of (eg:) lists,
or only for containers of pointers ?
> smallest) has been consistently positive. I had one major customer
> tell me that this feature saved them about 3/4 Mb in the code size of
> their application, though I don't know what the overall size of the app
> was.
Comes as no surprise, given that on my implementation, STL containers
cost 40-100k *per instance* (that means 7 different map classes would cost
nearly 3/4 Mb). These executable sizes also correlate with very slow compiles
...
> So yes, this approach can be a significant win. And although generally
> easy to implement, watch out for the member template methods. You
> really have to be careful with those to avoid some nasty bugs. And you
> might want an easy way to turn this feature off. It's a pain to try to
> view the contents of your container in a debugger when it is full of
> void*'s.
Thanks for the tip. I think I'll just keep it nice and simple and not
re-implement the member template methods -- I don't use them very often.
Cheers,
--
Donovan
Grzegorz Sakrejda
news:slrn9mo5ki....@panix6.panix.com...
> Hi. I've been working on a library which uses a number of instances
> of STL containers (mostly map and list) and template instances seem
> to make up a lot of the code.
>
> One idea was to roll my own, and implement pointer containers by using
> private inheritence and inheriting from container<void*>. The idea is
> that a template instance acts as some sort of type safety wrapper.
>
> Then it occurred to me that I could just reuse the STL containers void*
> instance
>
> eg
>
> template<class T> class ptrList : private std::list<void*>
> {
> public:
> typedef std::list<void*> base_class;
> inline void push_back(T* x){ base_class::push_back(x); }
> inline void push_front(T* x){ base_class::push_front(x); }
> ...
Why not public inheritance ?
Also this could be a specialization of std::list for pointers :
template <class T> class std::list<T*> : public std::list<void*> {
public :
class iterator : public std::list<void*>::iterator {...
and so on.
.> Is it possible/practical to use a void* container to implement a
value-based
> container (which is something my second map example comes close to doing)?
maybe rather define iterator for container of pointers ?
Also something has to be done with erase ( elements ownership).
grzegorz
>
> --
> Donovan
>
Howard Hinnant
<elf...@panix.com> wrote:
| Question -- do you do this sort of thing with *all* types of (eg:) lists,
| or only for containers of pointers ?
In our current desktop release (Pro 6), it is done only for pointers in
list, deque, slist and cdeque.
For vector it is done for all pods. But there is no automatic pod
detection so this effectively reduces it to just all built-in types.
Which built-in's share with which others varies with platform. The
built-in's must have the same sizeof to share. On Windows (for
example) the following built-in's share a vector implementation.
long
unsigned long
int
unsigned int
T*
There is more information on this topic at:
http://home.twcny.rr.com/hinnant/tip_archive/
tips #1 and #12.
| Comes as no surprise, given that on my implementation, STL containers
| cost 40-100k *per instance* (that means 7 different map classes would
| cost
| nearly 3/4 Mb)
Fwiw, although I've stated we don't do this optimization for set/map,
the code responsible for rebalancing the red-black tree under set/map
/is/ shared by /all/ instantiations across set, multiset, map,
multimap. This is a fair chunk of code that is completely independent
of the value_type in the tree. Therefore it is broken out so that the
same rebalancing code is used for /all/ trees.
Just thought I'd mention it to point out that there are techniques out
there in addition to the void* trick to help reduce template code
bloat.
We at Metrowerks are sensitive to code size since we have customers who
want to use the full power of the STL but in resource constrained
environments ... Has your toaster done STL lately? :-) But often
what's good for embedded is good for the desktop too.
--
Howard Hinnant
Metrowerks
Donovan Rebbechi
> "Donovan Rebbechi" <elf...@panix.com> wrote in message
> news:slrn9mo5ki....@panix6.panix.com...
> > Hi. I've been working on a library which uses a number of instances
> > of STL containers (mostly map and list) and template instances seem
> > to make up a lot of the code.
> >
> > One idea was to roll my own, and implement pointer containers by using
> > private inheritence and inheriting from container<void*>. The idea is
> > that a template instance acts as some sort of type safety wrapper.
> >
> > Then it occurred to me that I could just reuse the STL containers void*
> > instance
> >
> > eg
> >
> > template<class T> class ptrList : private std::list<void*>
> > {
> > public:
> > typedef std::list<void*> base_class;
> > inline void push_back(T* x){ base_class::push_back(x); }
> > inline void push_front(T* x){ base_class::push_front(x); }
> > ...
>
> Why not public inheritance ?
My main concern is that I don't want to expose the public interface of
list<void*>, because this could be quite dangerous. Another issue is
that
I don't want the lists to be treated polymorphically.
The following need re-implementing in the derived class:
(1) Any function that takes an argument of type value_type, because
having a function that accepted type void* arguments would throw away
type safety, and silently
accept any pointers.
(2) Any function that returns something of type value_type, because it
needs
to be cast.
(3) Anything that returns iterators (because operator* would do the
wrong thing
to an iterator of a void* list)
It's critical that no functions in class (1) or (2) or (3) are
exposed.
Better to hide them all by default (IMO)
> Also this could be a specialization of std::list for pointers :
>
> template <class T> class std::list<T*> : public std::list<void*> {
> public :
> class iterator : public std::list<void*>::iterator {...
> and so on.
Yes, this idea has merit, and is probably the write way to do it if
you're
implementing the container class. I'd prefer not assume that
the implementation has not already specialised it (IOW my only reason
for not
doing this is that I don't have control over the implementation of my
base class)
> maybe rather define iterator for container of pointers ?
Again, there's the same issue: that's the way I'd do it if I had
control
over the base class (and didn't mind making assumptions about it)
> Also something has to be done with erase ( elements ownership).
Yes, containers of pointers raise all sorts of sticky ownership
questions.
I've just implemented a value container based on void* which
simplifies
ownership questions by making its own copies, eg
void push_back(const T& x){ base::push_back(new T(x)); }
Of course this requires a destructor, and the destructor in the base
class is not virtual.
The Qt classes have an "autodelete" flag that does as the name
suggests (namely, the container takes responsibility for ownership)
Cheers,
--
Donovan
Bruce G. Stewart
>
> In article <slrn9mo5ki....@panix6.panix.com>, Donovan Rebbechi
> <elf...@panix.com> wrote:
>
> | Hi. I've been working on a library which uses a number of instances
> | of STL containers (mostly map and list) and template instances seem
> | to make up a lot of the code.
> |
> | One idea was to roll my own, and implement pointer containers by using
> | private inheritence and inheriting from container<void*>. The idea is
> | that a template instance acts as some sort of type safety wrapper.
> |
> | Then it occurred to me that I could just reuse the STL containers void*
> | instance
> |
> | eg
> |
> | template<class T> class ptrList : private std::list<void*>
> | {
> | public:
> | typedef std::list<void*> base_class;
> | inline void push_back(T* x){ base_class::push_back(x); }
> | inline void push_front(T* x){ base_class::push_front(x); }
> | ...
>
> The Metrowerks implementation of std::vector, std::list, std::deque,
> and the non-standard container Metrowerks::cdeque does this for you
> automatically (Windows, Mac, several embedded enivronments including
> Palm). We haven't done this optimization with set/map, though that
> remains a possibility for the future.
I wonder, does anyone know of a compiler that folds functions
automagically? Templates are a rich source of such things, but they can
also arise from "hand-written" code.
Andre Kostur
>In article <Xns90F36533BDC93...@209.53.75.21>, Andre
>Kostur wrote:
>> elf...@panix.com (Donovan Rebbechi) wrote in
>> <slrn9mo5ki....@panix6.panix.com>:
>>
>>> // more extreme ...
>>> template <class key> my_compare {
>>> public:
>>> bool operator()(void* left, void* right)
>>> {
>>> return *(key*)left < *(key*)right;
>>> }
>>
>> You can't dereference a void pointer. (OK, strictly speaking you can,
>> but the this your pointing at has no type...)
>
>You can only do it if you know something about the pointer in question.
>
>But I do know something about it -- namely that it points to something
>that was inserted through the exposed public interface, and that
>interface gaurantees that only things of type std::pair<key,value*> get
>inserted.
Whups, I wasn't quite paying enough attention... I missed the cast to
(key*)
>>> Is it possible/practical to use a void* container to implement a
>>> value-based container (which is something my second map example comes
>>> close to doing)?
>>
>> IMHO: you're defeating the entire type safety features of the
>> language. If
>
>I disagree. On the contrary, other containers that impose pseudo
>single-rooted heirarchies (as well as the java containers) defeat
>type safety features, by failing to distinguish between different types.
>
>Using base class pointers and having list<Base*> instead of
>list<Derived1*>, list<Derived2*>, list<Derived3*> also throws away type
>safety.
Huh? How does a list of base pointers throw away type safety? If you
treat every item that you insert into the list as a Base object, where's
the problem?
>My code on the other hand provides type-safe generic containers. For
>example, you can implement a ptrlist<Derived1> and even though it shares
>code with ptrlist<Base>, it has the advantage that you can't put Base
>class pointers into it.
You can't put a Base* into a list<Derived1*> either.... (barring casting)