Hacktoberfest 2026: những issue maintainer đã đánh dấu cho tháng Mười, đang mở và phù hợp người mới. Xem issue Hacktoberfest

Compute each position once before sorting by comparePos

Đã đóng
  • Có gì không ổn?
#129 0 bình luận 0 reaction 0 người được giao Xem trên GitHub

Maintainer thường phản hồi trong vòng 1 ngày

Chưa có ai nhận issue này.

Đánh giá

Độ khó
4/5
Thời gian dự kiến
3-5 ngày
Mức phù hợp với người mới
72/100
Loại issue
Tái cấu trúc
Độ rõ ràng
Đặc tả rõ ràng
Mức độ hoạt động
Sôi nổi
Công nghệ
go
Lĩnh vực
performance, tooling

Hướng nghiên cứu

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.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

enhancement

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.

Ngôn ngữ chính
Go
Star
18
Fork
0
Merge trung bình
59 phút
Pull request đã merge (30 ngày)
85

Chuẩn bị môi trường

Dự án này không cung cấp dev container, Dockerfile hay hướng dẫn đóng góp, nên bạn cần tự thiết lập môi trường: hãy bắt đầu từ README và xem hướng dẫn đóng góp lần đầu của chúng tôi để biết các bước chung.

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của mpyw/declscope

Tất cả issue của mpyw/declscope

Issue tương tự

Thêm issue về Go

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.