microbenchmark

microbench.py

from typing import cast
class Tree:
    def accept(self, v: 'TreeVisitor') -> object:
        pass
class Leaf(Tree):
    def accept(self, v: 'TreeVisitor') -> object:
        return v.visit_leaf(self)
class Node(Tree):
    def __init__(self, value: int, left: Tree, right: Tree) -> None:
        self.value = value
        self.left = left
        self.right = right
    def accept(self, v: 'TreeVisitor') -> object:
        return v.visit_node(self)

class TreeVisitor:
    def visit_leaf(self, x: Leaf) -> object: pass
    def visit_node(self, x: Node) -> object: pass

class SumVisitor(TreeVisitor):
    def sum(self, x: Tree) -> int:
        return cast(int, x.accept(self))
    def visit_leaf(self, x: Leaf) -> object:
        return 0
    def visit_node(self, x: Node) -> object:
        return x.value + self.sum(x.left) + self.sum(x.right)

def sum_tree(x: Tree) -> int:
    return SumVisitor().sum(x)

def lol(n: int) -> Tree:
    if n == 0:
        return Leaf()
    child = lol(n - 1)
    return Node(n, child, child)

def bench_sum_tree(x: Tree) -> None:
    for i in range(100000):
        sum_tree(x)