Hacker News Reader

Comment by Someone | Hacker News Reader

If you use a thread-local data structure, your allocator can pretend that it is running on a single-core, single-task system.

If you use a CPU-local data structure, you must handle the case where, mid-way through a call to your allocator, the CPU runs a second thread that makes another call to your allocator (and that, too, can get interrupted by another thread that allocates memory, etc.)

That makes thread-local easier to implement and likely faster (it doesn’t require any memory barriers in the fast path)

Also, good schedulers try to avoid moving threads between CPUs. The better they manage to do that, the lower the cost of having per thread data structures (there likely still is a price, as there most of the time are more threads than CPUs on a system)

View on HN

https://google.github.io/tcmalloc/rseq.html

i don’t believe rseq based cpu local caches require memory barriers on the fast path.

Setting aside whether or not you can pull off a lock free approach here we can be certain of a couple things. There will be at least some overhead that must be paid somewhere even if that's on a separate management thread. And there will be a lot of additional complexity because that's just how concurrency always is.

Meanwhile the better the scheduler performs the more competitive the thread local approach becomes.

https://docs.kernel.org/userspace-api/rseq.html

cost for interruption in an rseq critical section is that the PC gets overwritten to the rseq abort entry point before the task is rescheduled. no management thread necessary.

should be fairly minimal cost, especially assuming interruptions in the critical section are rare.

That's certainly interesting but I don't see how it would change my answer to you. Your question was why projects don't switch. My answer was because doing so seems likely to be a wash at absolute best.

Giving it some more thought, I expect caches will typically be wiped out by a context switch. So the only place rseq is likely to benefit an allocator is on systems with multiple NUMA nodes where you'd like to make sure any management code isn't paying a penalty by hitting the wrong address range.

IIUC rseq (ie CPU local data) is primarily good for two things. The first being obviating the need for atomics (specifically the resultant cache line ping-pong) but thread local data already accomplishes that. The second being massive oversubscription of physical CPU cores (ie tens of thousands of threads) where TLS becomes utterly wasteful while also thrashing the cache.

> seems likely to be a wash at absolute best

maybe i give it too much weight, but:

> massive oversubscription of physical CPU cores (ie tens of thousands of threads) where TLS becomes utterly wasteful while also thrashing the cache

seems worth solving to me

https://lwn.net/Articles/1033957/:

  rseq_cs

   The rseq_cs field is a pointer to a struct rseq_cs. Is is NULL when no
   rseq assembly block critical section is active for the registered
   thread. Setting it to point to a critical section descriptor (struct
   rseq_cs) marks the beginning of the critical section.

I’m not sure I fully understand that man page (it never seems to say callers have to clear that field at the end of a critical section, for example), but doesn’t that mean the caller has to guarantee setting rseq_cs happens_before any code in the critical section? That’s a memory barrier.

That is because you do not need to clear the field at the end of a critical section. It contains the contiguous instruction range where it fires so there is no problem with leaving it active forever unless you have another critical section where you want to use it.

No explicit memory barrier is required anywhere as the value is only read in supervisor mode and a privilege switch implicitly issues a LS-LS barrier on all major architectures. Even if you did not want to rely on that, you would only need a single S-LS barrier when you store the control structure the very first time.

> That is because you do not need to clear the field at the end of a critical section. It contains the contiguous instruction range where it fires so there is no problem with leaving it active forever unless you have another critical section where you want to use it.

Aha! So, to take advantage of that, a memory allocator uses the same abort handler for all operations?

TCMalloc has different abort handlers for each function: If preempted, we need to know where to restart.

If `rseq_cs` is no longer describing a relevant address, that is, the program counter has moved past it, the kernel just ignores it.

It's just a compiler barrier (signal fence), not a memory barrier that concerns the CPU. The CPU is free to reorder loads and stores.

TCMalloc TL here :)

The code is executed by a single thread. Everything retires in program order. There is no need for a memory barrier between starting the critical section and its body.

Reply on news.ycombinator.com