Lazarus

Free Pascal => Beginners => Topic started by: Anonimista on September 21, 2019, 08:00:40 pm

Title: TTree depth-first traversal
Post by: Anonimista on September 21, 2019, 08:00:40 pm
I am trying to do a depth-first traversal of a TTree (gtree). The tree I am building looks like

Code: Pascal  [Select][+][-]
  1. {*
  2. *
  3. *         1
  4. *       /   \
  5. *      2     3
  6. *     / \   / \
  7. *    4   5 6   7
  8. *
  9. * }

When using tree.DepthFirstTraverse() I get:

Code: Pascal  [Select][+][-]
  1. 1 3 7 6 2 5 4

which is right to left, but I need it to be from left to right, ie

Code: Pascal  [Select][+][-]
  1. 1 2 4 5 3 6 7

edit: pre-order per this article

https://en.wikipedia.org/wiki/Tree_traversal#Depth-first_search

I kind of see why this happens from the TTrree source:

Code: Pascal  [Select][+][-]
  1. procedure TTree.DepthFirstTraverse(Callback: TDepthFirstCallbackType);
  2. var
  3.   Stack: TStackType;
  4.   Node,Child: TTreeNodeType;
  5. begin
  6.   if Assigned(FRoot) then begin
  7.     Stack := TStackType.Create;
  8.     Stack.Push(FRoot);
  9.     while Stack.Size > 0 do begin
  10.       Node := Stack.Top;
  11.       Stack.Pop;
  12.       Callback(Node.Data);
  13.       for Child in Node.Children do Stack.Push(Child);
  14.     end;
  15.     Stack.Free;
  16.   end;
  17. end;

It pushes nodes to a stack and then pops them back so the rightmost nodes get processed first. Here is my test code:

Code: Pascal  [Select][+][-]
  1. program project1;
  2.  
  3. {$mode objfpc}{$H+}
  4.  
  5. uses
  6.     gtree, gvector, sysutils;
  7.  
  8.  
  9. type
  10.  
  11.     TExpression = class(TObject)
  12.     public
  13.         value: integer;
  14.         constructor Create(v: integer);
  15.     end;
  16.  
  17.     TExpressionNode = class(specialize TTreeNode<TExpression>)
  18.         destructor Destroy; override;
  19.     end;
  20.    
  21.     TExpressionTree = specialize TTree<TExpression>;
  22.    
  23.     TIntVector = specialize TVector<integer>;
  24.  
  25.  
  26.  
  27. var
  28.     tree: TExpressionTree;
  29.     n1, n2, n3, n4, n5, n6, n7: TExpressionNode;
  30.     e1, e2, e3, e4, e5, e6, e7: TExpression;
  31.    
  32.     v: TIntVector;
  33.     i: integer;
  34.    
  35.  
  36. constructor TExpression.Create(v: integer);
  37. begin
  38.     self.value := v;
  39. end;
  40.  
  41.  
  42. destructor TExpressionNode.Destroy;
  43. begin
  44.     self.Data.Free;
  45.     inherited;
  46. end;
  47.  
  48.  
  49. procedure WriteCallback(const e: TExpression);
  50. begin
  51.     write(e.value, ' ');
  52. end;
  53.  
  54.    
  55. begin
  56.  
  57. {*
  58. *
  59. *         1
  60. *       /   \
  61. *      2     3
  62. *     / \   / \
  63. *    4   5 6   7
  64. *
  65. * }
  66.  
  67.  
  68.     e1 := TExpression.Create(1);
  69.     e2 := TExpression.Create(2);
  70.     e3 := TExpression.Create(3);
  71.     e4 := TExpression.Create(4);
  72.     e5 := TExpression.Create(5);
  73.     e6 := TExpression.Create(6);
  74.     e7 := TExpression.Create(7);
  75.    
  76.     n1 := TExpressionNode.Create;
  77.     n2 := TExpressionNode.Create;
  78.     n3 := TExpressionNode.Create;
  79.     n4 := TExpressionNode.Create;
  80.     n5 := TExpressionNode.Create;
  81.     n6 := TExpressionNode.Create;
  82.     n7 := TExpressionNode.Create;
  83.    
  84.     tree := TExpressionTree.Create;
  85.    
  86.     n1.Data := e1;
  87.     n2.Data := e2;
  88.     n3.Data := e3;
  89.     n4.Data := e4;
  90.     n5.Data := e5;
  91.     n6.Data := e6;
  92.     n7.Data := e7;
  93.    
  94.     n1.Children.PushBack(n2);
  95.     n1.Children.PushBack(n3);
  96.    
  97.     n2.Children.PushBack(n4);
  98.     n2.Children.PushBack(n5);
  99.    
  100.     n3.Children.PushBack(n6);
  101.     n3.Children.PushBack(n7);    
  102.    
  103.     tree.Root := n1;
  104.    
  105.     tree.DepthFirstTraverse(@WriteCallback);
  106.     writeln;
  107.    
  108.     tree.BreadthFirstTraverse(@WriteCallback);
  109.     writeln;
  110.    
  111.     tree.Free;
  112.    
  113.     v := TIntVector.Create;
  114.    
  115.     for i := 1 to 10 do
  116.     begin
  117.         v.PushBack(i);
  118.     end;
  119.    
  120.     for i in v do
  121.     begin
  122.         write(i, ' ');
  123.     end;
  124.    
  125.     v.Free;
  126.    
  127.     writeln;
  128.    
  129. end.
  130.  
  131.  

The background is I am trying to build an AST from a Pyacc generated parser.
Title: Re: TTree depth-first traversal
Post by: simone on September 22, 2019, 12:07:05 am
A 'quick and dirty' solution is modify your code as follows (see comments added in code):

Code: Pascal  [Select][+][-]
  1. program project1;
  2.  
  3. {$mode objfpc}{$H+}
  4.  
  5. uses
  6.     gtree, gvector, sysutils;
  7.  
  8.  
  9. type
  10.  
  11.     TExpression = class(TObject)
  12.     public
  13.         value: integer;
  14.         constructor Create(v: integer);
  15.     end;
  16.  
  17.     TExpressionNode = class(specialize TTreeNode<TExpression>)
  18.         destructor Destroy; override;
  19.     end;
  20.  
  21.     { TExpressionTree }
  22.  
  23.     TExpressionTree = class(specialize TTree<TExpression>) //inherits from TTree<TExpression>
  24.       procedure DepthFirstTraverse(Callback: TDepthFirstCallbackType); //hide original procedure
  25.     end;
  26.  
  27.     TIntVector = specialize TVector<integer>;
  28.  
  29.  
  30.  
  31. var
  32.     tree: TExpressionTree;
  33.     n1, n2, n3, n4, n5, n6, n7: TExpressionNode;
  34.     e1, e2, e3, e4, e5, e6, e7: TExpression;
  35.  
  36.     v: TIntVector;
  37.     i: integer;
  38.  
  39. { TExpressionTree }
  40.  
  41. procedure TExpressionTree.DepthFirstTraverse(Callback: TDepthFirstCallbackType); //new depth first traverse
  42. var
  43.   Stack: TStackType;
  44.   Node{,Child}: TTreeNodeType; //Child variable no longer needed
  45.   ind : integer;
  46. begin
  47.   if Assigned(FRoot) then begin
  48.     Stack := TStackType.Create;
  49.     Stack.Push(FRoot);
  50.     while Stack.Size > 0 do begin
  51.       Node := Stack.Top;
  52.       Stack.Pop;
  53.       Callback(Node.Data);
  54.       //for Child in Node.Children do Stack.Push(Child); //(right to left order) replaced by following line
  55.       for ind:=Node.Children.Size-1 downto 0 do Stack.Push(Node.Children[ind]); //inverts order of iteration over children
  56.     end;
  57.     Stack.Free;
  58.   end;
  59. end;
  60.  
  61.  
  62. constructor TExpression.Create(v: integer);
  63. begin
  64.     self.value := v;
  65. end;
  66.  
  67.  
  68. destructor TExpressionNode.Destroy;
  69. begin
  70.     self.Data.Free;
  71.     inherited;
  72. end;
  73.  
  74.  
  75. procedure WriteCallback(const e: TExpression);
  76. begin
  77.     write(e.value, ' ');
  78. end;
  79.  
  80.  
  81. begin
  82.  
  83. {*
  84. *
  85. *         1
  86. *       /   \
  87. *      2     3
  88. *     / \   / \
  89. *    4   5 6   7
  90. *
  91. * }
  92.  
  93.  
  94.     e1 := TExpression.Create(1);
  95.     e2 := TExpression.Create(2);
  96.     e3 := TExpression.Create(3);
  97.     e4 := TExpression.Create(4);
  98.     e5 := TExpression.Create(5);
  99.     e6 := TExpression.Create(6);
  100.     e7 := TExpression.Create(7);
  101.  
  102.     n1 := TExpressionNode.Create;
  103.     n2 := TExpressionNode.Create;
  104.     n3 := TExpressionNode.Create;
  105.     n4 := TExpressionNode.Create;
  106.     n5 := TExpressionNode.Create;
  107.     n6 := TExpressionNode.Create;
  108.     n7 := TExpressionNode.Create;
  109.  
  110.     tree := TExpressionTree.Create;
  111.  
  112.     n1.Data := e1;
  113.     n2.Data := e2;
  114.     n3.Data := e3;
  115.     n4.Data := e4;
  116.     n5.Data := e5;
  117.     n6.Data := e6;
  118.     n7.Data := e7;
  119.  
  120.     n1.Children.PushBack(n2);
  121.     n1.Children.PushBack(n3);
  122.  
  123.     n2.Children.PushBack(n4);
  124.     n2.Children.PushBack(n5);
  125.  
  126.     n3.Children.PushBack(n6);
  127.     n3.Children.PushBack(n7);
  128.  
  129.     tree.Root := n1;
  130.  
  131.     tree.DepthFirstTraverse(@WriteCallback);
  132.     writeln;
  133.  
  134.     tree.BreadthFirstTraverse(@WriteCallback);
  135.     writeln;
  136.  
  137.     tree.Free;
  138.  
  139.     v := TIntVector.Create;
  140.  
  141.     for i := 1 to 10 do
  142.     begin
  143.         v.PushBack(i);
  144.     end;
  145.  
  146.     for i in v do
  147.     begin
  148.         write(i, ' ');
  149.     end;
  150.  
  151.     v.Free;
  152.  
  153.     writeln;
  154.  
  155.     readln;
  156.  
  157. end.
Title: Re: TTree depth-first traversal
Post by: jamie on September 22, 2019, 02:24:10 am
Nice guy you are..

 I wish I had  you around when I was doing my home work! :)
Title: Re: TTree depth-first traversal
Post by: avk on September 22, 2019, 04:23:35 am
@Anonimista, another option is to write your own recursive DFS that will do what you need, it is very simple.
Title: Re: TTree depth-first traversal
Post by: Anonimista on September 22, 2019, 07:14:38 am
Thank you guys. @avk yes I tend to lose time trying to find a ready-made solution even when it's probably easier to make one myself. oh well
Title: Re: TTree depth-first traversal
Post by: simone on September 22, 2019, 12:40:55 pm
Quote from: avk on September 22, 2019, 04:23:35 am
@Anonimista, another option is to write your own recursive DFS that will do what you need, it is very simple.

I agree. A recursive DFS would be more compact and elegant (I say this because I spent some time with Lisp and Prolog during my youth). I note only that it would have the two typical small disadvantages of recursive algorithms. First, it would be slightly slower. Second, since recursive calls allocate resources in the system stack, in the case of traversals of very large trees, a stack overflow could happen during execution.
Title: Re: TTree depth-first traversal
Post by: avk on September 22, 2019, 02:23:58 pm
Quote from: simone on September 22, 2019, 12:40:55 pm
I note only that it would have the two typical small disadvantages of recursive algorithms. First, it would be slightly slower. Second, since recursive calls allocate resources in the system stack, in the case of traversals of very large trees, a stack overflow could happen during execution.
Do you have any benchmark confirming the first thesis? I am interested because my own measurements usually show the opposite.
As for the second, it doesn't seem to matter much, since the TTreeNode destructor is already recursive.
Title: Re: TTree depth-first traversal
Post by: simone on September 22, 2019, 04:17:18 pm
Quote from: avk on September 22, 2019, 02:23:58 pm
Quote from: simone on September 22, 2019, 12:40:55 pm
I note only that it would have the two typical small disadvantages of recursive algorithms. First, it would be slightly slower. Second, since recursive calls allocate resources in the system stack, in the case of traversals of very large trees, a stack overflow could happen during execution.
Do you have any benchmark confirming the first thesis? I am interested because my own measurements usually show the opposite.
As for the second, it doesn't seem to matter much, since the TTreeNode destructor is already recursive.

This fact is well known in literature. See, for example:

https://en.wikipedia.org/wiki/Recursion_(computer_science)#Performance_issues
"Performance issues
In languages (such as C and Java) that favor iterative looping constructs, there is usually significant time and space cost associated with recursive programs, due to the overhead required to manage the stack and the relative slowness of function calls; in functional languages, a function call (particularly a tail call) is typically a very fast operation, and the difference is usually less noticeable.
As a concrete example, the difference in performance between recursive and iterative implementations of the "factorial" example above depends highly on the compiler used. In languages where looping constructs are preferred, the iterative version may be as much as several orders of magnitude faster than the recursive one. In functional languages, the overall time difference of the two implementations may be negligible; in fact, the cost of multiplying the larger numbers first rather than the smaller numbers (which the iterative version given here happens to do) may overwhelm any time saved by choosing iteration."

Sedgewick, Wayne, "Alghorithms", 4th ed. p. 415:
"Generally, recursive implementations are a bit easier to verify for correctness; nonrecursive
implementations are a bit more efficient."
Title: Re: TTree depth-first traversal
Post by: avk on September 22, 2019, 04:51:32 pm
We are not talking about the "grand and terrible" Factorial, but specifically about DFS, right?
Well, personally, I have never been able to write iterative DFS, which would be faster than recursive one.
Title: Re: TTree depth-first traversal
Post by: howardpc on September 22, 2019, 04:59:00 pm
"Iterative algorithms are typically faster than recursive ones."
Like many generalisations the correctness of the assertion is often belied by actual measurements.
Algorithms can vary so widely and be used on such varied data that generalisations about comparing them are no better than a rough guide.

Like avk the few times I have done actual measurements on equivalent algorithms chewing their way through identical data I have not found particularly significant speed differences between iterative and recursive methods (provided both routines are well optimsed, of course). Which is not to deny that there are cases where one type of algorithm performs consistently better than the other approach.


Title: Re: TTree depth-first traversal
Post by: 440bx on September 22, 2019, 04:59:21 pm
Quote from: simone on September 22, 2019, 04:17:18 pm
Sedgewick, Wayne, "Alghorithms", 4th ed. p. 415:
"Generally, recursive implementations are a bit easier to verify for correctness; nonrecursive implementations are a bit more efficient."
That's one of the books I keep at hand and, unsurprisingly, he is right.  One thing that should be noted is that, recursion can often be the simplest and most intuitive way of implementing an algorithm but, that doesn't mean it is the best (read, reasonably efficient) way.

Sedgewick's book has a chapter on recursion (chapter 5 in my edition) which provides some examples of the above.  Some algorithms are really simple to implement using recursion but have undesirable Big Os when implemented that way.  That is a problem of the algorithm, not of recursion (like a bubble sort is simply a poor algorithm regardless of how it is implemented.)

Just like everything else, some algorithms can be implemented simply, efficiently and elegantly using recursion, others, not so much. ;)


Title: Re: TTree depth-first traversal
Post by: simone on September 22, 2019, 05:45:45 pm
I have not revealed an absolute truth, but a typical situation: in general recursive alghorithms are slightly slower than iterative ones, because they require as many 'calls with return' as the number of recursive cycles.  These types of operations are very expensive for the CPU.  I mentioned authoritative sources in support of my thesis. If someone cites to me equally authoritative sources or shows me experimental evidence of the opposite sign, I am happy to change my mind, because I often use recursive algorithms. :D
Title: Re: TTree depth-first traversal
Post by: simone on September 22, 2019, 06:26:15 pm
Moreover, every recursive call requires a stack frame allocation. This is a further cause of slowing down performances and could generate stack overflow. Finally, note that the DFS algorithm implemented by Leledumbo in gtree unit is iterative. 
Title: Re: TTree depth-first traversal
Post by: avk on September 22, 2019, 08:06:11 pm
The algorithm implemented by Leledumbo is not equivalent to DFS, otherwise this thread would not have arisen.
Title: Re: TTree depth-first traversal
Post by: simone on September 22, 2019, 08:30:10 pm
Yes, I agree. In the gtree unit are implemented a Depth First Traversal and a Breadth First Traversal algorithm. However graph search and graph traversal are very similar algorithms. My posts were not a crusade against recursion! I just wanted to highlight some possible side effects.  O:-)
Title: Re: TTree depth-first traversal
Post by: 440bx on September 22, 2019, 08:40:33 pm
Quote from: simone on September 22, 2019, 05:45:45 pm
I have not revealed an absolute truth, but a typical situation:
I'm not sure if your post was a result of what I posted but, I agree.

Quote from: simone on September 22, 2019, 05:45:45 pm
in general recursive alghorithms are slightly slower than iterative ones, because they require as many 'calls with return' as the number of recursive cycles.
That's when one has to be very careful.  Some solutions can be implemented efficiently and elegantly using a recursive algorithm and, when such a recursive algorithm is restructured to avoid recursion, the implementation, as you pointed out in a recent post, tends to be more complicated.

Restructuring a simple, efficient and elegant recursive algorithm to eliminate recursion usually requires implementing a stack.  In such cases, all that is saved is the push of the return address needed in the recursive algorithm.  There is obviously a cost in pushing a return address to a memory location (the stack in this case) but, that operation isn't really very expensive. 

Quote from: simone on September 22, 2019, 05:45:45 pm
These types of operations are very expensive for the CPU.
There is obviously a cost but, pushing a return address on the stack isn't a very expensive operation but, in many cases, the added complexity resulting from converting a recursive algorithm into an iterative one can be considerable.  Personally, if the recursive algorithm performs well, I will forego the very small performance increase of an iterative algorithm because I don't think the small performance gain justifies the added complexity.

Quote from: simone on September 22, 2019, 05:45:45 pm
I mentioned authoritative sources in support of my thesis. If someone cites to me equally authoritative sources or shows me experimental evidence of the opposite sign, I am happy to change my mind, because I often use recursive algorithms. :D
Generally speaking, what you stated is true.  The keyword being "generally".

Title: Re: TTree depth-first traversal
Post by: simone on September 22, 2019, 08:49:20 pm
I wrote:

Quote from: simone on September 22, 2019, 12:40:55 pm
... I note only that it would have the two typical small disadvantages of recursive algorithms. First, it would be slightly slower. Second, since recursive calls allocate resources in the system stack, in the case of traversals of very large trees, a stack overflow could happen during execution.

It seems to me that you agree. 
Title: Re: TTree depth-first traversal
Post by: avk on September 23, 2019, 03:34:58 am
So, can anyone show an iterative DFS implementation(equivalent) that would be faster than the recursive version?
Title: Re: TTree depth-first traversal
Post by: simone on September 23, 2019, 07:50:29 am
As soon as possible I will do some tests to confirm (or deny) what is reported in scientific literature and on many programming forums. In the meantime, can you refute this thesis with technical arguments or quote authoritative sources, as I did?
Title: Re: TTree depth-first traversal
Post by: simone on September 23, 2019, 02:31:04 pm
I do a simple test. This is NOT a rigorous benchmark. I have adapted the code in order to generate a tree with a very simple topology (two levels) but with a big number of nodes N=100000000 nodes: 1 root and n-1 children. This topology should be the best case for recursion approach, because should reduce the nesting level of recursive calls (but this issue requires some further investigation). I wrote a Recursive DFT algorithm (DFS is a special case of DFT). Unlike the iterative case, the Node parameter is required for the procedure. At the first call this parameter must be the tree root, while in subsequent recursive calls acts as the root of the sub-trees. To avoid noise, the callback procedure does nothing.

Using Lazarus 2.0.4+FPC 3.0.4 (64bits) on a PC with a Intel Core i7, I have following results:

Recursive DFT
Start Timer
End Timer
Time Elapsed: 75345

Iterarive DFT
Start Timer
End Timer
Time Elapsed: 55202

However it's only a simple test. I need further confirmations.

This is the code:
Code: Pascal  [Select][+][-]
  1. program project1;
  2. {$mode objfpc}{$H+}
  3.  
  4. uses
  5.     gtree, gvector, sysutils;
  6.  
  7. type
  8.  
  9.     TExpression = class(TObject)
  10.     public
  11.         value: integer;
  12.         constructor Create(v: integer);
  13.     end;
  14.  
  15.     TExpressionNode = class(specialize TTreeNode<TExpression>)
  16.         destructor Destroy; override;
  17.     end;
  18.  
  19.     { TExpressionTree }
  20.  
  21.     TExpressionTree = class(specialize TTree<TExpression>)
  22.       procedure DepthFirstTraverseRecursive(Node : TTreeNodeType; Callback: TDepthFirstCallbackType);
  23.     end;
  24.  
  25. var
  26.     tree: TExpressionTree;
  27.     n,n1 : TExpressionNode;
  28.     e,e1 : TExpression;
  29.     T0,T1 : Comp;
  30.     ind : QWord;
  31.  
  32. procedure TimerOn;
  33. begin
  34.   Writeln('Start Timer');
  35.   T0:=TimestampToMSecs(DateTimeToTimestamp(Now));
  36. end;
  37.  
  38. procedure TimerOff;
  39. begin
  40.   T1:=TimestampToMSecs(DateTimeToTimestamp(Now));
  41.   Writeln('End Timer');
  42.   Writeln('Time Elapsed: '+IntToStr(QWord(T1-T0)));
  43. end;
  44.  
  45. { TExpressionTree }
  46.  
  47. procedure TExpressionTree.DepthFirstTraverseRecursive(Node : TTreeNodeType; Callback: TDepthFirstCallbackType);
  48. var
  49.   Child: TTreeNodeType;
  50. begin
  51.   if Assigned(Node) then
  52.     begin
  53.       Callback(Node.Data);
  54.       for Child in Node.Children do
  55.         DepthFirstTraverseRecursive(Child,Callback);
  56.     end;
  57. end;
  58.  
  59.  
  60. constructor TExpression.Create(v: integer);
  61. begin
  62.     self.value := v;
  63. end;
  64.  
  65.  
  66. destructor TExpressionNode.Destroy;
  67. begin
  68.     self.Data.Free;
  69.     inherited;
  70. end;
  71.  
  72.  
  73. procedure WriteCallback(const e: TExpression);
  74. begin
  75.   //write(e.value, ' ');
  76. end;
  77.  
  78.  
  79. begin
  80.     Tree:=TExpressionTree.Create;
  81.  
  82.     e1:=TExpression.Create(0);
  83.     n1:=TExpressionNode.Create;
  84.     n1.Data := e1;
  85.     tree.Root := n1;
  86.     for ind:=1 to 100000000 do
  87.       begin
  88.         e:= TExpression.Create(ind);
  89.         n:= TExpressionNode.Create;
  90.         n.Data:=e;
  91.         n1.Children.PushBack(n);
  92.       end;
  93.  
  94.     writeln('Recursive DFT');
  95.     TimerOn;
  96.     Tree.DepthFirstTraverseRecursive(n1,@WriteCallback);
  97.     TimerOff;
  98.     writeln;
  99.  
  100.     writeln('Iterarive DFT');
  101.     TimerOn;
  102.     Tree.DepthFirstTraverse(@WriteCallback);
  103.     TimerOff;
  104.     writeln;
  105.  
  106.     tree.Free;
  107.  
  108.     readln;
  109.  
  110. end.
  111.  
Title: Re: TTree depth-first traversal
Post by: avk on September 23, 2019, 02:42:30 pm
My English is certainly terrible, but you should have noticed that I was interested specifically in the DFS implementation for the reason that I already explained. And I'm not going to refute CS stars at all and I trust their opinion, I am interested in the practical aspect: is it possible to somehow improve the situation I described above.
As for DepthFirstTraverse, I have already said that it is not equivalent to recursive DFS (for example, yours).
Title: Re: TTree depth-first traversal
Post by: simone on September 23, 2019, 03:48:09 pm
Your English is certainly better than mine.  I didn't understand exactly what you need.  A search (for example using a DFS algorithm) on a data structure such as a list, a tree or a graph, unless It is ordered, requires a complete traversal of the structure (for example using a DFT algorithm).  In our example the library that implements the DFT allows the use of a callback procedure that can help to perform a search.
Title: Re: TTree depth-first traversal
Post by: avk on September 23, 2019, 05:01:44 pm
I'm trying to say that if we want to compare the performance of an iterative and recursive version of some algorithm, these versions should be equivalent, otherwise the comparison does not make sense. Of couse, DepthFirstTraverse does a complete traversal of the tree, without any doubt, but this is a different algorithm.
Title: Re: TTree depth-first traversal
Post by: 440bx on September 23, 2019, 05:03:31 pm
Quote from: avk on September 23, 2019, 02:42:30 pm
is it possible to somehow improve the situation I described above.
The answer to that is _very likely_ to be, yes.  The performance gain in most cases will be minimal to negligible and, the code to implement an iterative solution will be noticeably more complex.  It's simply not worth it.

Just FYI, Sedgewick, in the second edition of his book "Algorithms" presents both, a recursive and an iterative implementation (Pascal pseudocode) of a DFS (neither is optimized.)  As expected, the iterative implementation is more complex than the recursive one and, as presented in the book, it's unclear which one would actually perform better.

I _believe_ that, with careful optimization of both algorithms, the iterative algorithm would be a smidgen faster (most likely not humanly perceptible in the great majority of cases.)  I believe that because, in a good iterative implementation, a push of the return address on the stack will no longer be necessary (in most cases, that isn't much of a performance gain.)


Quote from: simone on September 22, 2019, 08:49:20 pm
It seems to me that you agree. 
In general, yes, I agree with what you've stated.

However, there is one statement you've made that I disagree with, which is:
Quote from: simone on September 22, 2019, 05:45:45 pm
These types of operations are very expensive for the CPU.
There is obviously a cost associated with pushing "items" on a stack but, they really aren't "very expensive". 


Title: Re: TTree depth-first traversal
Post by: Thaddy on September 23, 2019, 05:17:55 pm
In general iterative algorithms have better time complexity over recursion. But it will only show on *huge* amounts of data.
If there is a noticeable discrepancy between the two, likely  the slowest one has an inferior implementation.

(More on topic: left and right are a contract, keep to the contract and you are safe..)

Note
Quote
There is obviously a cost associated with pushing "items" on a stack but, they really aren't "very expensive".
Well, the obvious amazes me, since stack/queue are linked list based.  You can't improve on that, currently..... :'( 8-)
You are right, btw... But you should have added the details. Also, recursion is a hornet's nest of problems in the hands of all programmers....

Title: Re: TTree depth-first traversal
Post by: simone on September 23, 2019, 05:54:44 pm
Quote from: avk on September 23, 2019, 05:01:44 pm
I'm trying to say that if we want to compare the performance of an iterative and recursive version of some algorithm, these versions should be equivalent, otherwise the comparison does not make sense. Of couse, DepthFirstTraverse does a complete traversal of the tree, without any doubt, but this is a different algorithm.

Indeed in my test I compared a ricorsive DFT algorithm with an iterative  one

Quote from: 440bx on September 23, 2019, 05:03:31 pm
Quote from: 440bx on September 23, 2019, 05:03:31 pm

Quote from: simone on September 22, 2019, 08:49:20 pm
It seems to me that you agree. 
In general, yes, I agree with what you've stated.

However, there is one statement you've made that I disagree with, which is:
Quote from: simone on September 22, 2019, 05:45:45 pm
These types of operations are very expensive for the CPU.
There is obviously a cost associated with pushing "items" on a stack but, they really aren't "very expensive". 

Recursion, as well known, is implemented using stack. Every recursive call allocates a new 'stack frame' on the top of the stack. Each frame contains, among others, following information, for each execution of recursive procedure: the parameters values passed to procedure; the return address of the caller procedure; all the values of local variables of the procedure.  When recursion terminates, all these frames are deallocated, in reverse order. These operation are very expensive, since consume space of stack and time of CPU.
Title: Re: TTree depth-first traversal
Post by: 440bx on September 23, 2019, 07:24:38 pm
Quote from: simone on September 23, 2019, 05:54:44 pm
Recursion, as well known, is implemented using stack. Every recursive call allocates a new 'stack frame' on the top of the stack. Each frame contains, among others, following information, for each execution of recursive procedure: the parameters values passed to procedure; the return address of the caller procedure; all the values of local variables of the procedure.  When recursion terminates, all these frames are deallocated, in reverse order. These operation are very expensive, since consume space of stack and time of CPU.
What you stated above is correct except for the "very expensive" part.

A "very expensive" sequence of instructions is, for instance, servicing an exception, _that_ is very expensive.

I suggest you do the following to give yourself an idea of how relatively "expensive" some instruction sequences are: in a loop - say about a million times - call a procedure.  First with no parameters then, with an increasing number of parameters.  Obviously, time that.

You may also want to do the above with a function that returns an ordinal type (integer for instance) and a function that returns a structured type of 32 bytes.

Compare the results you obtained above (for the various cases), with a loop (same number of executions) that simply executes the expression "a := b + c;" (assign random values to b and c before the loop or the compiler may optimize the code causing it to be executed only once.)

It is obviously true that there is a cost in setting up a stack frame but, it is _not_ a very expensive operation.  The only time, setting up the stack frame is "very expensive" as you put it is when the total size of the local variables cause the stack pointer to "bump into" (or go past) the bottom of the stack.  In that case, one or more exceptions will need to be serviced by the O/S to commit whatever additional memory is needed on the stack to accommodate the local variables.  That is the only time when setting up a stack frame can legitimately be considered to be "very expensive".

It should also be noted that if a program is concerned about the amount of stack space it is going to consume during a time sensitive operation, it can specify a "stack commit size" in the PE file large enough to ensure that no exceptions will be necessary to ensure that enough memory has been committed to it.

HTH.


Title: Re: TTree depth-first traversal
Post by: simone on September 23, 2019, 07:36:25 pm
'Expensive' is a relative term… However I agree with your statements.
Title: Re: TTree depth-first traversal
Post by: julkas on September 23, 2019, 08:20:35 pm
What about {$optimization tailrec}? Any practical example?
Title: Re: TTree depth-first traversal
Post by: simone on September 23, 2019, 10:00:06 pm
I did not know this switch. Thanks for pointing this out to me. I will try it.
Title: Re: TTree depth-first traversal
Post by: jamie on September 23, 2019, 11:05:05 pm
My god, the use of DFT "Discrete Fourier Transfers " is throwing me here, I am sure that isn't what you are referring to ?
Title: Re: TTree depth-first traversal
Post by: simone on September 23, 2019, 11:34:16 pm
The subject is Depth First Traversal… I abbreviated with the acronym DFT... I removed from my memory continuous and discrete Fourier transforms :D More than twenty years have passed since I last used them!
Title: Re: TTree depth-first traversal
Post by: avk on September 24, 2019, 03:33:09 am
Quote from: simone on September 23, 2019, 05:54:44 pm
Quote from: avk on September 23, 2019, 05:01:44 pm
I'm trying to say that if we want to compare the performance of an iterative and recursive version of some algorithm, these versions should be equivalent, otherwise the comparison does not make sense. Of couse, DepthFirstTraverse does a complete traversal of the tree, without any doubt, but this is a different algorithm.

Indeed in my test I compared a ricorsive DFT algorithm with an iterative  one

For me, equivalence of implementations means that they perform the same steps in the same sequence. Therefore, I imagine an iterative implementation of DFS in a slightly different way:
Code: Pascal  [Select][+][-]
  1. program rec_vs_nonrec;
  2.  
  3. {$mode objfpc}{$H+}
  4. {$MODESWITCH ADVANCEDRECORDS}
  5.  
  6. uses
  7.   SysUtils, DateUtils, gtree, gstack;
  8. type
  9.   TIntTree   = specialize TTree<Integer>;
  10.   TTreeNode  = TIntTree.TTreeNodeType;
  11.   TStack     = specialize TStack<TTreeNode>;
  12.   TChildEnum = TTreeNode.TTreeNodeList.TEnumerator;
  13.  
  14.   TEnumNode = record
  15.     Node: TTreeNode;
  16.     Enum: TChildEnum;
  17.     Visited: Boolean;
  18.     constructor Create(aNode: TTreeNode);
  19.   end;
  20.   PEnumNode  = ^TEnumNode;
  21.   TEnumStack = specialize TStack<TEnumNode>;
  22.  
  23. constructor TEnumNode.Create(aNode: TTreeNode);
  24. begin
  25.   Node := aNode;
  26.   Visited := False;
  27. end;
  28.  
  29. var
  30.   Tree: TIntTree = nil;
  31.   TreeSize, I: Integer;
  32.   StartTime: TDateTime;
  33.  
  34. function GenRandomTree: TIntTree;
  35. var
  36.   NodeStack, ChildStack, Tmp: TStack;
  37.   Node, Child: TTreeNode;
  38.   I, J: Integer;
  39. begin
  40.   Result := TIntTree.Create;
  41.   Result.Root := TTreeNode.Create;
  42.   Inc(TreeSize);
  43.   NodeStack := TStack.Create;
  44.   ChildStack := TStack.Create;
  45.   try
  46.     NodeStack.Push(Result.Root);
  47.     for I := 1 to 10 do
  48.       begin
  49.         while NodeStack.Size > 0 do
  50.           begin
  51.             Node := NodeStack.Top;
  52.             NodeStack.Pop;
  53.             for J := 1 to Random(9)+1 do
  54.               begin
  55.                 Child := TTreeNode.Create;
  56.                 Inc(TreeSize);
  57.                 Node.Children.PushBack(Child);
  58.                 ChildStack.Push(Child);
  59.               end;
  60.           end;
  61.         Tmp := NodeStack;
  62.         NodeStack := ChildStack;
  63.         ChildStack := Tmp;
  64.       end;
  65.   finally
  66.     NodeStack.Free;
  67.     ChildStack.Free;
  68.   end;
  69. end;
  70.  
  71. procedure DfsTraversal(aTree: TIntTree); //iterative
  72. var
  73.   Stack: TEnumStack;
  74.   Next: TTreeNode;
  75.   Curr: PEnumNode;
  76. begin
  77.   if not Assigned(aTree.Root) then
  78.     exit;
  79.   Stack := TEnumStack.Create;
  80.   try
  81.     Stack.Push(TEnumNode.Create(aTree.Root));
  82.     while Stack.Size > 0 do
  83.       begin
  84.         Curr := Stack.TopItem;
  85.         if not Curr^.Visited then
  86.           begin
  87.             Curr^.Visited := True;
  88.             Curr^.Enum := Curr^.Node.Children.GetEnumerator;
  89.           end;
  90.         if Curr^.Enum.MoveNext then
  91.           begin
  92.             Next := Curr^.Enum.Current;
  93.             Stack.Push(TEnumNode.Create(Next));
  94.           end
  95.         else
  96.           begin
  97.             Curr^.Enum.Free;
  98.             Stack.Pop;
  99.           end;
  100.       end;
  101.   finally
  102.     Stack.Free;
  103.   end;
  104. end;
  105.  
  106. procedure DfsTraversalR(aTree: TIntTree);
  107.   procedure Dfs(aNode: TTreeNode);
  108.   var
  109.     Child: TTreeNode;
  110.   begin
  111.     for Child in aNode.Children do
  112.       Dfs(Child);
  113.   end;
  114. begin
  115.   if Assigned(aTree.Root) then
  116.     Dfs(aTree.Root);
  117. end;
  118.  
  119. begin
  120.   Randomize;
  121.   for I := 1 to 10 do
  122.     begin
  123.       TreeSize := 0;
  124.       Tree := GenRandomTree;
  125.       try
  126.         WriteLn('generated new tree with ', TreeSize, ' nodes');
  127.         StartTime := Time;
  128.         DfsTraversal(Tree);
  129.         WriteLn('non-recursive DFS: ', MillisecondsBetween(Time, StartTime), 'ms');
  130.         StartTime := Time;
  131.         DfsTraversalR(Tree);
  132.         WriteLn('recursive DFS:     ', MillisecondsBetween(Time, StartTime), 'ms');
  133.         WriteLn;
  134.       finally
  135.         Tree.Free;
  136.       end;
  137.     end;
  138. end.
  139.  
Accordingly, the comparison results look different:
Code: Text  [Select][+][-]
  1. generated new tree with 13274394 nodes
  2. non-recursive DFS: 1341ms
  3. recursive DFS:     1108ms
  4.  
  5. generated new tree with 18425042 nodes
  6. non-recursive DFS: 1872ms
  7. recursive DFS:     1544ms
  8.  
  9. generated new tree with 18404551 nodes
  10. non-recursive DFS: 2208ms
  11. recursive DFS:     1777ms
  12.  
  13. generated new tree with 6713672 nodes
  14. non-recursive DFS: 692ms
  15. recursive DFS:     567ms
  16.  
  17. generated new tree with 10211120 nodes
  18. non-recursive DFS: 1036ms
  19. recursive DFS:     862ms
  20.  
  21. generated new tree with 12273356 nodes
  22. non-recursive DFS: 1241ms
  23. recursive DFS:     1016ms
  24.  
  25. generated new tree with 22542599 nodes
  26. non-recursive DFS: 2274ms
  27. recursive DFS:     1883ms
  28.  
  29. generated new tree with 24004838 nodes
  30. non-recursive DFS: 2435ms
  31. recursive DFS:     1996ms
  32.  
  33. generated new tree with 566744 nodes
  34. non-recursive DFS: 68ms
  35. recursive DFS:     46ms
  36.  
  37. generated new tree with 5299324 nodes
  38. non-recursive DFS: 532ms
  39. recursive DFS:     436ms
  40.  
Title: Re: TTree depth-first traversal
Post by: simone on September 24, 2019, 10:45:20 am
Thanks for your work Avk. I'm not sure that the proposed implementation of iterative DFS is optimal. Moreover, I have tried to compile your code, but I get some compiler errors. Now I'm busy at work and I can't go any further. In the evening I hope to have free time to better study your code and do experiments. Have you tried with larger trees? (for example: N=100000000 node, as in my previous test)?
Title: Re: TTree depth-first traversal
Post by: avk on September 24, 2019, 01:37:45 pm
Oops, excuse me, forgot to mention, to use the enumerator TTreeNode.Children I had to modify the gvector unit a bit:
Code: Pascal  [Select][+][-]
  1. {
  2.    This file is part of the Free Pascal FCL library.
  3.    BSD parts (c) 2011 Vlado Boza
  4.  
  5.    See the file COPYING.FPC, included in this distribution,
  6.    for details about the copyright.
  7.  
  8.    This program is distributed in the hope that it will be useful,
  9.    but WITHOUT ANY WARRANTY;without even the implied warranty of
  10.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  11.  
  12. **********************************************************************}
  13. {$mode objfpc}
  14.  
  15. unit gvector;
  16.  
  17. interface
  18.  
  19. type
  20.  
  21.   { TVector }
  22.  
  23.   generic TVector<T> = class
  24.   private
  25.   type
  26.     PT = ^ T;
  27.     TArr = array of T;
  28.   var
  29.     FCapacity:SizeUInt;
  30.     FDataSize:SizeUInt;
  31.     FData:TArr;
  32.  
  33.     procedure SetValue(Position: SizeUInt; const Value: T); inline;
  34.     function GetValue(Position: SizeUInt): T; inline;
  35.     function GetMutable(Position: SizeUInt): PT; inline;
  36.     procedure IncreaseCapacity; inline;
  37.  
  38.   const
  39.     // todo: move these constants to implementation when
  40.     // mantis #0021310 will be fixed.
  41.     SVectorPositionOutOfRange      = 'Vector position out of range';
  42.     SAccessingElementOfEmptyVector = 'Accessing element of empty vector';
  43.  
  44.   type
  45.     TVectorEnumerator = class
  46.     private
  47.       FVector: TVector;
  48.       FPosition: SizeUInt;
  49.       FFirstDone: Boolean;
  50.       function GetCurrent: T; inline;
  51.     public
  52.       constructor Create(AVector: TVector);
  53.       function GetEnumerator: TVectorEnumerator; inline;
  54.       function MoveNext: Boolean; inline;
  55.       property Current: T read GetCurrent;
  56.     end;
  57.  
  58.   public
  59.   type
  60.     TEnumerator = TVectorEnumerator;// <-- make TVectorEnumerator public
  61.     constructor Create;
  62.     function Size: SizeUInt; inline;
  63.     procedure PushBack(const Value: T); inline;
  64.     procedure PopBack; inline;
  65.     function IsEmpty: boolean; inline;
  66.     procedure Insert(Position: SizeUInt; const Value: T); inline;
  67.     procedure Erase(Position: SizeUInt); inline;
  68.     procedure Clear; inline;
  69.     function Front: T; inline;
  70.     function Back: T; inline;
  71.     procedure Reserve(Num: SizeUInt);
  72.     procedure Resize(Num: SizeUInt);
  73.  
  74.     function GetEnumerator: TVectorEnumerator; inline;
  75.  
  76.     property Items[i : SizeUInt]: T read getValue write setValue; default;
  77.     property Mutable[i : SizeUInt]: PT read getMutable;
  78. end;
  79.  
And for optimization purposes, I added an extra method to TStack:
Code: Pascal  [Select][+][-]
  1. {
  2.    This file is part of the Free Pascal FCL library.
  3.    BSD parts (c) 2011 Vlado Boza
  4.  
  5.    See the file COPYING.FPC, included in this distribution,
  6.    for details about the copyright.
  7.  
  8.    This program is distributed in the hope that it will be useful,
  9.    but WITHOUT ANY WARRANTY;without even the implied warranty of
  10.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  11.  
  12. **********************************************************************}
  13. {$mode objfpc}
  14.  
  15. unit gstack;
  16.  
  17. interface
  18.  
  19. uses gvector;
  20.  
  21. type
  22.  
  23.   { TStack }
  24.  
  25.   generic TStack<T>=class
  26.     private
  27.     type TContainer= specialize TVector<T>;
  28.     var FData:TContainer;
  29.     public
  30.     type
  31.       PItem = ^T;                   //for optimisation
  32.     Procedure Clear;
  33.     procedure Push(x:T);inline;
  34.     procedure Pop();inline;
  35.     function Top():T;inline;
  36.     function TopItem: PItem;inline; //for optimisation
  37.     function Size():longint;inline;
  38.     function IsEmpty():boolean;inline;
  39.     constructor Create;
  40.     destructor Destroy;override;
  41. end;
  42.  
  43. implementation
  44.  
  45. constructor TStack.Create;
  46. begin
  47.   FData:=TContainer.Create;
  48. end;
  49.  
  50. procedure TStack.Clear;
  51. begin
  52.   FData.Clear;
  53. end;
  54.  
  55. destructor TStack.Destroy;
  56. begin
  57.   FData.Destroy;
  58. end;
  59.  
  60. procedure TStack.Push(x:T);inline;
  61. begin
  62.   FData.PushBack(x);
  63. end;
  64.  
  65. procedure TStack.Pop();
  66. begin
  67.   FData.PopBack;
  68. end;
  69.  
  70. function TStack.Top(): T;
  71. begin
  72.   Top:=FData.Back;
  73. end;
  74.  
  75. function TStack.TopItem: PItem;
  76. begin
  77.   Result := FData.Mutable[FData.Size-1];
  78. end;
  79.  
  80. function TStack.Size(): longint;
  81. begin
  82.   Size:=FData.Size;
  83. end;
  84.  
  85. function TStack.IsEmpty(): boolean;
  86. begin
  87.   IsEmpty:=FData.IsEmpty;
  88. end;
  89.  
  90. end.
  91.  
As for the size of the tree, on my machine the swapping begins at about the size of a tree of 65000000, and, accordingly, these results do not seem interesting.
Title: Re: TTree depth-first traversal
Post by: Leledumbo on September 24, 2019, 11:10:58 pm
Quote from: avk on September 22, 2019, 08:06:11 pm
The algorithm implemented by Leledumbo is not equivalent to DFS, otherwise this thread would not have arisen.
Feel free to make the correct implementation if you think mine is wrong, but in my understanding it is correct (you can find similar implementations both in theory and practice, here's one example (http://web.cs.unlv.edu/larmore/Courses/CSC477/bfsDfs.pdf)). DFS does not explicitly say how the node at the same level (siblings) must be visited, left-to-right, right-to-left, even random all are correct as long as once you visit a node and you see that node has children, then you must visit the children first before visiting that node's siblings.
Title: Re: TTree depth-first traversal
Post by: julkas on September 25, 2019, 09:25:24 am
From my bookmarks -
https://algs4.cs.princeton.edu/41graph/
https://algs4.cs.princeton.edu/41graph/DepthFirstSearch.java.html
https://algs4.cs.princeton.edu/lectures/
https://algs4.cs.princeton.edu/lectures/41UndirectedGraphs-2x2.pdf
https://algs4.cs.princeton.edu/lectures/42DirectedGraphs-2x2.pdf
Title: Re: TTree depth-first traversal
Post by: avk on September 25, 2019, 01:50:48 pm
@Leledumbo, sorry for the noise. I'm not saying that your algorithm is wrong, it just has a somewhat embarrassing name, you expect that it has the classic DFS inside.
Let me explain what I mean. Even if we ignore the order of traversal of nodes, the classic DFS can distinguish characteristic points that are extremely useful for various applications of this wonderful algorithm:
Code: Pascal  [Select][+][-]
  1. procedure Dfs(aNode: TTreeNode);
  2. var
  3.   Child: TTreeNode;
  4. begin
  5.   //2. here node visit
  6.   //callback provides pre-order
  7.   for Child in aNode.Children do
  8.     begin
  9.       //1. here node discovered
  10.       Dfs(Child);
  11.     end;
  12.   //3. here node and its subtree done
  13.   //callback provides post-order
  14. end;
  15.  

Try to find point 3 in your algorithm.

The iterative equivalent(DFS-B from your link) might look like this:
Code: Pascal  [Select][+][-]
  1. type
  2.   TIntTree   = specialize TTree<Integer>;
  3.   TTreeNode  = TIntTree.TTreeNodeType;
  4.  
  5.   TTopNode = record
  6.     Node: TTreeNode;
  7.     ChildPos: SizeInt;
  8.     constructor Create(aNode: TTreeNode);
  9.   end;
  10.  
  11.   TStack = specialize TStack<TTopNode>;
  12.  
  13. constructor TTopNode.Create(aNode: TTreeNode);
  14. begin
  15.   Node := aNode;
  16.   ChildPos := -1;
  17. end;
  18.  
  19. procedure DfsTraversal(aTree: TIntTree);
  20. var
  21.   Stack: TStack;
  22.   TopNode: TTopNode;
  23.   Next: TTreeNode;
  24. begin
  25.   if not Assigned(aTree.Root) then
  26.     exit;
  27.   Stack := TStack.Create;
  28.   Stack.Push(TTopNode.Create(aTree.Root));
  29.   while Stack.Size > 0 do
  30.     begin
  31.       TopNode := Stack.Top;
  32.       Stack.Pop;
  33.       if TopNode.ChildPos = -1 then
  34.         begin
  35.           //2. here node visit
  36.         end;
  37.       if Succ(TopNode.ChildPos) < TopNode.Node.Children.Size then
  38.         begin
  39.           Inc(TopNode.ChildPos);
  40.           Next := TopNode.Node.Children[TopNode.ChildPos];
  41.           //1. here node discovered
  42.           Stack.Push(TopNode);
  43.           Stack.Push(TTopNode.Create(Next));
  44.         end
  45.       else
  46.         begin
  47.           //3. here node done
  48.         end;
  49.     end;
  50.   Stack.Free;
  51. end;          
  52.  
 
You yourself decide whether to change anything in the gtree code or not.

Quote from: simone on September 24, 2019, 10:45:20 am
...I'm not sure that the proposed implementation of iterative DFS is optimal...
Yes, at least we can get rid of the Visited field in TEnumNode and reduce the number of local variables in the procedure:
Code: Pascal  [Select][+][-]
  1. type
  2.   TEnumNode = record
  3.     Node: TTreeNode;
  4.     Enum: TChildEnum;
  5.     constructor Create(aNode: TTreeNode);
  6.   end;
  7.  
  8. constructor TEnumNode.Create(aNode: TTreeNode);
  9. begin
  10.   Node := aNode;
  11.   Enum := nil;
  12. end;
  13.  
  14. procedure DfsTraversal(aTree: TIntTree); //iterative
  15. var
  16.   Stack: TEnumStack;
  17. begin
  18.   if not Assigned(aTree.Root) then
  19.     exit;
  20.   Stack := TEnumStack.Create;
  21.   Stack.Push(TEnumNode.Create(aTree.Root));
  22.   while Stack.Size > 0 do
  23.     with Stack.TopItem^ do
  24.       begin
  25.         if Enum = nil then
  26.           Enum := Node.Children.GetEnumerator;
  27.         if Enum.MoveNext then
  28.           Stack.Push(TEnumNode.Create(Enum.Current))
  29.         else
  30.           begin
  31.             Enum.Free;
  32.             Stack.Pop;
  33.           end;
  34.       end;
  35.   Stack.Free;
  36. end;
  37.  
But the situation seems to remain the same.
Title: Re: TTree depth-first traversal
Post by: marcov on September 25, 2019, 03:43:34 pm
Quote from: simone on September 23, 2019, 05:54:44 pm
When recursion terminates, all these frames are deallocated, in reverse order. These operation are very expensive, since consume space of stack and time of CPU.

Note that is the case for places where iteration has no dynamically allocated state. As soon as you start to make allocations, this is possibly no longer true. Dynamic allocation on the heap might (and I would bet it is) more expensive than stack.
Title: Re: TTree depth-first traversal
Post by: simone on September 25, 2019, 04:08:36 pm
I believe that this issue depends on the allocation strategy adopted by heap implementation (i.e. best fit / first fit). However, I basically agree with your statement
Title: Re: TTree depth-first traversal
Post by: BrunoK on September 27, 2019, 03:44:46 pm
In attachment pgmTreeDepthTrav_2.7z a test program mixing simone and rvk code.

I added 2 custom non recursive style DFT's, one using a home made customized pile and another one using TStack.

Also a slightly modified (far from perfect) random tree generator using TStack (see cMaxNodes,  cTreeDepth, MaxSiblings constants).

Note the non recursive one using TStack seems incredibly slower on Win/CPU64, if anyone has an idea about that I would be interested.

Result for a 20 mega nodes tree on I386 (CPU32) on my system :
Quote
Create random tree
Time Elapsed: 3468
GenRandomTree node count=20000000

Recursive DFT
Time Elapsed: 2437
Visited Nodes=20000000

Recursive DFT, rvk
Time Elapsed: 2421
Visited Nodes=20000000

Iterarive DFT
Time Elapsed: 2890
Visited Nodes=20000000

Procedural DFT, custom pile (bk)
Time Elapsed: 218
Visited Nodes=20000000

Procedural DFT _1, TStack (bk)
Time Elapsed: 797
Visited Nodes=20000000


Don't know if it is correct or even relevant to your discussion, if not, please ignore.


Title: Re: TTree depth-first traversal
Post by: howardpc on September 27, 2019, 05:42:42 pm
Nice one BrunoK!
Your RPile record implementation has impressive performance.
I get similar relative times for the various algorithms on my slightly slower 64bit hardware.

I found that enabling range checking or using heaptrc led to immediate errors or crashes, however.

Title: Re: TTree depth-first traversal
Post by: BrunoK on September 28, 2019, 10:45:06 am
Edit :
Quote from: BrunoK on September 27, 2019, 03:44:46 pm
In attachment pgmTreeDepthTrav_2.7z a test program mixing simone and rvk code.
Should read :
In attachment pgmTreeDepthTrav_2.7z a test program mixing simone and avk code.

Quote from: howardpc on September 27, 2019, 05:42:42 pm
I found that enabling range checking led to immediate errors or crashes.
Ok. In the RPile.Grow,  I used pointer subtraction for FillChar. The FillChar is not required so you can comment it out or replace the line with :
Code: Pascal  [Select][+][-]
  1. FillChar(Items[lOldCap], SizeOf(RPileItem) * (Capacity-lOldCap), 0);
Useful remark, I'll keep that in mind and when I use pointer subtractions.

Quote from: howardpc on September 27, 2019, 05:42:42 pm
or using heaptrc led to immediate errors or crashes, however.
This is absolutely normal if you kept the 20'000'000 nodes generation. Every heaptrc GetMem adds an overhead of ~100 bytes per memory allocation, so you get an OutOfMemory error.

Attachment corrected for Range checking and algorithm attributed to avk.
Title: Re: TTree depth-first traversal
Post by: avk on September 28, 2019, 12:31:39 pm
@BrunoK, great, but what happens if you compare your DepthFirstTraverseBk with such a recursive procedure?
Code: Pascal  [Select][+][-]
  1. procedure DfsTraversalR(aTree: TIntTree);
  2.   procedure Dfs(aNode: TTreeNode);
  3.   var
  4.     I: SizeInt = -1;
  5.   begin
  6.     while SizeUInt(Succ(I)) < aNode.Children.Size do
  7.      begin
  8.        Inc(I);
  9.        Dfs(aNode.Children[I]);
  10.      end;
  11.   end;
  12. begin
  13.   if Assigned(aTree.Root) then
  14.     Dfs(aTree.Root);
  15. end;  
  16.  
Title: Re: TTree depth-first traversal
Post by: BrunoK on September 28, 2019, 01:30:09 pm
Quote from: avk on September 28, 2019, 12:31:39 pm
@BrunoK, great, but what happens if you compare your DepthFirstTraverseBk with such a recursive procedure?
@avk, your last recursive code is the WINNER, congrats !

Sligtly modified to integerate to the test program in attachement to :
Code: Pascal  [Select][+][-]
  1.  
  2. procedure TIntTree.DepthFirstTraverseRecursive_avk(Node: TTreeNodeType;
  3.     Callback: TTreeNodeCallBack);
  4.   { avk 0 -> slow
  5.   procedure Dfs(aNode: TTreeNode);
  6.   var
  7.     Child: TTreeNode;
  8.   begin
  9.     Callback(aNode);
  10.     for Child in aNode.Children do
  11.       Dfs(Child);
  12.   end;
  13.   }
  14.   { avk 1 -> winnner }
  15.   procedure Dfs(aNode: TTreeNode);
  16.   var
  17.     I: SizeInt = 0;
  18.   begin
  19.     Callback(aNode); // Callback needed to check that all nodes where visited
  20.     while I < aNode.Children.Size do begin
  21.       Dfs(aNode.Children[I]);
  22.       Inc(I);
  23.     end;
  24.   end;
  25. begin
  26.   if Assigned(Node) then
  27.     Dfs(Node);
  28. end;

Test results :
Quote
===================================================================================
I386 -O3   20'000'000 nodes
===================================================================================
Create random tree
Time Elapsed: 3343
GenRandomTree node count=20000000

Recursive DFT
Time Elapsed: 2390
Visited Nodes=20000000

Recursive DFT (avk)
Time Elapsed: 156
Visited Nodes=20000000

Iterarive DFT
Time Elapsed: 2702
Visited Nodes=20000000

Procedural DFT, custom pile (bk)
Time Elapsed: 203
Visited Nodes=20000000

Procedural DFT _1, TStack (bk)
Time Elapsed: 781
Visited Nodes=20000000

===================================================================================
x86_64 -O3   20'000'000 nodes
===================================================================================
Create random tree
Time Elapsed: 5795
GenRandomTree node count=20000000

Recursive DFT
Time Elapsed: 1609
Visited Nodes=20000000

Recursive DFT (avk)
Time Elapsed: 172
Visited Nodes=20000000

Iterarive DFT
Time Elapsed: 1890
Visited Nodes=20000000

Procedural DFT, custom pile (bk)
Time Elapsed: 234
Visited Nodes=20000000

Procedural DFT _1, TStack (bk) skipped because it is catastrophicaly slow in x86_64

===================================================================================
x86_64 -O3    40'000'000 nodes
===================================================================================
Create random tree
Time Elapsed: 11466
GenRandomTree node count=40000000

Recursive DFT
Time Elapsed: 3327
Visited Nodes=40000000

Recursive DFT (avk)
Time Elapsed: 360
Visited Nodes=40000000

Iterarive DFT fails for too many nodes

Procedural DFT, custom pile (bk)
Time Elapsed: 406
Visited Nodes=40000000

Procedural DFT _1, TStack (bk) skipped because it is catastrophicaly slow in x86_64
Title: Re: TTree depth-first traversal
Post by: avk on September 28, 2019, 02:24:05 pm
@BrunoK, well, that's what I was talking about. Contrary to popular belief, recursive DFS is faster than its iterative equivalent. The fastest iterative DFS I can write for this case is:
Code: Pascal  [Select][+][-]
  1. procedure DfsTraversal(aTree: TIntTree);
  2. var
  3.   Stack, TopNode: PTopNode;
  4.   Next: TTreeNode;
  5.   AllocCount: SizeInt = 32;
  6.   StackTop: SizeInt = 0;
  7. begin
  8.   if not Assigned(aTree.Root) then
  9.     exit;
  10.   Stack := GetMem(AllocCount * SizeOf(TTopNode));
  11.   Stack[StackTop] := TTopNode.Create(aTree.Root);
  12.   while StackTop >= 0 do
  13.     begin
  14.       TopNode := Stack + StackTop;
  15.       if SizeUInt(Succ(TopNode^.ChildPos)) < TopNode^.Node.Children.Size then
  16.         begin
  17.           Inc(TopNode^.ChildPos);
  18.           Next := TopNode^.Node.Children[TopNode^.ChildPos];
  19.           Inc(StackTop);
  20.           if StackTop = AllocCount then
  21.             begin
  22.               AllocCount += AllocCount;
  23.               ReallocMem(Stack, AllocCount * SizeOf(TTopNode));
  24.             end;
  25.           Stack[StackTop] := TTopNode.Create(Next);
  26.         end
  27.       else
  28.         Dec(StackTop);
  29.     end;
  30.   FreeMem(Stack);
  31. end;  
  32.  
But it is still slower than the recursive one (at least on my machine).
Title: Re: TTree depth-first traversal
Post by: BrunoK on September 29, 2019, 05:25:31 pm
@avk : revisited your 2 approaches. They give the same timings on my machine and are the fastest for DFT tree traversal code of any tested in this discussion.

Recursive - what changes is the extraction of Size in the inner procedure for iteration of children.
Code: Pascal  [Select][+][-]
  1. procedure TIntTree.DFTRecursive_avk(aTree: TIntTree; Callback: TTreeNodeCallBack
  2.   );
  3.   procedure Dfs(aNode: TIntNode);
  4.   var
  5.     I: SizeInt = 0;
  6.     lSize : Integer;
  7.   begin
  8.     Callback(aNode);
  9.     lSize := aNode.Children.Size;
  10.     while I < lSize do begin
  11.       Dfs(aNode.Children[I]);
  12.       Inc(I);
  13.     end;
  14.   end;
  15. var
  16.   lNode : TIntNode;
  17. begin
  18.   lNode := aTree.Root;
  19.   if Assigned(lNode) then
  20.     Dfs(lNode);
  21. end;
  22.  

Revisited iterative using pointers and hand made inlining. There the use of "with" improves the generated code.
Code: Pascal  [Select][+][-]
  1.  
  2. type
  3.   RPileItem = record
  4.     Node:      TIntNode;
  5.     ChildPos:  Integer;
  6.     Size:      Integer;
  7.   end;
  8.   PPileItem = ^RPileItem;
  9.  
  10. procedure TIntTree.DFTIterative_avk(aTree: TIntTree; Callback: TTreeNodeCallBack
  11.   );
  12. var
  13.   lStackAr : array of RPileItem;
  14.   lStackBase, lStackTop: PPileItem;
  15.   lNode : TIntNode;
  16. begin
  17.   lNode := aTree.Root;
  18.   if not Assigned(lNode) then
  19.     exit;
  20.   SetLength(lStackAr, cTreeDepth); // Constant cTreeDepth must be >= aTree.'Depth'
  21.   lStackBase := @lStackAr[0];
  22.   lStackTop := lStackBase - 1;
  23.   repeat
  24.     Callback(lNode); // Callback needed to check that all nodes where visited
  25.     Inc(lStackTop);
  26.     with lStackTop^ do begin
  27.       Node := lNode;
  28.       ChildPos := -1;
  29.       Size := lNode.Children.Size;
  30.     end;
  31.     repeat
  32.       with lStackTop^ do begin
  33.         Inc(ChildPos);
  34.         if ChildPos < Size then begin
  35.           lNode := Node.Children[ChildPos];
  36.           break;
  37.         end
  38.       end;
  39.       Dec(lStackTop);
  40.       if lStackTop < lStackBase then begin
  41.         lNode := nil;
  42.         break;
  43.       end;
  44.     until False;
  45.   until not Assigned(lNode);
  46. end;
  47.  

Title: Re: TTree depth-first traversal
Post by: avk on September 30, 2019, 04:47:29 am
@BrunoK, nice, thank you. It seems that the DFTRecursive_avk can be simplified without losing performance.
Code: Pascal  [Select][+][-]
  1. procedure TIntTree.DFTRecursive_avk(aTree: TIntTree; Callback: TTreeNodeCallBack);
  2.   procedure Dfs(aNode: TIntNode);
  3.   var
  4.     I: SizeInt;
  5.   begin
  6.     Callback(aNode);
  7.     for I := 0 to Pred(SizeInt(aNode.Children.Size)) do
  8.       Dfs(aNode.Children[I]);
  9.   end;
  10. begin
  11.   if Assigned(aTree.Root) then
  12.     Dfs(aTree.Root);
  13. end;
  14.  
You can also notice that the above procedures are not completely equivalent, DFTRecursive_avk does not make any assumptions regarding the depth of the tree, but DFTIterative_avk does.
TinyPortal © 2005-2018