Skip to content

Instantly share code, notes, and snippets.

@benchristel

benchristel/bench_test.go

Created February 11, 2021 19:15
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save benchristel/62d361b79d39f472607fc1a42c798897 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save benchristel/62d361b79d39f472607fc1a42c798897 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. benchristel created this gist Feb 11, 2021.
    141 changes: 141 additions & 0 deletions bench_test.go
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,141 @@
    package main
    // run with go test -bench=.
    // My (oversimplified) conclusions are:
    // - if you have less than 64 items in each slice, it's faster to do an O(n^2) nested loop
    // - if you have more than 64 items, it's worth using a map as an index

    import "testing"
    import "math/rand"

    // prevent the compiler from optimizing away the function under test
    // by storing its result
    var result bool

    const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

    func BenchmarkSlices1(b *testing.B) {
    benchmarkSlices(b, 1)
    }

    func BenchmarkSlices2(b *testing.B) {
    benchmarkSlices(b, 2)
    }

    func BenchmarkSlices4(b *testing.B) {
    benchmarkSlices(b, 4)
    }

    func BenchmarkSlices8(b *testing.B) {
    benchmarkSlices(b, 8)
    }

    func BenchmarkSlices16(b *testing.B) {
    benchmarkSlices(b, 16)
    }

    func BenchmarkSlices32(b *testing.B) {
    benchmarkSlices(b, 32)
    }

    func BenchmarkSlices64(b *testing.B) {
    benchmarkSlices(b, 64)
    }

    func BenchmarkSlices128(b *testing.B) {
    benchmarkSlices(b, 128)
    }

    func BenchmarkMap1(b *testing.B) {
    benchmarkMap(b, 1)
    }

    func BenchmarkMap2(b *testing.B) {
    benchmarkMap(b, 2)
    }

    func BenchmarkMap4(b *testing.B) {
    benchmarkMap(b, 4)
    }

    func BenchmarkMap8(b *testing.B) {
    benchmarkMap(b, 8)
    }

    func BenchmarkMap16(b *testing.B) {
    benchmarkMap(b, 16)
    }

    func BenchmarkMap32(b *testing.B) {
    benchmarkMap(b, 32)
    }

    func BenchmarkMap64(b *testing.B) {
    benchmarkMap(b, 64)
    }

    func BenchmarkMap128(b *testing.B) {
    benchmarkMap(b, 128)
    }

    func benchmarkSlices(b *testing.B, length int) {
    as, bs := genSlices(length)
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
    result = IsSubset_UsingSlices(as, bs)
    }
    }

    func benchmarkMap(b *testing.B, length int) {
    as, bs := genSlices(length)
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
    result = IsSubset_UsingMap(as, bs)
    }
    }

    func genSlices(length int) ([]string, []string) {
    as := make([]string, length)
    bs := make([]string, length)
    for i := 0; i < length; i++ {
    as[i] = genString(10)
    }
    for i := 0; i < length; i++ {
    bs[i] = as[length-i-1]
    }
    return as, bs
    }

    func IsSubset_UsingSlices(as []string, bs []string) bool {
    next_a:
    for _, a := range as {
    for _, b := range bs {
    if b == a {
    continue next_a
    }
    }
    // if we're here, we got through all the Bs without finding a match for A
    return false
    }
    return true
    }

    func IsSubset_UsingMap(as []string, bs []string) bool {
    bs_map := make(map[string]bool)
    for _, b := range bs {
    bs_map[b] = true
    }
    for _, a := range as {
    if _, ok := bs_map[a]; !ok {
    return false
    }
    }
    return true
    }

    func genString(n int) string {
    b := make([]byte, n)
    for i := range b {
    b[i] = letters[rand.Intn(len(letters))]
    }
    return string(b)
    }