Artifact [2c591d1558]

Artifact 2c591d1558498a02445b01842f7a0001f8425e5681e4c680bf572fea182bf3b6:

• File internal/verify/rebuild_bench_test.go — part of check-in [9a9bc65f92] at 2026-10-19 01:50:41 on branch feat/submanifest-reader — perf(verify): check blob integrity by walking delta trees once

  Verify and Rebuild expanded every blob one at a time through a 256 MiB LRU cache. A real repository's delta chains run hundreds of revisions deep, so evicted chains were walked again from their roots: the blob check on the Fossil SCM repository ran for over 45 minutes.

  content.ExpandAll walks each delta tree from its root, as fossil's rebuild_step does, expanding every blob once from its parent's content and binding it to its name. It reports for each blob what a caching Expand of that blob alone reports, and expands blobs no sound root reaches (cycles, phantom-grounded or too-deep chains) on their own for that error. checkBlobs and Verify's checkCheckins both use it and sort their issues by rid, so reports are unchanged. (user: [email protected], size: 3708) [annotate] [blame] [check-ins using] [more...]

package verify_test

import (
	"fmt"
	"path/filepath"
	"testing"
	"time"

	libfossil "github.com/danmestas/go-libfossil/internal/fsltype"
	"github.com/danmestas/go-libfossil/internal/manifest"
	"github.com/danmestas/go-libfossil/internal/repo"
	_ "github.com/danmestas/go-libfossil/internal/testdriver"
	"github.com/danmestas/go-libfossil/internal/verify"
	"github.com/danmestas/go-libfossil/simio"
)

// BenchmarkRebuildDeepHistory measures verify.Rebuild over a repository whose
// files carry long, deltified histories -- the whole-repository-sweep case
// issue #151 routes through content.Cache.
//
// Methodology: commit `revisions` versions of two ~26 KB files, each changing a
// strided subset of lines off the previous, so Checkin deltifies every older
// file blob into a backward chain against its successor. Rebuild then sweeps
// every blob through checkBlobs and again through the manifest.Crosslink
// derivation. Blob by blob, either sweep would replay every blob's whole delta
// chain from its tip: O(revisions^2). checkBlobs instead walks each delta
// tree once from its root (content.ExpandAll), and the crosslink sweep's
// content cache walks each chain once.
func BenchmarkRebuildDeepHistory(b *testing.B) {
	for _, revisions := range []int{20, 60, 150, 400} {
		b.Run(fmt.Sprintf("revisions=%d", revisions), func(b *testing.B) {
			r := buildRebuildHistory(b, revisions)

			b.ReportAllocs()
			b.ResetTimer()
			for i := 0; i < b.N; i++ {
				if _, err := verify.Rebuild(r); err != nil {
					b.Fatalf("Rebuild: %v", err)
				}
			}
		})
	}
}

// BenchmarkVerifyDeepHistory measures verify.Verify over the same histories:
// the blob-integrity sweep plus the derived-table checks, which re-expand every
// check-in manifest through Verify's content cache. ns/op should grow about
// linearly in revisions; a quadratic blob sweep shows as ns/op growing with
// the square.
func BenchmarkVerifyDeepHistory(b *testing.B) {
	for _, revisions := range []int{20, 60, 150, 400} {
		b.Run(fmt.Sprintf("revisions=%d", revisions), func(b *testing.B) {
			r := buildRebuildHistory(b, revisions)

			b.ReportAllocs()
			b.ResetTimer()
			for i := 0; i < b.N; i++ {
				if _, err := verify.Verify(r); err != nil {
					b.Fatalf("Verify: %v", err)
				}
			}
		})
	}
}

func buildRebuildHistory(b *testing.B, revisions int) *repo.Repo {
	b.Helper()
	if revisions < 2 {
		panic("buildRebuildHistory: revisions must be >= 2")
	}

	path := filepath.Join(b.TempDir(), "hist.fossil")
	r, err := repo.Create(path, "bench", simio.CryptoRand{}, "")
	if err != nil {
		b.Fatalf("repo.Create: %v", err)
	}
	b.Cleanup(func() { r.Close() })

	base := time.Date(2024, 1, 1, 0, 0, 0, 0, time.UTC)
	var parent libfossil.FslID
	for k := 0; k < revisions; k++ {
		rid, _, err := manifest.Checkin(r, manifest.CheckinOpts{
			Files: []manifest.File{
				{Name: "a.txt", Content: rebuildRevision(k, 0)},
				{Name: "b.txt", Content: rebuildRevision(k, 7)},
			},
			Comment: fmt.Sprintf("rev %d", k),
			User:    "bench",
			Parent:  parent,
			Time:    base.Add(time.Duration(k) * time.Hour),
		})
		if err != nil {
			b.Fatalf("checkin rev %d: %v", k, err)
		}
		parent = rid
	}
	return r
}

// rebuildRevision returns revision k's content for a file seeded by `salt`, so
// the two files in a commit differ from each other while each still drifts by a
// handful of lines per revision.
func rebuildRevision(k, salt int) []byte {
	const lines = 400
	buf := make([]byte, 0, lines*66)
	for i := 0; i < lines; i++ {
		token := i + salt
		if i%11 == 0 {
			token = i + salt + k
		}
		buf = append(buf, fmt.Sprintf(
			"line %04d token %08d lorem ipsum dolor sit amet consectetur\n",
			i, token)...)
	}
	return buf
}