### Bookstore

 Computer Math and Games in Pascal (preview) Lazarus Handbook

### Author Topic: TTree depth-first traversal  (Read 4879 times)

#### jamie

• Hero Member
• Posts: 4343
##### Re: TTree depth-first traversal
« Reply #30 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 ?
The only true wisdom is knowing you know nothing

#### simone

• Sr. Member
• Posts: 378
##### Re: TTree depth-first traversal
« Reply #31 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 More than twenty years have passed since I last used them!
« Last Edit: September 23, 2019, 11:51:43 pm by simone »
Microsoft Windows 10 64 bit - Lazarus 2.0.10

#### avk

• Sr. Member
• Posts: 407
##### Re: TTree depth-first traversal
« Reply #32 on: September 24, 2019, 03:33:09 am »
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+}
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.

#### simone

• Sr. Member
• Posts: 378
##### Re: TTree depth-first traversal
« Reply #33 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)?
« Last Edit: September 24, 2019, 11:23:13 am by simone »
Microsoft Windows 10 64 bit - Lazarus 2.0.10

#### avk

• Sr. Member
• Posts: 407
##### Re: TTree depth-first traversal
« Reply #34 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,
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,
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.

#### Leledumbo

• Hero Member
• Posts: 8318
• Programming + Glam Metal + Tae Kwon Do = Me
##### Re: TTree depth-first traversal
« Reply #35 on: September 24, 2019, 11:10:58 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). 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.

#### julkas

• Guest
##### Re: TTree depth-first traversal
« Reply #36 on: September 25, 2019, 09:25:24 am »

#### avk

• Sr. Member
• Posts: 407
##### Re: TTree depth-first traversal
« Reply #37 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.

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.

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

#### marcov

• Global Moderator
• Hero Member
• Posts: 9220
• FPC developer.
##### Re: TTree depth-first traversal
« Reply #38 on: September 25, 2019, 03:43:34 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.

#### simone

• Sr. Member
• Posts: 378
##### Re: TTree depth-first traversal
« Reply #39 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
Microsoft Windows 10 64 bit - Lazarus 2.0.10

#### BrunoK

• Sr. Member
• Posts: 269
• Retired programmer
##### Re: TTree depth-first traversal
« Reply #40 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.

#### howardpc

• Hero Member
• Posts: 3675
##### Re: TTree depth-first traversal
« Reply #41 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.

#### BrunoK

• Sr. Member
• Posts: 269
• Retired programmer
##### Re: TTree depth-first traversal
« Reply #42 on: September 28, 2019, 10:45:06 am »
Edit :
In attachment pgmTreeDepthTrav_2.7z a test program mixing simone and rvk code.
In attachment pgmTreeDepthTrav_2.7z a test program mixing simone and avk code.

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.

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.

#### avk

• Sr. Member
• Posts: 407
##### Re: TTree depth-first traversal
« Reply #43 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.

#### BrunoK

• Sr. Member
• Posts: 269
• Retired programmer
##### Re: TTree depth-first traversal
« Reply #44 on: September 28, 2019, 01:30:09 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