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." <danie...@earth link.netwrote:

mike3 <mike4...@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.

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**********@v4 6g2000hsv.googl egroups.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 <jcof...@taeus. comwrote:

In article <1d5185f0-b105-4201-9c52-
b2d03c0c0...@v4 6g2000hsv.googl egroups.com>, mike4...@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.

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.go oglegroups.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******** *************** ***********@i12 g2000prf.google groups.com...
On Jan 26, 3:00 pm, "John Scheldroup" <johnscheldr... @hush.comwrote:

"mike3" <mike4...@yahoo .comwrote in messagenews:c3* *************** *************** ***@s19g2000prg .googlegroups.c om...

On Jan 26, 12:39 pm, "John Scheldroup" <johnscheldr... @hush.com>
wrote:

"mike3" <mike4...@yahoo .comwrote in messagenews:40* *************** *************** ***@d70g2000hsb .googlegroups.c om...
On Jan 26, 12:15 am, Jerry Coffin <jcof...@taeus. comwrote:
In article <74ca36c7-30fc-4d42-86ca-0e4f243161a6
@n22g2000prh.go oglegroups.com> , mike4...@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.

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" <johnscheldr... @hush.comwrote:

"mike3" <mike4...@yahoo .comwrote in messagenews:a0* *************** *************** ***@i12g2000prf .googlegroups.c om...

On Jan 26, 3:00 pm, "John Scheldroup" <johnscheldr... @hush.comwrote:

"mike3" <mike4...@yahoo .comwrote in messagenews:c3* *************** *************** ***@s19g2000prg .googlegroups.c om...

On Jan 26, 12:39 pm, "John Scheldroup" <johnscheldr... @hush.com>
wrote:
>"mike3" <mike4...@yahoo .comwrote in messagenews:40* *************** *************** ***@d70g2000hsb .googlegroups.c om...
On Jan 26, 12:15 am, Jerry Coffin <jcof...@taeus. comwrote:
>In article <74ca36c7-30fc-4d42-86ca-0e4f243161a6
>@n22g2000prh.g ooglegroups.com >, mike4...@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 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************ ************@ne ws.sunsite.dk>,
jc*****@taeus.c om 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.go oglegroups.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::MulIn Place(const RawDigit &a)
{
/* Obtain a temporary buffer to hold the result. */
std::auto_ptr<R awDigittmpBuf(r dStack.Pop());
RawDigit *pTmpBuf=tmpBuf .get();

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

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

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

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

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.