FlatConcurrentCache: is heap-allocating / user-defined work inside the per-bucket absl::base_internal::SpinLock intentional?

[yukawa]

Spun off from #1493 (comment)

While reading base/container/flat_concurrent_cache.h, I noticed that the per-bucket absl::base_internal::SpinLock ends up protecting any user-defined copy / move / destructor of Key and Value:

mozc/src/base/container/flat_concurrent_cache.h

Lines 71 to 80 in 9df9774

	bool Lookup(const Key& key, Value* value) const {
	auto [hash, bucket] = GetBucket(key);
	SpinLockHolder l(&bucket->mu);
	if (int i = bucket->FindIndex(key, hash, equal_); i != -1) {
	*value = *bucket->value[i];
	bucket->UpdateClock(i);
	return true;
	}
	return false;
	}

mozc/src/base/container/flat_concurrent_cache.h

Lines 82 to 101 in 9df9774

	// `value` accepts both references and movable objects.
	void Insert(const Key& key, Value&& value) {
	auto [hash, bucket] = GetBucket(key);
	SpinLockHolder l(&bucket->mu);
	// Update the value when key is found.
	if (int i = bucket->FindIndex(key, hash, equal_); i != -1) {
	bucket->value[i] =
	std::forward<Value>(value); // std::optional::operator=
	bucket->UpdateClock(i);
	return;
	}
	// Evicts the oldest value and insert new value.
	const int index = bucket->Evict();
	bucket->subhash[index] = hash;
	bucket->key[index] = key; // std::optional::operator=
	bucket->value[index] = std::forward<Value>(value);
	bucket->access_clock[index] = bucket->access_clock_val;
	}

For FlatConcurrentCache<std::string, std::string> with strings beyond the SSO threshold, each of those can call new / delete — heap work, and a potential page fault, under a spinlock.

Note that this is not a "100% CPU burning" failure mode: absl::base_internal::SpinLock's slow path falls through to SpinLockDelay, which on Windows is Sleep(0) then Sleep(N ms). Contenders do sleep. But that also means under contention every waiter pays a syscall + thread-yield, which is approximately the latency profile of absl::Mutex anyway — minus the wait queue and contention profile that Mutex actually gives us.

We are already violating Abseil's Compatibility Guideline here:

Do not depend upon internal details. If something is in a namespace, file, directory, or simply contains the string internal, impl, test, detail, benchmark, sample, or example, unless it is explicitly called out, it is not part of the public API. It’s an implementation detail. You cannot friend it, you cannot include it, you cannot mention it or refer to it in any way.

If there is no effective difference in the latency profile, can we just use absl::Mutex here?

[taku910]

This code ports the internal implementation. SpinLock is used simply for its size (absl::Mutex is 8 bytes, while SpinLock is half that at 4 bytes).

Each bucket allocates one SpinLock. Since a bucket has only 9 entries, (i.e,, size/9 SpinLock is allocated), using Mutex would overhead much memory.

[yukawa]

Ack. Smaller memory footprint sounds a good reason to not use absl::Mutex.

If it helps, here are what I learned after starting this thread regarding absl::base_internal::SpinLock vs std::atomic_flag.

Size comparison

• sizeof(absl::base_internal::SpinLock): 4 bytes
• sizeof(std::atomic_flag): 1 byte in Linux (libstdc++), macOS (libc++), and Windows (MSSTL).
• sizeof(std::atomic<int32_t>): 4 byte in Linux (libstdc++), macOS (libc++), and Windows (MSSTL).

Implementation comparison

• absl::base_internal::SpinLock::lock()
  • Linux: userspace spin -> futex on own word -> repeat
  • macOS and Windows: userspace spin -> kernel sleep() backoff with no kernel notify -> repeat
• std::atomic_flag::wait()
  • Linux (libstdc++): userspace spin ->futex on proxy waits with global hash tables -> repeat
  • macOS (libc++): userspace spin ->__ulock_wait on proxy waits with global hash tables -> repeat
  • Windows (MSSTL): WaitOnAddress() on own word, which internally has its own userspace spin -> repeat
• std::atomic<int32_t>::wait()
  • Linux (libstdc++): userspace spin ->futex on own word -> repeat
  • macOS (libc++): userspace spin ->__ulock_wait on own word -> repeat
  • Windows (MSSTL): WaitOnAddress() on own word, which internally has its own userspace spin -> repeat

Overall, the implementation of absl::base_internal::SpinLock as of Abseil LTS 20260107.1 is understandable on Linux, but questionable on macOS and Windows at least. On macOS and Windows, even 4-byte consumption might be hard to be justified if what we get is just a userspace spin with hardcoded sleep() backoff with no kernel notify.

To summarize my understandings:

• For OSS Mozc for Linux, absl::base_internal::SpinLock::lock() looks to be a simple and direct futex wrapper, which could be replaced with std::atomic<int32_t>::wait() with libstdc++.
• For OSS Mozc for macOS, std::atomic<int32_t>::wait() has more preferable characteristics compared to absl::base_internal::SpinLock::lock(). std::atomic_flag::wait() may also be a smaller alternative (only 1 byte!), but direct comparisons are a bit difficult due to its internal use of proxy-waits and global hash tables.
• For OSS Mozc for Windows, std::atomic_flag::wait() has much more preferable characteristics compared to absl::base_internal::SpinLock::lock().

References:

• [libc++] Switch to the officially documented APIs for implementing ulock_{wait,wake} on Apple llvm/llvm-project#146142
• [libc++] Improve performance of std::atomic_flag on Windows llvm/llvm-project#163524
• [libc++] Allows any types of size 4 and 8 to use native platform ulock_wait llvm/llvm-project#161086
• Windows: Implement condvar, mutex and rwlock using futex rust-lang/rust#121956
• atomic.cpp: Spinlock powering shared_ptr atomics can lead to priority inversion microsoft/STL#370
• https://news.ycombinator.com/item?id=41721668

[taku910]

It appears Abseil's spinlock is optimized for the common scenario where no one else is currently acquiring the lock, so further investigation into its performance may be necessary.

Additionally, the allocation size has been slightly improved by removing std::optional.