ory / x / 16046438045

62%

Build Type

push

github

Committed by web-flow

Commit Message

fix: fix sorting migration files much more than necessary & fix ordering function (#872)

## Problem

Crux of the issue: for each migration file being found while walking the
directory recursively, we added this file to the slice of all migration
files **and** immediately sorted this slice. Repeatedly. Since sorting
has a complexity of `O(n*log(n))`, the overall complexity is
`O(n*n*log(n))`. Thus the running time will worsen badly with each new
migration file added.



Before the fix, we can indeed see that the run time of `findMigrations`
is dominated (95%) by sorting:

<img width="1724" alt="Screenshot 2025-07-01 at 10 52 57"
src="https://github.com/user-attachments/assets/5c2d3057-a8e8-4c70-abaf-0fa7731f7054"
/>


## Solution

- Sort once, after `fs.Walkdir` is done collecting all files
- Sort with `slices.SortFunc` which docs claim is faster than the older
`sort.Sort`

Benefit: a nice speed-up, for example here when running tests in
`kratos-oss/selfservice/strategy/code`:

```
Benchmark 1: ./code.test.before
  Time (mean ± σ):     30.835 s ±  0.347 s    [User: 30.184 s, System: 8.271 s]
  Range (min … max):   30.409 s … 31.407 s    10 runs
 
Benchmark 2: ./code.test.after
  Time (mean ± σ):     27.441 s ±  0.188 s    [User: 26.719 s, System: 8.157 s]
  Range (min … max):   27.146 s … 27.798 s    10 runs
 
Summary
  ./code.test.after ran
    1.12 ± 0.01 times faster than ./code.test.before
```

Note: The previous sort function `Less` had a flaw: it was not a
transitive ordering. This has been fixed along with a test to check
that.

Run Details

18 of 18 new or added lines in 2 files covered. (100.0%)

4 existing lines in 1 file now uncovered.

7412 of 11999 relevant lines covered (61.77%)

0.7 hits per line