Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Do I really have to use an array?

Reply
Thread Tools

Do I really have to use an array?

 
 
mike3
Guest
Posts: n/a
 
      01-24-2008
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
 
Reply With Quote
 
 
 
 
Daniel T.
Guest
Posts: n/a
 
      01-24-2008
mike3 <(E-Mail Removed)> wrote:

> 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.
 
Reply With Quote
 
 
 
 
Salt_Peter
Guest
Posts: n/a
 
      01-24-2008
On Jan 24, 4:52 am, mike3 <(E-Mail Removed)> wrote:
> 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
};

 
Reply With Quote
 
Erik Wikström
Guest
Posts: n/a
 
      01-24-2008
On 2008-01-24 13:41, Daniel T. wrote:
> mike3 <(E-Mail Removed)> wrote:
>
>> 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.

--
Erik Wikström
 
Reply With Quote
 
mike3
Guest
Posts: n/a
 
      01-24-2008
On Jan 24, 10:11 am, Salt_Peter <(E-Mail Removed)> wrote:
> On Jan 24, 4:52 am, mike3 <(E-Mail Removed)> wrote:
>
>
>
> > 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?
 
Reply With Quote
 
mike3
Guest
Posts: n/a
 
      01-24-2008
On Jan 24, 5:41 am, "Daniel T." <(E-Mail Removed)> wrote:
> mike3 <(E-Mail Removed)> wrote:
> > 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.
 
Reply With Quote
 
Salt_Peter
Guest
Posts: n/a
 
      01-25-2008
On Jan 24, 3:15 pm, mike3 <(E-Mail Removed)> wrote:
> On Jan 24, 10:11 am, Salt_Peter <(E-Mail Removed)> wrote:
>
>
>
> > On Jan 24, 4:52 am, mike3 <(E-Mail Removed)> wrote:

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

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


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?

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

>
> 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++.
 
Reply With Quote
 
mike3
Guest
Posts: n/a
 
      01-25-2008
On Jan 24, 5:38*pm, Salt_Peter <(E-Mail Removed)> wrote:
> On Jan 24, 3:15 pm, mike3 <(E-Mail Removed)> wrote:

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

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

 
Reply With Quote
 
Jerry Coffin
Guest
Posts: n/a
 
      01-25-2008
In article <1d5185f0-b105-4201-9c52-
http://www.velocityreviews.com/forums/(E-Mail Removed)>, (E-Mail Removed) 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.
 
Reply With Quote
 
mike3
Guest
Posts: n/a
 
      01-25-2008
On Jan 24, 9:15*pm, Jerry Coffin <(E-Mail Removed)> wrote:
> In article <1d5185f0-b105-4201-9c52-
> (E-Mail Removed)>, (E-Mail Removed) 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
---
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
What the...? Hash does not have a key it really should have! Joshua Muheim Ruby 5 08-11-2007 02:17 PM
OT : But help really really needed re: Domain Name selling, hosting etc. problem nc HTML 1 02-03-2005 07:24 PM
REALLY REALLY WERID PROBLEM!!!!pls take a look Amir ASP .Net 3 01-23-2004 06:01 PM
really really mysterious IE6 problem--secure site ultraviolet353 Computer Support 7 11-22-2003 07:56 PM
MR. ED REALLY, REALLY LOVES THE D60 !!! Annika1980 Digital Photography 9 10-28-2003 04:53 PM



Advertisments