java-topology/docs/tickets/gorm-0001-sortcallbacks-getindex-quadratic.md

gorm-0001 — sortCallbacks: O(n²) getRIndex linear scans during callback registration

Status: OPEN Severity: MEDIUM Component: go-gorm/gorm — callbacks.go Affects: Application startup; every call to Register(), Remove(), or Replace()

---

Root Cause

callbacks.go:252 — getRIndex():

// DEFECTIVE — O(n) linear scan of string slice
func getRIndex(strs []string, str string) int {
    for i := len(strs) - 1; i >= 0; i-- {
        if strs[i] == str {
            return i
        }
    }
    return -1
}

getRIndex is called 13 times inside sortCallbacks() (lines 278, 287, 291, 297, 305, 309, 315, 335, 349) against names []string and sorted []string, both of length equal to the total callback count N.

sortCallbacks() is called on every Register(), Remove(), and Replace() invocation (callbacks.go:231, 239, 248). Each call re-sorts the full callback list from scratch. For N callbacks, each registration triggers O(N) getRIndex calls, each O(N) → O(N²) total per registration, O(N³) across all N registrations (amortized O(N²) for the full startup sequence).

GORM registers ~26 default callbacks at init time across 6 processors (create, query, update, delete, row, raw).

---

Complexity Analysis

Metric	Defective	Fixed
getRIndex(names, name)	O(N)	O(1) with map[string]int
getRIndex(sorted, name)	O(N)	O(1) with map[string]int
Full sortCallbacks(N)	O(N²)	O(N)
All N registrations combined	O(N³)	O(N²)

For N=26 default callbacks: ~8,788 comparisons vs ~676 with map-based index. The absolute count is small, but each additional Register() call (plugin registration, per-test setup) re-runs the full O(N²) sort. Long-lived GORM applications with many plugins accumulate registration cost.

---

Fix

Replace names []string and sorted []string with map[string]int for O(1) index lookup:

// FIXED — use maps for O(1) index lookup
func sortCallbacks(cs []*callback) (fns []func(*DB), err error) {
    namesMap := map[string]int{}   // name -> last index in cs
    sortedMap := map[string]int{}  // name -> index in sorted
    sorted := []string{}
    // ...
    // Replace: getRIndex(names, c.name)  ->  namesMap[c.name] (+ existence check)
    // Replace: getRIndex(sorted, c.name) ->  sortedMap[c.name] (+ existence check)
}

The getRIndex function returns the right-most index (for replace/remove semantics). The map can track the most-recently-appended index; update on each names = append(names, c.name).

---

Call Sites

File	Lines	Context
callbacks.go	252–258	getRIndex definition
callbacks.go	276–349	sortCallbacks — outer loop + inner sortCallback
callbacks.go	231, 239, 248	Register, Remove, Replace — trigger on every call

---

Speedup Estimate

For N=26 default callbacks: modest absolute savings (startup only). For applications with many plugin registrations or test suites that reinitialize GORM (recreate DB with callbacks): O(N)× improvement per sortCallbacks invocation. The primary value is eliminating quadratic scaling as N grows with plugin count.