Re: Use of std::vector slower than arrays?
On Nov 13, 3:13 am, mike3 <mike4...@yahoo.com> wrote:
On Nov 12, 6:33 pm, "Daniel T." <danie...@earthlink.net> wrote:
mike3 <mike4...@yahoo.com> wrote:
The timings show the simple array-based approach takes 4
seconds for 100 million operations on 128 bit numbers on my
machine. The one with std::vector, though, takes a whopping
40-41 seconds -- a 10x performance hit! OUCH!!! Why is that?
Because you did not optimize the build and/or did not remove
the debug checks from std::vector. Different compilers do
things differently in this regard. Check your documentation.
Well, I tried it with maximum optimization on, and that
got the time down to a nice 6 seconds, however the array-
based routine went down to a smoking-fast 2, so there's still a
3x performance gain from array use. I tried turning off the
debug, but that didn't seem to change it.
I think you mentionned earlier that you use VC++. I seem to
recall hearing that you need to add some special options (/D
something) to turn off all of the debug checking; that just
setting the usual options for an optimized build aren't
sufficient. (No guarantee, but try /D_SECURE_SCL=0.)
Would it be a good idea then to write my own encapsulation of
the digit array, with both "safe", slow access modes and
"unsafe", fast ones (ie. you could request a pointer to the
digit array contained in the thing and use it like a C-style
array), then use this for the time-critical areas (the bignum
package) and std::vector for everything else? Or would that
just be silly and a waste of work?
It depends. If you want to be 100% of not loosing any cycles,
regardless of the library implementation, then obviously, you'll
have to write your own. Of course, if you want to be 100% sure
that the code is really optimized, you'll have to write your own
compiler as well, or maybe write the critical parts in
assembler. (In assembler, for example, you'll be able to access
the carry bit directly, rather than needing some additional, ad
hoc test.)
Most of the time, of course, it should be sufficient to just
figure out how to get the best performance from your compiler.
Depending on the quality of your library implementation, you may
not be able to get top performance from it, and end up writing
your own, but I doubt that this will be a problem with the VC++
implementation. Finding out how to turn off all of the internal
checking might be, however.
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34