Whoa, are reverse iterators slower and should I really care?

This is a discussion on Whoa, are reverse iterators slower and should I really care? within the C++ Programming forums, part of the General Programming Boards category; Hello All, I have some code where I need to iterate backwards through a vector. I thought about writing this ...

  1. #1
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    1,276

    Whoa, are reverse iterators slower and should I really care?

    Hello All,

    I have some code where I need to iterate backwards through a vector.

    I thought about writing this with random access iterators and just subtracting one until I got to the beginning but then I looked it up and there are STL implemented reverse iterators so I just used those and they work perfectly for my needs.

    But I looked up if they were slower and the google searches seem to indicate yes.

    Granted, I'm only reverse iterating through like 4 elements at a maximum but I'm doing it quite a bit so I'm just curious, should I even care about using reverse iterators just long as they do the job properly?

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    If it creates a real bottleneck, then rewrite if you must. Otherwise, why bother? On a side note, many implementations of the STL have shown to suffer performance-wise in a number of areas. This can be quite frustrating, for example, when using vectors in place of arrays for high-performance applications; often the internal element access is constrained by an out-of-bounds check and usually operator [] isn't even made to be an inline function call. That said, if nothing else the STL does at least give us the ability to work out our ideas in an efficient manner, so it isn't all for naught either...
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  3. #3
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    1,276
    Gah, that is sooooo not what I wanted to hear. I love the STL and I'm convinced that there's no set of C++ programmers superior to them. Well, my code works and it's A LOT faster than it used to be anyway.

    I try to follow the mantra that if you try to over-optimize like this then you're a bad programmer because more often than not, a superior algorithm using slower containers is faster than a slow algorithm using faster containers. It's like doing something intelligently in a slightly slower way vs doing something stupid in a faster way.

    Oh well. I'll look into it but I don't think reverse iterators will be an issue.

  4. #4
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,523
    C++ (\STL) containers are generally associated with a set of algorithms, though.
    So, be careful when choosing your type of container.
    The differences are often significant in terms of complexity.

    For example, std::map implements some sort of balanced tree and std::unordered_map acts like a hash table.
    Manasij Mukherjee | gcc-4.9.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  5. #5
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    1,276
    What was it, I'm using these reverse iterators to add nodes from a graph to a stack for iterative traversal. My real code looks like this :
    Code:
    void search_tree(tree *root, particle *p, vector<tree*> & leaves) {
    
    
       set<tree*> visited;
    
    
       stack<tree*> traversal;
       traversal.push(root);
    
    
       while (!traversal.empty()) {
    
    
          tree *curr = traversal.top();
    
    
          if (!visited.insert(curr).second) {
    
    
             traversal.pop();
             continue;
          }
    
    
          if (curr->del == 0) {
    
    
             if (inside_tetra(curr->t, p) == -1) {
    
    
                traversal.pop();
                continue;
             }
    
    
             if (curr->children.empty()) {
    
    
                leaves.push_back(curr);
                traversal.pop();
                continue;
             } else {
    
    
                //for (auto it = curr->children.end(); it < curr->children.end(); ++it)
                   //traversal.push(*it);
    
    
                for (auto it = curr->children.crbegin(); it != curr->children.crend(); ++it)
                   traversal.push(*it);
    
    
                continue;
             }
          } else if (curr->del == 1) {
    
    
             //for (auto it = curr->children.begin(); it < curr->children.end(); ++it)
                //traversal.push(*it);
    
    
             for (auto it = curr->children.crbegin(); it != curr->children.crend(); ++it)
                traversal.push(*it);
    
    
             continue;
          }
       }
    
    
       return;
    }
    I only decided to add the children in reverse order because the way my code works, the way in which children are processed matters for the output and I was trying to make sure my iterative solution matches exactly to my recursive implementation which I've been using as a reference. The outputs match though. I was just trying to optimize the code.

  6. #6
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,523
    The reverse loop looks suspicious to me.
    For a DFS, the correct order should not need a reverse loop.

    Are you sure your recursive solution isn't searching the subtrees recursively out of order?
    Manasij Mukherjee | gcc-4.9.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  7. #7
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    1,276
    It needs to be in reverse because I'm using a stack which is last in, first out. So when I add the elements in the same order my recursive implementation searches, I need to put them on the stack in reverse order, if that makes sense.

    Basically, with my graph, each node stores its children in a vector. My recursive implementation started from the beginning to the end. But when I use a stack and I push() elements in that order, it starts with the last child first so I push() the elements in reverse order so the first child is pop'd first.

    The thing is, my code is triangulating points in space and does subsequent repairs. It is order sensitive and I was just trying to maintain consistency with previous incarnations even though it'd technically be irrelevant, mathematically.

    I tested the different orders using both small and large point sets and they were largely similar though.

  8. #8
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,523
    Quote Originally Posted by MutantJohn View Post
    It needs to be in reverse because I'm using a stack which is last in, first out. So when I add the elements in the same order my recursive implementation searches, I need to put them on the stack in reverse order, if that makes sense.

    Basically, with my graph, each node stores its children in a vector. My recursive implementation started from the beginning to the end. But when I use a stack and I push() elements in that order, it starts with the last child first so I push() the elements in reverse order so the first child is pop'd first.

    Well, the recursive version uses a stack as well (the call stack) in almost the exact same way.

    So, if your recursive function is giving output in an order reverse to the one you have with a normal loop, the recursive version has some bug.

    I have implemented a lot of graph search algorithms, but never seen one where you have to put elements in reverse order because you have a stack!
    A stack reverses it by its very nature, as you said.
    Manasij Mukherjee | gcc-4.9.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  9. #9
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    1,276
    It's not a bug. My recursive function goes from left to right of the vector of children. To emulate that behavior using an explicit stack like I have, to process the element I want first, it has to be put on the stack last and the element I want processed last has to be added first.

    Here, consider this original code which I think behaves as it should :
    Code:
    void search_tree(tree *root, particle *p, vector<tree*> & stack) {
    
    
       if (!visited.insert(root).second) {cout << "Duplicate\n"; return;}
    
    
    /* Is this a Delaunay node? */
    
    
       if (root->del == 0) { /* If no... */
    
    
    /* Is the point, p, outside the tetrahedron in the current node? */
    
    
          if (inside_tetra(root->t, p) == -1) { /* If yes... */
    
    
             return;
          }
    /* Is this node a leaf? */
    
    
          if (root->children.empty()) { /* If yes... */
    
    
    /* Is this leaf occupied? */
    
    
             //if (root->occ == 0) { /* If no... */
    
    
                root->occ = 1;
                stack.push_back(root);
    
    
                return;
    
    
             //} else if (root->occ == 1) /* If yes... */
                //return;
    
    
          } else { /* Else iterate over children */
     
             for (vector<tree*>::iterator it = root->children.begin(); it < root->children.end(); it++) {
    
    
                search_tree(*it, p, stack);
             }
          }      
    
    
       } else if (root->del == 1) { /* If yes... */
    
    
          for (vector<tree*>::iterator it = root->children.begin(); it < root->children.end(); it++) {
             search_tree(*it, p, stack);
          }
       }
    
    
       return;
    }
    The occ field is now rendered irrelevant due to the set visited scanning for duplicates so I commented it out. This is slightly old outdated code.
    Last edited by MutantJohn; 11-02-2013 at 08:41 PM.

  10. #10
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    1,276
    Okay, I'm sorry to spam this topic with my own jibber jabber but I know why the differences arose between using reverse and forward orders.

    You're right, my traversal can be done in any order.

    Basically, my code searches this tree for appropriate leaves and collects them. It then processes them in a totally separate function.

    But then I do conditional repairs and that's when the order really matters.

    So, repairing entries in different orders yields different results.

    To get a better idea of what I'm talking about, I'm mapping the insertion history of a tetrahedral mesh to a graph where each leaf is a valid element of the mesh. When I insert a point, I need to find all the leaves that contain the point. I collect those.

    I then insert that point into each collected leaf in a separate function. Here, the order still doesn't matter. The tetrahedra can be collected and fracture in any order.

    However and this is the key difference, the repair sequence for that new fracture set is order dependent. For example, I have 3 repair routines. 2-to-3, 3-to-2 and 4-to-4 where 2 tetrahedra are swapped for 3 good ones, etc.

    Here, the order really does matter because the way in which you repair a tetrahedron can cause subsequent repairs or it can prevent others so that's why I had to feed everything in reverse order so that way it would match the normal repair set I had before due to how the nature of the stack works.

    Sorry if this is too much but you got me thinking and I think I can justify the behavior of my code and considering that the differing outputs are small, even for something like 10,000 vertices being triangulated compared to 512 (both forwards and backwards yield relatively the same number of tetrahedra and repairs) so I think my code is performing properly. Feeding the elements in a reverse order is a completely arbitrary choice done by me, I guess, just to prove to myself that my code is behaving as it was when it was recursive.

    Granted, I'm using all of this for a Voronoi tessellation which should always be the same no matter how the Delauny triangulation was constructed so we'll see if I'm right or not. I'm fairly confident though. I really hope so. Sometimes there are situations where you can't do any repairs so we'll see...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Whoa, what happened?
    By webmaster in forum General Discussions
    Replies: 13
    Last Post: 01-10-2010, 11:29 AM
  2. Using reverse iterators in algorithms
    By 0rion in forum C++ Programming
    Replies: 1
    Last Post: 02-27-2006, 03:19 AM
  3. whoa....
    By camagitoe in forum C Programming
    Replies: 8
    Last Post: 03-21-2004, 09:29 PM
  4. Whoa!
    By gcn_zelda in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 09-07-2003, 07:55 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21