Re: [boost] Re: MPL containers and algorithms

From: Terje Slettebø (tslettebo_at_[hidden])
Date: 2002-08-14 04:19:22

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

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

>>>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.
>>
>> 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.

>No, I'm not confusing anything.  The standard library exists so that people
>don't have to rewrite these things.  That is implementation && concept
>uniformity.

Actually, the standard library imposes no implementation uniformity, it only
prescribes interface and behaviour (including complexity guarantees).

However, you may also claim that standardising on vector doesn't impose an
implementation uniformity, either, since it, being generic code, doesn't
require that the type is vector, only that it behaves like it. However, I've
yet to see how this would make writing the algorithms, etc. simpler, than
using the iterator concept.

>Also, this doesn't make it hard to develop the library at all.

Given the above, for the standard library, true.

>>>> 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.

>If the preprocessor is causing that massive of a drain, then the MPL is not
>using it properly.  That has nothing to do with the validity of different
>sequences.

It may instead be that some compilers, such as EDG based ones, have slow
preprocessors.

I agree that this, in itself, is not a principial reason for iterator
abstraction, but it's a practical one. Besides, the iterator abstraction
more or less works as if the library has standardised on a type - list - as
the iterator for list is more or less the list itself. So you already have
the effect of standardising on a type, yet making it possible to extend.

>> 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.

>No it doesn't.  Making something generic for no reason at all is _bad_
design,
>not good design.

I understand what you mean, and I agree to the last sentence. However, in
this case, it's far from clear that selecting one sequence, in particularly
vector, isn't going to make more complications, not less, when it comes to
practical use. Such as getting one that is larger than 50 elements, as
mentioned in another posting I just sent.

>If you have that point of view, why do we even need the
>template keyword anymore?  Everything could just automatically be a
template.
>Generality for the sake of generality is over-complication of a simple
concept
>and a waste of time.

I agree, but you misunderstood what I meant, as explained above.

>>>> 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 of the interest of scientific honesty!

>No I won't take it back.  Everybody does this all the time *because* of
basic
>assumptions.

I still disagree with this. I don't _want_ to see the iterator abstraction
as useful. That's not an aim in itself, for me. Why should it be that?
However, from what I've found, I've come to what I've come to what I've come
to. The same have you.

This has nothing to do with getting the results you want. When I've done the
tests, I tried to make them fair. If e.g. vector has come out especially
badly, I've looked into what could be the reason for this, to try to improve
it. This could have meant less efficiency argument, or argument at all, for
the sequence abstraction, but so what?

I'm interested in finding the truth, which I guess you are, as well.
Therefore, to be scientific, we should try to minimise any personal bias,
when doing such comparisons, measurements, etc. I've also published my
tests, so that others may verify them. Others are free to come up with their
own tests, of course.

>The timing result is not relevant if the all the time is spent in
>the preprocessor.

True. But if you look closer on that example, you'll see that I define it to
use preprocessed sources. Still, it may use the preprocessor some, anyway,
which makes it hard to separate out the part to measure, as mentioned in
another posting.

>What is the result otherwise?

You tell me. If you can make a test which factors out the preprocessor
completely, I could try it.

As I showed in the other posting, the preprocessor wasn't the problem,
though. It simply didn't go over 50 elements. At least, I didn't get it to
do that.

I tried to make some "random" changes (as this isn't documented in MPL) ,
now, such as, "#define BOOST_MPL_PREPROCESSING_MODE", as "vector.hpp" tests
for this, but this just gave different errors, with Intel C++ anf g++.

>>>> 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.

>I am the voice of reason.

Oh, right. So much for understanding the possible subjectivity involved.

I consider myself the voice of reason, too. So what? This is starting to get
silly.

>The STL creators *already* had a valid reason to
>abstract.  Also, there are *actual* reasons--as I've said (over and over
and
>over)--that different sequences are necessary at runtime.  Those reasons
*do not
>apply* to metaprogramming.  As far as commonality goes, it is fairly
obvious
>that vector and list are used more than range generators.

There has been presented examples of the usefulness of sequence abstractions
in this thread.

>> 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.

>How many times do I have to say the obvious.  What characteristics of list
and
>vector are you talking about?

See my other post with timing of vectors and lists, as well as the problem
with getting vectors over 50 in length. At least the way MPL is designed,
now. Without the preprocessor, you'd have to make large files with
duplication, and choose another arbitrary limit, which may still be too
small.

>And I'm not talking about blind references to the
>STL and runtime programming.  I'm talking about *actual* characteristics
where
>one is better than the other in one area vs. the other in another area.
Give me
>an example that shows that, and I'll listen.

I have. See above.

It shows that, in practical use, vectors over 50 in length may be slow or
impossible. On the other hand, list doesn't have such limit, but it doesn't
have random access, either. This is with reference to how the library is
implemented, now:

There you have your practical example.

>Otherwise, this is a bunch of theoretical nonsense.

This is hard facts.

>> 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.

>Why wouldn't you just use a random number instead?  If you have to specify
a
>seed every time what is the point?

Huh? If you want more than one, of course, such as to fill a sequence with
random numbers, or operate on a series of them.

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

>In what way is it limiting?  All of your "examples" in this regard are
contrived
>and motivated by no real world practicality.

See my other posting. I don't find not being able to have vectors longer
than 50 elements to be "contrieved". I've compiled lists with 1000 elements
(on the same Intel C++ compiler), and it took a few minutes, but it was
doable.

>> 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++.

>The creators of C++, i.e. the standards body as a whole, *do* think this
way.
>That is the reason that we don't have a ton more language features and
library
>facilities than we do.

I think you're mixing things, here. Both STL and MPL is about generality (or
more specifically, genericity), not adding a ton of features. You can use as
much or as little, or none at all, as you like, as it's all about concepts.
Concepts, that I don't think would be simpler, if you standardised on one
sequence.

>>>> 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.

>I don't need to show something concrete.  You do.

You're the one claiming that standardising on one sequence would make it
simpler. When I ask you to show you why that would be, concretely, you have
nothing to show for it. I think I see where this is heading. You say you
haven't seen much convincing, concrete, examples for the design of MPL. When
asked which other way, concretely, would make it simpler, you come up blank.

>Personally, I think that
>type-vectors are an implementation atrocity, but I think that is is more
>important to emphasize one type of sequence that the library is optimized
for
>than to use what I personally like best.  Otherwise, everyone is paying the
>price for generality that is almost never necessary.

I think I've shown enough practical examples, such as the unlimitedness of
list, limited only by the implementation, which tends to be much higher than
the library.

>>>> 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.

>What I was specifically wondering about was this...was the algorithm
operating
>on one element at a time?

Yes, it was a repetive push_front, to only test that operation.

>If so, I doubt that you would get a massive
>performance gain with vectors.  Only random access in quantity would make
it
>significant.

Which is what I mention below here, e.g. sort.

>> 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.

>As I said before, this is 1) irrelevant and 2) shows that the MPL is not
using
>the preprocessor in an efficient way.  That is not a big deal and can be
fixed.

I address this in the other mail I sent, now. As well as above here. In
summary: 1) Being unable to use it in practice on EDG based compilers is
relevant, as is using vectors more than 50 elements, at all. 2) The
preprocessor may be slow, in itself. You may avoid it, by making large
preprocessed files, but that still puts an arbitrary limit in the library
(which is 50, now).

>> 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.

>I know what you are saying.  I disagree with it, that's all. :)
Philosophically
>and logically.

Could you address what I said in the paragraph above, with specific respect
on "philosophically" and "logically"? I'm not sure if I understand what you
mean by it.

To summarize: There are practical considerations, such as large source files
(unless you use the preprocessor), and some compilers being quite slow for
vector, and there may be sequences where using an extensible vector could be
impractical, such as the Burton et al one.

In addition, there's the extensibility of iterators, although you may argue
that you can get the same with writing to the vector interface, or using
converters.

One thing: Some algorithms in MPL are significantly faster, if handled a
random-access iterator, than a forward/bidirectional one. If you standardise
on something with less than random-access iterators, you'll get a, possibly
unnecessary (if the sequence used can handle random access), performance hit
in some algorithms.

Regards,

Terje