C++ is Slow?

[nw]

"The C++ Programming Language" 3rd Edition or Special Edition by Bjarne
Stroustrup (the creator of C++), Chapter 22 "Numerics" (on page 657).

<reads> ok.. I see. So the message here is encapsulate a valarray in a
Matrix object and use the slice operations to access it. The advantage
to using valarray over vector here is that that it provides slice
operations, I don't need to implement my own? Or are there other
efficiency gains to using valarray?

I can't see a huge advantage to encapsulating a valarray to a vector
here.

 

[nw]

Having op[] return a dummy object is a poor idea, it makes it harder to
drop in different implementations. Only do something like that if you
absolutely have to. See the FAQ for more about this subject.
http://www.parashift.com/c++-faq-lite/operator-overloading.html#faq-1...

The FAQ is wrong about this. The choice between [j] and
(i,j) should depend on personal preference and local
conventions; both offer exactly the same possibilities for
optimization and supporting different implementations.

My reading was that the FAQ indicates that you can use [j] but
tries to steer
you away from it because it will be harder to implement. I'm veering
towards a
Matrix object with a operator() but I find it unfortunate that the STL
doesn't
already provide such an object, doing so would provide a standardized
interface
which would let people create compatible Matrix objects optimized for
different
platforms, spare matrices etc.

Are there are any plans for this to be added to a future standard?

 

[Ioannis Vranos]

<reads> ok.. I see. So the message here is encapsulate a valarray in a
Matrix object and use the slice operations to access it. The advantage
to using valarray over vector here is that that it provides slice
operations, I don't need to implement my own? Or are there other
efficiency gains to using valarray?

I can't see a huge advantage to encapsulating a valarray to a vector
here.

I haven't used valarray in practice myself, however valarray can be
aggressively optimised so if you have serious run-time concerns you
should use valarray with slice or gslice or whatever other valarray
auxiliary type fits better.

If you have not serious run-time concerns but the usual ones, you may
use the usual vector<vector<whatever> > combinations and have your job done.

 

[nw]

I haven't used valarray in practice myself, however valarray can be

aggressively optimised so if you have serious run-time concerns you
should use valarray with slice or gslice or whatever other valarray
auxiliary type fits better.

What is it about valarray that allows it to be aggressively optimised?
Is it because it has a fixed size? So that a compiler could choose to
store it in a small but fast region of memory and be sure that it
would be necessary to grow the array?

I'm trying to understand why I need this data structure, as others
have noted it's usually not well optimised and doesn't seem to have
been developed very well in the standard.

 

[Ioannis Vranos]

What is it about valarray that allows it to be aggressively optimised?
Is it because it has a fixed size? So that a compiler could choose to
store it in a small but fast region of memory and be sure that it
would be necessary to grow the array?

I'm trying to understand why I need this data structure, as others
have noted it's usually not well optimised and doesn't seem to have
been developed very well in the standard.

Have a look on the entire chapter 22 of TC++PL3, it provides some info
on this.

For example on page 663 it is mentioned:

"The valarray and its auxiliary facilities were designed for high-speed
computing. This is reflected in a few constraints on users and by a few
liberties granted to implementers. Basically, an implementer of valarray
is allowed to use just about every optimization technique you can think
of. For example, operations may be inlined and the valarray operations
are assumed to be free of side effects (except on their explicit
arguments of course). Also, valarrays are assumed to be alias free, and
the introduction of auxiliary types and *the elimination of temporaries*
is allowed as long as the basic semantics are maintained. Thus, the
declarations in <valarray> may look somewhat different from what you
find here (and in the standard), but they should provide the same
operations with the same meaning for code that doesn't go out of the way
to break rules. In particular, the elements of a valarray should have
the usual copy semantics (17.1.4)".


I do not know if you need valarray though. This is up to you to decide.
vector is efficient for most applications.

Have a look on 17.1.2 of TC++PL3 where the costs of the various
containers are mentioned.

 

[Erik Wikström]

If you have serious run-time concerns then you should use a library
which offers high performance multi-dimensional arrays, there are a few
around. However be aware that I have never heard anyone speak of the
valarray as being one of them except in theoretical situations.

Have a look on the entire chapter 22 of TC++PL3, it provides some info
on this.

For example on page 663 it is mentioned:

"The valarray and its auxiliary facilities were designed for high-speed
computing. This is reflected in a few constraints on users and by a few
liberties granted to implementers. Basically, an implementer of valarray
is allowed to use just about every optimization technique you can think
of. For example, operations may be inlined and the valarray operations
are assumed to be free of side effects (except on their explicit
arguments of course). Also, valarrays are assumed to be alias free, and
the introduction of auxiliary types and *the elimination of temporaries*
is allowed as long as the basic semantics are maintained. Thus, the
declarations in <valarray> may look somewhat different from what you
find here (and in the standard), but they should provide the same
operations with the same meaning for code that doesn't go out of the way
to break rules. In particular, the elements of a valarray should have
the usual copy semantics (17.1.4)".

A little history of valarray: It was developed at a time when vector-
computers were the latest and greatest in scientific computing and was
developed to allow C++ developers easy access to the power of these
vector-machines. Unfortunately there are a few problems with it, one
being that the number of vector-computers your code will ever run on is
none (with a very great probability). Another problem was that they guy
(or guys) who were working on the valarray stopped working on it some-
where half-way through. So the result is probably what they had come up
with so far, perhaps finished of by someone who was not very familiar
with the problem. And lastly I have heard that the assumed freedom from
aliases can not be fulfilled (I have heard that it cannot be in a
language that allows pointers (unless, perhaps you have something like
restrict in C)).

I am quite sure that many in the C++ committee would like to remove it,
but you are not allowed to do that in an ISO standard (at least not very
easily).

 

[Erik Wikström]

Having op[] return a dummy object is a poor idea, it makes it harder to
drop in different implementations. Only do something like that if you
absolutely have to. See the FAQ for more about this subject.
http://www.parashift.com/c++-faq-lite/operator-overloading.html#faq-1...

The FAQ is wrong about this. The choice between [j] and
(i,j) should depend on personal preference and local
conventions; both offer exactly the same possibilities for
optimization and supporting different implementations.

My reading was that the FAQ indicates that you can use [j] but
tries to steer
you away from it because it will be harder to implement. I'm veering
towards a
Matrix object with a operator() but I find it unfortunate that the STL
doesn't
already provide such an object, doing so would provide a standardized
interface
which would let people create compatible Matrix objects optimized for
different
platforms, spare matrices etc.

Are there are any plans for this to be added to a future standard?

No, (or rather probably not, I am not a member of the committee so I do
not know). It has always been the purpose of the standard library to
supply generic containers and algorithms. For specialised purposes third
part libraries are generally recommended. If you want a library you can
use to perform vector and matrix algebra there are a number of them
available, http://www.oonumerics.org/oon/ have a good list.

 

[Ioannis Vranos]

I am quite sure that many in the C++ committee would like to remove it,
but you are not allowed to do that in an ISO standard (at least not very
easily).

If this is the case they could deprecate it. It wasn't in C++03 and I am
not sure this will happen in "C++0x" too.

I agree that there are special-purpose, very efficient, C++ math
libraries out there, but I think we should stick with ISO C++ as much as
we can in our code.

If I had efficiency concerns and valarray didn't do the job, I would
check those 3rd party libraries of course.

 

[Maxx]

On My FreeBSD platform iostream takes about 3sec more than stdio to
compile a program that is approximately about 23MB big.And that lag in
speed is probably because of the large number of libraries that
iostream has within it.

 

[Ian Collins]

On My FreeBSD platform iostream takes about 3sec more than stdio to
compile a program that is approximately about 23MB big.And that lag in
speed is probably because of the large number of libraries that
iostream has within it.

Who makes these compilers (iostream and stdio)?

 

[Lionel B]

[...]

And lastly I have heard that the assumed freedom from
aliases can not be fulfilled (I have heard that it cannot be in a
language that allows pointers (unless, perhaps you have something like
restrict in C)).

FWIW, GNU g++ (or at least the version on my system) implements a
__restrict__ specifier which, checking the valarray code, is sprinkled
liberally about. My experience with g++ is that more recent versions do
manage a certain degree of vectorisation under optimisation, although
whether this is in any way facilitated by restricting aliasing I really
don't know. The Intel compiler icpc (which on my system uses the g++ std
libs) appears to vectorise more aggressively than g++. On the whole, I've
never seen much of a speed-up using valarray rather than std::vector.

I am quite sure that many in the C++ committee would like to remove it,
but you are not allowed to do that in an ISO standard (at least not very
easily).

Yes, valarray is a bit of a curate's egg.

 

[James Kanze]

Having op[] return a dummy object is a poor idea, it makes
it harder to drop in different implementations. Only do
something like that if you absolutely have to. See the FAQ
for more about this subject.
http://www.parashift.com/c++-faq-lite/operator-overloading.html#faq-1....

The FAQ is wrong about this. The choice between [j] and
(i,j) should depend on personal preference and local
conventions; both offer exactly the same possibilities for
optimization and supporting different implementations.

My reading was that the FAQ indicates that you can use [j]
but tries to steer you away from it because it will be harder
to implement.

Not significantly. My reading was that it also raised
performance issues, which aren't present either.

I'm veering towards a Matrix object with a operator() but I
find it unfortunate that the STL doesn't already provide such
an object, doing so would provide a standardized interface
which would let people create compatible Matrix objects
optimized for different platforms, spare matrices etc.

Are there are any plans for this to be added to a future standard?

It's probably true that there is a need for true
multi-dimensional arrays. To date, however, I don't think that
there has been a proposal.

 

[James Kanze]

On My FreeBSD platform iostream takes about 3sec more than stdio to
compile a program that is approximately about 23MB big.And that lag in
speed is probably because of the large number of libraries that
iostream has within it.

More likely the difference is due to the fact that iostream is a
template.

 

[Daniel T.]

Having op[] return a dummy object is a poor idea, it makes
it harder to drop in different implementations. Only do
something like that if you absolutely have to. See the FAQ
for more about this subject.

The FAQ is wrong about this. The choice between [j] and
(i,j) should depend on personal preference and local
conventions; both offer exactly the same possibilities for
optimization and supporting different implementations.

My reading was that the FAQ indicates that you can use [j]
but tries to steer you away from it because it will be harder
to implement.

Not significantly. My reading was that it also raised
performance issues, which aren't present either.

I recall having an extended discussion about this sometime last year. I
don't remember if James participated, but the conclusion was that any
class that supported the [x][y] syntax and was as flexible as one that
supported the at( x, y ) syntax, ended up supporting both. Make of that
what you will...

 

[nw]

Having op[] return a dummy object is a poor idea, it makes
it harder to drop in different implementations. Only do
something like that if you absolutely have to. See the FAQ
for more about this subject.
http://www.parashift.com/c++-faq-lite/operator-overloading.html#faq-1...
The FAQ is wrong about this. The choice between [j] and
(i,j) should depend on personal preference and local
conventions; both offer exactly the same possibilities for
optimization and supporting different implementations.

My reading was that the FAQ indicates that you can use [j]
but tries to steer you away from it because it will be harder
to implement.

Not significantly. My reading was that it also raised
performance issues, which aren't present either.

From the FAQ: "If you have a decent compiler and if you judiciously
use inlining, the compiler should optimize away the temporary objects.
In other words, the operator[]-approach above will hopefully not be
slower than what it would have been if you had directly called
Matrix:perator()(unsigned row, unsigned col) in the first place. Of
course you could have made your life simpler and avoided most of the
above work by directly calling Matrix:perator()(unsigned row,
unsigned col) in the first place. So you might as well directly call
Matrix:perator()(unsigned row, unsigned col) in the first place."

I guess he's saying that your compiler /should/ be able to optimize
your performance issues away, but perhaps that wont always be the
case.

It's probably true that there is a need for true
multi-dimensional arrays. To date, however, I don't think that
there has been a proposal.

Seeing as there is a lot of numerical code going in to TR1, perhaps it
wouldn't be a bad idea if this was suggested for TR2? Or does anyone
have an opinion as to why this would be a bad idea?

 

[James Kanze]

Having op[] return a dummy object is a poor idea, it makes
it harder to drop in different implementations. Only do
something like that if you absolutely have to. See the FAQ
for more about this subject.
The FAQ is wrong about this. The choice between [j] and
(i,j) should depend on personal preference and local
conventions; both offer exactly the same possibilities for
optimization and supporting different implementations.
My reading was that the FAQ indicates that you can use [j]
but tries to steer you away from it because it will be harder
to implement.

Not significantly. My reading was that it also raised
performance issues, which aren't present either.

I recall having an extended discussion about this sometime
last year. I don't remember if James participated, but the
conclusion was that any class that supported the [x][y] syntax
and was as flexible as one that supported the at( x, y )
syntax, ended up supporting both. Make of that what you
will...

Supporting both is also an option. Basically, all I'm saying
is that you shouldn't let supposed performance issues or
simplicity of implementation influence you. Present the options
to your users, and let them decide.

 

[Daniel T.]

Basically, all I'm saying is that you shouldn't let supposed
performance issues or simplicity of implementation influence you.
Present the options to your users, and let them decide.

Trying to be all interfaces to all users is what produced the
std::string class. I'm not sure if that is such a good idea.

 

[Hans Mull]

Who makes these compilers (iostream and stdio)?

Compilers?

 

[Hans Mull]

On My FreeBSD platform iostream takes about 3sec more than stdio to
compile a program that is approximately about 23MB big.And that lag in
speed is probably because of the large number of libraries that
iostream has within it.

Some C++ functions are using dynamic memory allocation. This is not as
fast as static memory allocation.

Kind regards, Hans

 

[Ian Collins]

Compilers?

To quote "iostream takes about 3sec more than stdio to compile a program"

Compilers compile.