Well in my search for always, wanting to write faster code and typically find ways of writing code which don't rely on recursive function calling to solve problems, I had an idea, to look abstraction recursive calling solutions into non-recusive solution, that facilitates the recursive behaviour. I manage to do this, which mean writing recursive solutions in this slightly simple transformed way with some bootstrap code, which actually yields higher performance than natural recursive functional calling. I believe that the performance could still be improved further especially for function with more than 2 recusive function calls to its self. Typically this could be achieved in c++, however, I think may be best to look at an official construct, that simplify this. Typicall a compiler could transform code to this as well, but I am not working on that. SO in C/C++, one should be able to further performance gains, as jump to variable contain instruction offset, so no conditional evaluations required.
So the suggestion is to basically implement jmp or goto, that allows direct relative instruction jump at cpu level compiled code. Currently, a switch statement would be needed and longer it gets the more conditionals there would be. So to improve performance, special construct.
- Ability for jump statement, to jump to a numerical variable or enumerator, where the type is constrained to specific values or the type for the parent block of code can be determine by the compiled that it can't obtain a different value. Otherwise it could include a range check with invalid case or throw of an error. either way code can still be speed up.
CaseJump
variablevariableptrBlock, if an enum can be translated to backing numerical, in which no range check is required. Then case jump, will actually translate the case identifiers to CPU instruction stack offset,
such that it can just jump. so i++ would basically be translated to an assignment or compiler dependent and arr of fixed offsets.
In this case it may be better.
label: casejump variableptrBlock(numerical/enum) {
case 0: continue label or recall
case 1:recall label
case 2:recall;// the parameters wold be left to the operator, as optermize them for there usuage.
default:
range:
}
CaseJump Stack and pos, totally managed
One could actually just have word case wit no numerical and the compiler just at end of the block updates the variable, it would need to know the stack offset however.
Thinking that this would be correct.
('casejump' or 'recase') (Instructionstack, pos) {
case : {
additional of stack parameters for positions pos.
recall({stack[pos] = NodeIt =NodeIt.left}) // this is an masync block of code, ran be run at the same time concurrent in registers.
}
case :
// Or manually you can also update the stack, have to call pos++ first or maybe statement recallinit followed by recall, where recallinit, increment pos and recall actually terminate, but just use return or break So recall with no paraters increments pos and basically break, would be the last line of code after parameters have been put on the stack.
case :
default:
range:
}
There of course is caching of the current parameter values, to prevent using indexing to look them up again, which also results in performance gain, the language compiler could improve this further, in back group.
More thought I not sure how to communicate cache variable to accelerate arr[pos] access look ups of specific stacks data type stacks for different parameters.
Performance Benchmark Code
Custom recursive function calling transformed non-recusive stack program
Code is between 300-1.2 second faster or equivalent performance in worst cases.
let node = {
left: {
left: {
left: {
left: {
value: 1,
right: {
left:{
value:1.2
},
value: 1.5
}
},
value: 2,
right: {
value: 3
}
},
value: 4,
right: {
left: {
value: 5
},
value: 6,
right: {
value: 7
}
}
},
value: 8,
right: {
left: {
left: {
value:9
},
value:10,
right: {
value:11
}
},
value: 12,
right: {
left: {
value: 13
},
value: 14,
right: {
value: 15
}
}
}
},
value: 16,
right: {
left: {
left: {
left: {
value: 17
},
value: 18,
right: {
value: 19
}
},
value: 20,
right: {
left: {
value: 21
},
value: 22,
right: {
value: 23
}
}
},
value: 24,
right: {
left: {
left: {
value:25
},
value:26,
right: {
value:27
}
},
value: 28,
right: {
left: {
value: 29
},
value: 30,
right: {
value: 31
}
}
}
}
}
function depthFirstWalk55(node) {
const start = new Date();
for (let i = 0; i < 50000000;i++) {
let arr = [];
let nodeIt = node;
let instruction = true;
let instStack = new Array(10); // must be intialized to the max binary tree height or any data structure, which cache variable kept upto date.
instStack[0] = instruction;
let stack = new Array(10);
stack[0] = nodeIt;
let pos = 0;
while (true) {
if(instruction === true) {
instruction = false;
instStack[pos] = instruction;
if (nodeIt.left != null) {
pos += 1;
nodeIt = nodeIt.left;
stack[pos] = nodeIt;
instruction = true;
instStack[pos] = instruction;
}
} else {
arr.push(nodeIt.value);
if (nodeIt.right != null) {
nodeIt = nodeIt.right;
stack[pos] = nodeIt;
instruction = true;
instStack[pos] = instruction;
}
else {
pos -= 1;
if (pos === -1) {
break;
}
nodeIt = stack[pos];
instruction = instStack[pos];
}
}
}
}
const end = new Date();
console.log("diff:" + (end.getTime() - start.getTime()))
//return arr;
}
*Typically recursive method
function depthFirstWalk8(node) {
const start = new Date();
function print(arr, node) {
if (node.left != null) {
print(arr, node.left);
}
arr.push(node.value);
if (node.right != null) {
print(arr, node.right);
}
}
for (let i = 0; i < 50000000;i++) {
let arr = [];
print(arr, node);
}
const end = new Date();
console.log("diff:" + (end.getTime() - start.getTime()))
//return arr;
}
Stats
diff:46438
diff:47153
diff:45716
diff:46981
diff:45389
diff:47021
diff:47289
diff:48164
diff:47147
diff:48994