Window Save

Moving Window Data Structure

Copyright (c) 2012. Jake Brukhman. ([email protected]). All rights reserved. See the LICENSE file for BSD-style license.

Installation

You need at least the following weekly version of Go:

go version weekly.2012-02-07 +52ba9506bd99

You can then use the 'go' command to obtain the package:

$ go get github.com/jbrukh/window
$ go install -v github.com/jbrukh/window

To run the benchmarks:

$ go test -test.bench=".*"

Documentation

A moving window is a FIFO data structure with a fixed maximum size and the property that if the size has been reached and an element is pushed into the window, then the head of the window is pushed out to accomodate it.

Typically, two operations are of importance whilst working with moving windows in a high-performance context. First, pushes are expected to happen often as lots of data comes in. Secondly, the window is typically converted to a simple array for interfacing with secondary processes, such as graphing.

The MovingWindow object implemented in this package optimizes both of these operations by trading off with space complexity. Given two parameters -- size S and space parameter M -- the window will allocate a single backing array of length SM and complexity of background copy operations will be proportional to 1/M.

As demonstrated in the benchmarks below, a MovingWindow can operate approximately 20x faster than a list-backed implementation and 3-4x faster than a ring-backed implementation. However, it is 5000x more efficient at generating array output because it can take slices of the backing array. It is also worth noting that most of the performance gain is reached quickly with relatively small M: for instance, setting M := S/100 is a good starting point.

Benchmarks

Here are some benchmarks:

 BenchmarkListS1000             10         188497800 ns/op
 BenchmarkRingS1000             50          35760520 ns/op
 BenchmarkS1000M1                1        2817453000 ns/op
 BenchmarkS1000M10             200           9012795 ns/op
 BenchmarkS1000M100            200           8807370 ns/op
 BenchmarkS1000M500            200           8471190 ns/op
 BenchmarkSlicifyList        50000             41656 ns/op
 BenchmarkSlicifyRing        50000             48598 ns/op
 BenchmarkSlicifyWindow  200000000              9.30 ns/op

The first set of benchmarks measures the time it takes for 1,000,000 points to go through a size 1000 list-based moving window, ring-based moving window, and a MovingWindow under different values of its space parameter M. The later test measures how long it takes to convert the moving windows into a slice, a common operation.