DOCSEARCHbyAlgolia
Submit Docs

xsync

repository·main·Indexed 23 days ago

https://github.com/puzpuzpuz/xsync

A Go library providing highly scalable, concurrent data structures optimized for high-contention scenarios. It offers alternatives to the standard sync package, including a Cache-Line Hash Table (CLHT) based Map, a striped Counter, reader-biased RBMutex, and various bounded and unbounded queues (UMPSCQueue, SPSCQueue, MPMCQueue). Requires Go 1.24 or higher.

Tokens
5.2K
Snippets
8
Records
42
Agent score
80%

What's inside xsync

  1. Performance optimization: xsync.Map bucket alignment fix

    main

    The xsync.Map implementation includes a bucket-alignment fix that addresses a false sharing issue occurring in specific map sizes.

    The Problem: False Sharing

    In Go, for allocations in the [16, 512) byte range, the allocator prefixes the allocation with an 8-byte malloc header. This causes the slice base to sit at offset 8 (mod 64) instead of 0. In the original field order, the mu (mutex) field of bucket[i] would share a cache line with the hot read fields of bucket[i+1]. Consequently, every write operation (Store/Delete) on bucket[i] would invalidate the cache line for concurrent readers of bucket[i+1].

    The Fix

    The fields in the bucket struct were reordered so that mu precedes next. This ensures that frequent lock writes stay within the bucket's primary cache line, while the next pointer (which is only written during overflow chain growth) occupies the offset that shares a cache line with the next bucket.

    Performance Impact

    The fix provides significant performance gains for maps with 64 to 256 buckets (the default size and intermediate growth stages) without any API changes or memory overhead:

    • Write-only workloads: 15–26% faster.
    • Mixed workloads (e.g., 90% Load / 10% Store): 11–14% faster.

    For maps with $\ge 512$ buckets, the allocation uses the large-object path (page-aligned), so the performance impact is negligible/zero.

  2. Install and import xsync/v4

    main

    To use xsync, import the package with the /v4 suffix. The library requires Go version 1.24 or higher.

    import (
	"github.com/puzpuzpuz/xsync/v4"
)
    import (
	"github.com/puzpuzpuz/xsync/v4"
)

  3. Run xsync benchmarks

    main

    To run the benchmarks for the xsync repository and generate a statistical comparison, use the following commands. This requires benchstat to be installed in your environment.

    1. Run the Go benchmarks across multiple CPU counts and save the output to bench.txt.
    2. Use benchstat to analyze the results and save the summary to benchstat.txt.
    $ go test -run='^$' -cpu=1,2,4,8,16,32,64 -bench . -count=30 -timeout=0 | tee bench.txt
$ benchstat bench.txt | tee benchstat.txt

  4. What is a UMPSCQueue and when to use it

    main

    A UMPSCQueue[T] is an unbounded multi-producer single-consumer concurrent queue. It is designed as a replacement for Go channels but with infinite capacity.

    Key Characteristics

    • Unbounded Capacity: It dynamically allocates memory to store temporary bursts, meaning producers never block.
    • No Backpressure: Because it is unbounded, if consumers cannot keep up with producers, the queue will eventually consume all available memory and crash the process.
    • Concurrency Model:
      • Producers: Safe to call Enqueue from multiple goroutines concurrently.
      • Consumers: NOT safe for multiple goroutines to call Dequeue simultaneously. Consumers must explicitly synchronize between themselves (e.g., using a mutex or ensuring only one goroutine is responsible for consumption).

    When to use it

    Use UMPSCQueue when you have a high-volume burst of data from multiple producers and you want to ensure producers are never blocked, provided you have a reliable way to manage memory or ensure the consumer eventually catches up.

  5. Use SPSCQueue for high-performance lock-free communication

    main

    A SPSCQueue is a bounded single-producer single-consumer concurrent queue. It is designed for scenarios where exactly one goroutine is responsible for publishing items (the producer) and exactly one goroutine is responsible for consuming items (the consumer).

    Constraints:

    • Not more than one goroutine must be publishing to the queue.
    • Not more than one goroutine must be consuming from the queue.
    • Instances must be created using NewSPSCQueue.
    • An SPSCQueue must not be copied after its first use.

  6. MPMCQueue overview and usage

    main

    An MPMCQueue[I] is a bounded, concurrent, multi-producer multi-consumer queue designed for high-performance data passing. It is based on the C++ MPMCQueue implementation.

    Usage Pattern

    Because the queue is non-blocking, you typically use TryEnqueue and TryDequeue in a loop or within a worker pool pattern where you handle the false/ok=false cases (e.g., by retrying, waiting, or performing other tasks).

  7. Use xsync.Map for high-performance concurrent maps

    main

    The Map is a concurrent hash table-based map that follows the sync.Map interface but includes extensions like Compute and Size. It is optimized for modern CPUs using a Cache-Line Hash Table (CLHT) structure, making Get operations obstruction-free and highly scalable.

    Key Features

    • Conversion: Use xsync.ToPlainMap(m) to convert an xsync.Map to a standard Go map.
    • Bulk Deletion: Use DeleteMatching to remove entries based on a predicate.
    • High-Performance Iteration:
      • Range: Standard iteration.
      • RangeRelaxed: Lock-free iteration with relaxed consistency (the same key may be visited more than once if concurrently deleted and re-inserted).
      • AllRelaxed: Go 1.23+ iterator version of RangeRelaxed.
    m := xsync.NewMap[string, string]()
m.Store("foo", "bar")
v, ok := m.Load("foo")
s := m.Size()

// Convert to plain map
pm := xsync.ToPlainMap(m)

// Bulk conditional deletion
m.DeleteMatching(func(key int, value int) (delete, stop bool) {
	return key%2 == 0, false // delete even keys
})

// High-performance relaxed iteration
m.RangeRelaxed(func(key int, value int) bool {
	// process entry
	return true // continue iteration
})

  8. Use RBMutex (Reader-Biased Reader/Writer Mutex)

    main

    An RBMutex is a reader-biased mutex optimized for scenarios where read operations are much more frequent than write operations (e.g., caches). It uses a sharded fast-path for readers to reduce contention on a single atomic counter.

    Locking Methods

    • Blocking: RLock() returns a token that must be passed to RUnlock(token). Lock() and Unlock() behave like standard sync.RWMutex.
    • Optimistic: TryRLock() returns (bool, token) and TryLock() returns bool.
    mu := xsync.NewRBMutex()
// reader lock calls return a token
t := mu.RLock()
// the token must be later used to unlock the mutex
mu.RUnlock(t)

// writer locks
mu.Lock()
mu.Unlock()

// optimistic locking
if locked, t := mu.TryRLock(); locked {
	// critical reader section...
	mu.RUnlock(t)
}
if mu.TryLock() {
	// critical writer section...
	mu.Unlock()
}

  9. Use UMPSCQueue (Unbounded Multi-Producer Single-Consumer Queue)

    main

    An UMPSCQueue is an unbounded queue where multiple goroutines can call Enqueue, but exactly one goroutine must call Dequeue.

    Warning: Because it is unbounded, it does not provide backpressure. If the consumer cannot keep up with producers, the queue will grow until it exhausts available memory.

    q := xsync.NewUMPSCQueue[string]()
// producer inserts an item into the queue; doesn't block
// safe to invoke from multiple goroutines
inserted := q.Enqueue("bar")

// consumer obtains an item from the queue
// must be called from a single goroutine
item := q.Dequeue() // string

  10. Use SPSCQueue (Bounded Single-Producer Single-Consumer Queue)

    main

    A SPSCQueue is a bounded queue designed for exactly one producer and exactly one consumer. It uses a ring-buffer approach to minimize CPU cache coherency traffic.

    Since operations are optimistic and non-blocking, you must implement a back-off strategy (e.g., runtime.Gosched()) if TryEnqueue or TryDequeue fails.

    q := xsync.NewSPSCQueue[string](1024)
// producer inserts an item into the queue; optimistic attempt
inserted := q.TryEnqueue("bar")

// consumer obtains an item from the queue; optimistic attempt
item, ok := q.TryDequeue() // string

  11. Use xsync.Counter for high-contention counting

    main

    A Counter is a striped int64 counter (inspired by Java's LongAdder) designed to perform better than a single atomically updated int64 in high contention scenarios. Use Inc() to increment, Dec() to decrement, and Value() to read the current total.

    c := xsync.NewCounter()
// increment and decrement the counter
c.Inc()
c.Dec()
// read the current value
v := c.Value()

  12. Use MPMCQueue (Bounded Multi-Producer Multi-Consumer Queue)

    main

    An MPMCQueue is a bounded queue designed for scenarios with multiple concurrent producers and multiple concurrent consumers. It uses a ticket-based algorithm to allow parallelism.

    Best Practices:

    • Set the capacity to be significantly larger (e.g., an order of magnitude) than the number of producers/consumers to allow them to progress in parallel.
    • Implement a back-off strategy (like runtime.Gosched()) for failed optimistic attempts via TryEnqueue or TryDequeue.
    // capacity is rounded up to the next power of 2 (1000 -> 1024)
q := xsync.NewMPMCQueue[string](1000)
// producer optimistically inserts an item into the queue
inserted := q.TryEnqueue("bar")

// consumer optimistically obtains an item from the queue
item, ok := q.TryDequeue() // string