aboutsummaryrefslogtreecommitdiff
path: root/lib/std/multi_array_list.zig
diff options
context:
space:
mode:
authorAndrew Kelley <andrew@ziglang.org>2021-06-25 12:50:18 -0700
committerAndrew Kelley <andrew@ziglang.org>2021-06-25 12:58:21 -0700
commit73f77f30804f3a512fbb35caad3d87ff2778ecc0 (patch)
treebcb3f80f6faea5847b83e6ed066c2fc3c4679306 /lib/std/multi_array_list.zig
parent49b3986417378278cef4157e71c38a817726ddc8 (diff)
downloadzig-73f77f30804f3a512fbb35caad3d87ff2778ecc0.tar.gz
zig-73f77f30804f3a512fbb35caad3d87ff2778ecc0.zip
AstGen: fix O(N^2) perf for many decls with same parent
AstGen was calling findLineColumn() for every sibling Decl, using the parent Decl as the starting point for the search for newlines. This resulted in poor performance for large numbers of Decls with the same parent. The solution is simple: since AstGen progresses monotonically through the AST, keep a single cursor into the source file, and whenever line/column information is needed, advance the cursor. This guarantees O(N) on the number of bytes in the file. Perf: As an example I ran ast-check on zigwin32/win32/everything.zig (a 17 MiB file) in master branch, and after this commit. With master branch, I killed the process after 17 seconds out of boredom. With this commit, it completed in 300 milliseconds. Closes #9234
Diffstat (limited to 'lib/std/multi_array_list.zig')
0 files changed, 0 insertions, 0 deletions