Skip to content

tsort: use iterative dfs to prevent stack overflows#8737

Merged
sylvestre merged 1 commit intouutils:mainfrom
Nekrolm:tsort-no-recursion
Oct 28, 2025
Merged

tsort: use iterative dfs to prevent stack overflows#8737
sylvestre merged 1 commit intouutils:mainfrom
Nekrolm:tsort-no-recursion

Conversation

@Nekrolm
Copy link
Contributor

@Nekrolm Nekrolm commented Sep 24, 2025 •
edited
Loading

Rewrite DFS method in iterative way to avoid stack overflows

Closes #8695

PR is on top of #8694
but changes are independent. Only top commit can be cherry-picked, if needed

@sylvestre
Copy link
Contributor

sylvestre commented Sep 24, 2025

please add a test that trigger the stackoverflow

@codspeed-hq
Copy link

codspeed-hq bot commented Sep 24, 2025 •
edited
Loading

CodSpeed Performance Report

Merging #8737 will improve performances by 54.11%

Comparing Nekrolm:tsort-no-recursion (1244caf) with main (c85d8b5)

Summary

⚡ 1 improvement
✅ 104 untouched
⏩ 74 skipped1

Benchmarks breakdown

Benchmark BASE HEAD Change
⚡ tsort_input_parsing_heavy[50000] 12.8 s 8.3 s +54.11%

Footnotes

  1. 74 benchmarks were skipped, so the baseline results were used instead. If they were deleted from the codebase, click here and archive them to remove them from the performance reports. ↩

@github-actions
Copy link

github-actions bot commented Sep 24, 2025

GNU testsuite comparison:

Skip an intermittent issue tests/misc/tee (fails in this run but passes in the 'main' branch)
Skipping an intermittent issue tests/timeout/timeout (passes in this run but fails in the 'main' branch)

@github-actions
Copy link

github-actions bot commented Sep 25, 2025

GNU testsuite comparison:

Skipping an intermittent issue tests/timeout/timeout (passes in this run but fails in the 'main' branch)

@Nekrolm Nekrolm force-pushed the tsort-no-recursion branch 2 times, most recently from 86c8710 to f5dfb27 Compare September 25, 2025 10:03
@github-actions
Copy link

github-actions bot commented Sep 25, 2025

GNU testsuite comparison:

Skip an intermittent issue tests/misc/tee (fails in this run but passes in the 'main' branch)

@Nekrolm Nekrolm force-pushed the tsort-no-recursion branch 4 times, most recently from 90ac3c2 to 8f0bf8b Compare September 25, 2025 11:43
@Nekrolm Nekrolm mentioned this pull request Sep 25, 2025
Open
@github-actions
Copy link

github-actions bot commented Sep 25, 2025

GNU testsuite comparison:

Skipping an intermittent issue tests/misc/tee (passes in this run but fails in the 'main' branch)

@github-actions
Copy link

github-actions bot commented Sep 29, 2025

GNU testsuite comparison:

Skipping an intermittent issue tests/misc/tee (passes in this run but fails in the 'main' branch)
Skipping an intermittent issue tests/tail/overlay-headers (passes in this run but fails in the 'main' branch)

@Nekrolm Nekrolm force-pushed the tsort-no-recursion branch 2 times, most recently from 34d5994 to 4ae348d Compare October 2, 2025 13:11
@github-actions
Copy link

github-actions bot commented Oct 2, 2025

GNU testsuite comparison:

Skipping an intermittent issue tests/tail/overlay-headers (passes in this run but fails in the 'main' branch)

@Nekrolm
Copy link
Contributor Author

Nekrolm commented Oct 2, 2025

Hope, eventually all unrelated tests pass :)

@Nekrolm
Copy link
Contributor Author

Nekrolm commented Oct 2, 2025 •
edited
Loading 

/// Generate DAG data for input parsing stress tests
fn generate_input_parsing_heavy(num_edges: usize) -> Vec<u8> {
    // Create a scenario with many edges but relatively few unique nodes
    // This stresses the input parsing and graph construction optimizations
    let num_unique_nodes = (num_edges as f64).sqrt() as usize;
    let mut data = Vec::new();

    for i in 0..num_edges {
        let from = i % num_unique_nodes;
        let to = (i / num_unique_nodes) % num_unique_nodes;
        if from != to {
            data.extend_from_slice(format!("n{from} n{to}\n").as_bytes());
        }
    }

    data
}

It's not necessary a DAG.
It most likely has cycles -- that's why dfs optimization improved this test :)

@Nekrolm Nekrolm force-pushed the tsort-no-recursion branch from 4ae348d to 17f10b8 Compare October 7, 2025 19:17
@github-actions
Copy link

github-actions bot commented Oct 7, 2025

GNU testsuite comparison:

Skipping an intermittent issue tests/timeout/timeout (passes in this run but fails in the 'main' branch)

@Nekrolm Nekrolm force-pushed the tsort-no-recursion branch from 17f10b8 to 6baaf65 Compare October 13, 2025 16:21
@github-actions
Copy link

github-actions bot commented Oct 13, 2025

GNU testsuite comparison:

Skip an intermittent issue tests/misc/tee (fails in this run but passes in the 'main' branch)
Skipping an intermittent issue tests/timeout/timeout (passes in this run but fails in the 'main' branch)

@anastygnome
Copy link
Contributor

anastygnome commented Oct 28, 2025

@sylvestre is there anything left before this can be merged?

@github-actions
Copy link

github-actions bot commented Oct 28, 2025

GNU testsuite comparison:

Skip an intermittent issue tests/misc/tee (fails in this run but passes in the 'main' branch)

@sylvestre sylvestre merged commit 5c5494a into uutils:main Oct 28, 2025
121 checks passed
@sylvestre
Copy link
Contributor

sylvestre commented Oct 28, 2025

well done for the perf improvement

naoNao89 added a commit to naoNao89/coreutils that referenced this pull request Nov 2, 2025
@naoNao89
fix(tsort): correct minimal cycle reporting and precise back-edge rem…
5f0c697 
…oval with iterative DFS

- Implement iterative DFS to prevent stack overflows (from PR uutils#8737)
- Fix minimal cycle reporting to show only actual cycle nodes
- Remove redundant back-edge from last cycle node to first
- Update test expectations for corrected cycle handling
naoNao89 added a commit to naoNao89/coreutils that referenced this pull request Nov 3, 2025
@naoNao89
fix(tsort): correct minimal cycle reporting and precise back-edge rem…
4d6fdea 
…oval with iterative DFS

- Implement iterative DFS to prevent stack overflows (from PR uutils#8737)
- Fix minimal cycle reporting to show only actual cycle nodes
- Remove redundant back-edge from last cycle node to first
- Update test expectations for corrected cycle handling
sylvestre pushed a commit that referenced this pull request Nov 7, 2025
@naoNao89
fix(tsort): correct minimal cycle reporting and precise back-edge rem…
adcfcfa 
…oval with iterative DFS (#8786)

- Implement iterative DFS to prevent stack overflows (from PR #8737)
- Fix minimal cycle reporting to show only actual cycle nodes
- Remove redundant back-edge from last cycle node to first
- Update test expectations for corrected cycle handling
asder8215 pushed a commit to asder8215/coreutils that referenced this pull request Nov 8, 2025
@naoNao89 @asder8215
fix(tsort): correct minimal cycle reporting and precise back-edge rem…
dbbda80 
…oval with iterative DFS (uutils#8786)

- Implement iterative DFS to prevent stack overflows (from PR uutils#8737)
- Fix minimal cycle reporting to show only actual cycle nodes
- Remove redundant back-edge from last cycle node to first
- Update test expectations for corrected cycle handling
naoNao89 added a commit to naoNao89/coreutils that referenced this pull request Nov 8, 2025
@naoNao89
fix(tsort): correct minimal cycle reporting and precise back-edge rem…
ae8e0d6 
…oval with iterative DFS (uutils#8786)

- Implement iterative DFS to prevent stack overflows (from PR uutils#8737)
- Fix minimal cycle reporting to show only actual cycle nodes
- Remove redundant back-edge from last cycle node to first
- Update test expectations for corrected cycle handling
naoNao89 added a commit to naoNao89/coreutils that referenced this pull request Nov 9, 2025
@naoNao89
fix(tsort): correct minimal cycle reporting and precise back-edge rem…
276484a 
…oval with iterative DFS (uutils#8786)

- Implement iterative DFS to prevent stack overflows (from PR uutils#8737)
- Fix minimal cycle reporting to show only actual cycle nodes
- Remove redundant back-edge from last cycle node to first
- Update test expectations for corrected cycle handling
@BrewTestBot BrewTestBot mentioned this pull request Nov 10, 2025
Merged
@moonfruit moonfruit mentioned this pull request Nov 10, 2025
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

tsort: segfault on large cycles

3 participants

@Nekrolm @sylvestre @anastygnome