alternative tuple implementation (was: [boost] Re: Any interest for a parser class?)

From: brianjparker (brianjparker_at_[hidden])
Date: 2002-01-27 22:56:09

--- In boost_at_y..., "David Abrahams" <david.abrahams_at_r...> wrote:
> 
> ----- Original Message -----
> From: "Aleksey Gurtovoy" <alexy_at_m...>
> 
> > I am not sure about the number of template instantiations - it 
might be
> > pretty much the same, - but, for one thing, they (instantiations) 
won't be
> > nested, so it's very likely that such implementation will also 
take a less
> > time to compile (compilers with EDG front-end is a different 
story, and
> > there are ways to deal with them :). But the main advantage would 
be, of
> > course, a size/speed of the generated code.
> 
> Agreed, that's crucially important! Why will the code be faster?

In my testing with a few benchmarks using a compiler with a low 
abstraction penalty (Intel C++ 6 beta) I could find no measurable 
difference in performance between boost::tuple and an equivalent C 
struct in terms of speed.

However, the deciding argument for me against the current recursive 
implementation of boost::tuple is space efficiency- a recursive 
implementation is compelled, by the language alignment rules, to use 
more padding space in many cases.
e.g.

struct tt {
    char c1;
    char c2;
    double d;
    char c3;
};

uses 24 bytes under Windows default system alignment (the alignment 
of the whole structure must be at least that of the worst case 
element- d- and so c1 must also be 8-byte aligned and the structure 
itself must be padded out to a multiple of 8, giving 24 bytes in 
total).

boost::tuple<char, char, double, char> *requires* 32 bytes as the 
recursive implementation forces these alignment requirements on each 
substructure (i.e. d and c3 must be 8-aligned and so use 16 bytes; c2 
with the 2-tuple (d, c3) must be a multiple of 8 in size and so is 24 
bytes, and similarly c1 with (c2, (d, c3)) must be a multiple of 8 in 
size to give a total size of 32 bytes).

As well as wasting space, this also causes boost::tuple to not be 
layout-compatible with struct PODs, which may or may not be a problem 
depending upon the application.

An alternative implementation that is layout-compatible with POD 
structs, that I use in my tuple class (in the files section under 
bjp_utilities*.zip), is to simply partially specialise for all tuple 
lengths, which is not too onerous for tuples up to, say, 20 in length 
(the submitted implementation is up to length 10) (of course, the 
production of the header could be automated if longer tuples were 
required). 

A further advantage of partially specialising for all cases is that 
it is easy then to add named members (in the style of 
std::pair's .first and .second) which I have found to be more obvious 
in code and analogous to std::pair (in fact, if a tuple class was to 
be added in a future library revision, then std::pair could simply be 
made a template typedef for a 2-tuple).

,Brian Parker