flatten linked list bench

demo.py

import sys
from typing import Self, cast
import dataclasses

@dataclasses.dataclass(slots=False)
class Node:
    _parent: Self | None

MessagePump = Node
DOMNode = Node


def mk_nodes():
    node = Node(None)
    for i in range(1000000):
        node = Node(node)

    return node

def ancestors_with_self_orig(self):
    nodes: list[MessagePump | None] = [self]
    add_node = nodes.append
    node: MessagePump | None = self
    while (node := node._parent) is not None:
        add_node(node)
    return cast("list[DOMNode]", nodes)

def ancestors_with_self_orig_repeat_append_lookup(self):
    nodes: list[MessagePump | None] = [self]
    node: MessagePump | None = self
    while (node := node._parent) is not None:
        nodes.append(node)
    return cast("list[DOMNode]", nodes)


def ancestors_with_self_traditional(self):
    nodes = []
    node: Node | None = self

    while node is not None:
        nodes.append(node)
        node = node._parent

    return nodes

def ancestors_with_self_traditional_while_true(self):
    nodes = []
    node: Node | None = self

    while True:
        if node is None:
            return nodes

        nodes.append(node)
        node = node._parent


def ancestors_with_self_traditional_while_true_break(self):
    nodes = []
    node: Node | None = self

    while True:
        if node is None:
            break

        nodes.append(node)
        node = node._parent

    return nodes


import pyperf

def main():
    runner = pyperf.Runner()
    runner.timeit(name="flatten a linked list with a walrus",
                  stmt="demo.ancestors_with_self_orig(nodes)",
                  setup="import demo; nodes = demo.mk_nodes()")
    runner.timeit(name="flatten a linked list with a walrus, nodes.append(node)",
                  stmt="demo.ancestors_with_self_orig_repeat_append_lookup(nodes)",
                  setup="import demo; nodes = demo.mk_nodes()")
    runner.timeit(name="flatten a linked list tradition",
                  stmt="demo.ancestors_with_self_traditional(nodes)",
                  setup="import demo; nodes = demo.mk_nodes()")
    runner.timeit(name="flatten a linked list tradition while true",
                  stmt="demo.ancestors_with_self_traditional_while_true(nodes)",
                  setup="import demo; nodes = demo.mk_nodes()")
    runner.timeit(name="flatten a linked list tradition while true break",
                  stmt="demo.ancestors_with_self_traditional_while_true_break(nodes)",
                  setup="import demo; nodes = demo.mk_nodes()")


if __name__ == "__main__":
    sys.exit(main())

.....................
WARNING: the benchmark result may be unstable
* the standard deviation (5.40 ms) is 11% of the mean (51.2 ms)

Try to rerun the benchmark with more runs, values and/or loops.
Run 'python -m pyperf system tune' command to reduce the system jitter.
Use pyperf stats, pyperf dump and pyperf hist to analyze results.
Use --quiet option to hide these warnings.

flatten a linked list with a walrus: Mean +- std dev: 51.2 ms +- 5.4 ms
.....................
WARNING: the benchmark result may be unstable
* Not enough samples to get a stable result (95% certainly of less than 1% variation)

Try to rerun the benchmark with more runs, values and/or loops.
Run 'python -m pyperf system tune' command to reduce the system jitter.
Use pyperf stats, pyperf dump and pyperf hist to analyze results.
Use --quiet option to hide these warnings.

flatten a linked list with a walrus, nodes.append(node): Mean +- std dev: 46.6 ms +- 4.3 ms
.....................
WARNING: the benchmark result may be unstable
* the standard deviation (5.57 ms) is 11% of the mean (50.2 ms)

Try to rerun the benchmark with more runs, values and/or loops.
Run 'python -m pyperf system tune' command to reduce the system jitter.
Use pyperf stats, pyperf dump and pyperf hist to analyze results.
Use --quiet option to hide these warnings.

flatten a linked list tradition: Mean +- std dev: 50.2 ms +- 5.6 ms
.....................
WARNING: the benchmark result may be unstable
* Not enough samples to get a stable result (95% certainly of less than 1% variation)

Try to rerun the benchmark with more runs, values and/or loops.
Run 'python -m pyperf system tune' command to reduce the system jitter.
Use pyperf stats, pyperf dump and pyperf hist to analyze results.
Use --quiet option to hide these warnings.

flatten a linked list tradition while true: Mean +- std dev: 44.8 ms +- 3.4 ms
.....................
WARNING: the benchmark result may be unstable
* Not enough samples to get a stable result (95% certainly of less than 1% variation)

Try to rerun the benchmark with more runs, values and/or loops.
Run 'python -m pyperf system tune' command to reduce the system jitter.
Use pyperf stats, pyperf dump and pyperf hist to analyze results.
Use --quiet option to hide these warnings.

flatten a linked list tradition while true break: Mean +- std dev: 45.6 ms +- 4.4 ms