7

I've implemented two different algorithms which do essentially the same, check for visibility from one node to another in a tree of nodes, with the rules being simple - a node is only visible to another node if it precedes it along the same branch.

The first method goes down the tree from child to parent, skipping other potential children in the parent to get the tree indices for both nodes and uses some basic logic to determine if there is visibility. I decided to go for this one first because I already had the methods for the node indices which I needed for something else and I assumed it to be potentially faster.

bool isVisibleTo(Node * accessor) {
  QList<uint> accessedI = getIndex();
  QList<uint> accessorI = accessor->getIndex();
  if (accessedI.size() > accessorI.size()) {
    return false; 
  } else if (accessedI.size() == accessorI.size()) { 
    for (int i = 0; i < accessedI.size() - 1; ++i) {
      if (accessedI.at(i) != accessorI.at(i)) {
        return false; 
      }
    }
    if (accessedI.last() > accessorI.last()) {
      return false; 
    }
  }
  for (int i = 0; i < accessorI.size() - (accessorI.size() - accessedI.size()); ++i) {
    if (accessedI.at(i) > accessorI.at(i)) {
      return false; 
    }
  }
  return true;
}

The second one traverses the tree completely, every child down to the parent and so on, going through significantly more nodes and I can only assume memory pages and cache lines.

bool isVisibleTo2(Node * accessor) {
  Node * node = accessor;
  while (node) {
    if (node == this)
      return true;
    if (node->_parent) {
      uint i = node->_parent->_children.indexOf(node);
      while (i) {
        if (node->_parent->_children.at(--i) == this) {
          return true;
        }
      }
    }
    node = node->_parent;
  }
  return false;
}

I expected this to be the slower algorithm for big trees. But it turned out to be 10-20 times faster for small trees and as the tree size increased it stuck at a consistent 4x better in the last few test, the final of which took about 20 minutes and involved 10 million nodes in the tree (granted most of the time was the node allocation, the actual visibility check was several seconds).

So what are those performance figures due to? Considering that they provide identical results (checked that thoroughly - there is no work saved by the second method) and the first method involves fewer memory hops and I assume is much more cache friendly and also it can just check the depth and do a much shorter evaluation? Granted it does 2 traversals rather than one, but they are directly child to parent, skipping the rest of the children along the way. And yes, I do realize the second method does not need to go all the way down, but still...

Edit: I switched to -O3 compilation, but the figures did not change. I also tried to change the list of getIndex to a vector but it actually caused a substantial performance drop, since the indices need to be inserted in reverse order, e.g. prepended, which is very inefficient for a vector.

Edit 2: Did a quick test with a vector once again, this time I scrapped prepending and went of a regular insert and a reverse operation before returning, this made the vector solution slightly faster, from 8 times slower than the full traversal method to "only" 6 times slower. I suspected that the QList allocations might be the primary culprit for the low performance, but as it seems, there is something more to it.

20
  • 1
    Have you done a iteration count, or do you know the figures?
    – Stefan
    Nov 21, 2013 at 14:19
  • @Stefan - no I have not, it would be pointless at this point, when it is just a random abstract tree and does not reflect its actual future intended use. I will likely keep both methods to check it later on, but I am still curious about the performance at this point.
    – dtech
    Nov 21, 2013 at 14:23
  • What platform are you on? What compiler and options are you using? Nov 21, 2013 at 14:25
  • 2
    What does getIndex do?
    – klm123
    Nov 21, 2013 at 15:17
  • 2
    @ddriver That is what getIndex returns. What does it do? If getIndex spends 5 hours playing MP3 files, then returns that list, it will perform differently, but return the exact same thing. What does getIndex do? Does it by any chance uint i = node->_parent->_children.indexOf(node) or something equivalent? (source would be good) Nov 21, 2013 at 15:26

3 Answers 3

1

If I understand you correctly the getIndex() function, which you call in the first case does basically the same walk over all tree, which isVisibleTo2() does. But isVisibleTo1() has additional to getIndex operations, therefore it is slower.

12
  • No, getIndes takes a huge shortcut - it only goes from child to parent down to the root, while the second method goes through every child along the way.
    – dtech
    Nov 21, 2013 at 15:22
  • @ddriver, from which child to which parent? Could you just give a code of this and indexOf() functions?
    – klm123
    Nov 21, 2013 at 15:23
  • From the parameter Node to its parent down to its parent and so forth down to the root. getIndex skips all other siblings/children of its parent.
    – dtech
    Nov 21, 2013 at 15:25
  • @ddriver, I don't see any parameters at getIndex() function.
    – klm123
    Nov 21, 2013 at 15:28
  • The parameter of isVisibleTo. The difference is that getIndex goes fro Node -> parent -> parent -> parent until the root, while in isVisible2 it goes child -> child -> child -> until the parent, then switches the parent to a "child" context, down all the children to the next parent, all children to the next parent until the root.
    – dtech
    Nov 21, 2013 at 15:31
0

More info on the actual structure methods might change this but:

the other possible difference here is branch predictability

It seems like the second version might be more predictable than the first

0

That's easy. The problem with the first version is that you are calling getIndex() twice, which allocates memory. You can prove it or disprove it by posting your code for getIndex().

There is nothing 'logically slower' about not calling into an expensive function, by the way.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.