Re: [boost] Re: MPL containers and algorithms

From: Paul Mensonides (pmenso57_at_[hidden])
Date: 2002-08-14 10:08:26

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

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

It describes exactly what something is supposed to do (that is implementation),
and it describes a full interface as well.

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

This is fine for the STL.  Different means and ends, as usual.

>> 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 do most of my preprocessor work (I am maintaining the preprocessor library.)
with Comeau C++.  I use VC++, MWCC, and others just to test it.  I am telling
you:  EDG-based front-ends *are* slow, but proper use of the preprocessor lib
(which, I know isn't easy given the lack of documentation) can still make it
acceptable.

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

Okay.  <-- This is not agreement :), just acknowledgement of your opinion.

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

It is amazing how much you are hanging onto this supposed real-world example.
This is a deficiency with MPL's preprocessor implementation not a type-vector in
the general sense.

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

Okay.

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

Just as an example, you have repeatedly put words into my mouth and
misinterpreted what I have said to show your viewpoint.  Either I am writing
unclearly, or you are reading what you want.  It is probably a little of both.

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

I don't think it has preprocessed source files that go past fifteen or so.
Anyway, it wouldn't be too hard to measure--just preprocess it separately.

>What is the result otherwise?

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

I don't know the command line syntax for Intel C++, but most compilers use -E or
/E to preprocess only.  You can output that to a file and then compile that
file.

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

What do you mean?  The preprocessor didn't go past fifty elements?

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

Well, the current preprocessor library that is on the CVS is unstable on some
non-compliant implementations (such as VC++ and MWCC).  I'm renonvating it as we
speak.  This may be part of the problem, but I doubt it with the EDG-front-end
(as in, compliant).

More importantly, as I'll say again, vectors become an implementation nightmare
at really large sizes.  Why would this be a good argument to use list instead?
Basically this gives you the exact opposite of your random-access efficiency
argument.  Use vectors for small sizes and lists for large sizes?

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

You asked a question, and I answered it.  I am a programmer, and I see other
programmers, etc..  That gives me the ability to judge whether or not something
is common.  This isn't completely arbitrary you know.  There are things that are
extremely specific to a small community, and there are things which are more
general.  People have to make these types of judgements all the time.

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

It is only silly because you ask ridiculous questions that you never meant to be
answered, like this:  "Who are you to say what would be the common or uncommon
thing to use?"  How about the opposite, "Who are you to say that something is
commonly useful?"  It is a pointless question, and one lacking in realistic
application.

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

There have not been any actual real-world examples, just theoretical could-be's
and what-if's, most of which, in these last couple messages, relying on the
'preprocessor is to slow' argument.  There is nothing wrong with
experimentation, and I have no problem with it.  If nothing else, it
familiarizes you with the available tools.  But that doesn't make something
ready for practicality.

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

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

Yes, and this is in argument for what?  All it looks like to me is an argument
against vectors in general because of the repetitive nature of their
implementation.  I agree with that, so why do we need vectors at all?  This is
just a compelling reason *not* to use vector.

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

No, you haven't.  You've only said that really large vector implementations are
a pain.  That doesn't demonstrate anything that I haven't already said.

>Otherwise, this is a bunch of theoretical nonsense.

-> This is hard facts.

Yes, large vectors require large source files (or preprocessing, etc.).  This
makes the implementation unreasonable at that size.  This is just an argument
against vectors altogether.  What is the point of using vectors at small sizes
when you already have list?

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

Okay, what is the *actual* example that makes it worthwhile to support a
compile-time random number generator as a sequence?  This is another 'what-if':
"What if you want to fill a sequence with random numbers?"  This goes into the
ends and means being different again.

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

Why do we need vector than?

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

I'm not mixing things, things to get into the standard without good examples to
prove they have a point.  The same goes for the template system.  Template
metaprogramming was a happy accident.  We can agree that the accident was
"happy" at least. :)

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

What do you want me to do, reimplement the MPL in order to show that it can be
simplified without sequence abstraction?  This is a critique of the parts of the
MPL's design.  It is not my job to prove that it is invalid or provide an
alterative; it is the library's job to prove that it is.

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

I haven't come up blank, we have already discussed what makes it simpler in this
thread many times.  Every time that you add a layer of abstraction, you also
make it slightly more difficult to use.  Algorithms written on vector could be
highly-optimized to work on vectors.  Same thing goes for lists.

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

You have not shown one single practical example (as in *code*).  You keep saying
the same things ( as do I :) ).  About the only thing that is different here is
saying that vectors aren't feasible for large sequences.  To me, that seems like
a justification to get rid of vectors altogether, because you have effectively
proven that they are an implementation and maintenance nightmare at large
sizes--with large sizes being their only real justification in the first place.

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

The only real way to compare is with a vector's strength:  random-access.  A
for_each algorithm could be highly optimized to take advantage of that, for
example.  However, If you only mess with one element at a time--in an
algorithmic way--it won't show vector being all that superior (if at all).
Sort, as you say, would probably be a good test of the relative speeds at small
sizes.

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

It isn't relavent because it could be corrected to work at reasonable efficiency
up to 128 (up to 256 actually).

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

I addressed this in the other post.

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

I disagree that "works best for you" is based on any logical premise or that
"making it possible to make new ones" is based on any practical premise.  What
is left is only personal taste for one thing or another.  I disagree with that
philosophically.

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

What kind of differences are you talking about here and at what sizes?  I
seriously doubt that a 10-element list or vector would make a big difference.  I
can certainly see where it would be that way for large sequences--and that is
exactly where 'random-access' breakes down.  Random-access implies repetition.

Paul Mensonides