You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@asyncband.apache.org by "Huliiiiii (via GitHub)" <gi...@apache.org> on 2026/08/26 20:33:41 UTC
[PR] perf: sharded `OnceTable` [asyncband]
Huliiiiii opened a new pull request, #225:
URL: https://github.com/apache/asyncband/pull/225
Alternative of #205
### Improvements
CPU: AMD Ryzen 9 9950X
OS: NixOS 25.11
#### Thread: 8
Benchmark (entry size) | Baseline | #205 | This PR (Mutex) | This PR vs. #205 | parking_lot::RwLock | RwLock vs. #205 | RwLock vs. This PR
-- | -- | -- | -- | -- | -- | -- | --
once_map::contended_compute_coalesced | 7.027 µs | 6.650 µs | 6.906 µs | 3.7% slower | 6.666 µs | 0.2% slower | 3.5% faster
once_map::contended_compute_hit_same_key | 964 ns | 296 ns | 1.113 µs | 73.4% slower | 312 ns | 5.1% slower | 3.6× faster
once_map::contended_compute_hit_disjoint (64) | 1.114 µs | 357 ns | 110 ns | 3.2× faster | 103 ns | 3.5× faster | 6.3% faster
once_map::contended_compute_hit_disjoint (1024) | 1.156 µs | 296 ns | 94 ns | 3.1× faster | 103 ns | 2.9× faster | 8.4% slower
once_map::contended_compute_miss_churn (64) | 3.552 µs | 4.979 µs | 208 ns | 23.9× faster | 223 ns | 22.4× faster | 6.6% slower
once_map::contended_compute_miss_churn (1024) | 3.542 µs | 4.867 µs | 223 ns | 21.8× faster | 231 ns | 21.1× faster | 3.4% slower
once_map::contended_compute_mixed (64) | 2.589 µs | 3.305 µs | 163 ns | 20.3× faster | 166 ns | 19.9× faster | 1.9% slower
once_map::contended_compute_mixed (1024) | 2.513 µs | 3.200 µs | 169 ns | 18.9× faster | 168 ns | 19.0× faster | 0.4% faster
once_map::contended_get_hit_same_key | 852 ns | 322 ns | 960 ns | 66.5% slower | 638 ns | 49.5% slower | 1.5× faster
once_map::contended_get_hit_disjoint (64) | 935 ns | 464 ns | 89 ns | 5.2× faster | 124 ns | 3.8× faster | 28.0% slower
once_map::contended_get_hit_disjoint (1024) | 963 ns | 461 ns | 65 ns | 7.1× faster | 70 ns | 6.6× faster | 7.4% slower
singleflight::contended_work_coalesced | 6.746 µs | 6.937 µs | 7.351 µs | 5.6% slower | 6.594 µs | 4.9% faster | 10.3% faster
singleflight::contended_work_same_key | 1.881 µs | 2.167 µs | 1.719 µs | 1.3× faster | 1.790 µs | 1.2× faster | 4.0% slower
singleflight::contended_work_disjoint_churn | 3.533 µs | 4.780 µs | 217 ns | 22.0× faster | 221 ns | 21.7× faster | 1.6% slower
#### Thread: 32
Benchmark (entry size) | Baseline | #205 | This PR (Mutex) | This PR vs. #205 | parking_lot::RwLock | RwLock vs. #205 | RwLock vs. This PR
-- | -- | -- | -- | -- | -- | -- | --
once_map::contended_compute_coalesced | 28.900 µs | 31.010 µs | 29.900 µs | 3.6% faster | 46.520 µs | 33.3% slower | 35.7% slower
once_map::contended_compute_hit_same_key | 3.915 µs | 2.576 µs | 6.607 µs | 61.0% slower | 2.097 µs | 18.6% faster | 3.2× faster
once_map::contended_compute_hit_disjoint (64) | 5.513 µs | 3.004 µs | 882 ns | 3.4× faster | 278 ns | 10.8× faster | 3.2× faster
once_map::contended_compute_hit_disjoint (1024) | 5.981 µs | 2.869 µs | 334 ns | 8.6× faster | 243 ns | 11.8× faster | 1.4× faster
once_map::contended_compute_miss_churn (64) | 29.290 µs | 42.010 µs | 948 ns | 44.3× faster | 1.246 µs | 33.7× faster | 23.9% slower
once_map::contended_compute_miss_churn (1024) | 26.960 µs | 38.790 µs | 988 ns | 39.3× faster | 1.257 µs | 30.9× faster | 21.4% slower
once_map::contended_compute_mixed (64) | 19.780 µs | 25.620 µs | 822 ns | 31.2× faster | 872 ns | 29.4× faster | 5.7% slower
once_map::contended_compute_mixed (1024) | 19.140 µs | 24.010 µs | 721 ns | 33.3× faster | 780 ns | 30.8× faster | 7.6% slower
once_map::contended_get_hit_same_key | 3.428 µs | 2.098 µs | 5.190 µs | 59.6% slower | 2.954 µs | 29.0% slower | 1.8× faster
once_map::contended_get_hit_disjoint (64) | 4.849 µs | 2.755 µs | 623 ns | 4.4× faster | 319 ns | 8.6× faster | 2.0× faster
once_map::contended_get_hit_disjoint (1024) | 4.896 µs | 2.810 µs | 325 ns | 8.6× faster | 234 ns | 12.0× faster | 1.4× faster
singleflight::contended_work_coalesced | 30.750 µs | 28.620 µs | 35.160 µs | 18.6% slower | 32.200 µs | 11.1% slower | 8.4% faster
singleflight::contended_work_same_key | 12.920 µs | 13.960 µs | 13.120 µs | 6.0% faster | 17.480 µs | 20.1% slower | 24.9% slower
singleflight::contended_work_disjoint_churn | 28.160 µs | 39.170 µs | 916 ns | 42.8× faster | 1.274 µs | 30.7× faster | 28.1% slower
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@asyncband.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@asyncband.apache.org
For additional commands, e-mail: commits-help@asyncband.apache.org
Re: [PR] perf: sharded `OnceTable` [asyncband]
Posted by "tisonkun (via GitHub)" <gi...@apache.org>.
tisonkun commented on code in PR #225:
URL: https://github.com/apache/asyncband/pull/225#discussion_r3879347724
##########
asyncband/src/internal/mod.rs:
##########
@@ -91,3 +85,13 @@ pub(crate) mod waitlist;
// `new`. One constructor is therefore unused in every single-primitive build.
#[allow(dead_code)]
pub(crate) mod waitset;
+
+#[cfg(any(feature = "once-map", feature = "singleflight"))]
+pub fn default_shard_count() -> usize {
+ // Tested on a 32-core machine, the optimal shard count for `OnceMap` and `Singleflight` is 256.
+ // So I use 8 as the coefficient, which is 256 / 32.
+ // Need to test on other machines to see if this coefficient is optimal.
+ // Dashmap use 4.
+ (std::thread::available_parallelism().map_or(1, |parallelism| parallelism.get()) * 8)
Review Comment:
[P2] Bound or expose the eager shard allocation
Eager CPU-scaled sharding has precedent, but this exact default is unusually aggressive for `OnceMap` and especially `singleflight::Group`. DashMap uses [`available_parallelism * 4`](https://docs.rs/dashmap/6.1.0/src/dashmap/lib.rs.html#67-72), eagerly creates its shards, and exposes [`with_shard_amount`](https://docs.rs/dashmap/latest/dashmap/struct.DashMap.html#method.with_shard_amount) constructors so callers can trade contention for footprint. The canonical [Go singleflight implementation](https://github.com/golang/sync/blob/master/singleflight/singleflight.go#L71-L81) instead lazily initializes one mutex-protected map, and [`scc::HashIndex`](https://docs.rs/scc/latest/scc/hash_index/struct.HashIndex.html#method.new), already used by this PR, starts with zero capacity.
This implementation uses `available_parallelism * 8` with no override. On this 14-way host that becomes 128 `#[repr(align(64))]` shards. An allocator probe measured:
- `OnceMap::new()` and `Group::new()`: 1 allocation / 8,192 bytes, versus 0 allocations in 0.6.7.
- `OnceMap::with_capacity(1)`: 132 allocations / 14,592 bytes, versus 1 allocation / 44 bytes in 0.6.7.
On the 32-core machine used to choose the coefficient, every empty instance starts with 256 shards and at least 16 KiB of cache-line-padded storage. The throughput results establish the benefit for a hot shared table, but do not cover construction or workloads containing many empty/small maps and groups.
Could we add construction/allocation benchmarks and either expose an explicit shard-count constructor with a more conservative or capped default, or allocate shard storage lazily? The sharding optimization itself is justified; the concern is making its most aggressive configuration an unavoidable per-instance cost.
##########
asyncband/src/once/once_map/table.rs:
##########
@@ -0,0 +1,394 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::borrow::Borrow;
+use std::fmt;
+use std::hash::BuildHasher;
+use std::hash::BuildHasherDefault;
+use std::hash::Hash;
+use std::hash::Hasher;
+use std::panic::UnwindSafe;
+use std::sync::Arc;
+use std::sync::MutexGuard;
+use std::sync::atomic::AtomicBool;
+use std::sync::atomic::Ordering;
+
+use hashbrown::HashTable;
+use scc::Equivalent;
+use scc::HashIndex;
+use scc::hash_index::Entry as IndexEntry;
+
+use crate::internal::default_shard_count;
+use crate::internal::mutex::CachePaddedMutex;
+use crate::internal::mutex::Mutex;
+use crate::once::OnceCell;
+
+type Entries<K, V> = HashTable<Arc<Entry<K, V>>>;
+
+pub struct Entry<K, V> {
+ hash: u64,
+ key: K,
+ cell: OnceCell<V>,
+ was_indexed: AtomicBool,
+}
+
+pub enum Lookup<K, V> {
+ Ready(V),
+ Entry(Arc<Entry<K, V>>),
+}
+
+impl<K, V> Entry<K, V> {
+ pub fn initialized(&self) -> bool {
+ self.cell.initialized()
+ }
+
+ pub fn get(&self) -> Option<&V> {
+ self.cell.get()
+ }
+
+ pub async fn get_or_init<F>(&self, init: F) -> &V
+ where
+ F: AsyncFnOnce() -> V,
+ {
+ self.cell.get_or_init(init).await
+ }
+
+ pub async fn get_or_try_init<E, F>(&self, init: F) -> Result<&V, E>
+ where
+ F: AsyncFnOnce() -> Result<V, E>,
+ {
+ self.cell.get_or_try_init(init).await
+ }
+}
+
+struct ReadyEntry<K, V>(Arc<Entry<K, V>>);
+
+impl<K: Eq, V> PartialEq for ReadyEntry<K, V> {
+ fn eq(&self, other: &Self) -> bool {
+ self.0.hash == other.0.hash && self.0.key == other.0.key
+ }
+}
+
+impl<K: Eq, V> Eq for ReadyEntry<K, V> {}
+
+impl<K, V> Hash for ReadyEntry<K, V> {
+ fn hash<H: Hasher>(&self, state: &mut H) {
+ state.write_u64(self.0.hash);
+ }
+}
+
+type BuildIdentityHasher = BuildHasherDefault<IdentityHasher>;
+
+#[derive(Default)]
+struct IdentityHasher(u64);
+
+impl Hasher for IdentityHasher {
+ fn finish(&self) -> u64 {
+ self.0
+ }
+
+ fn write(&mut self, bytes: &[u8]) {
+ for byte in bytes {
+ self.0 = self.0.rotate_left(8) ^ u64::from(*byte);
+ }
+ }
+
+ fn write_u64(&mut self, value: u64) {
+ self.0 = value;
+ }
+}
+
+pub struct Table<K, V, S> {
+ shards: Box<[CachePaddedMutex<Entries<K, V>>]>,
+ index: HashIndex<ReadyEntry<K, V>, (), BuildIdentityHasher>,
+ hasher: S,
+}
+
+/// `HashIndex` prevents `Table` from being automatically `UnwindSafe` unless `K` and `V` are
+/// `UnwindSafe`.
+/// Table operations are unwind-safe regardless, but since it was refactored from a
+/// mutex-backed implementation, implement `UnwindSafe` manually to retain the same auto-trait
+/// semantics.
+impl<K, V, S: UnwindSafe> UnwindSafe for Table<K, V, S> {}
+
+impl<K, V, S> fmt::Debug for Table<K, V, S>
+where
+ K: fmt::Debug,
+ V: fmt::Debug,
+{
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ let mut debug_map = f.debug_map();
+ for shard in &self.shards {
+ let entries = shard.0.lock();
+ debug_map.entries(entries.iter().map(|entry| (&entry.key, &entry.cell)));
+ }
+ debug_map.finish()
+ }
+}
+
+impl<K, V, S> Table<K, V, S> {
+ pub fn with_hasher(hasher: S) -> Self {
+ Self::with_capacity_and_hasher(0, hasher)
+ }
+
+ pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> Self {
+ let shard_count = default_shard_count();
+ let shard_capacity = capacity.div_ceil(shard_count);
+ let shards = (0..shard_count)
+ .map(|_| CachePaddedMutex(Mutex::new(HashTable::with_capacity(shard_capacity))))
+ .collect();
+
+ Self {
+ shards,
+ index: HashIndex::with_capacity_and_hasher(capacity, BuildIdentityHasher::default()),
+ hasher,
+ }
+ }
+
+ fn lock_shard(&self, hash: u64) -> MutexGuard<'_, Entries<K, V>> {
+ self.shards[(hash as usize) & (self.shards.len() - 1)]
+ .0
+ .lock()
+ }
+
+ #[cfg(test)]
+ pub fn len(&self) -> usize {
+ self.shards.iter().map(|shard| shard.0.lock().len()).sum()
+ }
+
+ #[cfg(test)]
+ pub fn is_empty(&self) -> bool {
+ self.shards.iter().all(|shard| shard.0.lock().is_empty())
+ }
+}
+
+impl<K, V, S> Table<K, V, S>
+where
+ K: Eq + Hash,
+ S: BuildHasher,
+{
+ fn lockup_index<Q>(&self, hash: u64, key: &Q) -> Option<V>
+ where
+ K: Borrow<Q>,
+ Q: Eq + ?Sized,
+ V: Clone,
+ {
+ // I think we need to add a function-based peek_with to scc instead of using new type here.
+ // Alternatively, we could write our own HashIndex.
+ struct LookupKey<'a, Q: ?Sized> {
+ hash: u64,
+ key: &'a Q,
+ }
+
+ impl<Q: ?Sized> Hash for LookupKey<'_, Q> {
+ fn hash<H: Hasher>(&self, state: &mut H) {
+ state.write_u64(self.hash);
+ }
+ }
+
+ impl<K, V, Q> Equivalent<ReadyEntry<K, V>> for LookupKey<'_, Q>
+ where
+ K: Borrow<Q>,
+ Q: Eq + ?Sized,
+ {
+ fn equivalent(&self, entry: &ReadyEntry<K, V>) -> bool {
+ entry.0.key.borrow() == self.key
+ }
+ }
+
+ self.index
+ .peek_with(&LookupKey { hash, key }, |entry, ()| entry.0.get().cloned())
+ .flatten()
+ }
+
+ pub fn get_or_insert(&self, key: K) -> Lookup<K, V>
+ where
+ V: Clone,
+ {
+ let hash = self.hasher.hash_one(&key);
+ if let Some(value) = self.lockup_index(hash, &key) {
+ return Lookup::Ready(value);
+ }
+
+ let entry = {
+ let mut shard = self.lock_shard(hash);
+ shard
+ .entry(hash, |entry| entry.key.eq(&key), |entry| entry.hash)
+ .or_insert_with(|| {
+ Arc::new(Entry {
+ hash,
+ key,
+ cell: OnceCell::new(),
+ was_indexed: AtomicBool::new(false),
+ })
+ })
+ .into_mut()
+ .clone()
+ };
+
+ match self.index_if_ready(&entry) {
+ Some(value) => Lookup::Ready(value),
+ None => Lookup::Entry(entry),
+ }
+ }
+
+ pub fn get<Q>(&self, key: &Q) -> Option<V>
+ where
+ K: Borrow<Q>,
+ Q: Eq + Hash + ?Sized,
+ V: Clone,
+ {
+ let hash = self.hasher.hash_one(key);
+
+ if let Some(value) = self.lockup_index(hash, key) {
+ Some(value)
+ } else {
+ let entry = self
+ .lock_shard(hash)
+ .find(hash, |entry| entry.key.borrow() == key)
+ .map(Arc::clone)?;
+
+ self.index_if_ready(&entry)
+ }
+ }
+
+ fn index_if_ready(&self, entry: &Arc<Entry<K, V>>) -> Option<V>
+ where
+ V: Clone,
+ {
+ let value = entry.get()?.clone();
+
+ {
+ let shard = self.lock_shard(entry.hash);
+ if shard
+ .find(entry.hash, |stored| Arc::ptr_eq(stored, entry))
+ .is_some()
+ {
+ self.index(entry);
+ }
+ }
+
+ Some(value)
+ }
+
+ pub fn remove<Q>(&self, key: &Q) -> Option<Arc<Entry<K, V>>>
+ where
+ K: Borrow<Q>,
+ Q: Eq + Hash + ?Sized,
+ {
+ let hash = self.hasher.hash_one(key);
+ let mut shard = self.lock_shard(hash);
+
+ let occupied = shard
+ .find_entry(hash, |entry| entry.key.borrow() == key)
+ .ok()?;
+ let (entry, _) = occupied.remove();
+
+ self.remove_from_index(&entry);
+ Some(entry)
+ }
+
+ pub fn cleanup_abandoned_entry(&self, entry: Arc<Entry<K, V>>) {
+ let mut shard = self.lock_shard(entry.hash);
+ // If the table still owns this entry, a count of two means the current call is its only
+ // owner outside the table. The pointer comparison rejects a detached or replaced entry.
+ if Arc::strong_count(&entry) == 2 && !entry.initialized() {
+ if let Ok(occupied) = shard.find_entry(entry.hash, |stored| Arc::ptr_eq(stored, &entry))
+ {
+ drop(occupied.remove());
+ }
+ }
+
+ // Drop this call's reference before unlocking so a waiting cleanup observes the updated
+ // reference count.
+ drop(entry);
+ }
+
+ fn insert(&self, key: K, value: V) {
+ let hash = self.hasher.hash_one(&key);
+ let entry = Arc::new(Entry {
+ hash,
+ key,
+ cell: OnceCell::from_value(value),
+ was_indexed: AtomicBool::new(false),
+ });
+
+ let mut shard = self.lock_shard(hash);
+ if let Ok(occupied) = shard.find_entry(hash, |stored| stored.key.eq(&entry.key)) {
+ let (replaced, _) = occupied.remove();
+ self.remove_from_index(&replaced);
+ }
+ shard.insert_unique(hash, Arc::clone(&entry), |entry| entry.hash);
+
+ self.index(&entry);
+ }
+
+ fn index(&self, entry: &Arc<Entry<K, V>>) {
+ loop {
+ match self.index.entry_sync(ReadyEntry(Arc::clone(entry))) {
+ IndexEntry::Occupied(occupied) => {
+ if Arc::ptr_eq(&occupied.key().0, entry) {
+ break;
+ }
+ occupied.remove_entry();
+ }
+ IndexEntry::Vacant(vacant) => {
+ vacant.insert_entry(());
+ break;
+ }
+ }
+ }
+
+ entry.was_indexed.store(true, Ordering::Relaxed);
+ }
+
+ fn remove_from_index(&self, entry: &Arc<Entry<K, V>>) {
+ struct EntryIdentity<'a, K, V>(&'a Arc<Entry<K, V>>);
+
+ impl<K, V> Hash for EntryIdentity<'_, K, V> {
+ fn hash<H: Hasher>(&self, state: &mut H) {
+ state.write_u64(self.0.hash);
+ }
+ }
+
+ impl<K, V> Equivalent<ReadyEntry<K, V>> for EntryIdentity<'_, K, V> {
+ fn equivalent(&self, entry: &ReadyEntry<K, V>) -> bool {
+ Arc::ptr_eq(&entry.0, self.0)
+ }
+ }
+
+ if entry.was_indexed.load(Ordering::Relaxed) {
+ self.index.remove_if_sync(&EntryIdentity(entry), |()| true);
Review Comment:
[P1] Drop entries when they are discarded
`HashIndex::remove_if_sync` only marks an entry unreachable and explicitly permits its memory to be reclaimed later. Because `ReadyEntry` owns a strong `Arc<Entry<K, V>>`, removing the entry from the shard does not release its key or value. The following integration test fails on this head with `left: 0, right: 1`, while it passes against 0.6.7:
```rust
#[test]
fn discard_drops_the_removed_value() {
use std::sync::Arc;
use std::sync::atomic::{AtomicUsize, Ordering};
use asyncband::once::OnceMap;
#[derive(Clone)]
struct DropCounter(Arc<AtomicUsize>);
impl Drop for DropCounter {
fn drop(&mut self) {
self.0.fetch_add(1, Ordering::SeqCst);
}
}
let drops = Arc::new(AtomicUsize::new(0));
let map: OnceMap<_, _> =
[(0, DropCounter(Arc::clone(&drops)))].into_iter().collect();
map.discard(&0);
assert_eq!(drops.load(Ordering::SeqCst), 1);
}
```
This is the documented reclamation behavior of [`HashIndex::remove_if_sync`](https://docs.rs/scc/latest/scc/hash_index/struct.HashIndex.html#method.remove_if_sync), but it is observable here because the deferred index entry owns the map's key and value transitively. Under insert/discard churn, resources can accumulate until the index collector—or the whole `OnceMap`—is dropped. Please avoid retaining a strong `Arc` in the deferred-reclamation index, or otherwise ensure that strong ownership is released before `discard` returns.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@asyncband.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@asyncband.apache.org
For additional commands, e-mail: commits-help@asyncband.apache.org
Re: [PR] perf: sharded `OnceTable` [asyncband]
Posted by "Huliiiiii (via GitHub)" <gi...@apache.org>.
Huliiiiii commented on PR #225:
URL: https://github.com/apache/asyncband/pull/225#issuecomment-5443421051
New Result:
### 1 Thread
Benchmark | 8ceb6b6 vs. baseline | std::sync::RwLock vs. baseline | Current vs. baseline | Current vs. 8ceb6b6 | Current vs. RwLock
-- | -- | -- | -- | -- | --
once_map::contended_compute_coalesced (baseline: 3.495 µs) | 1.1% slower (3.533 µs) | 2.0% faster (3.425 µs) | 1.4% faster (3.447 µs) | 2.4% faster | On par
once_map::contended_compute_hit_disjoint (64) | 22.2% slower | 19.0% slower | 7.7% slower | 15.7% faster | 12.2% faster
once_map::contended_compute_hit_disjoint (1024) | 25.8% slower | 22.8% slower | 9.5% slower | 1.22× faster | 14.6% faster
once_map::contended_compute_hit_same_key | 25.8% slower | 23.6% slower | 7.3% slower | 1.25× faster | 1.21× faster
once_map::contended_compute_miss_churn (64) | 3.1% slower | 10.8% slower | 13.2% slower | 10.4% slower | 2.7% slower
once_map::contended_compute_miss_churn (1024) | 7.9% slower | 12.7% slower | 13.9% slower | 6.5% slower | 1.4% slower
once_map::contended_compute_mixed (64) | 9.7% slower | 13.4% slower | 12.1% slower | 2.6% slower | 1.6% faster
once_map::contended_compute_mixed (1024) | 12.7% slower | 15.0% slower | 12.6% slower | On par | 2.6% faster
once_map::contended_get_hit_disjoint (64) | 32.7% slower | 32.9% slower | 6.1% faster | 1.58× faster | 1.59× faster
once_map::contended_get_hit_disjoint (1024) | 33.1% slower | 33.2% slower | 4.7% faster | 1.57× faster | 1.57× faster
once_map::contended_get_hit_same_key | 28.1% slower | 29.4% slower | 7.5% faster | 1.50× faster | 1.53× faster
### 2 Threads
Benchmark | 8ceb6b6 vs. baseline | std::sync::RwLock vs. baseline | Current vs. baseline | Current vs. 8ceb6b6 | Current vs. RwLock
-- | -- | -- | -- | -- | --
once_map::contended_compute_coalesced (baseline: 3.657 µs) | On par (3.655 µs) | On par (3.622 µs) | On par (3.688 µs) | On par | 1.8% slower
once_map::contended_compute_hit_disjoint (64) | 1.93× faster | 1.80× faster | 3.82× faster | 1.98× faster | 2.13× faster
once_map::contended_compute_hit_disjoint (1024) | 1.80× faster | 1.80× faster | 3.76× faster | 2.08× faster | 2.08× faster
once_map::contended_compute_hit_same_key | 61.9% slower | 48.7% slower | 1.93× faster | 5.05× faster | 3.75× faster
once_map::contended_compute_miss_churn (64) | 3.66× faster | 3.47× faster | 3.55× faster | 3.2% slower | 2.3% faster
once_map::contended_compute_miss_churn (1024) | 3.06× faster | 3.01× faster | 3.00× faster | 2.1% slower | On par
once_map::contended_compute_mixed (64) | 3.07× faster | 3.01× faster | 3.80× faster | 1.24× faster | 1.26× faster
once_map::contended_compute_mixed (1024) | 2.82× faster | 2.84× faster | 3.45× faster | 1.22× faster | 1.22× faster
once_map::contended_get_hit_disjoint (64) | 3.04× faster | 3.21× faster | 6.48× faster | 2.13× faster | 2.01× faster
once_map::contended_get_hit_disjoint (1024) | 2.26× faster | 1.49× faster | 6.29× faster | 2.78× faster | 4.22× faster
once_map::contended_get_hit_same_key | 31.3% slower | 3.6% slower | 6.09× faster | 8.86× faster | 6.31× faster
### 8 Threads
Benchmark | 8ceb6b6 vs. baseline | std::sync::RwLock vs. baseline | Current vs. baseline | Current vs. 8ceb6b6 | Current vs. RwLock
-- | -- | -- | -- | -- | --
once_map::contended_compute_coalesced (baseline: 7.193 µs) | 2.0% faster (7.050 µs) | 8.7% faster (6.567 µs) | 1.5% slower (7.299 µs) | 3.4% slower | 10.0% slower
once_map::contended_compute_hit_disjoint (64) | 12.2× faster | 10.3× faster | 32.0× faster | 2.63× faster | 3.12× faster
once_map::contended_compute_hit_disjoint (1024) | 12.2× faster | 9.95× faster | 31.5× faster | 2.57× faster | 3.17× faster
once_map::contended_compute_hit_same_key | 20.1% slower | 2.96× faster | 30.0× faster | 37.6× faster | 10.1× faster
once_map::contended_compute_miss_churn (64) | 17.1× faster | 17.9× faster | 18.1× faster | 5.7% faster | On par
once_map::contended_compute_miss_churn (1024) | 15.7× faster | 17.2× faster | 17.4× faster | 9.8% faster | 1.5% faster
once_map::contended_compute_mixed (64) | 16.2× faster | 17.5× faster | 24.3× faster | 1.50× faster | 1.39× faster
once_map::contended_compute_mixed (1024) | 15.5× faster | 17.2× faster | 21.5× faster | 1.38× faster | 1.25× faster
once_map::contended_get_hit_disjoint (64) | 11.6× faster | 6.95× faster | 50.3× faster | 4.35× faster | 7.24× faster
once_map::contended_get_hit_disjoint (1024) | 14.3× faster | 14.0× faster | 51.2× faster | 3.57× faster | 3.66× faster
once_map::contended_get_hit_same_key | 19.6% slower | 1.30× faster | 47.6× faster | 59.2× faster | 36.5× faster
### 32 Threads
Benchmark | 8ceb6b6 vs. baseline | std::sync::RwLock vs. baseline | Current vs. baseline | Current vs. 8ceb6b6 | Current vs. RwLock
-- | -- | -- | -- | -- | --
once_map::contended_compute_coalesced (baseline: 32.500 µs) | 11.0% slower (36.500 µs) | 4.2% faster (31.140 µs) | 15.2% slower (38.340 µs) | 4.8% slower | 18.8% slower
once_map::contended_compute_hit_disjoint (64) | 8.57× faster | 18.4× faster | 119.6× faster | 14.0× faster | 6.49× faster
once_map::contended_compute_hit_disjoint (1024) | 15.6× faster | 24.2× faster | 123.5× faster | 7.93× faster | 5.10× faster
once_map::contended_compute_hit_same_key | 33.6% slower | 1.98× faster | 109.1× faster | 164.2× faster | 55.0× faster
once_map::contended_compute_miss_churn (64) | 33.9× faster | 40.5× faster | 44.0× faster | 1.30× faster | 7.8% faster
once_map::contended_compute_miss_churn (1024) | 31.1× faster | 37.9× faster | 40.8× faster | 1.31× faster | 6.9% faster
once_map::contended_compute_mixed (64) | 28.0× faster | 36.5× faster | 57.2× faster | 2.04× faster | 1.57× faster
once_map::contended_compute_mixed (1024) | 28.6× faster | 37.5× faster | 54.1× faster | 1.89× faster | 1.44× faster
once_map::contended_get_hit_disjoint (64) | 7.58× faster | 16.2× faster | 175.2× faster | 23.1× faster | 10.8× faster
once_map::contended_get_hit_disjoint (1024) | 15.3× faster | 25.5× faster | 170.7× faster | 11.2× faster | 6.69× faster
once_map::contended_get_hit_same_key | 26.7% slower | 1.43× faster | 157.0× faster | 214.1× faster | 109.7× faster
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@asyncband.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@asyncband.apache.org
For additional commands, e-mail: commits-help@asyncband.apache.org
Re: [PR] perf: sharded `OnceTable` [asyncband]
Posted by "tisonkun (via GitHub)" <gi...@apache.org>.
tisonkun merged PR #225:
URL: https://github.com/apache/asyncband/pull/225
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@asyncband.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@asyncband.apache.org
For additional commands, e-mail: commits-help@asyncband.apache.org
Re: [PR] perf: sharded `OnceTable` [asyncband]
Posted by "aisk (via GitHub)" <gi...@apache.org>.
aisk commented on PR #225:
URL: https://github.com/apache/asyncband/pull/225#issuecomment-5438628084
Verified on bare-metal Linux: AMD Ryzen 7 5700X (8C/16T), NixOS 26.11, kernel 7.2.0, rustc 1.96.0, t=8, `--sample-count 100 --sample-size 10000`, interleaved rounds ×3 against base (c461305) and #205's head (6c55ca4). Values are medians of the 3 round-medians; per-round variance was <5% throughout, including the churn scenarios.
| scenario | base | this PR | #205 (6c55ca4) |
|---|---|---|---|
| `compute_hit_same_key` | 809.1 ns | 810.3 ns | **165.9 ns** |
| `get_hit_same_key` | 547.9 ns | 599.0 ns | **343.9 ns** |
| `compute_hit_disjoint` (64) | 908.3 ns | **100.9 ns** | 168.5 ns |
| `compute_hit_disjoint` (1024) | 913.0 ns | **96.3 ns** | 174.7 ns |
| `get_hit_disjoint` (64) | 715.6 ns | **84.2 ns** | 518.9 ns |
| `get_hit_disjoint` (1024) | 727.3 ns | **78.8 ns** | 530.8 ns |
| `compute_miss_churn` (64) | 3.06 µs | **223.6 ns** | 4.05 µs |
| `compute_miss_churn` (1024) | 2.91 µs | **232.5 ns** | 3.92 µs |
| `compute_mixed` (64) | 2.21 µs | **175.1 ns** | 2.63 µs |
| `compute_mixed` (1024) | 2.16 µs | **179.0 ns** | 2.54 µs |
| `compute_coalesced` | 18.41 µs | 18.53 µs | 18.47 µs |
| `work_same_key` | 2.07 µs | **1.80 µs** | 2.14 µs |
| `work_disjoint_churn` | 3.02 µs | **233.4 ns** | 3.74 µs |
| `work_coalesced` | 18.58 µs | 18.47 µs | 18.67 µs |
- The headline wins reproduce: 8.5–9.5× on disjoint hits, 12–13.7× on `miss_churn`/`mixed`/`work_disjoint_churn` (below the 16–24× on the 9950X, still decisive).
- The same-key penalty is milder here: `get_hit_same_key` −9% vs base, `compute_hit_same_key` on par, `work_same_key` +15%.
- Same-key hits are the one weak spot vs #205: every hit takes the shard mutex exclusively, so same-key traffic serializes on one shard — 810 vs 166 ns on `compute` hits (4.9×), 599 vs 344 ns on `get` (1.7×).
- Question: the branch only contains the Mutex-shard variant; the `parking_lot::RwLock` column from the table doesn't seem to be in the code. Is that variant pushed anywhere?
The two approaches look complementary: sharding covers disjoint/churn, a shared reader path plus the hit shortcut from 6c55ca4 covers same-key. A per-shard reader path on top of this PR should cover every scenario — happy to help with that.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@asyncband.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@asyncband.apache.org
For additional commands, e-mail: commits-help@asyncband.apache.org
Re: [PR] perf: sharded `OnceTable` [asyncband]
Posted by "Huliiiiii (via GitHub)" <gi...@apache.org>.
Huliiiiii commented on PR #225:
URL: https://github.com/apache/asyncband/pull/225#issuecomment-5455607962
Removed additional dependencies:
#### 32 threads
| Benchmark | Baseline (ns) | Before (ns) | Current (ns) | Before vs. baseline | Current vs. baseline | Before vs. Current |
|---|---:|---:|---:|---:|---:|---:|
| `once_map::contended_compute_hit_disjoint (64)` | 5355 | **45.80** | 87.51 | **116.92× faster** | 61.19× faster | **1.91× faster** |
| `once_map::contended_compute_hit_disjoint (1024)` | 6356 | **46.37** | 76.73 | **137.07× faster** | 82.84× faster | **1.65× faster** |
| `once_map::contended_compute_hit_same_key` | 4351 | **39.26** | 1392 | **110.83× faster** | 3.13× faster | **35.46× faster** |
| `once_map::contended_compute_miss_churn (64)` | 29150 | **440.1** | 469.9 | **66.23× faster** | 62.03× faster | **1.07× faster** |
| `once_map::contended_compute_miss_churn (1024)` | 28260 | **422.7** | 435.2 | **66.86× faster** | 64.94× faster | **1.03× faster** |
| `once_map::contended_compute_mixed (64)` | 20140 | **224.5** | 282.1 | **89.71× faster** | 71.39× faster | **1.26× faster** |
| `once_map::contended_compute_mixed (1024)` | 19570 | **227.6** | 262.6 | **85.98× faster** | 74.52× faster | **1.15× faster** |
| `once_map::contended_get_hit_disjoint (64)` | 4498 | **25.55** | 95.87 | **176.05× faster** | 46.92× faster | **3.75× faster** |
| `once_map::contended_get_hit_disjoint (1024)` | 4953 | **25.81** | 58.56 | **191.90× faster** | 84.58× faster | **2.27× faster** |
| `once_map::contended_get_hit_same_key` | 3834 | **24.41** | 2132 | **157.07× faster** | 1.80× faster | **87.34× faster** |
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@asyncband.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@asyncband.apache.org
For additional commands, e-mail: commits-help@asyncband.apache.org