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.]

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.

 

[Salt_Peter]

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

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. Since the vector
knows its length, why are you duplicating?
Your iterators should be declared in class as well, they are dependant
types.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

template< typename T >
class Container
{
std::vector< T > vt;
typedef typename std::vector< T >::iterator iterator;
public:
Container() { }
Container(const std::size_t sz, const T& t)
: vt(sz, t) { }
void push_back(const T& t)
{
vt.push_back(t);
}
iterator begin() { return vt.begin(); }
iterator end() { return vt.end(); }
std::size_t size() const { return vt.size(); }
// etc
};

 

[Erik Wikström]

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.

OT: In Visual Studio I think you have to do a bit more than just turn on
optimisations, look in the documentation for checked iterators.

 

[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

Measure the std::vector's performance when optimized.

Optimizations were set to maximum for the test.

Your code uses
integer everywhere instead of std::size_t (or size_type) to track
length.

Could these conversions actually cost as much as the entire
multiplication
loop?

So what you probably have is repeated conversions from integer
to unsigned (or unsigned long presumeably) and back. Since the vector
knows its length, why are you duplicating?

First of all, I need to know what you mean by "duplicating" the
length.
You mean having a separate length parameter in the RawDigit class like
I do?
Can one be sure the vector will be *exactly* a given length and won't
get bigger on you unless you tell it to (ie. using push_back(),
resize(), etc.)?

Your iterators should be declared in class as well, they are dependant
types.

What's the point of doing that, anyway?

 

[mike3]

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.

 

[Salt_Peter]

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

Measure the std::vector's performance when optimized.

Optimizations were set to maximum for the test.

Your code uses
integer everywhere instead of std::size_t (or size_type) to track
length.

Could these conversions actually cost as much as the entire
multiplication
loop?

Which loop? Does a conversion cost nothing? no.
I'm trying to figure out how you are 'managing' your elements, i see a
std::vector of pointers and std::auto_ptrs that are being released()
to transfer ownership. Thats very strange to say the least.
Any reason you aren't using boost::shared_ptr? Those are copyable and
assigneable.
Any chance you might show a shortened, simplified version of what you
are doing?

First of all, I need to know what you mean by "duplicating" the
length.
You mean having a separate length parameter in the RawDigit class like
I do?
Can one be sure the vector will be *exactly* a given length and won't
get bigger on you unless you tell it to (ie. using push_back(),
resize(), etc.)?

The vector's size() member function will return the number of elements
stored. Not its capacity or reserve.
Since this will happen whether you use it or not, why duplicate what
is already being done? Why dilly-dally with having to compute /
maintain something that a std::vector does impeccably?

What's the point of doing that, anyway?

An iterator is a type, its dependant on the type the vector is
storing.
So std::vector<int>::iterator doesn't have the same type as
std::vector<double>::iterator.
If your compiler thinks otherwise, its non-comformant, broken or you
aren't coding in C++.

 

[mike3]

On Jan 24, 3:15 pm, mike3 <[email protected]> wrote:

Which loop?

The loop that multiplies the digits together to get the result. Didn't
you see it in the code?

Does a conversion cost nothing? no.

No, but the cost should be miniscule compared to the arithmetic
operation itself. It couldn't possibly account for a 2x
difference in performance between the two routines, could it?
Also, changing it all to size_t, plus abandoning the "length" element
of the RawDigit type did _nothing_ to improve performance, at least
not by any noticeable level. This just confirms my original suspicion
that it's that vecstack that's the problem. What to do about it?

I'm trying to figure out how you are 'managing' your elements, i see a
std::vector of pointers and std::auto_ptrs that are being released()
to transfer ownership. Thats very strange to say the least.
Any reason you aren't using boost::shared_ptr? Those are copyable and
assigneable.
Any chance you might show a shortened, simplified version of what you
are doing?

The stack of vectors approach was suggested to me by (I think) a
poster here with a pseudonym of "werasm". The point is to set up
buffers that multiple threads of the program can use, as this is
supposed to be used in a multithreaded environment, and without having
to reallocate the memory for them all the time (which costs quite a
bit of time and hence its not acceptable for something that needs to
be fast). So what the stack does is store a certain amount of vectors,
then when a thread needs one, it pops it off and starts using it. When
it's done, it pushes it back on. The number of buffers on the stack
should be at least the number of running threads.

The vector's size() member function will return the number of elements
stored. Not its capacity or reserve.
Since this will happen whether you use it or not, why duplicate what
is already being done? Why dilly-dally with having to compute /
maintain something that a std::vector does impeccably?

So then if I create an std::vector of length 4 (ex. "DigitVector
v(4)"), assign it all zeroes, then it will have size 4? Just chcked
it, it does seem to work. Mmm.

An iterator is a type, its dependant on the type the vector is
storing.
So std::vector<int>::iterator doesn't have the same type as
std::vector<double>::iterator.
If your compiler thinks otherwise, its non-comformant, broken or you
aren't coding in C++.

Um, I mean, what's the point of declaring the iterator in-
class?

 

[Jerry Coffin]

[ ... ]

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.

 

[mike3]

[ ... ]

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
---

 

[James Kanze]

Which loop? Does a conversion cost nothing? no.

It depends on which conversion. Conversions between integer
types, or between pointers, as long as no multiple inheritance
or virtual base classes are involved, typically have no runtime
cost.

I'm trying to figure out how you are 'managing' your elements,
i see a std::vector of pointers and std::auto_ptrs that are
being released() to transfer ownership. Thats very strange to
say the least. Any reason you aren't using boost::shared_ptr?
Those are copyable and assignable.

But copying them and assigning them has a very definite runtime
penalty. Not usually an issue, but since he's addressing a
performance problem.

There is one case where std::vector is significantly slower than
an array: creation and destruction. If he's creating a lot of
small, short lived vectors, that could slow things down. As an
alternative to array, he might want to look into boost::array.

 

[mike3]

It depends on which conversion. Conversions between integer
types, or between pointers, as long as no multiple inheritance
or virtual base classes are involved, typically have no runtime
cost.


But copying them and assigning them has a very definite runtime
penalty. Not usually an issue, but since he's addressing a
performance problem.

There is one case where std::vector is significantly slower than
an array: creation and destruction. If he's creating a lot of
small, short livedvectors, that couldslowthings down. As an
alternative to array, he might want to look into boost::array.

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.

 

[Jerry Coffin]

[ ... ]

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.

 

[mike3]

[ ... ]

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.

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.

I push _pointers_ on the stack, not the vector objects themselves. The
vectors are made using a "new", then the resulting pointer is filed
away
on the stack. When I need it, I pop off the pointer, use it, then
stick it back on.

Should I just use raw pointers instead of auto_ptr?

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.

What about though if you allocate a vector with new, push the
_pointer_
to that vector onto the stack, then pop that _pointer_ off when you
need
it, resize the vector if it's not big enough, use it, then finally
push that _pointer_ back on?

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.

But how do I assign those stacks to each thread without passing a
parameter
to the bignum routines (which looks bad and is outright impossible
when
using overloaded operators!)?

Hey, if I can do this, then why not just assign vector buffers to each
thread,
directly, and forget about stacks altogether? That was the whole
problem
the stack was originally intended to solve in the first place. If
there
is an alternative method to tackle this problem then I'll just toss
the whole
stack idea altogether and go for it!

PS. What did your profiling say the rest of the time was spent on?

 

[James Kanze]

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.

I'd have to see the code, but if the stack itself is based on
the STL, you may simply have some deep copies in there. Which
is likely to be even slower than constructing a new vector each
time around.

It's just a hunch, of course. What you really should do is see
where the profiler says you're spending your time. If it's in
the allocator of vector, then there's probably something you
can do about it. If not, I doubt that the problem is vector
itself.

 

[John Scheldroup]

[ ... ]

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...

#include <vector>
#include <stdexcept>

template <class T, class U = std::vector<T> >
class FG3DStack {
private:
U stack; // stack of elements
// std::vector<T *> stack;
public:
void push_back(T const&); // push element
void pop_back(); // pop element
T reset() const; // return top element
bool empty() const { // return whether the stack is empty
return stack.empty();
}
};

template <class T, class U>
void FG3DStack<T,U>:ush_back (T const& stack)
{
stack.push_back(elem); // append copy of passed elem
}

template <class T, class U>
void FG3DStack<T,U>:op_back ()
{
if (stack.empty()) {
throw std:ut_of_range("Stack<>:op_back(): empty stack");
}
stack.pop_back(); // remove last element
}

template <class T, class U>
T FG3DStack<T,U>::reset () const
{
if (stack.empty()) {
throw std:ut_of_range("Stack<>::reset(): empty stack");
}
return stack.back(); // return copy of last element
}

 

[mike3]

[ ... ]
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_?

Furthermore, is there a way to get rid of the stack entirely, and
just assign buffers to each thread of the program?

 

[mike3]

I'd have to see the code, but if the stack itself is based on
the STL, you may simply have some deep copies in there.  Which
is likely to be even slower than constructing a new vector each
time around.

It's just a hunch, of course.  What you really should do is see
where the profiler says you're spending your time.  If it's in
the allocator of vector, then there's probably something you
can do about it.  If not, I doubt that the problem is vector
itself.

Well, links to the code have been provided in this thread.
You can download and see it if you want.

Anyway, what would be a good free profiler I could use?

 

[John Scheldroup]

[ ... ]

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

A vector of objects should form an incomplete picture that when
sliced into individual pieces might be a thing for change but with
unlimited identities. A single identity alone can come to form
one area of the picture to encapsulate then contain other actions.
A vector of objects may collect to act on other pieces in the structure,
those which have unique shape or size, but no single element can know
the details of the next or which piece or element it falls into.
Relevant abstractions depend upon all the elements that contain the
irrelevant details. A vector of elements when derived by their uniqueness
are ubiquitous and unknown, but they do share irrelevant properties so
together can define its relevant shape. Details of location for such
things like pointers or directions should remain hidden.

Furthermore, is there a way to get rid of the stack entirely, and
just assign buffers to each thread of the program?

A single object can grow get more properties of its children..
polymorphic where those children join with the mothership,
but eventually all will leave the nest.

John

 

[mike3]

[ ... ]
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?

A vector of objects should form an incomplete picture that when
sliced into individual pieces might be a thing for change but with
unlimited identities. A single identity alone can come to form
one area of the picture to encapsulate then contain other actions.
A vector of objects may collect to act on other pieces in the structure,
those which have unique shape or size, but no single element can know
the details of the next or which piece or element it falls into.
Relevant abstractions depend upon all the elements that contain the
irrelevant details. A vector of elements when derived by their uniqueness
are ubiquitous and unknown, but they do share irrelevant properties so
together can define its relevant shape. Details of location for such
things like pointers or directions should remain hidden.

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.