perf: speed up path conflict detection by lczyk · Pull Request #29 · letFunny/chisel

lczyk · 2026-07-10T10:22:04Z

Have you signed the CLA?

two optimisations for pathConflictTree, on top of the trie from this branch. no behaviour change intended: same conflicts detected, same error type. tests pass unchanged. checked with my fuzz tests too.

perf: use a custom trie for path conflict validation canonical/chisel#302

1. reuse the traversal queues (`f449d7a`)

pathHasConflict used to grow currentQueue and nextQueue from nil on every path insertion, and seeded the first level with slices.Collect(maps.Values(...)). with a few thousand paths this dominated allocation: the queues were the single largest source of gc work in the whole conflict check.

i've changed currentQueue and nextQueue to fields on pathConflictTree, reset with [:0] per call and restored through a defer, so the backing arrays are grown once and reused.

proof of gc work (drop somewhere in internal/setup):

func BenchmarkConflictAlloc(b *testing.B) {
      paths := map[string][]*setup.Slice{}
      for i := 0; i < 1000; i++ {
              pkg := fmt.Sprintf("pkg%04d", i)
              p := "/usr/bin/" + pkg + "-*"
              paths[p] = []*setup.Slice{{Package: pkg, Name: "s",
                      Contents: map[string]setup.PathInfo{p: {Kind: setup.GlobPath}}}}
      }
      for i := 0; i < b.N; i++ {
              tree := setup.NewConflictTree(paths)
              if err := tree.HasConflict(); err != nil {
                      b.Fatal(err)
              }
      }
}

$ go test ./internal/setup/ -run '^$' -bench ConflictAlloc -benchtime 20x \
  -memprofile /tmp/mem.prof -o /tmp/base.test
$ go tool pprof -list 'pathHasConflict$' -sample_index=alloc_space /tmp/base.test /tmp/mem.prof | grep -E '(nextQueue =|of Total)'
  218.43MB   218.43MB (flat, cum) 90.63% of Total
  218.43MB   218.43MB    156:								nextQueue = append(nextQueue, child)
$ GODEBUG=gctrace=1 go test ./internal/setup/ -run '^$' -bench ConflictAlloc -benchtime 20x 2>&1 | grep '^gc ' | wc -l
     149

after:

$ go tool pprof -list 'pathHasConflict$' -sample_index=alloc_space /tmp/base.test /tmp/mem.prof | grep -E '(nextQueue =|of Total)'
  514.38kB   514.38kB (flat, cum)  1.72% of Total
         .          .    111:		g.currentQueue, g.nextQueue = currentQueue, nextQueue
  514.38kB   514.38kB    166:								nextQueue = append(nextQueue, child)
$ GODEBUG=gctrace=1 go test ./internal/setup/ -run '^$' -bench ConflictAlloc -benchtime 20x 2>&1 | grep '^gc ' | wc -l
      40

2. exact-match child lookup (`3c097a7`)

when a segment matched, the old traversal enqueued every child of the matched node and compared each one against the next segment on the following round. but Children is already keyed by segment text, so for a literal next-segment the only children that can possibly match are the one with the identical text and
any child whose segment holds a wildcard.

now appendCandidates does and exact map lookup, plus a scan of the new node.GlobChildren list. a wildcard next-segment still considers every child, since it can match anything. glob-vs-glob comparisons are unchanged.

this turns the linear sibling scan in wide directories into a map lookup. real chisel-releases paths are at present aboout ~60% literal directories and this speeds this up, especially because the wide nodes tend to also be mostly literal so the quadratic scan hurts a lot there).

proof, with fix 1 above applied, otherwise GC noise swamps the signal:

func BenchmarkConflictWideDir(b *testing.B) {
      for _, n := range []int{1250, 2500, 5000} {
              paths := map[string][]*setup.Slice{}
              for i := 0; i < n; i++ {
                      pkg := fmt.Sprintf("pkg%04d", i)
                      p := fmt.Sprintf("/usr/share/doc/file%05d", i)
                      paths[p] = []*setup.Slice{{Package: pkg, Name: "s",
                              Contents: map[string]setup.PathInfo{p: {Kind: setup.CopyPath}}}}
              }
              b.Run(fmt.Sprintf("files=%d", n), func(b *testing.B) {
                      for i := 0; i < b.N; i++ {
                              tree := setup.NewConflictTree(paths)
                              if err := tree.HasConflict(); err != nil {
                                      b.Fatal(err)
                              }
                      }
              })
      }
}

$ go test ./internal/setup/ -run '^$' -bench ConflictWideDir -count=1 | grep 'BenchmarkConflictWideDir'
BenchmarkConflictWideDir/files=1250-8         	      68	  14806423 ns/op
BenchmarkConflictWideDir/files=2500-8         	      16	  69988763 ns/op
BenchmarkConflictWideDir/files=5000-8         	       4	 273993969 ns/op

after:

go test ./internal/setup/ -run '^$' -bench ConflictWideDir -count=1 | grep 'BenchmarkConflictWideDir'
BenchmarkConflictWideDir/files=1250-8         	    1753	    679446 ns/op
BenchmarkConflictWideDir/files=2500-8         	     903	   1294642 ns/op
BenchmarkConflictWideDir/files=5000-8         	     466	   2629180 ns/op

Add workshop configuration, with agent SDKs to enable standard agent-based work.

Some package stores only publish SHA3-384 hashes. This PR enables storing entries in the cache using SHA3-384 hashes. Consumers of the cache package must now explicitly select the algorithm to be used to create/write/read an entry.

Chisel intermittently fails with `expected digest X, got Y` when Ubuntu's archive is mid-publication and InRelease is temporarily inconsistent with `Packages.gz` at the named path (a window we observed lasting at least 39 minutes against the same publication in real CI runs for [Ella Core](https://github.com/ellanetworks/core)). Fetch the package index by content hash using apt's `Acquire-By-Hash` , which Ubuntu archives have advertised since 16.04 (2016), so the URL itself encodes the expected bytes; falls back to the named path when an archive doesn't advertise the feature or a specific hash has been garbage-collected. Fixes canonical#295 Reference: https://wiki.debian.org/DebianRepository/Format#Acquire-By-Hash

This refactoring PR moves the package-format-agnostic extraction logic (glob matching, hard-link two-pass handling, parent-directory permission preservation) out of deb and into a new tarball package, leaving deb with only the deb-specific DataReader (the ar + data.tar.* opener). This is a pure, behavior-preserving refactor, no logic was altered — only relocated. It prepares the ground for adding an XZ-strict data reader to enable bin package extraction.

This PR is the first step to support the `bin` package kind in Chisel. It introduces the `Store` concept and reworks the package naming model so that `Package.Name` is always a **unique** identifier across the release, while the new `Package.RealName` field preserves the bare name of the package needed for package lookups. It adds support for: - a `stores` section in `chisel.yaml` - `store` and `default-track` fields in slice definition files. The fetching and extraction of the corresponding bins will be implemented in a following PR.

Since Snapcraft 8.12, track and arch are repeated on each line of `snapcraft status` when piping the output. See canonical/snapcraft#5720 This fix get the right field from the awk parsing.

letFunny

Thank you looking into this Marcin, I added comment about each improvement but basically IMO one of them should certainly go in, and for the other one we can discuss it.

With that said, I think it is better if we wait for the original PR to be merged. I spoke with Gustavo and he was very clear in that he didn't want to pile up more improvements; he wanted to have a clear algorithm first then improve it later. Let's do the following, once the original PR is merged you can create a new PR with these improvements, I wouldn't want to claim authorship :)

letFunny · 2026-07-13T08:42:49Z

 type pathConflictTree struct {
 	Root         *node
 	PathToSlices map[string][]*Slice
+	// currentQueue and nextQueue are kept across pathHasConflict calls so


When writing the original PR I cached the queues, then I removed it, then added it back, etc. and in the end I don't have a strong opinion on whether to do it or not. It obviously increases performance (around 20% on my machine, so 20ms out of 100ms). The only reason I didn't add it from the get go was a similar case in the past where there was an optimization by caching the results and Gustavo argued against it as it increased the complexity.

After seeing you came up with the same idea I think we should start the debate again.

letFunny · 2026-07-13T08:45:21Z

 	Segment       segment
 	SegmentSlices []*segmentSlice
 	Children      map[string]*node
+	// GlobChildren lists the children whose segment contains a wildcard, so


This is very interesting. I didn't expect such a simple change to have 25% improvement (my machine). I had done another more complex optimization for looking for candidates that had the same % improvement but the implementation was far worse.

I think we should go for this one.

lczyk · 2026-07-13T09:43:20Z

yep. no problem :)) happy to submit it afterwards and yeah, i agree that it's better to split them. i wanted to look into this now in case 1) there would be a l-line improvement or 2) there would be a bigger perf gain but behind some slight reengineer which might as well land at this stage. none of those are the case and yeah, this PR can easily go in afterwards.

re the improvements here; they are somewhat coupled, bit throughout but through effect. i did add this line from my initial message, but it's just one and maybe i should have been clearer about it:

proof, with fix 1 above applied, otherwise GC noise swamps the signal: ...

fix 2 by itself works ok, but does induce much more GC pressure w/out fix 1.

tbd after your bade PR is merged and we send this one in, i think 👍

This is a CI security enhancement. In canonical#284, we improved the security of the build CI workflow, ensuring the whole CI job wouldn't have unnecessary write permissions to the repository, instead shifting towards a fine grained personal token that would only be used within a single, conditional step that only ran on GitHub release events. NEW: this PR goes one step further by removing the need to have a bot account (which owns the aforementioned fine grained personal token) with write permissions in the repository's collaborators list. Instead, this PR splits the privileged step into a separate privileged job. This means the new job can use the ephemeral GITHUB_TOKEN to perform the privileged step, without giving unnecessary privileges to other jobs&steps of the workflow. Closes: canonical#308

@FinnRG

- [x] Have you signed the [CLA](http://www.ubuntu.com/legal/contributors/)? ----- Attempted fix for canonical#305. Resolve digests through a small preference list (strongest first: `SHA512`, then `SHA256`) instead of hardcoding one field, and carry the hash kind alongside the digest so downloads are verified and cached with the matching algorithm. This covers: - the Release index table (`Packages` digest), - the per-package digest (the `.deb`), and - the `Acquire-By-Hash` path merged from main, which now builds `by-hash/<algo>/<digest>` URLs from the resolved field rather than assuming `by-hash/SHA256/`. Archives only guarantee a by-hash directory for the *strongest* hash they advertise, so the by-hash URL must be built from that one -- thanks @FinnRG for catching this. Since the preference list is strongest-first, the resolved field is already the right one, and a single ordering serves both purposes. As of this writing Stonking publishes SHA512 only, in the base suite and in `-security`/`-updates` alike, so the whole suite resolves via SHA512. Resolute and earlier remain SHA256-only An archive advertising *both* digests, content is now verified and cached under its SHA512 digest rather than its SHA256 one. Cache entries written by an older chisel are keyed by SHA256, so they go cold and are fetched once more, then expire normally (which, at the moment means they don't expire canonical#261, but that's a separate issue). Nothing gets corrupted. Importantly, at present no archive Chisel targets advertises both digests (Resolute is `SHA256`-only, Stonking is `SHA512`-only), so in practice this is not a behaviour change. ### Testing Added unit tests for the new behaviour and tested manually against the Stonking archive. The by-hash tests cover the four archive shapes: a by-hash directory for the strongest hash only, directories for several hashes (as Stonking actually publishes), a directory for a weaker hash only (a buggy archive, falls back to the named path), and no by-hash directories at all. ### Out of scope Something i've deliberately decided is out of scope but really **should be fixed** in a followup: The manifest's per-package digest still reads `SHA256`, so on a SHA512-only archive it still errors. Most `chisel cut`'s still work unless the user requests the manifest to be cut too.

Introduce a manifestutil.PackageInfo interface to keep a clear separation of concerns: the manifest is built from whatever a package source reports, not from archive-specific data. As a result, manifestutil no longer depends on archive; archive.PackageInfo keeps its apt-native fields and gains Pkg-prefixed accessors to satisfy the interface. validatePackage now rejects non-SHA256 digests, with a TODO marking recording store digests as future work. This prepares fetching and recording of store bins without changing current behavior.

Add default maintenance values for 25.10 and 26.04.

…ical#313) When an Ubuntu release passes its end-of-life date, Chisel routes to old-releases.ubuntu.com. However, the physical migration of the suite to that mirror is a manual admin operation that can lag the scheduled EOL — so for recently-EOL releases (e.g. 25.04, 25.10), old-releases returns 404 and archive.Open fails, blocking rootfs cuts. archiveURL became candidateArchiveURLs, returning the base URLs to try in order of preference (old-releases first, current archive as fallback for old releases). openUbuntu now attempts a full open against each candidate, falling back only on a missing release (404) — auth, network or signature errors still fail immediately, so a broken archive is never masked. The index-opening flow was extracted into ubuntuArchive.setupIndexes so it can be retried per candidate without duplicate downloads: the winning candidate's InRelease fetch is the one used going forward.

`CHISEL_HACKS=1` used to make `chisel-hacked` skip release validation entirely. now it runs the full `validate()`, with the trie from canonical/chisel#302 in place of the quadratic path conflict loop, plus the letFunny/chisel#29 speedups on top. with `CHISEL_HACKS` unset it behaves like upstream. release | before (no skip) | trie | no validation ---|---|---|--- 22.04 | 2.2s | 43ms | 42ms 24.04 | 16.7s | 131ms | 96ms 26.04 | 13.6s | 87ms | 59ms 26.10 | 11.8s | 74ms | 48ms

Add scaffolding for agent-agnostic agent workflows. At least two more directories could benefit from a dedicated KB, internals/slicer and internal/setup but I want to keep this PR focus on the scaffolding.

The traversal queues regrew from nil on every path insertion, which accounted for ~90% of allocated bytes. BenchmarkConflictTree/pkgs=1000: -91% B/op, -37% allocs/op, -17% sec/op.

A literal segment scanned every sibling node linearly even though Children is keyed by segment text. Look up the exact child directly and scan only wildcard children, tracked in a new GlobChildren list. BenchmarkConflictTree/pkgs=1000: -70% sec/op; DeepPaths: -85% sec/op.

bumps the chisel pin v1.5.0 -> v1.5.1. upstream v1.5.1 = #325 (maintenance dates), #313 (current-archive fallback for recently-eol releases), #302 (trie path conflict check) and #290 (AGENTS.md only). - 0003 dropped -- it was our gated backport of #302, which is now upstream and ungated. - 0004 (letFunny/chisel#29, faster trie traversal) applies cleanly on v1.5.1's `conflict.go`, but with 0003 gone it would have run unconditionally. it now carries its own gate: `newConflictTree` sets a `Fast` flag from `CHISEL_HACKS=1`; unset = upstream's traversal (every child a candidate, fresh queues per path). - 0001 / 0002 unchanged, `cmd_cut.go` is byte-identical between the two tags. - contract test + release blurb updated to v1.5.1. tested: - chisel `go test ./...` with patches applied, in `ubuntu/go:1.25-26.04_edge`: all green with and without `CHISEL_HACKS=1`. `internal/setup` 2.2s -> 0.9s with it set. - `make binaries ARCH=arm64` ok; `chisel-hacked --version` -> `v1.5.1-hacked`. - `bread-chisel-releases:{22.04,24.04,25.10,26.04,26.10}-arm64` built, `chisel` / `chisel-hacked --version` both report `v1.5.1-hacked`. - full spread suite not run locally (outer backend needs `flock`, macOS host) -- leaning on ci for that + amd64 / s390x / ppc64le.

lczyk · 2026-10-09T02:20:25Z

closing in favour of canonical#327

upils and others added 6 commits June 15, 2026 18:33

build(workshop): add initial workshop configuration (canonical#297)

d9040ff

Add workshop configuration, with agent SDKs to enable standard agent-based work.

feat: support SHA384 for cache entries (canonical#298)

23fc7e4

Some package stores only publish SHA3-384 hashes. This PR enables storing entries in the cache using SHA3-384 hashes. Consumers of the cache package must now explicitly select the algorithm to be used to create/write/read an entry.

chore: improve comment in strdist (canonical#301)

eb3a622

docs: update README to include documentation section (canonical#303)

ea61b84

lczyk mentioned this pull request Jul 10, 2026

perf: use a custom trie for path conflict validation canonical/chisel#302

Merged

1 task done

upils added 2 commits July 10, 2026 13:48

ci: fix snap promote revision parsing (canonical#304)

3323d36

Since Snapcraft 8.12, track and arch are repeated on each line of `snapcraft status` when piping the output. See canonical/snapcraft#5720 This fix get the right field from the awk parsing.

letFunny approved these changes Jul 13, 2026

View reviewed changes

cjdcordeiro and others added 3 commits August 7, 2026 17:17

lczyk mentioned this pull request Sep 21, 2026

feat(26.10): subslice coreutils canonical/chisel-releases#1193

Merged

3 tasks done

upils added 2 commits September 21, 2026 20:45

chore: update default maintenance for recent releases (canonical#325)

177035e

Add default maintenance values for 25.10 and 26.04.

lczyk mentioned this pull request Sep 27, 2026

perf: trie conflict check in chisel-hacked lczyk/spread-bread#41

Merged

letFunny and others added 4 commits September 28, 2026 16:22

perf: use a custom trie for path conflict validation (canonical#302)

b8b8016

ai: prepare for agentic workflows (canonical#290)

0a817bd

Add scaffolding for agent-agnostic agent workflows. At least two more directories could benefit from a dedicated KB, internals/slicer and internal/setup but I want to keep this PR focus on the scaffolding.

perf: reuse conflict traversal queues

06a1c52

The traversal queues regrew from nil on every path insertion, which accounted for ~90% of allocated bytes. BenchmarkConflictTree/pkgs=1000: -91% B/op, -37% allocs/op, -17% sec/op.

lczyk force-pushed the perf/tree-perf-improvements branch from 3c097a7 to abb0ccc Compare September 29, 2026 07:09

lczyk mentioned this pull request Sep 29, 2026

perf: even faster trie canonical/chisel#327

Open

1 task done

lczyk mentioned this pull request Oct 8, 2026

chore(deps): bump chisel to v1.5.1 lczyk/spread-bread#42

Merged

lczyk closed this Oct 9, 2026

Navigation Menu

Repository navigation

perf: speed up path conflict detection - #29

perf: speed up path conflict detection#29
lczyk wants to merge 17 commits into
letFunny:performance-treefrom
lczyk:perf/tree-perf-improvements

lczyk commented Jul 10, 2026 •

edited

Loading

Uh oh!

letFunny left a comment

Uh oh!

letFunny Jul 13, 2026

Uh oh!

letFunny Jul 13, 2026

Uh oh!

lczyk commented Jul 13, 2026

Uh oh!

lczyk commented Oct 9, 2026

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

Conversation

lczyk commented Jul 10, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

1. reuse the traversal queues (f449d7a)

2. exact-match child lookup (3c097a7)

Uh oh!

letFunny left a comment

Choose a reason for hiding this comment

Uh oh!

letFunny Jul 13, 2026

Choose a reason for hiding this comment

Uh oh!

letFunny Jul 13, 2026

Choose a reason for hiding this comment

Uh oh!

lczyk commented Jul 13, 2026

Uh oh!

lczyk commented Oct 9, 2026

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

lczyk commented Jul 10, 2026 •

edited

Loading

1. reuse the traversal queues (`f449d7a`)

2. exact-match child lookup (`3c097a7`)