From 9f78ac0691ef55feda885780f21960e05c7a85a5 Mon Sep 17 00:00:00 2001 From: Anton Blanchard Date: Mon, 27 Sep 2021 11:00:56 +1000 Subject: [PATCH] hdl.ast: remove quadratic time complexity in Statement.cast(). Using `sum(lst, [])` to flatten a list of lists has quadratic time complexity. Use `chain.from_iterable()` instead. While not strictly necessary to improve performance, convert to `map()`. A test case writing out verilog for a 512k entry FIFO is 120x faster with this applied. --- nmigen/hdl/ast.py | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/nmigen/hdl/ast.py b/nmigen/hdl/ast.py index 1ccc446..685924a 100644 --- a/nmigen/hdl/ast.py +++ b/nmigen/hdl/ast.py @@ -4,6 +4,7 @@ import functools from collections import OrderedDict from collections.abc import Iterable, MutableMapping, MutableSet, MutableSequence from enum import Enum +from itertools import chain from .. import tracer from .._utils import * @@ -1404,7 +1405,7 @@ class Statement: @staticmethod def cast(obj): if isinstance(obj, Iterable): - return _StatementList(sum((Statement.cast(e) for e in obj), [])) + return _StatementList(list(chain.from_iterable(map(Statement.cast, obj)))) else: if isinstance(obj, Statement): return _StatementList([obj]) -- 2.30.2