Re: [boost] Re: MPL containers and algorithms

From: Terje Slettebø (tslettebo_at_[hidden])
Date: 2002-08-13 08:07:54

>From: "Paul Mensonides" <pmenso57_at_[hidden]>

>>From: "Terje Slettebø" <tslettebo_at_[hidden]>

>> As Dave pointed out, too, why would uniformity be an advantage? Isn't one
>> for the advantages for the iterator consept at STL that you may use it
>> with anything that provides iterators, including things like generators?

>Why is it frowned upon to reimplement your own string class?  Why is
>frowned
>upon to reimplement what is already done a freely available?  Uniformity is
>the purpose that the C++ standard library exists at all (except for the
parts
>that are actually tightly integrated with the language itself!).

And MPL has a uniform iterator interface. _This_kind of uniformity, a
uniformity of interface (rather than implementation, such as standardising
on _one_ sequence), ensures interoperability, removes duplication, and keeps
the design open-ended. Oh, and did I mention you get a free doll, as well?
:) And a picture of the company president. :) Furthermore, there's a 30-day
money-back guarantee. Uh, come to think of it, it's free already, never
mind. :)

I think you may confuse interface/concept uniformity, which may be an
advantage, with implementation uniformity, which may make it hard to develop
and extend a library.

>> If you go for a uniform way, that means people have to agree on a uniform
>> way. So far, there haven't been any compelling reasons for exclusively
>> selecting one sequence compared to another, which you have pointed out,
>> too, as they vary in their behaviour,

>I have pointed out nothing of the sort except to say that vectors
outperform
>lists and that both are unrealistic at large sizes.

As mentioned in another posting, vectors more or less don't work on e.g.
Intel C++, except small ones, due to slow preprocessor, etc. Lists work.
This is some of what I meant.

>We have no compelling
>reasons (or example to that effect) to *have* more than one sequence type.

I think we do. I gave one reason above, here.

The Burton et al paper is another example. Doug (and the paper) showed in a
recent posting, that such immutable vectors may be good for some
applications, especially if large structures are needed. On the other hand,
lists or mutable vectors may be useful for other applications. How would you
operate on both kinds, without iterators? Creating sequence converters for
the large, immutable vector is largely out, because of its size. If you
create a lazy converter, you essentially have an iterator. Why make it hard
for yourself, by creating abstractions (like fixed sequence type) that
requires such workarounds all the time?

To counter the argument in another posting of yours, about how you could
operate on such a big sequence in the first place, the answer is that
algorithms don't necessarily have to traverse the whole sequence. The size
operation you mentioned could be solved by storing the size in the
structure. This is what Burton et al did.

>There are reasons in runtime programming--different *actual* runtime
>performance
>characteristics and memory usage, etc..  These _do_ _not_ _apply_ to
compile
>time programming.  Therefore, if you want to say that emulation of the STL
>analogy is good, you have to prove it by other means.

>> which is yet another reason for not fixing
>> it to a specific sequence. Especially as the field is quite new, as you
>> say, you don't want to standardise on something, to not make a decision
that
>> later turns out to be bad.

>What is the purpose of Boost?  Isn't it to create "existing practice"?  Why
>would we want to create existing practice in an area that is largely
>experimental with absolutely no concrete data saying that it is worthwhile?

Boost, as I understand it, is also a testing ground for libraries.

Furthermore, your argument goes against your own suggestion, as well. Why
should we standardise on one sequence, unless we know that to be the best
way? And in addition, there's the choice of which sequence, if any, to
standardise for.

> So I think the argument that this is a new field, actually works against
> fixing the framework to things like specific sequences.

>Obviously.  You and I have are viewpoints, and all that is happening is
that
>we see things as we want to see things.

No. I find that an insulting characterisation. We may use different base
assumptions, and therefore arrive at different conclusions. This is _not_
the same as seeing things that we want to. I challenge you to substantiate
that claim, or take it back. I even published the timing result, showing
that vector was faster than list, even though I had expected it to come the
other way around, and even though that meant that I couldn't use it as a
speed argument for list, out for the interest at scientific honesty!

>> In addition, you have the mentioned advantages that David B. Held and
>> others have pointed out, that with the iterator abstraction, anything
providing
>> iterators may be used for the algorithms, that includes things like
>> generators, too. range_c works like that. Are you disregarding this, as
>> well?

>Why would it be difficult to make a convertor for the specific and uncommon
>case of something like range_c?  Input/output doesn't apply, random number
>generators don't apply, etc..

Who are you to say what would be the common or uncommon thing to use? If the
creators of STL thought like this, they may have standardised on one
sequence, as well, e.g. vector, because it would be the "common" thing to
use. If you wanted something with the characteristics of list, you could
make a list, but then you'd need a vector converter, to use it in any of the
algorithms, because they expect vector. Sorry, but your argument goes both
ways, also towards STL. Would this be the kind of STL you like? It certainly
wouldn't be for me.

RNG may well apply. Sure, to get a different result, you need to supply a
different seed. However, getting a different result may not be that
necessary. You may for example use it for stocastical analysis, or to test
various sort implementations. In those cases, the starting seed doesn't
matter that much.

Personally, I object to a library design that makes unnecessary limiting
decisions, because at the time, no other use was found for it.

If the creators of C++ thought like this, when designing the template
system, that it wouldn't be necessary to make it more advanced than
supporting containers of T, because they couldn't think of anything else,
then there would be no metaprogramming in C++.

>> In my opinion, this is a strong argument for the iterator abstraction. It
>> enables extension and experimentation, in this new, exciting field. MPL
>> would be much less extensible, if algorithms and functions only worked
for
>>a fixed set of sequences, that couldn't be extended.

>No it wouldn't be.  It would simply be a case of defining convertors in
some
>case (yet to be seen) where it is absolutely necessary.  That doesn't make
>it less extensible, it just shifts the extensibility and simplifies the
>implementation.

As mentioned in other postings, that I'm sending now, in what way would it
be simpler to implement an algorithm to work on e.g. vector, than iterators?
Please show something concrete.

>> By the way, I later found that the example program I posted (sequence
>> timing), used the typeof() of g++, a non-standard extension. Doing some
>> simple testing on MSVC 6.0 (which doesn't have typeof()), vector and list
>> came out equally fast.

>What kind of test were you doing?  In order to really see performance
>benefits with a vector, you'd have to do random access of many elements at
once.

It was the same test as posted earlier. This is a little dodgy, though, as
some compilers may optimise away the nested types. It may be hard to make
accurate tests, factoring out the part that doesn't contribute to what is
being tested.

A reasonably good test might be sorting a random sequence, and trying it
with different sequences. From these preliminary tests, it appears that
vector generally is fastest. However, it has the problem that it may be very
slow on other compilers, such as the EDG based ones, especially if the
preprocessor is used.

In any case, as this varies across sequences, sizes, and implementations,
I've more focused on the flexibility in being able to select the sequence
that works best for you, and also making it possible to make new ones,
without having to convert them into vector, which in some cases (such as
large sequences, like the Burton et al ones) may be simply infeasable.
Rather, you may want to operate on the sequence in-place.

Regards,

Terje