Compute each position once before sorting by comparePos
I maintainer di solito rispondono entro 1 giorno
Nessuno ha ancora preso questa issue.
Valutazione
- Difficoltà
- 4/5
- Tempo stimato
- 3-5 giorni
- Idoneità per principianti
- 72/100
- Tipo di issue
- Refactoring
- Chiarezza
- Specificata chiaramente
- Stato di attività
- Attiva
- Stack tecnologico
- go
- Ambito
- performance, tooling
Direzione di ricerca
Start with comparePos in internal/subject.go:313, then inspect its ten sorting call sites in internal/ignore.go, report.go, scopesite.go, surplus.go, and survey.go. Check the two internal/surplus.go sites around lines 579 and 659 for later sorted-order use, and run the existing test suite; done means each sort preserves its current ordering while avoiding repeated position lookups.
Scritto dal modello di indicizzazione a partire dal testo della issue.
Descrizione
Summary
comparePos (internal/subject.go:313) computes two token.Position values on every comparison. It is the comparator of 10 sorts, in ignore.go, report.go, scopesite.go, surplus.go and survey.go. Computing each position once before the sort cuts the work from about 2·n·log n position lookups to n.
Current shape
func comparePos(fset *token.FileSet, a, b token.Pos) int {
pa, pb := fset.Position(a), fset.Position(b) // two lookups per comparison
if c := strings.Compare(pa.Filename, pb.Filename); c != 0 {
return c
}
return cmp.Compare(pa.Offset, pb.Offset)
}
// internal/ignore.go:202
slices.SortFunc(sites, func(a, b *ignoreSite) int { return comparePos(pass.Fset, a.ig.Pos, b.ig.Pos) })
fset.Position finds the file with a binary search, then finds the line with another binary search. It also applies //line adjustment.
Why the change helps
A sort of n elements makes about n·log n comparisons. Each comparison looks up two positions, and the same element's position is looked up again every time it is compared.
type keyed[T any] struct {
pos token.Position
v T
}
// One lookup per element.
ks := make([]keyed[finding], len(findings))
for i, f := range findings {
ks[i] = keyed[finding]{fset.Position(f.pos), f}
}
slices.SortFunc(ks, func(a, b keyed[finding]) int {
if c := strings.Compare(a.pos.Filename, b.pos.Filename); c != 0 {
return c
}
return cmp.Compare(a.pos.Offset, b.pos.Offset)
})
For 1,000 findings, that is about 20,000 lookups today and 1,000 after the change.
A sort that only needs the first element
Two call sites sort only to take the smallest element:
// internal/surplus.go:579 and :659
slices.SortFunc(names, func(a, b *target) int { return comparePos(pass.Fset, a.ident.Pos(), b.ident.Pos()) })
pos := names[0].boundBy.ScopePos
slices.MinFunc finds the same element in one pass, with n-1 comparisons instead of about n·log n. Check first that nothing reads names in sorted order after this line.
Risk
None, provided the key is the same fset.Position the comparator reads today.
Low impact. The sorted lists are findings and directives, which are small in a clean package. It matters most in a baseline or survey run over a large module with many findings.
- Lingua principale
- Go
- Stelle
- 18
- Fork
- 0
- Merge medio
- 59m
- PR unite (30g)
- 85
Preparare l'ambiente
Questo progetto non fornisce container di sviluppo, Dockerfile né guida per i contributori, quindi l'ambiente è a tuo carico: parti dal suo README e consulta la nostra guida al primo contributo per i passaggi generali.
Come iniziare
- Leggi tutta la issue e poi la guida ai contributi del progetto.
- Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
- Fai un fork del repository e lavora su un branch.
- Apri una pull request che faccia riferimento al numero della issue.
Altre issue di mpyw/declscope
-
Inflections are generated in one direction, so an inflected file name is never carried by its stemAperta
Difficoltà 4/5 3-5 giorni Idoneità per principianti 48/100
I maintainer di solito rispondono entro 1 giorno
Tutte le issue di mpyw/declscope
Issue simili
-
automation models
Difficoltà 2/5 1-3 ore Idoneità per principianti 78/100
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 72/100
txn2/mcp-data-platform#1984 ·
I maintainer di solito rispondono entro 1 giorno
-
agentic-workflows
Difficoltà 2/5 1-3 ore Idoneità per principianti 68/100
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 88/100
I maintainer di solito rispondono entro 1 giorno
-
kind/docs prio/P2
Difficoltà 1/5 Meno di un'ora Idoneità per principianti 95/100
agent-substrate/substrate#1986 ·
I maintainer di solito rispondono entro 1 giorno