Do I really have to use an array?

[mike3]

Hi.

I can't believe I may have to use an array here.

I've got this bignum package I was making in C++ for a fractal
generator, and tried an approach that was suggested to me here a while
back, about using a "stack of vectors" instead of a static array.

Anyway, I put the suggestion into effect, and it seems the routine
that uses the stack of vectors (an in-place multiplication routine) is
real slow -- too slow for my liking. The out-of-place multiplication
is like twice as fast. What gives? Do I really have to use an evil
array on the stack? (in my code it would be something like "Digit
tmpBuf[2*MAX_PRECISION]".) I don't think so since it was said the
stack-of-vectors approach can be at least as fast as the array.

You can get the relevant code snippets here if you need to see them:
http://www.mediafire.com/?51qszh1cv2j

[Daniel T.]

mike3 <mi******@yahoo.comwrote:

I can't believe I may have to use an array here.

I've got this bignum package I was making in C++ for a fractal
generator, and tried an approach that was suggested to me here a while
back, about using a "stack of vectors" instead of a static array.

Anyway, I put the suggestion into effect, and it seems the routine
that uses the stack of vectors (an in-place multiplication routine) is
real slow -- too slow for my liking. The out-of-place multiplication
is like twice as fast. What gives? Do I really have to use an evil
array on the stack? (in my code it would be something like "Digit
tmpBuf[2*MAX_PRECISION]".) I don't think so since it was said the
stack-of-vectors approach can be at least as fast as the array.

You can get the relevant code snippets here if you need to see them:
http://www.mediafire.com/?51qszh1cv2j

Did you turn on optimization? In some systems vector does a whole bunch
of error checking unless full optimizations have been turned on.

[mike3]

On Jan 24, 5:41 am, "Daniel T." <[e-mail]:

mike3 <[e-mail]:

I can't believe I may have to use an array here.

I've got this bignum package I was making in C++ for a fractal
generator, and tried an approach that was suggested to me here a while
back, about using a "stack of vectors" instead of a static array.

Anyway, I put the suggestion into effect, and it seems the routine
that uses the stack of vectors (an in-place multiplication routine) is
real slow -- too slow for my liking. The out-of-place multiplication
is like twice as fast. What gives? Do I really have to use an evil
array on the stack? (in my code it would be something like "Digit
tmpBuf[2*MAX_PRECISION]".) I don't think so since it was said the
stack-of-vectors approach can be at least as fast as the array.

You can get the relevant code snippets here if you need to see them:
http://www.mediafire.com/?51qszh1cv2j

Did you turn on optimization? In some systems vector does a whole bunch
of error checking unless full optimizations have been turned on.

Yes, I did. It doesn't seem to be the vector -- the out-of-place
routine
uses vectors as well, and it performs twice as fast as the in-place
one,
at least on my machine. It seems to have to do with that stack
thingy.

[Jerry Coffin]

In article <1d5185f0-b105-4201-9c52-
b2**********@v46g2000hsv.googlegroups.com>, mi******@yahoo.com says...

[ ... ]

Yes, I did. It doesn't seem to be the vector -- the out-of-place
routine uses vectors as well, and it performs twice as fast as the
in-place one, at least on my machine. It seems to have to do with
that stack thingy.

It would help tremendously if you posted (here or to the web site) code
that could be compiled and included (at least) the routine with which
you're having a problem.

--
Later,
Jerry.

The universe is a figment of its own imagination.

[mike3]

On Jan 24, 9:15*pm, Jerry Coffin <[e-mail]:

In article <1d5185f0-b105-4201-9c52-
[e-mail]>, [e-mail] says...

[ ... ]

Yes, I did. It doesn't seem to be the vector -- the out-of-place
routine uses vectors as well, and it performs twice as fast as the
in-place one, at least on my machine. It seems to have to do with
that stack thingy.

It would help tremendously if you posted (here or to the web site) code
that could be compiled and included (at least) the routine with which
you're having a problem.

Here's a version that will compile and run on a Windows
system with Microsoft's Visual C++ compiler (it can be
easily modified to compile and run on other systems, by
the way):

http://www.mediafire.com/?cznivxxynnr

And it has tests added in that run the routines in
question. The results on my machine were:

---
Test 1: 100M out-of-place multiplications @ 128 bits...done.
CPU time: 14.078 second(s).
Wall time: 14 second(s).
Final result: d08f168e 0b3a70a4 edb740a8 321bd2f1
Expected: d08f168e 0b3a70a4 edb740a8 321bd2f1

Test 2: 100M in-place multiplications @ 128 bits...done.
CPU time: 29.547 second(s).
Wall time: 30 second(s).
Final result: 39adced5 f7724919 3d983ab3 358522c1
Expected: 39adced5 f7724919 3d983ab3 358522c1
---

[Jerry Coffin]

In article <74ca36c7-30fc-4d42-86ca-0e4f243161a6
@n22g2000prh.googlegroups.com>, mi******@yahoo.com says...

[ ... ]

That's what the point of the vector stack was: to avoid having to keep
creating vectors. It would set up a pile of them that could then be
popped off as needed. Once there's enough for all the threads, no
more are created. They're just pushed/popped on/off the stack.

The vector stack probably isn't doing much good. In fact, it's probably
harmful.

The problem is that vector (like other standard containers) is value-
based. When you push something on the stack, it does NOT put the
original item on the stack. Rather, it creates a _copy_ of the value on
the stack. Likewise, when you pop something off of the stack, what you
get is a copy of what was on the stack. After the copy is made, the one
what was on the stack gets destroyed.

IOW, when you finish using a vector, you really ARE destroying it (just
what you wanted to avoid) AND you're making a copy of its (now mostly
useless) contents. When you need a vector again, you don't just create
an empty one and use it -- instead, create a copy of an existing on with
useless contents, then destroy that existing useless one, then (more
likely than not) resize its content to fit what you currently need.

C++ 0x will allow you to get what you want -- it has rvalue references
and move constructors, that allow you to actually move the original
object when you put it on the stack and again when you pop it off the
stack.

For now, you can probably get (sort of) the same effect by using some
sort of reference-counted wrapper, to avoid creating and destroying
vectors every time you push/pop them. Right now, I'd guess your attempt
at optimization is really a pessimization; this modification should at
least get you back to neutral (i.e. it should at least be as fast as
really simple-minded code would have been).

Looking over your code, I'd also advise restructuring your stack a bit.
Specifically, instead of sharing a single stack between all threads, I'd
create a separate stack for each thread. Profiling your code, it's
currently spending about 10% of its time entering and leaving critical
sections, which would be avoided by creating a stack per thread.

--
Later,
Jerry.

The universe is a figment of its own imagination.

[John Scheldroup]

"mike3" <mi******@yahoo.comwrote in message news:a0**********************************@i12g2000 prf.googlegroups.com...
On Jan 26, 3:00 pm, "John Scheldroup" <[e-mail]:

"mike3" <[e-mail] in messagenews:c3**********************************@s 19g2000prg.googlegroups.com...

On Jan 26, 12:39 pm, "John Scheldroup" <[e-mail]>
wrote:

"mike3" <[e-mail] in messagenews:40**********************************@d 70g2000hsb.googlegroups.com...
On Jan 26, 12:15 am, Jerry Coffin <[e-mail]:
In article <74ca36c7-30fc-4d42-86ca-0e4f243161a6
@n22g2000prh.googlegroups.com>, [e-mail] says...

[ ... ]

That's what the point of the vector stack was: to avoid having to keep
creating vectors. It would set up a pile of them that could then be
popped off as needed. Once there's enough for all the threads, no
more are created. They're just pushed/popped on/off the stack.

The vector stack probably isn't doing much good. In fact, it's probably
harmful.

If you notice how it's coded, the stack contains a list of _pointers_
to preallocated vectors.

Would there be a Template parameter defined in its list to see
what types are preallocated. The compiler can preinstall the
type first before the stack allocates. I could be wrong but the other
way *what type of parameter* do we have before FGWDStack()
initializes. Templates.. those curious creatures...

<snip>

I've noticed you got rid of the vector of _pointers_ and replaced it
with a vector of objects. But then you run into all those problems
with copying objects -- why not keep the vector of _pointers_?

If objects are being copied they are not getting reused,
likely such the result of to many details to early on

>Like what, exactly? What sort of details would that be?

Its a template not an algorithm

>><snip>

>Does all that stuff like hiding pointers impact the
performance any? Remember, I need every last ounce of
performance I can get out of this.

I don't recall your saying such.. why use templates
anyhow ? If not what kind are the reusability issues
that lead you to employ them ?

John

[mike3]

On Jan 26, 5:59*pm, "John Scheldroup" <[e-mail]:

"mike3" <[e-mail] in messagenews:a0**********************************@i 12g2000prf.googlegroups.com...

On Jan 26, 3:00 pm, "John Scheldroup" <[e-mail]:

"mike3" <[e-mail] in messagenews:c3**********************************@s 19g2000prg.googlegroups.com...

On Jan 26, 12:39 pm, "John Scheldroup" <[e-mail]>
wrote:
>"mike3" <[e-mail] in messagenews:40**********************************@d 70g2000hsb.googlegroups.com...
On Jan 26, 12:15 am, Jerry Coffin <[e-mail]:
>In article <74ca36c7-30fc-4d42-86ca-0e4f243161a6
>@n22g2000prh.googlegroups.com>, [e-mail] says...

>[ ... ]

That's what the point of the vector stack was: to avoid having to keep
creating vectors. It would set up a pile of them that could thenbe
popped off as needed. Once there's enough for all the threads, no
more are created. They're just pushed/popped on/off the stack.

>The vector stack probably isn't doing much good. In fact, it's probably
>harmful.

If you notice how it's coded, the stack contains a list of _pointers_
to preallocated vectors.

>Would there be a Template parameter defined in its list to see
>what types are preallocated. The compiler can preinstall the
>type first before the stack allocates. I could be wrong but the other
>way *what type of parameter* do we have before FGWDStack()
>initializes. Templates.. those curious creatures...

<snip>

I've noticed you got rid of the vector of _pointers_ and replaced it
with a vector of objects. But then you run into all those problems
with copying objects -- why not keep the vector of _pointers_?

If objects are being copied they are not getting reused,
likely such the result of to many details to early on

Like what, exactly? What sort of details would that be?

Its a template not an algorithm

><snip>

Does all that stuff like hiding pointers impact the
performance any? Remember, I need every last ounce of
performance I can get out of this.

I don't recall your saying such.. *why use templates
anyhow ? If not what kind are the reusability issues
that lead you to employ them ?

I'm using templates because I might need stacks of other
types of buffers beside vectors of bignum digits.

[Jerry Coffin]

In article <MP************************@news.sunsite.dk>,
jc*****@taeus.com says...

[ ... ]

Func Func+Child Hit
Time % Time % Count Function
---------------------------------------------------------
380.550 5.3 7165.489 100.0 1 _main (rawdigit.obj)

This says that main executed for 380.550 milliseconds, which was 5.3
percent of the total time taken. Along with the other functions it
called, it took 7165.489 milliseconds, which was 100% of the total time
(as you'd expect for main). The name in the object file is _main, and
the object file it came from is rawdigit.obj.

Oops, sorry. I skipped over the hit count -- that's the number of times
the profiler saw this function called.

--
Later,
Jerry.

The universe is a figment of its own imagination.

[Jerry Coffin]

In article <5be30f55-e321-4ad8-9890-e2930e973674
@s27g2000prg.googlegroups.com>, mi******@yahoo.com says...

[ ... ]

Hmm. This makes a lot more sense and would be
quite a bit better than the stack -- it wouldn't
involve that mutex in there either.

I've finally had a chance to look at the code a bit more. I was looking
at MulInPlace:

void RawDigit::MulInPlace(const RawDigit &a)
{
/* Obtain a temporary buffer to hold the result. */
std::auto_ptr<RawDigittmpBuf(rdStack.Pop());
RawDigit *pTmpBuf=tmpBuf.get();

/* Make it big enough if it isn't already. */
pTmpBuf->Resize(length + a.length);

/* Do multiplication */
pTmpBuf->Mul(*this, a);

/* Copy result back */
Copy(*pTmpBuf);

/* Done! Save the buffer for future reuse. */
rdStack.Push(tmpBuf);
}

Since you don't need pTmpBuf's value after you copy it into the current
object, you can probably save a fair amount of time by swapping the two
vectors instead. Copying has linear complexity but swapping is constant
complexity.

--
Later,
Jerry.

The universe is a figment of its own imagination.

[mike3]

On Jan 27, 8:22 am, Jerry Coffin <[e-mail]:

In article <5be30f55-e321-4ad8-9890-e2930e973674
@s27g2000prg.googlegroups.com>, [e-mail] says...

[ ... ]

Hmm. This makes a lot more sense and would be
quite a bit better than the stack -- it wouldn't
involve that mutex in there either.

I've finally had a chance to look at the code a bit more. I was looking
at MulInPlace:

void RawDigit::MulInPlace(const RawDigit &a)
{
/* Obtain a temporary buffer to hold the result. */
std::auto_ptr<RawDigittmpBuf(rdStack.Pop());
RawDigit *pTmpBuf=tmpBuf.get();

/* Make it big enough if it isn't already. */
pTmpBuf->Resize(length + a.length);

/* Do multiplication */
pTmpBuf->Mul(*this, a);

/* Copy result back */
Copy(*pTmpBuf);

/* Done! Save the buffer for future reuse. */
rdStack.Push(tmpBuf);

}

Since you don't need pTmpBuf's value after you copy it into the current
object, you can probably save a fair amount of time by swapping the two
vectors instead. Copying has linear complexity but swapping is constant
complexity.

But a copy shouldn't take the same length as the whole multiplication,
as it does for the 128-bit numbers I tested.

Furthermore, doesn't a swap then though go and result in a potentially
shorter vector being brought on to the stack, which would then
have to be resized later to accomodate the full product on the next
multiplication, eating time?

Hmm. I noticed that I had made Mul() so it could produce a truncated
product, so we could just make the buffer on stack as large as the
result vector, and then no resize is needed... I'll give that a try
and see what happens.

[mike3]

On Jan 27, 12:53*pm, mike3 <[e-mail]:

On Jan 27, 8:22 am, Jerry Coffin <[e-mail]:

In article <5be30f55-e321-4ad8-9890-e2930e973674
@s27g2000prg.googlegroups.com>, [e-mail] says...

[ ... ]

Hmm. This makes a lot more sense and would be
quite a bit better than the stack -- it wouldn't
involve that mutex in there either.

I've finally had a chance to look at the code a bit more. I was looking
at MulInPlace:

void RawDigit::MulInPlace(const RawDigit &a)
{
* * /* Obtain a temporary buffer to hold the result. */
* * std::auto_ptr<RawDigittmpBuf(rdStack.Pop());
* * RawDigit *pTmpBuf=tmpBuf.get();

* * /* Make it big enough if it isn't already. */
* * pTmpBuf->Resize(length + a.length);

* * /* Do multiplication */
* * pTmpBuf->Mul(*this, a);

* * /* Copy result back */
* * Copy(*pTmpBuf);

* * /* Done! Save the buffer for future reuse. */
* * rdStack.Push(tmpBuf);

}

Since you don't need pTmpBuf's value after you copy it into the current
object, you can probably save a fair amount of time by swapping the two
vectors instead. Copying has linear complexity but swapping is constant
complexity.

But a copy shouldn't take the same length as the whole multiplication,
as it does for the 128-bit numbers I tested.

Furthermore, doesn't a swap then though go and result in a potentially
shorter vector being brought on to the stack, which would then
have to be resized later to accomodate the full product on the next
multiplication, eating time?

Hmm. I noticed that I had made Mul() so it could produce a truncated
product, so we could just make the buffer on stack as large as the
result vector, and then no resize is needed... I'll give that a try
and see what happens.

Anyway, I just went to the thread-local storage method.
It seems to be the winner in terms of performance, and
a lot cleaner than that goofy stack thing, which was
such an awful kludge.

[mike3]

On Jan 24, 10:11*am, Salt_Peter <[e-mail]:
<snip>

Measure the std::vector's performance when optimized. Your code uses
integer everywhere instead of std::size_t (or size_type) to track
length. So what you probably have is repeated conversions from integer
to unsigned (or unsigned long presumeably) and back.

I was using int instead of std::size_t becuase loops like
this, which are used in several routines, do not work:

---
std::size_t myLength(myVector.size());

for(std::size_t i(myLength-1);i>=0;i--)
{
... do something ...
}
---

"i" decreases down beyond zero. But with an int, ie.

---
int myLength(myVector.size());

for(int i(myLength-1);i>=0;i--)
{
... do something ...
}
---

it works fine.

Does that make any sense? It seems you've just got to have
a conversion somewhere.

Or is there a way to still use std::size_t without these
conversions???

[Sam]

mike3 writes:

On Jan 24, 10:11Â*am, Salt_Peter <[e-mail]:
<snip>

>Measure the std::vector's performance when optimized. Your code uses
integer everywhere instead of std::size_t (or size_type) to track
length. So what you probably have is repeated conversions from integer
to unsigned (or unsigned long presumeably) and back.

I was using int instead of std::size_t becuase loops like
this, which are used in several routines, do not work:

---
std::size_t myLength(myVector.size());

for(std::size_t i(myLength-1);i>=0;i--)

size_t is unsigned, so your >= 0 comparison always evaluates to true, since
decrementing a size_t of 0 wraps around to a huge positive value.

Or is there a way to still use std::size_t without these
conversions???

Yes. In most cases, you just need to use a construct of the form:

size_t i=myLength;

while (i 0)
{
--i;

// your code here
}
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (GNU/Linux)

iD8DBQBHno+5x9p3GYHlUOIRAjJFAJ9od6MZ8+wBd7GwGzWPuh rcg10ULQCeMKUj
IsS2gZ2S0vF3upZUqEKjuWE=
=dpzn
-----END PGP SIGNATURE-----

[mike3]

On Jan 28, 7:30*pm, Sam <[e-mail]:

*application_pgp-signature_part
1KDownload

mike3 writes:

On Jan 24, 10:11*am, Salt_Peter <[e-mail]:
<snip>

Measure the std::vector's performance when optimized. Your code uses
integer everywhere instead of std::size_t (or size_type) to track
length. So what you probably have is repeated conversions from integer
to unsigned (or unsigned long presumeably) and back.

I was using int instead of std::size_t becuase loops like
this, which are used in several routines, do not work:

---
std::size_t myLength(myVector.size());

for(std::size_t i(myLength-1);i>=0;i--)

size_t is unsigned, so your >= 0 comparison always evaluates to true, since
decrementing a size_t of 0 wraps around to a huge positive value.

And int is signed, so...

Or is there a way to still use std::size_t without these
conversions???

Yes. In most cases, you just need to use a construct of the form:

size_t i=myLength;

while (i 0)
{
* * --i;

* * // your code here

}

Alright, I'll use that then. Thanks for the answer.

[Daniel T.]

In article
<ce**********************************@s19g2000prg. googlegroups.com>,
mike3 <mi******@yahoo.comwrote:

On Jan 24, 10:11*am, Salt_Peter <[e-mail]:
<snip>

Measure the std::vector's performance when optimized. Your code uses
integer everywhere instead of std::size_t (or size_type) to track
length. So what you probably have is repeated conversions from integer
to unsigned (or unsigned long presumeably) and back.

I was using int instead of std::size_t becuase loops like
this, which are used in several routines, do not work:

---
std::size_t myLength(myVector.size());

for(std::size_t i(myLength-1);i>=0;i--)
{
... do something ...
}
---

"i" decreases down beyond zero. But with an int, ie.

---
int myLength(myVector.size());

for(int i(myLength-1);i>=0;i--)
{
... do something ...
}
---

it works fine.

Does that make any sense? It seems you've just got to have
a conversion somewhere.

Or is there a way to still use std::size_t without these
conversions???

Here is a different answer. Use iterators.

for ( vector<X>::reverse_iterator it = myVector.rbegin();
it != myVector.rend();
++it )
{
// do something
}

Because the above uses a reverse_iterator, you are stepping through the
vector backwards. You might also want to consider a functor:

struct LoopGuts : unary_function< X, void {
void operator()( const X& myX ) const {
// do something
}
};

then the loop would be:

for_each( myVector.rbegin(), myVector.rend(), LoopGuts() );

or...

void doSomething( const X& x ) {
// do something
}

then...

for_each( myVector.rbegin(), myVector.rend(), &doSomething );

[mike3]

On Jan 28, 8:24*pm, "Daniel T." <[e-mail]:
<snip>

Here is a different answer. Use iterators.

for ( vector<X>::reverse_iterator it = myVector.rbegin();
* *it != myVector.rend();
* *++it )
{
* *// do something

}

Because the above uses a reverse_iterator, you are stepping through the
vector backwards. You might also want to consider a functor:

struct LoopGuts : unary_function< X, void {
* *void operator()( const X& myX ) const {
* * * // do something
* *}

};

then the loop would be:

for_each( myVector.rbegin(), myVector.rend(), LoopGuts() );

or...

void doSomething( const X& x ) {
* *// do something

}

then...

for_each( myVector.rbegin(), myVector.rend(), &doSomething );

Is this just as fast as a simple for() loop over the vector?
I admit, it would shorten the code, but the indirection...

See, I need speed, and so I can't have too much
calling overhead in those tight loops or too much indirection.
The functions I use that do the operations in the inner loops
are inlined, removing the call overhead.

In that case, I'll just settle for the iterator.

[James Kanze]

On Jan 29, 2:46 am, mike3 <[e-mail]:

On Jan 24, 10:11 am, Salt_Peter <[e-mail]:
<snip>

Measure the std::vector's performance when optimized. Your
code uses integer everywhere instead of std::size_t (or
size_type) to track length. So what you probably have is
repeated conversions from integer to unsigned (or unsigned
long presumeably) and back.

I was using int instead of std::size_t becuase loops like
this, which are used in several routines, do not work:

---
std::size_t myLength(myVector.size());

for(std::size_t i(myLength-1);i>=0;i--)
{
... do something ...}

Hmmm. I'd use a while loop here:

size_t i = myLength ;
while ( i != 0 ) {
-- i ;
// do something...
}

But no matter.

---

"i" decreases down beyond zero. But with an int, ie.

Not if i has type size_t, it doesn't:-). The loop as you just
wrote is an infinite loop. (Some compilers will warn about
this: something along the lines of "condition always true".)

---
int myLength(myVector.size());

for(int i(myLength-1);i>=0;i--)
{
... do something ...}

---

it works fine.

Unless the vector contains more than INT_MAX elements, of
course.

Does that make any sense? It seems you've just got to have
a conversion somewhere.

Or is there a way to still use std::size_t without these
conversions???

Or does it matter? Depending on the hardware, I think that
there will be two possible cases:

-- If size_t and int have the same size (usually the case on 32
bit machines), the conversion is purely a compile time
thing. No machine code is involved---you're just telling
the compiler to interpret the bytes differently. (Note that
at the machine code level, "words" are basically
untyped---type is determined by the instructions applied to
them, rather than by the data type.)

-- If size_t and int have different sizes, then the conversion
may cost an instruction or two. Or not, it depends. In all
of the cases I know of, when the sizes are different, int is
smaller than size_t, so once again, it may be just a
question of choosing instructions which only consider a part
of the size_t word. (That's the case on my 64 bit Sparc,
for example.) In other cases, however, (e.g. 16 bit 8086,
in model huge, but probably some modern architectures as
well), manipulating an int may be significantly faster, and
the conversion involves simply loading part of the size_t,
rather than the entire size_t, and is faster than
initializing a size_t variable would be.

In general, unless there are very strong reasons for not doing
so, you should use int in C++. The only motivation for possibly
using a size_t in your case would be to support vectors with
more than INT_MAX elements.

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, [phone]

[James Kanze]

On Jan 29, 5:10 am, mike3 <[e-mail]:

On Jan 28, 8:24 pm, "Daniel T." <[e-mail]:
<snip>

Here is a different answer. Use iterators.

for ( vector<X>::reverse_iterator it = myVector.rbegin();
it != myVector.rend();
++it )
{
// do something
}

Because the above uses a reverse_iterator, you are stepping
through the vector backwards. You might also want to
consider a functor:

struct LoopGuts : unary_function< X, void {
void operator()( const X& myX ) const {
// do something
}
};

then the loop would be:

for_each( myVector.rbegin(), myVector.rend(), LoopGuts() );

or...

void doSomething( const X& x ) {
// do something
}

then...

for_each( myVector.rbegin(), myVector.rend(), &doSomething );

Is this just as fast as a simple for() loop over the vector?

It might be, it might not be.

I admit, it would shorten the code, but the indirection...

I'm not sure what you mean about the indirection. On most
modern machines (and most not so modern machines as well---it
was definitely the case on the Interdata 8/32, ca. 1977),
something like:

for ( double* p = array ; p != array + N ; ++ p ) {
use *p
}

is faster than:

for ( int i = 0 ; i < N ; ++ i ) {
use array[ i ]
}

Or would be, except that the compiler translates the two into
exactly the same machine code (which corresponds to the first).

With regards to the for_each, a lot depends on how much the
compiler can inline. Measures I did some years back (four or
five, at least) suggest that with the compiler (g++) I had then,
using a reverse iterator (rather than a normal iterator and
decrementing) did have measurable runtime cost. Measures others
have made also suggest that using a pointer to a function,
rather than a functional object, can be expensive---with the
pointer to the function, the compiler wasn't able to inline the
function, and did generate an indirect function call, which
wrecked havoc with the pipeline on the machine in question.

Note, however, that those are specific measurements on specific
machines, using specific compilers, and probably aren't
representative of what you might find in your environment.

See, I need speed, and so I can't have too much
calling overhead in those tight loops or too much indirection.
The functions I use that do the operations in the inner loops
are inlined, removing the call overhead.

Use a functional object, and most compilers will be able to
inline it in the expansion of for_each. (The reason for this is
that each functional object is a different type, resulting in a
different specialization of for_each, i.e. a different function.
All of the pointers to functions have the same type, and are
handled by the same specialization of for_each---the optimizer
must do constant propagation into the inlined function to avoid
the indirect call. And since historically, people didn't use
pointers to functions if the function was a constant, older
compilers generally don't propagate such constants.)

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, [phone]

[Ralph D. Ungermann]

mike3 wrote:

I was using int instead of std::size_t becuase loops like
this, which are used in several routines, do not work:

std::size_t myLength(myVector.size());

for(std::size_t i(myLength-1);i>=0;i--)
{
... do something ...
}

Or is there a way to still use std::size_t without these
conversions???

for ( std::size_t i = myLength; i--; )
{
//...
}

-- ralph

[mike3]

On Feb 5, 7:27 am, "Ralph D. Ungermann" <[e-mail]>
wrote:
<snip>

for ( std::size_t i = myLength; i--; )
{
//...

}

So that actually stops after "i" goes to 0?

[James Kanze]

On Feb 5, 3:27 pm, "Ralph D. Ungermann" <[e-mail]>
wrote:

mike3 wrote:

I was using int instead of std::size_t becuase loops like
this, which are used in several routines, do not work:

std::size_t myLength(myVector.size());

for(std::size_t i(myLength-1);i>=0;i--)
{
... do something ...
}
Or is there a way to still use std::size_t without these
conversions???

for ( std::size_t i = myLength; i--; )
{
//...
}

Nice obfuscation.

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, [phone]

[Andrew Koenig]

"Alf P. Steinbach" <al***@start.nowrote in message
news:13*************@corp.supernews.com...

If you want the range myLenght-1 downto 0, inclusive, consider just

for( size_t i = myLength-1; i != size_t(-1); --i )

Cheers, & hth.,

I have to say that this example is too clever for my taste. I'd rather
write:

for (size_t i = myLength; i != 0; ) {
--i;

// whatever

}

One reason for my preference is that this technique works for bidirectional
iterators too:

for (list<T>::iterator it = myList.end(); it != myList.begin(); ) {
--it;

// whatever

}

whereas the "myLength-1" technique doesn't.

[Richard Herring]

In message
<f1**********************************@j78g2000hsd. googlegroups.com>,
James Kanze <ja*********@gmail.comwrites

>On Feb 5, 3:27 pm, "Ralph D. Ungermann" <[e-mail]>
wrote:

>mike3 wrote:

I was using int instead of std::size_t becuase loops like
this, which are used in several routines, do not work:

std::size_t myLength(myVector.size());

for(std::size_t i(myLength-1);i>=0;i--)
{
... do something ...
}
Or is there a way to still use std::size_t without these
conversions???

>for ( std::size_t i = myLength; i--; )
{
//...
}

Nice obfuscation.

That's another word for "idiom", isn't it? Guaranteed termination, loop
invariant exists throughout the block, ... what more do you want?

(And it doesn't use break ;-)

--
Richard Herring

[James Kanze]

On Feb 6, 6:34 pm, Richard Herring <ju**@[127.0.0.1]wrote:

In message
<[e-mail]>,
James Kanze <[e-mail]

for ( std::size_t i = myLength; i--; )
{
//...
}

Nice obfuscation.

That's another word for "idiom", isn't it? Guaranteed
termination, loop invariant exists throughout the block, ...
what more do you want?

Readability.

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, [phone]

[Richard Herring]

In message
<86**********************************@e4g2000hsg.g ooglegroups.com>,
James Kanze <ja*********@gmail.comwrites

>On Feb 6, 6:34 pm, Richard Herring <ju**@[127.0.0.1]wrote:

>In message
<[e-mail]>,
James Kanze <[e-mail]

>for ( std::size_t i = myLength; i--; )
{
//...
}

>Nice obfuscation.

>That's another word for "idiom", isn't it? Guaranteed
termination, loop invariant exists throughout the block, ...
what more do you want?

Readability.

If it's an idiom, you don't need to read it. Whether it's an idiom is
ultimately a question of style guides and/or familiarity. If you want to
say that all reverse-indexing (as opposed to hiding the reversal inside
reverse iterators) is inherently unidiomatic, I wouldn't argue.

--
Richard Herring

[Ralph D. Ungermann]

James Kanze wrote:

On Feb 5, 3:27 pm, "Ralph D. Ungermann" <[e-mail]>
wrote:

>for ( std::size_t i = myLength; i--; )

Nice obfuscation.

The postfix `trick' is uncommon, but not unknown. After a first
irritation, one ought to get it -- and remember, if repeated.

Though the decrement is more correctly placed at the beginning of the
loop, this does neither enhance readability nor safety (IMHO).

I've seen too much code, where each loop has been handcrafted: mixing
int and size_t, cast both ways, decrementing i on-the-fly at the first
occurrance in the loop body, and worse. You'll agree, that this causes
much more obfuscation.

So I use my way, whenever I have to: using uncommon syntax for uncommon
loops.

But as you mention it, I'm willing to change my style to:

for ( std::size_t i = myLength; i--; /*backward*/ )
-- ralph

[Richard Herring]

In message <fo**********@murphy.mediascape.de>, Ralph D. Ungermann
<us****@mloge-ungermann.dewrites

>James Kanze wrote:

>On Feb 5, 3:27 pm, "Ralph D. Ungermann" <[e-mail]>
wrote:

>>for ( std::size_t i = myLength; i--; )

Nice obfuscation.

The postfix `trick' is uncommon, but not unknown. After a first
irritation, one ought to get it -- and remember, if repeated.

Though the decrement is more correctly placed at the beginning of the
loop, this does neither enhance readability nor safety (IMHO).

I've seen too much code, where each loop has been handcrafted: mixing
int and size_t, cast both ways, decrementing i on-the-fly at the first
occurrance in the loop body, and worse. You'll agree, that this causes
much more obfuscation.

So I use my way, whenever I have to: using uncommon syntax for uncommon
loops.

But as you mention it, I'm willing to change my style to:

for ( std::size_t i = myLength; i--; /*backward*/ )

I was happy with this until yesterday, when a colleague pointed out that
the equivalent for iterators:

for (iterator i=container.end(); i-- != container.begin(); )
{
//...
}

doesn't work if the container is empty, whereas this is fine:

for (iterator i=container.end(); i != container.begin(); )
{
--i;
//...
}
--
Richard Herring