def Append.message

bend-lint-rules@0.2.0.0 · performance/append_in_loop.bend:44

import Base
import bend-lint-api@0.2.0.0/linter/lint.bend as Lint

44# What a finding says about an append of `acc` in the loop `loop`. `args` are the append's arguments.
45def Append.message(
46  a: Append,
47  loop: String,
48  +acc: String,
49  +source: String,
50  +args: List<&2, Lint.Node>
51) -> String:
52  match a:
53    case ListAppend{}:
54      +q = Lint.Span.text(source, Lint.Node.span(List.get(&2, Lint.Node, args, 0n)))
55      +t = Lint.Span.text(source, Lint.Node.span(List.get(&2, Lint.Node, args, 1n)))
56      "List.append copies "
57        ++ acc
58        ++ " on each call of "
59        ++ loop
60        ++ ", so a loop of n steps copies O(n²) items. All lanes. Confidence: high, as the copies grow with the square of the steps. Add each item at the head instead, with `item <> "
61        ++ acc
62        ++ "`, and reverse "
63        ++ acc
64        ++ " once when the loop ends: `List.reverse("
65        ++ q
66        ++ ", "
67        ++ t
68        ++ ", "
69        ++ acc
70        ++ ")`; to add a list each step, collect the lists, with `piece <> pieces`, and join them once: `List.concat("
71        ++ q
72        ++ ", "
73        ++ t
74        ++ ", List.reverse("
75        ++ q
76        ++ ", List<"
77        ++ q
78        ++ ", "
79        ++ t
80        ++ ">, pieces))`. If the loop runs only a few steps, expect this finding."
81    case StringAppend{}:
82      "++ copies "
83        ++ acc
84        ++ " on each call of "
85        ++ loop
86        ++ ", so a loop of n steps copies O(n²) characters. CPU and GPU: measured 12.6 s for 20,000 lines, against 0.07 s after the fix. JS: strings join natively, at no cost. Confidence: high, as the copies grow with the square of the steps. Collect the pieces in a list instead, with `piece <> pieces`, and join them once when the loop ends: `String.concat(List.reverse(&2, String, pieces))`. If the loop runs only a few steps, expect this finding."