quickfilter

README

quickfilter

quickfilter provides utility modules for filtering slices with minimal allocations and performance overhead.

Documentation

Overview

Package quickfilter provides a QuickFilter module for performing filtering of slices with minimal allocations. It works by allocating a bit array that stores the indices of the elements to be added to the resulting slice. This means that the total number of allocations for the filtering operation will be a static two (2), `len(sourceSlice)/8` bytes for the bit array and `len(resultSlice)*size_of_element` for the results array. This helps with providing predictable performance for your filter operations.

QuickFilter should not be used blindly due to the readability overhead, and it may not even be the fastest option available. Usually it's more efficient to do the operation in-place if you can mutate the original slice. You can see an example of this in the benchmarks. You might also consider using resource pooling instead. As always, optimize when needed and benchmark to find the best solution.

For reference, here are the benchmark results on a MacBook Pro (early 2015, 3.1GHz i7, 16GB memory) of filtering a large arbitrary payload:

goos: darwin
goarch: amd64
pkg: github.com/jussi-kalliokoski/quickfilter
Benchmark/QuickFilter-4                       30          45195222 ns/op        240249702 B/op         5 allocs/op
Benchmark/dynamic_allocations-4               10         104337103 ns/op        612835667 B/op        25 allocs/op
Benchmark/in_place-4                          30          39128758 ns/op        160161952 B/op         3 allocs/op

As we can see, QuickFilter is more than twice as fast as using dynamic allocations, allocates almost a third of the memory, and is almost as fast as doing the operation in-place.

Example

package main

import (
	"fmt"

	"github.com/jussi-kalliokoski/quickfilter"
)

func main() {
	data := make([]int, 0, 8)
	for len(data) < cap(data) {
		data = append(data, len(data))
	}
	qf := quickfilter.New(len(data))
	for i := range data {
		if data[i]%2 == 0 {
			qf = qf.Add(i)
		}
	}
	newData := make([]int, 0, qf.Len())
	for it := qf.Iterate(); !it.Done(); it = it.Next() {
		newData = append(newData, data[it.Value()])
	}

	fmt.Println(newData)
}

Output:

[0 2 4 6]

Example (Intersection)

package main

import (
	"fmt"

	"github.com/jussi-kalliokoski/quickfilter"
)

func main() {
	data := make([]int, 0, 16)
	for len(data) < cap(data) {
		data = append(data, len(data))
	}
	qf1 := quickfilter.New(len(data))
	for i := range data {
		if data[i]%2 == 0 {
			qf1 = qf1.Add(i)
		}
	}
	qf2 := quickfilter.New(len(data))
	for i := range data {
		if data[i]%3 == 0 {
			qf2 = qf2.Add(i)
		}
	}
	qf := quickfilter.New(len(data))
	qf = qf.IntersectionOf(qf1, qf2)
	newData := make([]int, 0, qf.Len())
	for it := qf.Iterate(); !it.Done(); it = it.Next() {
		newData = append(newData, data[it.Value()])
	}

	fmt.Println(newData)
}

Output:

[0 6 12]

Example (Union)

package main

import (
	"fmt"

	"github.com/jussi-kalliokoski/quickfilter"
)

func main() {
	data := make([]int, 0, 16)
	for len(data) < cap(data) {
		data = append(data, len(data))
	}
	qf1 := quickfilter.New(len(data))
	for i := range data {
		if data[i]%2 == 0 {
			qf1 = qf1.Add(i)
		}
	}
	qf2 := quickfilter.New(len(data))
	for i := range data {
		if data[i]%3 == 0 {
			qf2 = qf2.Add(i)
		}
	}
	qf := quickfilter.New(len(data))
	qf = qf.UnionOf(qf1, qf2)
	newData := make([]int, 0, qf.Len())
	for it := qf.Iterate(); !it.Done(); it = it.Next() {
		newData = append(newData, data[it.Value()])
	}

	fmt.Println(newData)
}

Output:

[0 2 3 4 6 8 9 10 12 14 15]

Index

• type Iterator
  • func (it Iterator) Done() bool
  • func (it Iterator) Next() Iterator
  • func (it Iterator) Value() int
• type QuickFilter
  • func New(sourceLen int) QuickFilter
  • func NewFilled(sourceLen int) QuickFilter
  • func (qf QuickFilter) Add(index int) QuickFilter
  • func (qf QuickFilter) Cap() int
  • func (qf QuickFilter) Clear() QuickFilter
  • func (qf QuickFilter) Copy() QuickFilter
  • func (qf QuickFilter) CopyFrom(qf2 QuickFilter) QuickFilter
  • func (qf QuickFilter) Delete(index int) QuickFilter
  • func (qf QuickFilter) Fill() QuickFilter
  • func (qf QuickFilter) Has(index int) bool
  • func (qf QuickFilter) IntersectionOf(qf1, qf2 QuickFilter) QuickFilter
  • func (qf QuickFilter) Iterate() Iterator
  • func (qf QuickFilter) Len() int
  • func (qf QuickFilter) Resize(sourceLen int) QuickFilter
  • func (qf QuickFilter) UnionOf(qf1, qf2 QuickFilter) QuickFilter

Examples

• Package
• Package (Intersection)
• Package (Union)

Types

type Iterator

type Iterator struct {
	// contains filtered or unexported fields
}

Iterator over the offsets of a QuickFilter.

func (Iterator) Done

func (it Iterator) Done() bool

Done returns a boolean indicating whether the Iterator has been exhausted.

func (Iterator) Next

func (it Iterator) Next() Iterator

Next returns the Iterator at the next offset.

func (Iterator) Value

func (it Iterator) Value() int

Value returns the currently found offset.

type QuickFilter

type QuickFilter struct {
	// contains filtered or unexported fields
}

QuickFilter is a utility module that stores offsets and allows you to iterate over them.

func New

func New(sourceLen int) QuickFilter

New returns a new QuickFilter with enough space reserved to store sourceLen offsets.

In a filtering operation, sourceLen should be the len() of the original slice.

func NewFilled

func NewFilled(sourceLen int) QuickFilter

NewFilled returns a new QuickFilter, like New, but instead of all items being left out by default, all are included in the filter result. This allows for doing multi-level filtering where the results from one filter function are passed to the next as a QuickFilter.

func (QuickFilter) Add

func (qf QuickFilter) Add(index int) QuickFilter

Add an index to the offset list.

The original QuickFilter is no longer usable and must be replaced with the returned one. This approach prevents the QuickFilter from escaping to the heap.

func (QuickFilter) Cap

func (qf QuickFilter) Cap() int

Cap returns the maximum number of values that can be stored.

func (QuickFilter) Clear

func (qf QuickFilter) Clear() QuickFilter

Clear the entries in the QuickFilter.

The original QuickFilter is no longer usable and must be replaced with the returned one. This approach prevents the QuickFilter from escaping to the heap.

func (QuickFilter) Copy

func (qf QuickFilter) Copy() QuickFilter

Copy a QuickFilter with its results to a new QuickFilter.

func (QuickFilter) CopyFrom

func (qf QuickFilter) CopyFrom(qf2 QuickFilter) QuickFilter

CopyFrom copies the set values from an existing QuickFilter.

If the two QuickFilters are not of the same Cap(), the receiver will be resized.

The original QuickFilter is no longer usable and must be replaced with the returned one. This approach prevents the QuickFilter from escaping to the heap.

func (QuickFilter) Delete

func (qf QuickFilter) Delete(index int) QuickFilter

Delete an index from the offset list.

The original QuickFilter is no longer usable and must be replaced with the returned one. This approach prevents the QuickFilter from escaping to the heap.

func (QuickFilter) Fill

func (qf QuickFilter) Fill() QuickFilter

Fill the QuickFilter to contain all the entries in the source slice.

The original QuickFilter is no longer usable and must be replaced with the returned one. This approach prevents the QuickFilter from escaping to the heap.

func (QuickFilter) Has

func (qf QuickFilter) Has(index int) bool

Has returns a boolean indicating whether the QuickFilter has the bit at given index set.

func (QuickFilter) IntersectionOf

func (qf QuickFilter) IntersectionOf(qf1, qf2 QuickFilter) QuickFilter

IntersectionOf fills the QuickFilter with the set values in one or both of the provided QuickFilters.

The receiver and passed QuickFilters must all be the same size or this will panic.

The original QuickFilter is no longer usable and must be replaced with the returned one. This approach prevents the QuickFilter from escaping to the heap.

func (QuickFilter) Iterate

func (qf QuickFilter) Iterate() Iterator

Iterate over the stored offsets.

func (QuickFilter) Len

func (qf QuickFilter) Len() int

Len returns the number of offsets stored.

func (QuickFilter) Resize

func (qf QuickFilter) Resize(sourceLen int) QuickFilter

Resize a QuickFilter to a new source length. Will allocate a new backing buffer if the source length won't fit in the old one.

The original QuickFilter is no longer usable and must be replaced with the returned one. This approach prevents the QuickFilter from escaping to the heap.

func (QuickFilter) UnionOf

func (qf QuickFilter) UnionOf(qf1, qf2 QuickFilter) QuickFilter

UnionOf fills the QuickFilter with the set values in one or both of the provided QuickFilters.

The receiver and passed QuickFilters must all be the same size or this will panic.

The original QuickFilter is no longer usable and must be replaced with the returned one. This approach prevents the QuickFilter from escaping to the heap.