Re: C++ Speed Vs. Java
Carlos Moreno wrote:
James Kanze wrote:
I think Mathias' point was strong enough --- the compiler
could, and IMO *should* make that assumption up front;
std::vector can only be what the language specifies it to
be; now, the thing is, is the guarantee that they're either
the same, or entirely non-overlapping blocks, given explicitly,
or is it rather a "side-effect" of the *typical* way in which
it is implemented?
I think there are a number of people who don't; who are of the
opinion that it should be possible to write the equivalent of
std::vector as a true user defined type [...]
On the other hand, there's
been a very strong demand (and maybe still is) that the user be
able to replace the library with another implementation. Which
limits what the compiler can "know".
Wait! Two things: 1) std::vector *is* a user-defined type.
For what definition of "user-defined type"? An instantiation of
std::vector is a class type; in some contexts, it is
conventional to divide the types into "fundamental types", and
"user-defined types", and in these contexts, it is a user
defined type. More generally, however (and this corresponds to
the use of the expression in the library sections of the
standard), a user-defined type is a type defined by the user,
and thus, not by the standard.
That was just a "nit pick" --- the important point is 2)
std::vector is a user-defined type that must follow certain
specifications that the compiler *know* about.
It's part of the standard, and it is part of the "compiler", in
the larger sense that the standard uses the word. The compiler
can know not only about its specifications, but also the most
intimate details of its implementation. A perfectly legal
implementation of the header <vector> could be:
#pragma __turnon_buildin( "vector" )
or something along those lines. (For that matter, the compiler
could directly recognize the line "#include <vector>", and
execute whatever was necessary, without there even being a
header anywhere.)
The compiler can make any assumptions that follow from the
Standard specification of std::vector, and if those
assumptions happen to be false, then it would be up to the
user to replace the defective STL implementation.
The compiler can assume a specific implementation of
std::vector; it's part of the compiler implementation, and not
an external component or library.
A compiler implementation can, if it so desires, as an
extension, provide a means for replacing the standard library,
either completely, or in parts. The standard doesn't require
this, but it is (or was) an often requested feature, and most
compilers do provide it, at least in part. (I daresay that
replacing <typeinfo> would cause a number of problems, but you
can usually replace the STL part in block.)
At any rate, current compilers don't seem to use this
information.
Ok, good point. Still, the discussion was fun while it
lasted, no? :-)
Certainly. I think we all agree that compilers could do better
than they do:-). Among compiler writers, there is general
agreement that C and C++ are bitches to optimize, because of the
aliasing, but that doesn't mean that with a bit more work...
(Among tool writers, C and C++ aren't very popular either,
because of the preprocessor. And users don't like all the
undefined behavior. All in all, C++ is a horrible language.
The only problem is that the others are even worse.)
We do have some programs that, at least under certain
conditions, are faster when using vectors --- such is the
case with vectors of vectors, when the dimension of the
rows is not a power of 2 --- for C arrays, a "non-trivial"
multiplication is required, whereas for vectors of vectors,
two dereferences and a trivial multiplication (a two-bit
shift) does it (and does it faster, at least for the one
test that I did a while ago --- vector of vectors was
almost twice as fast as the C-arrays version.
Interesting. The cost of the multiplication is high enough to
offset the loss of locality and the extra indirection. Given
the importance of locality and the cost of memory accesses on
modern machines, I would not have expected this.
Given your results, I would not be too surprised if on some
machines, the C style array was also faster for "simple"
multiplications---things like a power of 2 +/- 1, which can
still be done by a shift and an add/sub., but slower for more
"exotic" values.
That was the case when I did the test (which was on Linux,
with g++, not sure which version, but maybe some time around
version 3.2 or 3.3, on an Athlon XP processor).
C arrays of the form a[N][32] or [N][64], etc. were faster
(don't remember by how much), but precisely, something of
the form a[N][100] was close to twice slower than
vector< vector<T> > a (N, 100).
For random access, or for nested loops? (A good compiler should
be able to "unnest" the loops, and access sequentially, with a C
style array. Provided it sees the array, and not just a pointer
to the first element.)
Also, how big was N? And did the results continue to hold when
the first dimension got very big. I would imagine (but I'm
really just guessing) that locality would kick in, and slow up
std::vector, if when the second dimension gets into the
thousands or tens of thousands.
A couple of quick tests on my machine (Sun Sparc, but using g++
4.1.0) gave some surprising results. First, as expected,
running through the values in order was a lot faster (about five
times) than inverting the rows and the columns. Other than
that, strangely enough, using powers of 2 (1024x1024) was
significantly slower than using a power of 10
(1000x1000)---given that the machine I'm on doesn't have
hardware multiply and divide, I really cannot explain it.
std::vector, of course, doesn't display this difference; it's a
lot faster than C-style arrays for 1024x1024, and significantly
slower for 1000x1000. Wierd. (A quick look at the generated
code shows that g++ is maintaining both a pointer and an index
in the inner loop, thus avoiding any multiplication there. With
close to 32 registers to play with, there are obviously
optimization opportunities that you don't have on an Intel
architecture. But that still doesn't explain why the power of 2
dimensionned arrays were so slow.)
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orientie objet/
Beratung in objektorientierter Datenverarbeitung
9 place Simard, 78210 St.-Cyr-l'Icole, France, +33 (0)1 30 23 00 34
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]