sharded.go

package sharded

import(
	"unsafe"
	"sync/atomic"
	"reflect"
	"math/bits"
	"runtime"
)

type shardedValue uintptr // *[N]shard

const (
    lenbits = 6
    lenmask = (uintptr)((1<<lenbits)-1)
    addrmask = ^(uintptr)(lenmask)
    elemsize = 64

    empty = 0
    locked = ^uintptr((1 << lenbits)-1)
)

func (v *shardedValue) GetUintptr() *uintptr {
    pv := v.get()
    return (*uintptr)(unsafe.Pointer(pv))
}

func (v *shardedValue) GetUint32() *uint32 {
    pv := v.get()
    return (*uint32)(unsafe.Pointer(pv))
}

func (v *shardedValue) GetUint64() *uint64 {
    pv := v.get()
    return (*uint64)(unsafe.Pointer(pv))
}

func (v *shardedValue) get() uintptr {
retry:
    pv := v.load()
    l := ptrToLen(pv)
    idx := cpuIndex()
    if l <= idx {
        v.allocate(pv)
        goto retry
    }
    addr := pv & addrmask
    return addr + uintptr(idx) * elemsize
}

func ptrToLen(pv uintptr) int {
    return 1 << ((pv & lenmask)-1)
}

func ptrToSlice(pv uintptr) []byte {
    return toSlice(
        pv & addrmask,
        ptrToLen(pv) * elemsize,
        ptrToLen(pv) * elemsize,
    )
}

func toSlice(data uintptr, len, cap int) []byte {
    var s []byte
    hdr := (*reflect.SliceHeader)(unsafe.Pointer(&s))
    hdr.Data = data
    hdr.Len = len
    hdr.Cap = cap
    return s
}

func (v *shardedValue) allocate(pv uintptr) {
    if v.load() != pv {
        return
    }
    c := cpuCount()
    l := bits.Len(uint(c))
    c = ptrToLen(uintptr(l))
    n := make([]byte, (c+1) * elemsize)
    p := uintptr(unsafe.Pointer(&n[elemsize]))
    p = (p & addrmask) | uintptr(l)
    if !v.cas(pv, locked) {
        return
    }
    copy(ptrToSlice(p), ptrToSlice(pv))
    v.store(p)
}

func (v *shardedValue) reset() uintptr {
    for {
        pv := v.load()
        if v.cas(pv, empty) {
			v.allocate(empty)
            return pv
        }
    }
}

func (v *shardedValue) load() uintptr {
    return atomic.LoadUintptr((*uintptr)(v))
}

func (v *shardedValue) store(new uintptr) {
    atomic.StoreUintptr((*uintptr)(v), new)
}

func (v *shardedValue) cas(old, new uintptr) bool {
    return atomic.CompareAndSwapUintptr((*uintptr)(v), old, new)
}

func cpuCount() int {
    return runtime.NumCPU()
}

func cpuIndex() int {
    return 1
}

sharded2.go

package sharded

type value struct { ... }
// get returns a cacheline-sized, cacheline-aligned slice of bytes corresponding
// to the shard owned by the current P. 
func (*value) get() []byte {}
// atomically resets all shards to the zero value; returns the previous value of all shards
func (*value) reset() [][]byte {}

// value with acquire/release, to allow reset to complete only when reads/writes have completed
type avalue struct { value }
func (*avalue) acquire() {}
func (*avalue) release() {}
func (*avalue) get() []byte {}
func (*avalue) reset() [][]byte {}

type Uint64 struct { avalue }
func (*Uint64) get() *uint64 {}
func (*Uint64) Load() uint64 {}
func (*Uint64) Store(uint64) {}
func (*Uint64) Add(uint64) uint64 {}
func (*Uint64) CompareAndSwap(uint64, uint64) (uint64, bool) {}
func (*Uint64) Reset() []uint64 {}

/*
func (v *Uint64) CompareAndSwap(old, new uint64) (new uint64, swapped bool) {
  v.acquire()
  p := v.get()
  swapped = atomic.CompareAndSwapUint64(p, old, new)
  if !swapped {
    new = atomic.LoadUint64(p)
  }
  v.release()
  return
}

func (v *Uint64) get() *uint64 {
  s := v.avalue.get()
  return (uint64*)unsafe.Pointer(&s[0])
}
*/