perf: use a custom trie for path conflict validation by letFunny · Pull Request #302 · canonical/chisel

letFunny · 2026-06-10T11:12:05Z

Have you signed the CLA?

Copilot

Pull request overview

Note

Copilot was unable to run its full agentic suite in this review.

Introduces a trie-based conflict detector for slice path collisions and expands tests to cover more glob/double-glob conflict cases.

Changes:

Replaced the O(n²) glob/generate conflict scan in Release.validate() with a pathConflictTree-based detector.
Added extensive regression tests for glob conflicts and new focused unit tests for the conflict tree/segmenter.
Exposed internal conflict-tree types/helpers to external tests via export_test.go.

Reviewed changes

Copilot reviewed 5 out of 5 changed files in this pull request and generated 6 comments.

Show a summary per file

File	Description
internal/setup/setup.go	Switches validation to the new conflict-tree implementation.
internal/setup/conflict.go	Adds trie-based conflict detection and path segmentation logic.
internal/setup/setup_test.go	Adds multiple new test cases for glob/double-glob conflicts.
internal/setup/conflict_test.go	Adds unit tests for `pathToSegments` and the conflict tree structure.
internal/setup/export_test.go	Exports internal symbols to support `setup_test` package tests.

💡 Add Copilot custom instructions for smarter, more guided reviews. Learn how to get started.

Copilot

Pull request overview

Copilot reviewed 5 out of 5 changed files in this pull request and generated 6 comments.

letFunny · 2026-06-12T08:59:25Z

After some very light work on performance to improve the algorithm without added complexity (basically caching some data to avoid map lookups, iteration order, etc. *) the performance is:

Benchmark 1: BASE
  Time (mean ± σ):     14.511 s ±  0.071 s    [User: 15.039 s, System: 0.079 s]
  Range (min … max):   14.411 s … 14.617 s    10 runs
 
Benchmark 2: HEAD
  Time (mean ± σ):     151.2 ms ±   3.1 ms    [User: 181.2 ms, System: 18.6 ms]
  Range (min … max):   143.9 ms … 155.8 ms    19 runs
 
Summary
  'HEAD' ran
   95.96 ± 2.00 times faster than 'BASE'

*: All verified to reduce the number of cache misses using perf which is why the time also improves reliably.

upils

Thanks @letFunny ! I am amazed at how faster this is. I even looked at the messages we display to the user to see if we could remove any as this is now pretty much instantaneous.

The overall approach looks very sane. I could not find corner cases not handled properly. I have suggestions and questions but nothing that would change the approach.
This is definitely more complex than the previous implementation but the massive performance gains justify it I think.

upils

Thanks @letFunny. This is approved even though I think segmentEnd could be a bit more tweaked as suggested in the other comment. Feel free to move it to core review if you want to keep it like that or after this is fixed.

lczyk · 2026-07-10T06:46:21Z

+// explicit termination in the trie to distinguish them from parent directories
+// of other paths.
+func pathToSegments(path string) ([]segment, error) {
+	if path[0] != '/' {


Suggested change

if path[0] != '/' {

if path == "" || path[0] != '/' {

otherwise path[0] panics

i guess the error message needs adjusting or there should be two checks with different error messages then

aah! damn! sorry @letFunny / @upils i did not know the bot would do this. 😬 will do a comment and ping you in the future.

@lczyk See https://github.com/canonical/chisel/pull/302/files#discussion_r3389540125 :D

yep. the legitimate case i found was my own validation of this PR for which i wrote some fuzzers, and just directly called the fun. can be easily added if we ever add fuzzers here.

for reference, my fuzzers

all clean on 5m runs

Ty for looking into this

lczyk

i did some fuzzing to validate this PR and all looks green on 5m run. +1 from me :)

for reference, my fuzzers

lczyk · 2026-07-10T10:24:10Z

@letFunny FYI found some more speed (and memory) letFunny#29. i promise i'm going to stop tinkering now. 😅

lczyk · 2026-09-27T20:38:25Z

adding 'priority' because it's unbearable to open a new release and wait for all the chisel cut's.

so far ~413k cuts. we're ~1/2 way through, so ~830k for the whole 26.10 opening. each cut spends ~28s of its ~32s re-validating the release; with this PR that drops to ~0.3s. 830000 * 28 / 3600 ~= 6.4k vcpu-hours. some jobs can parallelise cuts a bit, so this actually goes down to ~120-220h of wall-clock time.

`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

niemeyer

Alright, thanks for your input @lczyk, and for exercising the PR. I have not had the time to sit down and review the heart of the algorithm in detail, but the algorithm is the product of extensive discussions on the topic that we had at the last sprint, so I'm comfortable with the theory behind it, and the surface that this touches on existing code is minimal, besides being functional and side-effect free in nature. The API and the testing is also elegant. So I'm giving it a vote of faith so we can stop the pain and benefit from the dramatic performance improvement.

letFunny force-pushed the performance-tree branch 3 times, most recently from d4113ef to b8da2e8 Compare June 10, 2026 11:29

perf: use a custom trie for path conflict validation

2191ba1

letFunny force-pushed the performance-tree branch from b8da2e8 to 2191ba1 Compare June 10, 2026 14:28

letFunny requested a review from Copilot June 10, 2026 15:25

Copilot AI reviewed Jun 10, 2026

View reviewed changes

letFunny added 3 commits June 12, 2026 10:02

trigger ci

99dd58b

address review

4c13443

make order deterministic

3f5d3f3

letFunny requested a review from Copilot June 12, 2026 08:16

Copilot AI reviewed Jun 12, 2026

View reviewed changes

address review

14a5a80

letFunny marked this pull request as ready for review June 12, 2026 08:46

This was referenced Jun 12, 2026

Try naive paralellism #294

Closed

perf: improve GlobPath performance #282

Closed

perf: improve release validation performance #279

Closed

letFunny requested a review from upils June 12, 2026 09:01

I had a great idea: simplify!

04318d9

upils suggested changes Jun 18, 2026

View reviewed changes

letFunny added 7 commits June 18, 2026 16:29

address review

b122990

segmentEnd returns the next character

985463a

new <-> old

7767813

more renaming

ae5d09b

comment

d2d3815

naming in tests

7a68e23

rearrange

825b71a

letFunny requested a review from upils June 18, 2026 15:07

upils approved these changes Jun 19, 2026

View reviewed changes

letFunny added 2 commits June 19, 2026 09:47

remove unneeded comment

66df398

change segmentEnd to be explicit over /

2e43258

lczyk suggested changes Jul 10, 2026

View reviewed changes

lczyk approved these changes Jul 10, 2026

View reviewed changes

lczyk mentioned this pull request Jul 10, 2026

perf: speed up path conflict detection letFunny/chisel#29

Closed

1 task done

This was referenced Sep 21, 2026

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

Merged

fix(26.10): more libssl4 canonical/chisel-releases#1188

Merged

lczyk added the Priority Look at me first label Sep 27, 2026

This was referenced Sep 27, 2026

fix(26.04): gnu-coreutils sort dlopens libcrypto canonical/chisel-releases#1263

Merged

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

Merged

niemeyer approved these changes Sep 28, 2026

View reviewed changes

niemeyer merged commit b8b8016 into canonical:main Sep 28, 2026
18 checks passed

This was referenced Sep 29, 2026

bug(ci): spread tasks time out on the s390x runners canonical/chisel-releases#1357

Closed

perf: even faster trie #327

Open

Conversation

letFunny commented Jun 10, 2026

Uh oh!

Copilot AI left a comment

Choose a reason for hiding this comment

Pull request overview

Reviewed changes

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Copilot AI left a comment

Choose a reason for hiding this comment

Pull request overview

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

letFunny commented Jun 12, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

upils left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

upils left a comment

Choose a reason for hiding this comment

Uh oh!

lczyk Jul 10, 2026

Choose a reason for hiding this comment

Uh oh!

lczyk Jul 10, 2026

Choose a reason for hiding this comment

Uh oh!

lczyk Jul 10, 2026

Choose a reason for hiding this comment

Uh oh!

upils Jul 10, 2026

Choose a reason for hiding this comment

Uh oh!

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

Uh oh!

Choose a reason for hiding this comment

Uh oh!

letFunny Jul 10, 2026

Choose a reason for hiding this comment

Uh oh!

lczyk left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

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

Uh oh!

Uh oh!

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

Uh oh!

Uh oh!

niemeyer left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

letFunny commented Jun 12, 2026 •

edited

Loading

lczyk Jul 10, 2026 •

edited

Loading

lczyk left a comment •

edited

Loading

lczyk commented Jul 10, 2026 •

edited

Loading

lczyk commented Sep 27, 2026 •

edited

Loading