ref: e6ee208f91acdc61f4e9ba2d9d450cce94477673
parent: 2cb9c32187f0f14f38ab8124466f0ad17f77c5d0
author: Runxi Yu <me@runxiyu.org>
date: Sat Feb 21 16:24:07 EST 2026
repository: Add full-traversal benchmark
--- /dev/null
+++ b/repository/traversal_bench_test.go
@@ -1,0 +1,60 @@
+package repository_test
+
+import (
+ "os"
+ "strings"
+ "testing"
+
+ "codeberg.org/lindenii/furgit/object"
+ "codeberg.org/lindenii/furgit/repository"
+)
+
+const benchRepoPathEnv = "FURGIT_BENCH_REPO"
+
+// BenchmarkTraverseHeadTree measures iterative traversal of HEAD's root tree.
+//
+// Set FURGIT_BENCH_REPO to a repository path (typically .git or a bare repo)
+// before running this benchmark.
+func BenchmarkTraverseHeadTree(b *testing.B) {+ repoPath := strings.TrimSpace(os.Getenv(benchRepoPathEnv))
+ if repoPath == "" {+ b.Fatalf("missing %s", benchRepoPathEnv)+ }
+
+ repo, err := repository.Open(repoPath)
+ if err != nil {+ b.Fatalf("repository.Open(%q): %v", repoPath, err)+ }
+ b.Cleanup(func() {+ _ = repo.Close()
+ })
+
+ head, err := repo.ResolveRefFully("HEAD")+ if err != nil {+ b.Fatalf("ResolveRefFully(HEAD): %v", err)+ }
+ stored, err := repo.ReadStored(head.ID)
+ if err != nil {+ b.Fatalf("ReadStored(%s): %v", head.ID, err)+ }
+ commit, ok := stored.Object().(*object.Commit)
+ if !ok {+ b.Fatalf("HEAD object type %T, want *object.Commit", stored.Object())+ }
+
+ b.ReportAllocs()
+ b.ResetTimer()
+
+ var lastCount int
+ for range b.N {+ lastCount, err = traverseTreeIter(repo, commit.Tree)
+ if err != nil {+ b.Fatalf("traverseTreeIter: %v", err)+ }
+ }
+
+ b.StopTimer()
+ if lastCount <= 0 {+ b.Fatalf("traverseTreeIter count = %d, want > 0", lastCount)+ }
+}
--- /dev/null
+++ b/repository/traversal_helpers_test.go
@@ -1,0 +1,79 @@
+package repository_test
+
+import (
+ "codeberg.org/lindenii/furgit/object"
+ "codeberg.org/lindenii/furgit/objectid"
+ "codeberg.org/lindenii/furgit/repository"
+)
+
+func traverseTreeIter(repo *repository.Repository, root objectid.ObjectID) (int, error) {+ stack := []objectid.ObjectID{root}+ total := 0
+
+ for len(stack) > 0 {+ id := stack[len(stack)-1]
+ stack = stack[:len(stack)-1]
+
+ stored, err := repo.ReadStored(id)
+ if err != nil {+ return 0, err
+ }
+ total++
+
+ tree, ok := stored.Object().(*object.Tree)
+ if !ok {+ continue
+ }
+ for i := len(tree.Entries) - 1; i >= 0; i-- {+ entry := tree.Entries[i]
+ if entry.Mode == object.FileModeGitlink {+ continue
+ }
+ stack = append(stack, entry.ID)
+ }
+ }
+
+ return total, nil
+}
+
+func traverseReachableIter(repo *repository.Repository, root objectid.ObjectID) (int, error) {+ stack := []objectid.ObjectID{root}+ visited := make(map[objectid.ObjectID]struct{})+ total := 0
+
+ for len(stack) > 0 {+ id := stack[len(stack)-1]
+ stack = stack[:len(stack)-1]
+ if _, ok := visited[id]; ok {+ continue
+ }
+ visited[id] = struct{}{}+
+ stored, err := repo.ReadStored(id)
+ if err != nil {+ return 0, err
+ }
+ total++
+
+ switch obj := stored.Object().(type) {+ case *object.Commit:
+ stack = append(stack, obj.Tree)
+ stack = append(stack, obj.Parents...)
+ case *object.Tree:
+ for i := len(obj.Entries) - 1; i >= 0; i-- {+ entry := obj.Entries[i]
+ if entry.Mode == object.FileModeGitlink {+ continue
+ }
+ stack = append(stack, entry.ID)
+ }
+ case *object.Tag:
+ stack = append(stack, obj.Target)
+ case *object.Blob:
+ default:
+ // Unknown parsed object variants are treated as leaves.
+ }
+ }
+
+ return total, nil
+}
--- a/repository/traversal_test.go
+++ b/repository/traversal_test.go
@@ -8,7 +8,6 @@
"testing"
"codeberg.org/lindenii/furgit/internal/testgit"
- "codeberg.org/lindenii/furgit/object"
"codeberg.org/lindenii/furgit/objectid"
"codeberg.org/lindenii/furgit/repository"
)
@@ -103,43 +102,11 @@
if err != nil { t.Fatalf("ResolveRefFully(HEAD): %v", err)}
-
- visited := make(map[objectid.ObjectID]bool)
- queue := []objectid.ObjectID{head.ID}- objectsRead := 0
-
- for len(queue) > 0 {- id := queue[0]
- queue = queue[1:]
-
- if visited[id] {- continue
- }
- visited[id] = true
-
- stored, err := repo.ReadStored(id)
- if err != nil {- t.Fatalf("ReadStored(%s): %v", id, err)- }
- objectsRead++
-
- switch obj := stored.Object().(type) {- case *object.Commit:
- queue = append(queue, obj.Tree)
- queue = append(queue, obj.Parents...)
- case *object.Tree:
- for _, entry := range obj.Entries {- queue = append(queue, entry.ID)
- }
- case *object.Tag:
- queue = append(queue, obj.Target)
- case *object.Blob:
- default:
- t.Fatalf("unexpected object type: %T", obj)- }
+ objectsRead, err := traverseReachableIter(repo, head.ID)
+ if err != nil {+ t.Fatalf("traverseReachableIter(%s): %v", head.ID, err)}
-
- if objectsRead == 0 {+ if objectsRead <= 0 { t.Fatalf("no objects were enumerated from HEAD (%s)", fmt.Sprintf("%q", repoPath))}
}
--
⑨