From 2d939c9c6e62395ed924fe7c5cd4c4b294e391a9 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 5 Feb 2023 12:06:30 -0700 Subject: Rename to git.lukeshu.com/go/containers, split in to 2 separate packages --- .golangci.yml | 1 + cachemap.go | 114 ------------------------------------------------ go.mod | 2 +- map.go | 69 ----------------------------- map_go118.go | 9 ---- map_go120.go | 9 ---- pool.go | 33 -------------- syncutil/cachemap.go | 116 +++++++++++++++++++++++++++++++++++++++++++++++++ syncutil/map_go118.go | 9 ++++ syncutil/map_go120.go | 9 ++++ typedsync/map.go | 69 +++++++++++++++++++++++++++++ typedsync/map_go118.go | 9 ++++ typedsync/map_go120.go | 9 ++++ typedsync/pool.go | 33 ++++++++++++++ typedsync/value.go | 67 ++++++++++++++++++++++++++++ value.go | 67 ---------------------------- 16 files changed, 323 insertions(+), 302 deletions(-) delete mode 100644 cachemap.go delete mode 100644 map.go delete mode 100644 map_go118.go delete mode 100644 map_go120.go delete mode 100644 pool.go create mode 100644 syncutil/cachemap.go create mode 100644 syncutil/map_go118.go create mode 100644 syncutil/map_go120.go create mode 100644 typedsync/map.go create mode 100644 typedsync/map_go118.go create mode 100644 typedsync/map_go120.go create mode 100644 typedsync/pool.go create mode 100644 typedsync/value.go delete mode 100644 value.go diff --git a/.golangci.yml b/.golangci.yml index 1cd4c02..841866d 100644 --- a/.golangci.yml +++ b/.golangci.yml @@ -37,6 +37,7 @@ linters-settings: sections: - standard - default + - prefix(git.lukeshu.com/go/containers) gofmt: simplify: true gosec: diff --git a/cachemap.go b/cachemap.go deleted file mode 100644 index 3294aa2..0000000 --- a/cachemap.go +++ /dev/null @@ -1,114 +0,0 @@ -// Copyright (C) 2023 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package typedsync - -import ( - "sync" -) - -type cacheVal[V any] struct { - wg sync.WaitGroup - v V -} - -// The techniques used by CacheMap are similar to the techniques used -// by encoding/json's type cache. - -// A CacheMap is similar to a Map, but also has a .LoadOrCompute -// sibling to .LoadOrStore. This is useful for caching the results of -// computation where it is undesirable for concurrent calls to -// duplicate work. -// -// Compared to a plain Map, a CacheMap has both more space overhead -// and more time overhead. -type CacheMap[K mapkey, V any] struct { - inner Map[K, *cacheVal[V]] - pool Pool[*cacheVal[V]] -} - -func (m *CacheMap[K, V]) Delete(key K) { - m.inner.Delete(key) -} - -// Load returns the value stored in the map for a key. If the value -// for that key is actively being computed by LoadOrCompute, this -// blocks until the value has been computed. -func (m *CacheMap[K, V]) Load(key K) (value V, ok bool) { - _value, ok := m.inner.Load(key) - if !ok { - var zero V - return zero, false - } - _value.wg.Wait() - return _value.v, true -} - -// LoadAndDelete deletes the value for a key, returning the previous -// value if any. The loaded result reports whether the key was -// present. If the value for that key was actively being computed by -// LoadOrCompute, this immediately removes the partial value from the -// CacheMap, but does not return until the computation has finished. -func (m *CacheMap[K, V]) LoadAndDelete(key K) (value V, loaded bool) { - _value, ok := m.inner.LoadAndDelete(key) - if !ok { - var zero V - return zero, false - } - _value.wg.Wait() - return _value.v, true -} - -// LoadOrStore returns the existing value for the key if -// present. Otherwise, it stores and returns the given value. The -// loaded result is true if the value was loaded, false if stored. If -// the value for that key is actively being computed by LoadOrCompute, -// this blocks until the value has been computed. -func (m *CacheMap[K, V]) LoadOrStore(key K, value V) (actual V, loaded bool) { - _value, _ := m.pool.Get() - if _value == nil { - _value = new(cacheVal[V]) - } - _value.v = value - _actual, loaded := m.inner.LoadOrStore(key, _value) - if loaded { - *_value = cacheVal[V]{} - m.pool.Put(_value) - _actual.wg.Wait() - } - return _actual.v, loaded -} - -// LoadOrCompute returns the existing value for the key if present. -// Otherwise, it computes and stores a value using the given function. -// The loaded result is true if the value was loaded, false if -// computed. If a prior call to LoadOrCompute is still computing the -// value for that key, a latter call blocks until the computation is -// complete, and then returns the initial call's value. -func (m *CacheMap[K, V]) LoadOrCompute(key K, fn func(K) V) (actual V, loaded bool) { - _value, _ := m.pool.Get() - if _value == nil { - _value = new(cacheVal[V]) - } - _value.wg.Add(1) - _actual, loaded := m.inner.LoadOrStore(key, _value) - if loaded { - *_value = cacheVal[V]{} - m.pool.Put(_value) - _actual.wg.Wait() - } else { - _actual.v = fn(key) - _actual.wg.Done() - } - return _actual.v, loaded -} - -func (m *CacheMap[K, V]) Store(key K, value V) { - _value, _ := m.pool.Get() - if _value == nil { - _value = new(cacheVal[V]) - } - _value.v = value - m.inner.Store(key, _value) -} diff --git a/go.mod b/go.mod index bf43b51..cce6a1d 100644 --- a/go.mod +++ b/go.mod @@ -1,3 +1,3 @@ -module git.lukeshu.com/go/typedsync +module git.lukeshu.com/go/containers go 1.18 diff --git a/map.go b/map.go deleted file mode 100644 index 6bb1170..0000000 --- a/map.go +++ /dev/null @@ -1,69 +0,0 @@ -// Copyright (C) 2022-2023 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package typedsync - -import ( - "sync" -) - -// Map is a type-safe equivalent of the standard library's sync.Map. -// -// With versions of Go prior to Go 1.20, Map is specified too loosely, -// as -// -// Map[K any, V any] -// -// while with Go 1.20 and later, Map is specified as -// -// Map[K comparable, V any] -// -// This is because with Go versions prior to 1.20, 'comparable' was -// overly strict, disallowing many types that are valid map-keys (see -// https://github.com/golang/go/issues/56548). The type used as K in -// a Map older versions of Go must be a valid map-key type, even -// though the type specification of Map does not enforce that. -type Map[K mapkey, V any] struct { - inner sync.Map -} - -func (m *Map[K, V]) Delete(key K) { - m.inner.Delete(key) -} - -func (m *Map[K, V]) Load(key K) (value V, ok bool) { - _value, ok := m.inner.Load(key) - if ok { - //nolint:forcetypeassert // Typed wrapper around untyped lib. - value = _value.(V) - } - return value, ok -} - -func (m *Map[K, V]) LoadAndDelete(key K) (value V, loaded bool) { - _value, ok := m.inner.LoadAndDelete(key) - if ok { - //nolint:forcetypeassert // Typed wrapper around untyped lib. - value = _value.(V) - } - return value, ok -} - -func (m *Map[K, V]) LoadOrStore(key K, value V) (actual V, loaded bool) { - _actual, loaded := m.inner.LoadOrStore(key, value) - //nolint:forcetypeassert // Typed wrapper around untyped lib. - actual = _actual.(V) - return actual, loaded -} - -func (m *Map[K, V]) Range(f func(key K, value V) bool) { - m.inner.Range(func(key, value any) bool { - //nolint:forcetypeassert // Typed wrapper around untyped lib. - return f(key.(K), value.(V)) - }) -} - -func (m *Map[K, V]) Store(key K, value V) { - m.inner.Store(key, value) -} diff --git a/map_go118.go b/map_go118.go deleted file mode 100644 index 5446c88..0000000 --- a/map_go118.go +++ /dev/null @@ -1,9 +0,0 @@ -// Copyright (C) 2023 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -//go:build !go1.20 - -package typedsync - -type mapkey = any diff --git a/map_go120.go b/map_go120.go deleted file mode 100644 index 0d4ff5b..0000000 --- a/map_go120.go +++ /dev/null @@ -1,9 +0,0 @@ -// Copyright (C) 2023 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -//go:build go1.20 - -package typedsync - -type mapkey = comparable diff --git a/pool.go b/pool.go deleted file mode 100644 index c196085..0000000 --- a/pool.go +++ /dev/null @@ -1,33 +0,0 @@ -// Copyright (C) 2022-2023 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package typedsync - -import ( - "sync" -) - -type Pool[T any] struct { - New func() T - - inner sync.Pool -} - -func (p *Pool[T]) Get() (val T, ok bool) { - _val := p.inner.Get() - switch { - case _val != nil: - //nolint:forcetypeassert // Typed wrapper around untyped lib. - return _val.(T), true - case p.New != nil: - return p.New(), true - default: - var zero T - return zero, false - } -} - -func (p *Pool[T]) Put(val T) { - p.inner.Put(val) -} diff --git a/syncutil/cachemap.go b/syncutil/cachemap.go new file mode 100644 index 0000000..8eab4bc --- /dev/null +++ b/syncutil/cachemap.go @@ -0,0 +1,116 @@ +// Copyright (C) 2023 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package syncutil + +import ( + "sync" + + "git.lukeshu.com/go/containers/typedsync" +) + +type cacheVal[V any] struct { + wg sync.WaitGroup + v V +} + +// The techniques used by CacheMap are similar to the techniques used +// by encoding/json's type cache. + +// A CacheMap is similar to a typedsync.Map, but also has a +// .LoadOrCompute sibling to .LoadOrStore. This is useful for caching +// the results of computation where it is undesirable for concurrent +// calls to duplicate work. +// +// Compared to a plain typedsync.Map, a CacheMap has both more space +// overhead and more time overhead. +type CacheMap[K mapkey, V any] struct { + inner typedsync.Map[K, *cacheVal[V]] + pool typedsync.Pool[*cacheVal[V]] +} + +func (m *CacheMap[K, V]) Delete(key K) { + m.inner.Delete(key) +} + +// Load returns the value stored in the map for a key. If the value +// for that key is actively being computed by LoadOrCompute, this +// blocks until the value has been computed. +func (m *CacheMap[K, V]) Load(key K) (value V, ok bool) { + _value, ok := m.inner.Load(key) + if !ok { + var zero V + return zero, false + } + _value.wg.Wait() + return _value.v, true +} + +// LoadAndDelete deletes the value for a key, returning the previous +// value if any. The loaded result reports whether the key was +// present. If the value for that key was actively being computed by +// LoadOrCompute, this immediately removes the partial value from the +// CacheMap, but does not return until the computation has finished. +func (m *CacheMap[K, V]) LoadAndDelete(key K) (value V, loaded bool) { + _value, ok := m.inner.LoadAndDelete(key) + if !ok { + var zero V + return zero, false + } + _value.wg.Wait() + return _value.v, true +} + +// LoadOrStore returns the existing value for the key if +// present. Otherwise, it stores and returns the given value. The +// loaded result is true if the value was loaded, false if stored. If +// the value for that key is actively being computed by LoadOrCompute, +// this blocks until the value has been computed. +func (m *CacheMap[K, V]) LoadOrStore(key K, value V) (actual V, loaded bool) { + _value, _ := m.pool.Get() + if _value == nil { + _value = new(cacheVal[V]) + } + _value.v = value + _actual, loaded := m.inner.LoadOrStore(key, _value) + if loaded { + *_value = cacheVal[V]{} + m.pool.Put(_value) + _actual.wg.Wait() + } + return _actual.v, loaded +} + +// LoadOrCompute returns the existing value for the key if present. +// Otherwise, it computes and stores a value using the given function. +// The loaded result is true if the value was loaded, false if +// computed. If a prior call to LoadOrCompute is still computing the +// value for that key, a latter call blocks until the computation is +// complete, and then returns the initial call's value. +func (m *CacheMap[K, V]) LoadOrCompute(key K, fn func(K) V) (actual V, loaded bool) { + _value, _ := m.pool.Get() + if _value == nil { + _value = new(cacheVal[V]) + } + _value.wg.Add(1) + _actual, loaded := m.inner.LoadOrStore(key, _value) + if loaded { + *_value = cacheVal[V]{} + m.pool.Put(_value) + _actual.wg.Wait() + } else { + _actual.v = fn(key) + _actual.wg.Done() + } + return _actual.v, loaded +} + +func (m *CacheMap[K, V]) Store(key K, value V) { + _value, _ := m.pool.Get() + if _value == nil { + _value = new(cacheVal[V]) + } + _value.v = value + m.inner.Store(key, _value) +} diff --git a/syncutil/map_go118.go b/syncutil/map_go118.go new file mode 100644 index 0000000..2e71015 --- /dev/null +++ b/syncutil/map_go118.go @@ -0,0 +1,9 @@ +// Copyright (C) 2023 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +//go:build !go1.20 + +package syncutil + +type mapkey = any diff --git a/syncutil/map_go120.go b/syncutil/map_go120.go new file mode 100644 index 0000000..d6f62c1 --- /dev/null +++ b/syncutil/map_go120.go @@ -0,0 +1,9 @@ +// Copyright (C) 2023 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +//go:build go1.20 + +package syncutil + +type mapkey = comparable diff --git a/typedsync/map.go b/typedsync/map.go new file mode 100644 index 0000000..6bb1170 --- /dev/null +++ b/typedsync/map.go @@ -0,0 +1,69 @@ +// Copyright (C) 2022-2023 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package typedsync + +import ( + "sync" +) + +// Map is a type-safe equivalent of the standard library's sync.Map. +// +// With versions of Go prior to Go 1.20, Map is specified too loosely, +// as +// +// Map[K any, V any] +// +// while with Go 1.20 and later, Map is specified as +// +// Map[K comparable, V any] +// +// This is because with Go versions prior to 1.20, 'comparable' was +// overly strict, disallowing many types that are valid map-keys (see +// https://github.com/golang/go/issues/56548). The type used as K in +// a Map older versions of Go must be a valid map-key type, even +// though the type specification of Map does not enforce that. +type Map[K mapkey, V any] struct { + inner sync.Map +} + +func (m *Map[K, V]) Delete(key K) { + m.inner.Delete(key) +} + +func (m *Map[K, V]) Load(key K) (value V, ok bool) { + _value, ok := m.inner.Load(key) + if ok { + //nolint:forcetypeassert // Typed wrapper around untyped lib. + value = _value.(V) + } + return value, ok +} + +func (m *Map[K, V]) LoadAndDelete(key K) (value V, loaded bool) { + _value, ok := m.inner.LoadAndDelete(key) + if ok { + //nolint:forcetypeassert // Typed wrapper around untyped lib. + value = _value.(V) + } + return value, ok +} + +func (m *Map[K, V]) LoadOrStore(key K, value V) (actual V, loaded bool) { + _actual, loaded := m.inner.LoadOrStore(key, value) + //nolint:forcetypeassert // Typed wrapper around untyped lib. + actual = _actual.(V) + return actual, loaded +} + +func (m *Map[K, V]) Range(f func(key K, value V) bool) { + m.inner.Range(func(key, value any) bool { + //nolint:forcetypeassert // Typed wrapper around untyped lib. + return f(key.(K), value.(V)) + }) +} + +func (m *Map[K, V]) Store(key K, value V) { + m.inner.Store(key, value) +} diff --git a/typedsync/map_go118.go b/typedsync/map_go118.go new file mode 100644 index 0000000..5446c88 --- /dev/null +++ b/typedsync/map_go118.go @@ -0,0 +1,9 @@ +// Copyright (C) 2023 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +//go:build !go1.20 + +package typedsync + +type mapkey = any diff --git a/typedsync/map_go120.go b/typedsync/map_go120.go new file mode 100644 index 0000000..0d4ff5b --- /dev/null +++ b/typedsync/map_go120.go @@ -0,0 +1,9 @@ +// Copyright (C) 2023 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +//go:build go1.20 + +package typedsync + +type mapkey = comparable diff --git a/typedsync/pool.go b/typedsync/pool.go new file mode 100644 index 0000000..c196085 --- /dev/null +++ b/typedsync/pool.go @@ -0,0 +1,33 @@ +// Copyright (C) 2022-2023 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package typedsync + +import ( + "sync" +) + +type Pool[T any] struct { + New func() T + + inner sync.Pool +} + +func (p *Pool[T]) Get() (val T, ok bool) { + _val := p.inner.Get() + switch { + case _val != nil: + //nolint:forcetypeassert // Typed wrapper around untyped lib. + return _val.(T), true + case p.New != nil: + return p.New(), true + default: + var zero T + return zero, false + } +} + +func (p *Pool[T]) Put(val T) { + p.inner.Put(val) +} diff --git a/typedsync/value.go b/typedsync/value.go new file mode 100644 index 0000000..99c8876 --- /dev/null +++ b/typedsync/value.go @@ -0,0 +1,67 @@ +// Copyright (C) 2022-2023 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package typedsync + +import ( + "sync" +) + +// Value is a typed equivalent of sync/atomic.Value. +// +// It is not actually a wrapper around sync/atomic.Value for +// allocation-performance reasons. +type Value[T comparable] struct { + mu sync.Mutex + ok bool + val T +} + +// This uses a dumb mutex-based solution because +// +// 1. Performance is good enough, because in the fast-path mutexes +// use the same compare-and-swap as sync/atomic.Value; and because +// all of these methods are short we're unlikely to hit the +// mutex's slow path. +// +// 2. We could use sync/atomic.Pointer[T], which by itself would have +// the same performance characteristics as sync/atomic.Value but +// without the benefit of runtime_procPin()/runtime_procUnpin(). +// We want to avoid that because it means we're doing an +// allocation for every store/swap; avoiding that is our whole +// reason for not just wraping sync/atomic.Value. So then we'd +// want to use a Pool to reuse allocations; but (1) that adds more +// sync-overhead, and (2) it also gets trickier because we'd have +// to be careful about not adding a pointer back to the pool when +// load has grabbed the pointer but not yet dereferenced it. + +func (v *Value[T]) Load() (val T, ok bool) { + v.mu.Lock() + defer v.mu.Unlock() + return v.val, v.ok +} + +func (v *Value[T]) Store(val T) { + v.mu.Lock() + defer v.mu.Unlock() + v.val, v.ok = val, true +} + +func (v *Value[T]) Swap(newV T) (oldV T, oldOK bool) { + v.mu.Lock() + defer v.mu.Unlock() + oldV, oldOK = v.val, v.ok + v.val, v.ok = newV, true + return +} + +func (v *Value[T]) CompareAndSwap(oldV, newV T) (swapped bool) { + v.mu.Lock() + defer v.mu.Unlock() + if !v.ok || v.val != oldV { + return false + } + v.val = newV + return true +} diff --git a/value.go b/value.go deleted file mode 100644 index 99c8876..0000000 --- a/value.go +++ /dev/null @@ -1,67 +0,0 @@ -// Copyright (C) 2022-2023 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package typedsync - -import ( - "sync" -) - -// Value is a typed equivalent of sync/atomic.Value. -// -// It is not actually a wrapper around sync/atomic.Value for -// allocation-performance reasons. -type Value[T comparable] struct { - mu sync.Mutex - ok bool - val T -} - -// This uses a dumb mutex-based solution because -// -// 1. Performance is good enough, because in the fast-path mutexes -// use the same compare-and-swap as sync/atomic.Value; and because -// all of these methods are short we're unlikely to hit the -// mutex's slow path. -// -// 2. We could use sync/atomic.Pointer[T], which by itself would have -// the same performance characteristics as sync/atomic.Value but -// without the benefit of runtime_procPin()/runtime_procUnpin(). -// We want to avoid that because it means we're doing an -// allocation for every store/swap; avoiding that is our whole -// reason for not just wraping sync/atomic.Value. So then we'd -// want to use a Pool to reuse allocations; but (1) that adds more -// sync-overhead, and (2) it also gets trickier because we'd have -// to be careful about not adding a pointer back to the pool when -// load has grabbed the pointer but not yet dereferenced it. - -func (v *Value[T]) Load() (val T, ok bool) { - v.mu.Lock() - defer v.mu.Unlock() - return v.val, v.ok -} - -func (v *Value[T]) Store(val T) { - v.mu.Lock() - defer v.mu.Unlock() - v.val, v.ok = val, true -} - -func (v *Value[T]) Swap(newV T) (oldV T, oldOK bool) { - v.mu.Lock() - defer v.mu.Unlock() - oldV, oldOK = v.val, v.ok - v.val, v.ok = newV, true - return -} - -func (v *Value[T]) CompareAndSwap(oldV, newV T) (swapped bool) { - v.mu.Lock() - defer v.mu.Unlock() - if !v.ok || v.val != oldV { - return false - } - v.val = newV - return true -} -- cgit v1.2.3-54-g00ecf