Binary Search — Programuoki

Code

Three searches, two ways to measure

Create search.go (see the panel). It holds three searches, timeIt and two commands.

Why every search exists twice

The file has LowerBound and lowerBoundRaw. The same algorithm, except the second has no counter.

That is not lazy duplication. The counter is called once per comparison — n/2 times in the linear scan, log n times in the binary one. Time the code with the counter in it and you penalise the linear scan roughly 250× harder than the binary one.

I measured it both ways. With the counter, the crossover lands at n ≈ 3; without it, at n ≈ 6. The instrument moved the thing it was measuring by a factor of two.

In lesson 4 the counter could not see memory. Here it changes the result. Count with one version, time with the other.

So timeIt calls the ...Raw functions, and the counts are collected separately.

`timeIt` — the answer to lesson 1's "wall 0s"

func timeIt(d time.Duration, f func()) (time.Duration, int)

A single run cannot be timed — in lesson 1 the clock read 0s. timeIt repeats until at least d has passed, then divides. transit does exactly this, for exactly this reason.

Three searches, one question

LinearAtOrAfter, LowerBound and LowerBoundStd return the same answer. If they did not, comparing their speed would be meaningless.

search_test.go (next step) proves it before any measurement — 620 different targets, all three agreeing. It is the discipline transit follows: prove they are the same function first, then benchmark.

search.go CREATE

Create this file in ./

package main

import (
	"flag"
	"fmt"
	"sort"
	"time"

	"algo/metrics"
)

// All three searches answer the SAME question, or the comparison would be
// meaningless: return the index of the FIRST item whose Title is >= target.
// That is "at-or-after" — the same semantics transit uses for "the next
// departure at or after this time", and it is the shape you actually want.
// An exact-match search is this plus one equality check.

// LinearAtOrAfter walks from the front. O(n).
func LinearAtOrAfter(items []Item, target string, c *metrics.Counter) int {
	for i := range items {
		c.Hit()
		if items[i].Title >= target {
			return i
		}
	}
	return len(items)
}

// LowerBound is the hand-rolled binary search. O(log n).
//
// The invariant is the whole thing: the answer is always in [lo, hi]. lo starts
// at 0, hi at len(items) — ONE PAST the end, because "not found" is a legal
// answer and it lives there.
func LowerBound(items []Item, target string, c *metrics.Counter) int {
	lo, hi := 0, len(items)
	for lo < hi {
		mid := int(uint(lo+hi) >> 1) // >>1 not /2, and uint to avoid overflow
		c.Hit()
		if items[mid].Title < target {
			lo = mid + 1 // mid is too small, so it cannot be the answer
		} else {
			hi = mid // mid might BE the answer, so it stays in range
		}
	}
	return lo
}

// LowerBoundStd is the same job through the standard library.
func LowerBoundStd(items []Item, target string, c *metrics.Counter) int {
	return sort.Search(len(items), func(i int) bool {
		c.Hit()
		return items[i].Title >= target
	})
}

// timeIt runs f until it has spent at least d, then reports the per-call cost.
// Lesson 1 showed a single run reporting "wall 0s"; this is the fix, and it is
// the same trick transit uses for the same reason.
func timeIt(d time.Duration, f func()) (time.Duration, int) {
	runs := 0
	start := time.Now()
	for time.Since(start) < d {
		for i := 0; i < 128; i++ {
			f()
		}
		runs += 128
	}
	return time.Since(start) / time.Duration(runs), runs
}

func cmdSweep(args []string) error {
	fs := flag.NewFlagSet("sweep", flag.ContinueOnError)
	scattered := fs.Bool("scattered", false, "reach each slice through a map, as a real index would")
	ints := fs.Bool("ints", false, "search int32 keys (transit's shape) instead of Titles")
	if err := fs.Parse(args); err != nil {
		return err
	}
	sizes := []int{2, 4, 8, 12, 16, 24, 32, 64, 127, 256, 1024, 2254}

	// One sorted collection per size. In -scattered mode each is reached
	// through a map, so it is not sitting in cache when the search starts.
	byN := make(map[int][]Item, len(sizes))
	intsByN := make(map[int][]int32, len(sizes))
	for _, n := range sizes {
		s := make([]Item, n)
		xs := make([]int32, n)
		for i := range s {
			s[i] = Item{ID: i, Title: fmt.Sprintf("%08d", i*2)}
			xs[i] = int32(i * 2)
		}
		byN[n] = s
		intsByN[n] = xs
	}

	key := "Title (string)"
	if *ints {
		key = "int32"
	}
	layout := "contiguous"
	if *scattered {
		layout = "reached through a map"
	}
	fmt.Printf("key: %s   layout: %s\n\n", key, layout)
	fmt.Printf("%6s | %10s %10s | %12s %12s | %s\n",
		"n", "lin cmps", "bin cmps", "lin ns/op", "bin ns/op", "winner by CLOCK")
	fmt.Println("-------|-----------------------|---------------------------|----------------")
	for _, n := range sizes {
		var cl, cb metrics.Counter
		var lin, bin time.Duration

		if *ints {
			target := int32(n)
			get := func() []int32 { return intsByN[n] }
			if !*scattered {
				xs := intsByN[n]
				get = func() []int32 { return xs }
			}
			LinearInts(get(), target, &cl)
			LowerBoundInts(get(), target, &cb)
			lin, _ = timeIt(40*time.Millisecond, func() { linearIntsRaw(get(), target) })
			bin, _ = timeIt(40*time.Millisecond, func() { lowerBoundIntsRaw(get(), target) })
		} else {
			target := fmt.Sprintf("%08d", n)
			get := func() []Item { return byN[n] }
			if !*scattered {
				s := byN[n]
				get = func() []Item { return s }
			}
			LinearAtOrAfter(get(), target, &cl)
			LowerBound(get(), target, &cb)
			lin, _ = timeIt(40*time.Millisecond, func() { linearRaw(get(), target) })
			bin, _ = timeIt(40*time.Millisecond, func() { lowerBoundRaw(get(), target) })
		}

		win := "binary"
		if lin < bin {
			win = "LINEAR"
		}
		fmt.Printf("%6d | %10d %10d | %12d %12d | %s\n",
			n, cl.N(), cb.N(), lin.Nanoseconds(), bin.Nanoseconds(), win)
	}
	return nil
}

func cmdStd(args []string) error {
	fs := flag.NewFlagSet("std", flag.ContinueOnError)
	n := fs.Int("n", 2254, "slice size")
	if err := fs.Parse(args); err != nil {
		return err
	}
	s := make([]Item, *n)
	for i := range s {
		s[i] = Item{ID: i, Title: fmt.Sprintf("%08d", i*2)}
	}
	target := fmt.Sprintf("%08d", *n/3*2)

	var c1, c2 metrics.Counter
	a := LowerBound(s, target, &c1)
	b := LowerBoundStd(s, target, &c2)

	hand, _ := timeIt(120*time.Millisecond, func() { lowerBoundRaw(s, target) })
	std, _ := timeIt(120*time.Millisecond, func() { lowerBoundStdRaw(s, target) })

	fmt.Printf("n = %d, same answer: hand=%d std=%d (%v)\n\n", *n, a, b, a == b)
	fmt.Printf("%-22s %12s %12s\n", "", "comparisons", "ns/op")
	fmt.Printf("%-22s %12d %12d\n", "hand-rolled LowerBound", c1.N(), hand.Nanoseconds())
	fmt.Printf("%-22s %12d %12d\n", "sort.Search", c2.N(), std.Nanoseconds())
	return nil
}

// ── The same two searches over a cheap key ──────────────────────────────
//
// transit searches []int32 departure times, not strings. One int comparison
// is a single machine instruction; one string comparison is a function call
// that may walk several bytes. That difference moves the crossover, which is
// why the sweep measures both.

func LinearInts(xs []int32, target int32, c *metrics.Counter) int {
	for i := range xs {
		c.Hit()
		if xs[i] >= target {
			return i
		}
	}
	return len(xs)
}

func LowerBoundInts(xs []int32, target int32, c *metrics.Counter) int {
	lo, hi := 0, len(xs)
	for lo < hi {
		mid := int(uint(lo+hi) >> 1)
		c.Hit()
		if xs[mid] < target {
			lo = mid + 1
		} else {
			hi = mid
		}
	}
	return lo
}

// ── Uncounted twins, for TIMING only ────────────────────────────────────
//
// The counted versions above call c.Hit() once per comparison. That call is
// cheap, but the linear scan makes n/2 of them and the binary search makes
// log n — so instrumenting the code penalises the linear scan far more than
// the binary one, and the timing would be measuring the COUNTER.
//
// So: count with one version, time with the other. Same algorithm, no probe.

func linearIntsRaw(xs []int32, target int32) int {
	for i := range xs {
		if xs[i] >= target {
			return i
		}
	}
	return len(xs)
}

func lowerBoundIntsRaw(xs []int32, target int32) int {
	lo, hi := 0, len(xs)
	for lo < hi {
		mid := int(uint(lo+hi) >> 1)
		if xs[mid] < target {
			lo = mid + 1
		} else {
			hi = mid
		}
	}
	return lo
}

func linearRaw(items []Item, target string) int {
	for i := range items {
		if items[i].Title >= target {
			return i
		}
	}
	return len(items)
}

func lowerBoundRaw(items []Item, target string) int {
	lo, hi := 0, len(items)
	for lo < hi {
		mid := int(uint(lo+hi) >> 1)
		if items[mid].Title < target {
			lo = mid + 1
		} else {
			hi = mid
		}
	}
	return lo
}

func lowerBoundStdRaw(items []Item, target string) int {
	return sort.Search(len(items), func(i int) bool { return items[i].Title >= target })
}

Three searches, two ways to measure

Why every search exists twice

timeIt — the answer to lesson 1's "wall 0s"

Three searches, one question

`timeIt` — the answer to lesson 1's "wall 0s"