Nix Language - Public Room Timeline

	Nix Language	1925 Members
	Nix programming language	358 Servers

Load older messages

Sender	Message	Time
19 Jun 2026
llakala	* listDfs itself runs `tail` when recursing, which in the worst case (where all the elements are before the current one), makes it O(n^2)	00:01:08
hexa	yep, bingo	00:01:27
llakala	and then listDfs gets called once for every element in toposort	00:01:29
hexa	yep	00:01:40
llakala	thought so. i think i got it down to O(n^2) for hm, which has more axioms than we do	00:02:06
llakala	they consume the toposort function for their DAGs	00:02:16
llakala	but rather than taking a generic function (which can obey as few axioms as it wants), it stores `before` and `after` nodes	00:02:53
llakala	so i wrote this: toposort = let nixpkgsToposort = lib.toposort (a: b: elem a.name b.after); partitionNodes = partition (node: node.after == [ ]); getNames = catAttrs "name"; recurse = final: remaining: if remaining == [ ] then final else let partitioned = partitionNodes remaining; isRemovedName = flip elem (getNames partitioned.right); toporest = recurse (final ++ partitioned.right) ( map ( node: if any isRemovedName node.after then { inherit (node) name data; after = filter (name: !isRemovedName name) node.after; } else node ) partitioned.wrong ); in if partitioned.right == [ ] then # null represents a cycle null else toporest; in dag: let result = recurse [ ] dag; in # We defer to the nixpkgs function for returning exactly what the cycle was, # since tracking that is more expensive if result == null then nixpkgsToposort dag else { inherit result; };	00:03:01
llakala	in the case of a linear list with each node pointing to the next, this is O(n) for each iteration thanks to the `map` on `partitioned.wrong`	00:04:20
llakala	this still sucks. hypothetically, toposort can be done in O(n) steps	00:05:30
llakala	but i can't find a good way to achieve that in nix	00:06:25
llakala	so for now, i'm happy with O(n). i'll PR toposort in nixpkgs to mention its n^3 status	00:06:49
llakala	* so for now, i'm happy with O(n^2). i'll PR toposort in nixpkgs to mention its n^3 status	00:06:54
llakala	nevermind, i understand nothing. this is the growth rate of the nixpkgs toposort function for different input sizes `100 -> 200: x4.75 primops 200 -> 400: x3.47 primops 400 -> 800: x3.69 primops 800 -> 1600: x5.12 primops 1600 -> 3200: x3.44 primops`	01:28:57
llakala	my toposort function behaves sanely! `100 -> 200: x3.90 primops 200 -> 400: x3.95 primops 400 -> 800: x3.97 primops 800 -> 1600: x3.98 primops 1600 -> 3200: x3.99 primops`	01:30:09
llakala	Download image.png	01:46:01
llakala	nixpkgs toposort for different sized inputs	01:46:12
llakala	i've come to the conclusion that somehow the toposort function has an extreme performance dropoff as the input size reaches a new power of 10 Benchmark 1: nix-instantiate --eval --strict --expr '(import ./benchmark.nix)."999"' Time (mean ± σ): 244.7 ms ± 4.7 ms [User: 177.6 ms, System: 65.8 ms] Range (min … max): 238.5 ms … 256.3 ms 25 runs Benchmark 2: nix-instantiate --eval --strict --expr '(import ./benchmark.nix)."1000"' Time (mean ± σ): 245.9 ms ± 4.8 ms [User: 177.1 ms, System: 67.6 ms] Range (min … max): 239.4 ms … 258.7 ms 25 runs Benchmark 3: nix-instantiate --eval --strict --expr '(import ./benchmark.nix)."1001"' Time (mean ± σ): 392.6 ms ± 8.8 ms [User: 280.1 ms, System: 108.8 ms] Range (min … max): 381.2 ms … 411.2 ms 25 runs same thing happens at 99, 100, and 101	02:04:56
	andiandi 🐈 @ 🏰 HadR ☎️ 2634 changed their display name from andiandi 🐈 🏰 HadR ☎️ 2634@DECT to andiandi 🐈 @ 🏰 HadR ☎️ 2634.	07:55:53
alexfmpe	In reply to @llakala:matrix.org nevermind, i understand nothing. this is the growth rate of the nixpkgs toposort function for different input sizes `100 -> 200: x4.75 primops 200 -> 400: x3.47 primops 400 -> 800: x3.69 primops 800 -> 1600: x5.12 primops 1600 -> 3200: x3.44 primops` I love nix the concept, nixpkgs the repository of executable knowledge. But dear lord is nix a horrible language	12:06:14
alexfmpe	I once tried doing some DFS or BFS shenanigans	12:06:32
alexfmpe	I couldn't make heads or tails of running times	12:06:43
alexfmpe	A good deal was probably from me getting confused by lazyness but still	12:07:04
alexfmpe	In reply to @llakala:matrix.org i've come to the conclusion that somehow the toposort function has an extreme performance dropoff as the input size reaches a new power of 10 Benchmark 1: nix-instantiate --eval --strict --expr '(import ./benchmark.nix)."999"' Time (mean ± σ): 244.7 ms ± 4.7 ms [User: 177.6 ms, System: 65.8 ms] Range (min … max): 238.5 ms … 256.3 ms 25 runs Benchmark 2: nix-instantiate --eval --strict --expr '(import ./benchmark.nix)."1000"' Time (mean ± σ): 245.9 ms ± 4.8 ms [User: 177.1 ms, System: 67.6 ms] Range (min … max): 239.4 ms … 258.7 ms 25 runs Benchmark 3: nix-instantiate --eval --strict --expr '(import ./benchmark.nix)."1001"' Time (mean ± σ): 392.6 ms ± 8.8 ms [User: 280.1 ms, System: 108.8 ms] Range (min … max): 381.2 ms … 411.2 ms 25 runs same thing happens at 99, 100, and 101 Oddly specific. Maybe some util is called chunking/partioning things into 10 pieces recursively? Then crossing to 10^n+1 territory means one more level of depth	12:10:02
llakala	you'd think so... but the entire code is two functions, both of which I've read	12:24:02
llakala	hang on I'll link it	12:25:22
llakala	https://github.com/NixOS/nixpkgs/blob/805dc355c3c19ceca8b2dc2726d4f0414a64322e/lib/lists.nix#L1246	12:26:12
llakala	just toposort and listDfs	12:26:32
alexfmpe	maybe it happens at the nix impl level? quickly grepping on NixOS/nix gives me nothing obvious though	12:41:08
alexfmpe	but that's the first thing that comes to mind when things magically get slower with lists of size 10^n+1	12:41:38

Show newer messages

Back to Room ListRoom Version: 6