README
¶
longadder
Thread-safe, high performance, contention-aware LongAdder and DoubleAdder for Go, inspired by OpenJDK9.
Beside JDK-based LongAdder and DoubleAdder, library includes other adders for various use.
Usage
JDKAdder (recommended)
package main
import (
"fmt"
"time"
ga "github.com/linxGnu/go-adder"
)
func main() {
adder := ga.NewLongAdder(ga.JDKAdderType)
for i := 0; i < 100; i++ {
go func() {
adder.Add(123)
}()
}
time.Sleep(3 * time.Second)
// get total added value
fmt.Println(adder.Sum())
}
RandomCellAdder
- A
LongAdderwith simple strategy of preallocating atomic cell and select random cell for update. - Slower than JDK LongAdder but 1.5-2x faster than atomic adder on contention.
- Consume ~1KB to store cells.
adder := ga.NewLongAdder(ga.RandomCellAdderType)
AtomicAdder
- A
LongAdderbased on atomic variable. All routines share this variable.
adder := ga.NewLongAdder(ga.AtomicAdderType)
MutexAdder
- A
LongAdderbased on mutex. All routines share same value and mutex.
adder := ga.NewLongAdder(ga.MutexAdderType)
Benchmark
- System: Dell PowerEdge R640
- CPU: 2 x Xeon Silver 4114 2.20GHz (40/40cores)
- Memory: 64GB 2400MHz DDR4
- OS: CentOS 7.5, 64-bit
- Source code: pkg_bench_test.go
- Go version: 1.12
goos: linux
goarch: amd64
BenchmarkAtomicF64AdderSingleRoutine-8 100 11558784 ns/op 0 B/op 0 allocs/op
BenchmarkJDKF64AdderSingleRoutine-8 100 12663869 ns/op 0 B/op 0 allocs/op
BenchmarkAtomicF64AdderMultiRoutine-8 3 414693263 ns/op 6672 B/op 18 allocs/op
BenchmarkJDKF64AdderMultiRoutine-8 30 39951114 ns/op 1178 B/op 4 allocs/op
BenchmarkAtomicF64AdderMultiRoutineMix-8 3 410603215 ns/op 16 B/op 1 allocs/op
BenchmarkJDKF64AdderMultiRoutineMix-8 30 49619434 ns/op 56 B/op 1 allocs/op
BenchmarkMutexAdderSingleRoutine-40 30 42931025 ns/op 0 B/op 0 allocs/op
BenchmarkAtomicAdderSingleRoutine-40 100 10022343 ns/op 0 B/op 0 allocs/op
BenchmarkRandomCellAdderSingleRoutine-40 50 38920149 ns/op 108 B/op 0 allocs/op
BenchmarkJDKAdderSingleRoutine-40 100 14030302 ns/op 0 B/op 0 allocs/op
BenchmarkMutexAdderMultiRoutine-40 2 576540605 ns/op 1456 B/op 16 allocs/op
BenchmarkAtomicAdderMultiRoutine-40 20 88861041 ns/op 419 B/op 2 allocs/op
BenchmarkRandomCellAdderMultiRoutine-40 30 45493866 ns/op 239 B/op 3 allocs/op
BenchmarkJDKAdderMultiRoutine-40 50 25724032 ns/op 140 B/op 2 allocs/op
BenchmarkMutexAdderMultiRoutineMix-40 2 581924480 ns/op 1120 B/op 12 allocs/op
BenchmarkAtomicAdderMultiRoutineMix-40 20 93733789 ns/op 16 B/op 1 allocs/op
BenchmarkRandomCellAdderMultiRoutineMix-40 20 62700287 ns/op 331 B/op 4 allocs/op
BenchmarkJDKAdderMultiRoutineMix-40 30 45089173 ns/op 230 B/op 3 allocs/op
Documentation
¶
Overview ¶
Package goadder contains a collection of thread-safe, concurrent data structures for reading and writing numeric int64-counter, inspired by OpenJDK9 LongAdder.
Beside JDKAdder, ported version of OpenJDK9 LongAdder, package also provides other alternatives for various use cases.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type AtomicAdder ¶
type AtomicAdder struct {
// contains filtered or unexported fields
}
AtomicAdder is simple atomic-based adder. Fastest at single routine but slow at multi routine when high-contention happens.
func (*AtomicAdder) Reset ¶
func (a *AtomicAdder) Reset()
Reset variables maintaining the sum to zero. This method may be a useful alternative to creating a new adder, but is only effective if there are no concurrent updates. Because this method is intrinsically racy.
func (*AtomicAdder) Store ¶
func (a *AtomicAdder) Store(v int64)
Store value. This function is only effective if there are no concurrent updates.
func (*AtomicAdder) Sum ¶
func (a *AtomicAdder) Sum() int64
Sum return the current sum. The returned value is NOT an atomic snapshot because of concurrent update.
func (*AtomicAdder) SumAndReset ¶
func (a *AtomicAdder) SumAndReset() (sum int64)
SumAndReset equivalent in effect to sum followed by reset. Like the nature of Sum and Reset, this function is only effective if there are no concurrent updates.
type AtomicF64Adder ¶ added in v0.1.2
type AtomicF64Adder struct {
// contains filtered or unexported fields
}
AtomicF64Adder is simple atomic-based adder. Fastest at single routine but slow at multi routine when high-contention happens.
func NewAtomicF64Adder ¶ added in v0.1.2
func NewAtomicF64Adder() *AtomicF64Adder
NewAtomicF64Adder create new AtomicF64Adder
func (*AtomicF64Adder) Add ¶ added in v0.1.2
func (a *AtomicF64Adder) Add(v float64)
Add the given value
func (*AtomicF64Adder) Reset ¶ added in v0.1.2
func (a *AtomicF64Adder) Reset()
Reset variables maintaining the sum to zero. This method may be a useful alternative to creating a new adder, but is only effective if there are no concurrent updates. Because this method is intrinsically racy.
func (*AtomicF64Adder) Store ¶ added in v0.1.2
func (a *AtomicF64Adder) Store(v float64)
Store value. This function is only effective if there are no concurrent updates.
func (*AtomicF64Adder) Sum ¶ added in v0.1.2
func (a *AtomicF64Adder) Sum() float64
Sum return the current sum. The returned value is NOT an atomic snapshot because of concurrent update.
func (*AtomicF64Adder) SumAndReset ¶ added in v0.1.2
func (a *AtomicF64Adder) SumAndReset() (sum float64)
SumAndReset equivalent in effect to sum followed by reset. Like the nature of Sum and Reset, this function is only effective if there are no concurrent updates.
type Float64Adder ¶ added in v0.1.2
type Float64Adder interface {
Add(x float64)
Inc()
Dec()
Sum() float64
Reset()
SumAndReset() float64
Store(v float64)
}
Float64Adder interface
func NewFloat64Adder ¶ added in v0.1.2
func NewFloat64Adder(t Type) Float64Adder
NewFloat64Adder create new float64 adder upon type
type FloatBinaryOperator ¶ added in v0.1.2
FloatBinaryOperator represents an operation upon two float64-valued operands and producing an float64-valued result
type JDKAdder ¶
type JDKAdder struct {
Striped64
}
JDKAdder is ported version of OpenJDK9 LongAdder.
When multiple routines update a common sum that is used for purposes such as collecting statistics, not for fine-grained synchronization control, contention overhead could be a pain.
JDKAdder is preferable to atomic, delivers significantly higher throughput under high contention, at the expense of higher space consumption, while keeping same characteristics under low contention.
One or more variables, called Cells, together maintain an initially zero sum. When updates are contended across routines, the set of variables may grow dynamically to reduce contention. In other words, updates are distributed over Cells. The value is lazy, only aggregated (sum) over Cells when needed.
JDKAdder is high performance, non-blocking and safe for concurrent use.
func (*JDKAdder) Reset ¶
func (u *JDKAdder) Reset()
Reset variables maintaining the sum to zero. This method may be a useful alternative to creating a new adder, but is only effective if there are no concurrent updates. Because this method is intrinsically racy.
func (*JDKAdder) Store ¶
Store value. This function is only effective if there are no concurrent updates.
func (*JDKAdder) Sum ¶
Sum return the current sum. The returned value is NOT an atomic snapshot because of concurrent update.
func (*JDKAdder) SumAndReset ¶
SumAndReset equivalent in effect to sum followed by reset. Like the nature of Sum and Reset, this function is only effective if there are no concurrent updates.
type JDKF64Adder ¶ added in v0.1.2
type JDKF64Adder struct {
StripedF64
}
JDKF64Adder is ported version of OpenJDK9 DoubleAdder.
When multiple routines update a common sum that is used for purposes such as collecting statistics, not for fine-grained synchronization control, contention overhead could be a pain.
JDKAdder is preferable to atomic, delivers significantly higher throughput under high contention, at the expense of higher space consumption, while keeping same characteristics under low contention.
One or more variables, called Cells, together maintain an initially zero sum. When updates are contended across routines, the set of variables may grow dynamically to reduce contention. In other words, updates are distributed over Cells. The value is lazy, only aggregated (sum) over Cells when needed.
JDKF64Adder is high performance, non-blocking and safe for concurrent use.
func NewJDKF64Adder ¶ added in v0.1.2
func NewJDKF64Adder() *JDKF64Adder
NewJDKF64Adder create new JDKF64Adder
func (*JDKF64Adder) Reset ¶ added in v0.1.2
func (f *JDKF64Adder) Reset()
Reset variables maintaining the sum to zero. This method may be a useful alternative to creating a new adder, but is only effective if there are no concurrent updates. Because this method is intrinsically racy.
func (*JDKF64Adder) Store ¶ added in v0.1.2
func (f *JDKF64Adder) Store(v float64)
Store value. This function is only effective if there are no concurrent updates.
func (*JDKF64Adder) Sum ¶ added in v0.1.2
func (f *JDKF64Adder) Sum() float64
Sum return the current sum. The returned value is NOT an atomic snapshot because of concurrent update.
func (*JDKF64Adder) SumAndReset ¶ added in v0.1.2
func (f *JDKF64Adder) SumAndReset() (sum float64)
SumAndReset equivalent in effect to sum followed by reset. Like the nature of Sum and Reset, this function is only effective if there are no concurrent updates.
type LongAdder ¶
type LongAdder interface {
Add(x int64)
Inc()
Dec()
Sum() int64
Reset()
SumAndReset() int64
Store(v int64)
}
LongAdder interface
func NewLongAdder ¶
NewLongAdder create new long adder upon type
type LongBinaryOperator ¶
LongBinaryOperator represents an operation upon two int64-valued operands and producing an int64-valued result
type MutexAdder ¶
type MutexAdder struct {
// contains filtered or unexported fields
}
MutexAdder is mutex-based LongAdder. Slowest compared to other alternatives.
func (*MutexAdder) Reset ¶
func (m *MutexAdder) Reset()
Reset variables maintaining the sum to zero. This method may be a useful alternative to creating a new adder, but is only effective if there are no concurrent updates. Because this method is intrinsically racy.
func (*MutexAdder) Store ¶
func (m *MutexAdder) Store(v int64)
Store value. This function is only effective if there are no concurrent updates.
func (*MutexAdder) Sum ¶
func (m *MutexAdder) Sum() (sum int64)
Sum return the current sum. The returned value is NOT an atomic snapshot because of concurrent update.
func (*MutexAdder) SumAndReset ¶
func (m *MutexAdder) SumAndReset() (sum int64)
SumAndReset equivalent in effect to sum followed by reset. Like the nature of Sum and Reset, this function is only effective if there are no concurrent updates.
type RandomCellAdder ¶
type RandomCellAdder struct {
// contains filtered or unexported fields
}
RandomCellAdder takes idea from JDKAdder by preallocating a fixed number of Cells. Unlike JDKAdder, in each update, RandomCellAdder assign a random-fixed Cell to invoker instead of retry/reassign Cell when contention.
RandomCellAdder is often faster than JDKAdder in multi routine race benchmark but slower in case of single routine (no race).
RandomCellAdder consume ~1KB for storing cells, which is often larger than JDKAdder which number of cells is dynamic.
func NewRandomCellAdder ¶
func NewRandomCellAdder() *RandomCellAdder
NewRandomCellAdder create new RandomCellAdder
func (*RandomCellAdder) Reset ¶
func (r *RandomCellAdder) Reset()
Reset variables maintaining the sum to zero. This method may be a useful alternative to creating a new adder, but is only effective if there are no concurrent updates. Because this method is intrinsically racy
func (*RandomCellAdder) Store ¶
func (r *RandomCellAdder) Store(v int64)
Store value. This function is only effective if there are no concurrent updates.
func (*RandomCellAdder) Sum ¶
func (r *RandomCellAdder) Sum() (sum int64)
Sum return the current sum. The returned value is NOT an atomic snapshot; invocation in the absence of concurrent updates returns an accurate result, but concurrent updates that occur while the sum is being calculated might not be incorporated.
func (*RandomCellAdder) SumAndReset ¶
func (r *RandomCellAdder) SumAndReset() (sum int64)
SumAndReset equivalent in effect to sum followed by reset. This method may apply for example during quiescent points between multithreaded computations. If there are updates concurrent with this method, the returned value is guaranteed to be the final value occurring before the reset.
type Striped64 ¶
type Striped64 struct {
// contains filtered or unexported fields
}
Striped64 is ported version of OpenJDK9 Striped64. It maintains a lazily-initialized table of atomically updated variables, plus an extra "base" field. The table size is a power of two. Indexing uses masked per-routine hash codes. Nearly all declarations in this class are package-private, accessed directly by subclasses.
In part because Cells are relatively large, we avoid creating them until they are needed. When there is no contention, all updates are made to the base field. Upon first contention (a failed CAS on base update), the table is initialized to size 2 and cap 4. The table size is doubled upon further contention until reaching the nearest power of two greater than or equal to the number of CPUS. Table slots remain empty (null) until they are needed.
A single spinlock ("cellsBusy") is used for initializing and resizing the table, as well as populating slots with new Cells. There is no need for a blocking lock; when the lock is not available, routines try other slots (or the base). During these retries, there is increased contention and reduced locality, which is still better than alternatives.
The routine probe maintain by SystemTime nanoseconds instead of OpenJDK ThreadLocalRandom. Contention and/or table collisions are indicated by failed CASes when performing an update operation. Upon a collision, if the table size is less than the capacity, it is doubled in size unless some other routine holds the lock. If a hashed slot is empty, and lock is available, a new Cell is created. Otherwise, if the slot exists, a CAS is tried. Retries proceed with reproducing probe.
The table size is capped because, when there are more routines than CPUs, supposing that each routine were bound to a CPU, there would exist a perfect hash function mapping routines to slots that eliminates collisions. When we reach capacity, we search for this mapping by randomly varying the hash codes of colliding routines. Because search is random, and collisions only become known via CAS failures, convergence can be slow, and because routines are typically not bound to CPUS forever, may not occur at all. However, despite these limitations, observed contention rates are typically low in these cases.
It is possible for a Cell to become unused when routines that once hashed to it terminate, as well as in the case where doubling the table causes no routine to hash to it under expanded mask. We do not try to detect or remove such cells, under the assumption that for long-running instances, observed contention levels will recur, so the cells will eventually be needed again; and for short-lived ones, it does not matter.
type StripedF64 ¶ added in v0.1.2
type StripedF64 struct {
// contains filtered or unexported fields
}
StripedF64 same as Striped64 but for float64
type Type ¶
type Type int
Type of LongAdder
const ( // JDKAdderType is type for JDK-based LongAdder JDKAdderType Type = iota // RandomCellAdderType is type for RandomCellAdder RandomCellAdderType // AtomicAdderType is type for atomic-based adder AtomicAdderType // MutexAdderType is type for MutexAdder MutexAdderType // JDKF64AdderType is type for JDK-based DoubleAdder JDKF64AdderType // AtomicF64AdderType is type for atomic-based float64 adder AtomicF64AdderType )
Source Files