optimize iteration over a list of sorted periods

Admin 1
Viewed 65

given a list of periods, already sorted, and containing no dups.

periods := periods{
    period{min: 0, max: time.Millisecond},
    period{min: time.Millisecond, max: time.Millisecond * 1},
    period{min: time.Millisecond * 1, max: time.Millisecond * 2},
    period{min: time.Millisecond * 2, max: time.Millisecond * 7},
    period{min: time.Millisecond * 7, max: 0},
}

with the types periods and period defined as

type periods []period

func (ks periods) index(v time.Duration) period {
    for i := 0; i < len(ks); i++ {
        if ks[i].contains(v) {
            return ks[i]
        }
    }
    return period{}
}

type period struct {
    min time.Duration
    max time.Duration
}

func (k period) String() string {
    if k.max == 0 && k.max < k.min {
        return fmt.Sprintf("%v-", k.min)
    }
    return fmt.Sprintf("%v-%v", k.min, k.max)
}

func (k period) contains(t time.Duration) bool {
    if t <= 0 && k.min == 0 {
        return true
    }
    return t > k.min && (k.max == 0 || t <= k.max)
}

The full code is available at https://play.golang.org/p/cDmQ7Ho6hUI

Can you suggest solution(s) to improve the search implementation in the periods.index function ?

Also, can you provide a factorized solution such as it is possible to re use the implementation ? A generics included solution is OK for that i can still specialize using code gen.

A benchmark is included

func BenchmarkIndex(b *testing.B) {
    periods := periods{
        period{min: 0, max: 8000},
        period{min: 8000, max: 16000},
        period{min: 16000, max: 24000},
        period{min: 24000, max: 32000},
        period{min: 32000, max: 40000},
        period{min: 40000, max: 48000},
        period{min: 48000, max: 56000},
        period{min: 56000, max: 64000},
        period{min: 64000, max: 72000},
        period{min: 72000, max: 80000},
        period{min: 80000, max: 0},
    }

    inputs := []time.Duration{
        time.Duration(0),
        time.Duration(72000 + 1),
        time.Duration(80000 + 1),
    }
    b.ResetTimer()
    b.ReportAllocs()
    for i := 0; i < b.N; i++ {
        for _, input := range inputs {
            _ = periods.index(input)
        }
    }
}
go
1 Answers

It's unlikely you can achieve better performance than a simple, sequential search for a list as small as yours (11 elements).

If your slice would be much bigger (e.g. hundreds or even thousands of periods), since your periods is sorted as you claim, then you could use binary search.

Binary search is implemented in sort.Search(). You just basically have to provide a lessOrContains() implementation for period. This is how it could look like:

func (k period) lessOrContains(t time.Duration) bool {
    return k.max == 0 || t <= k.max
}

Now an index() function using binary search:

func (ks periods) indexBinary(v time.Duration) period {
    idx := sort.Search(len(ks), func(i int) bool {
        return ks[i].lessOrContains(v)
    })
    if idx < len(ks) && ks[idx].contains(v) {
        return ks[idx]
    }
    return period{}
}

Now on to benchmarking. Let's create a createPeriods() helper function that creates either a small or big periods slice:

func createPeriods(big bool) periods {
    ps := periods{
        period{min: 0, max: 8000},
        period{min: 8000, max: 16000},
        period{min: 16000, max: 24000},
        period{min: 24000, max: 32000},
        period{min: 32000, max: 40000},
        period{min: 40000, max: 48000},
        period{min: 48000, max: 56000},
        period{min: 56000, max: 64000},
        period{min: 64000, max: 72000},
        period{min: 72000, max: 80000},
        period{min: 80000, max: 0},
    }

    if big {
        psbig := periods{}
        for i := 0; i < 1000; i++ {
            psbig = append(psbig, period{time.Duration(i), time.Duration(i + 1)})
        }
        psbig = append(psbig, ps[1:]...)
        ps = psbig
    }

    return ps
}

Now let's write benchmark functions for all cases:

func BenchmarkIndexSmall(b *testing.B) {
    benchmarkIndexImpl(b, false)
}

func BenchmarkIndexBinarySmall(b *testing.B) {
    benchmarkIndexBinaryImpl(b, false)
}

func BenchmarkIndexBig(b *testing.B) {
    benchmarkIndexImpl(b, true)
}

func BenchmarkIndexBinaryBig(b *testing.B) {
    benchmarkIndexBinaryImpl(b, true)
}

func benchmarkIndexImpl(b *testing.B, big bool) {
    periods := createPeriods(big)

    inputs := []time.Duration{
        time.Duration(0),
        time.Duration(72000 + 1),
        time.Duration(80000 + 1),
    }
    b.ResetTimer()
    b.ReportAllocs()
    for i := 0; i < b.N; i++ {
        for _, input := range inputs {
            _ = periods.index(input)
        }
    }
}

func benchmarkIndexBinaryImpl(b *testing.B, big bool) {
    periods := createPeriods(big)

    inputs := []time.Duration{
        time.Duration(0),
        time.Duration(72000 + 1),
        time.Duration(80000 + 1),
    }
    b.ResetTimer()
    b.ReportAllocs()
    for i := 0; i < b.N; i++ {
        for _, input := range inputs {
            _ = periods.indexBinary(input)
        }
    }
}

And now let's see the benchmark results:

BenchmarkIndexSmall-8        44408948      25.50 ns/op    0 B/op     0 allocs/op
BenchmarkIndexBinarySmall-8  18441049      58.35 ns/op    0 B/op     0 allocs/op
BenchmarkIndexBig-8            562202    1908 ns/op       0 B/op     0 allocs/op
BenchmarkIndexBinaryBig-8     9234846     125.1 ns/op     0 B/op     0 allocs/op

As you can see, index() is faster than indexBinary() for small lists with 11 elements (25 ns vs 58 ns).

But when the list gets big (more than a thousand periods, 1010 in the above benchmark), then indexBinary() outperforms index() by more than an order of magnitude (125 ns vs 2000 ns), and this difference will get even bigger if the lists gets bigger.

user_17055980
Related