Do I really have to use an array?

Discussion in 'C++' started by mike3, Jan 24, 2008.

  1. mike3

    mike3 Guest

    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
     
    mike3, Jan 24, 2008
    #1
    1. Advertising

  2. mike3

    Daniel T. Guest

    mike3 <> 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.
     
    Daniel T., Jan 24, 2008
    #2
    1. Advertising

  3. mike3

    Salt_Peter Guest

    On Jan 24, 4:52 am, mike3 <> 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
    };
     
    Salt_Peter, Jan 24, 2008
    #3
  4. On 2008-01-24 13:41, Daniel T. wrote:
    > mike3 <> 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
     
    Erik Wikström, Jan 24, 2008
    #4
  5. mike3

    mike3 Guest

    On Jan 24, 10:11 am, Salt_Peter <> wrote:
    > On Jan 24, 4:52 am, mike3 <> 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?
     
    mike3, Jan 24, 2008
    #5
  6. mike3

    mike3 Guest

    On Jan 24, 5:41 am, "Daniel T." <> wrote:
    > mike3 <> 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.
     
    mike3, Jan 24, 2008
    #6
  7. mike3

    Salt_Peter Guest

    On Jan 24, 3:15 pm, mike3 <> wrote:
    > On Jan 24, 10:11 am, Salt_Peter <> wrote:
    >
    >
    >
    > > On Jan 24, 4:52 am, mike3 <> 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++.
     
    Salt_Peter, Jan 25, 2008
    #7
  8. mike3

    mike3 Guest

    On Jan 24, 5:38 pm, Salt_Peter <> wrote:
    > On Jan 24, 3:15 pm, mike3 <> 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?
     
    mike3, Jan 25, 2008
    #8
  9. mike3

    Jerry Coffin Guest

    In article <1d5185f0-b105-4201-9c52-
    >, 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.
     
    Jerry Coffin, Jan 25, 2008
    #9
  10. mike3

    mike3 Guest

    On Jan 24, 9:15 pm, Jerry Coffin <> wrote:
    > In article <1d5185f0-b105-4201-9c52-
    > >, 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
    ---
     
    mike3, Jan 25, 2008
    #10
  11. mike3

    James Kanze Guest

    On Jan 25, 1:38 am, Salt_Peter <> wrote:
    > On Jan 24, 3:15 pm, mike3 <> wrote:


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


    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.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Jan 25, 2008
    #11
  12. mike3

    mike3 Guest

    On Jan 25, 6:41 am, James Kanze <> wrote:
    > On Jan 25, 1:38 am, Salt_Peter <> wrote:
    >
    > > On Jan 24, 3:15 pm, mike3 <> wrote:
    > > > > 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.

    >
    > 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 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.
     
    mike3, Jan 26, 2008
    #12
  13. mike3

    Jerry Coffin Guest

    In article <74ca36c7-30fc-4d42-86ca-0e4f243161a6
    @n22g2000prh.googlegroups.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.
     
    Jerry Coffin, Jan 26, 2008
    #13
  14. mike3

    mike3 Guest

    On Jan 26, 12:15 am, Jerry Coffin <> wrote:
    > In article <74ca36c7-30fc-4d42-86ca-0e4f243161a6
    > @n22g2000prh.googlegroups.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.

    > 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?
     
    mike3, Jan 26, 2008
    #14
  15. mike3

    James Kanze Guest

    On Jan 26, 4:18 am, mike3 <> wrote:
    > On Jan 25, 6:41 am, James Kanze <> wrote:
    > > On Jan 25, 1:38 am, Salt_Peter <> wrote:


    > > > On Jan 24, 3:15 pm, mike3 <> wrote:
    > > > > > 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.


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


    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.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Jan 26, 2008
    #15
  16. "mike3" <> wrote in message news:...
    > On Jan 26, 12:15 am, Jerry Coffin <> wrote:
    >> In article <74ca36c7-30fc-4d42-86ca-0e4f243161a6
    >> @n22g2000prh.googlegroups.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...

    #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>::push_back (T const& stack)
    {
    stack.push_back(elem); // append copy of passed elem
    }

    template <class T, class U>
    void FG3DStack<T,U>::pop_back ()
    {
    if (stack.empty()) {
    throw std::eek:ut_of_range("Stack<>::pop_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::eek:ut_of_range("Stack<>::reset(): empty stack");
    }
    return stack.back(); // return copy of last element
    }
     
    John Scheldroup, Jan 26, 2008
    #16
  17. mike3

    mike3 Guest

    On Jan 26, 12:39 pm, "John Scheldroup" <>
    wrote:
    > "mike3" <> wrote in messagenews:...
    > > On Jan 26, 12:15 am, Jerry Coffin <> wrote:
    > >> In article <74ca36c7-30fc-4d42-86ca-0e4f243161a6
    > >> @n22g2000prh.googlegroups.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_?

    Furthermore, is there a way to get rid of the stack entirely, and
    just assign buffers to each thread of the program?
     
    mike3, Jan 26, 2008
    #17
  18. mike3

    mike3 Guest

    On Jan 26, 4:13 am, James Kanze <> wrote:
    > On Jan 26, 4:18 am, mike3 <> wrote:
    >
    >
    >
    >
    >
    > > On Jan 25, 6:41 am, James Kanze <> wrote:
    > > > On Jan 25, 1:38 am, Salt_Peter <> wrote:
    > > > > On Jan 24, 3:15 pm, mike3 <> wrote:
    > > > > > > 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.
    > > > 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 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.

    >
    > 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?
     
    mike3, Jan 26, 2008
    #18
  19. "mike3" <> wrote in message news:...
    > On Jan 26, 12:39 pm, "John Scheldroup" <>
    > wrote:
    >> "mike3" <> wrote in messagenews:...
    >> > On Jan 26, 12:15 am, Jerry Coffin <> wrote:
    >> >> In article <74ca36c7-30fc-4d42-86ca-0e4f243161a6
    >> >> @n22g2000prh.googlegroups.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

    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
     
    John Scheldroup, Jan 26, 2008
    #19
  20. mike3

    mike3 Guest

    On Jan 26, 3:00 pm, "John Scheldroup" <> wrote:
    > "mike3" <> wrote in messagenews:...
    > > On Jan 26, 12:39 pm, "John Scheldroup" <>
    > > wrote:
    > >> "mike3" <> wrote in messagenews:...
    > >> > On Jan 26, 12:15 am, Jerry Coffin <> wrote:
    > >> >> In article <74ca36c7-30fc-4d42-86ca-0e4f243161a6
    > >> >> @n22g2000prh.googlegroups.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?

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

    > > 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.
    >
     
    mike3, Jan 27, 2008
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Amir
    Replies:
    3
    Views:
    621
  2. nc
    Replies:
    1
    Views:
    529
    nice.guy.nige
    Feb 3, 2005
  3. Replies:
    2
    Views:
    368
  4. Jeannie
    Replies:
    15
    Views:
    916
    Jeannie
    Aug 30, 2005
  5. Joshua Muheim
    Replies:
    5
    Views:
    143
    Phlip
    Aug 11, 2007
Loading...

Share This Page