does anyone familiar with the art have thoughts on why only tcmalloc switched from thread caches to cpu caches? would it make linux behavior diverge too much from other platforms?
(Not an expert but ...) unless you pin threads to cores, which is not the default and somewhat awkward in Linux for user applications, having a per-thread cache doesn't really make sense as your thread could be moved to another core and then your cache will no longer be local to the physical cache.
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)
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.
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.
> massive oversubscription of physical CPU cores (ie tens of thousands of threads) where TLS becomes utterly wasteful while also thrashing the cache
Are you sure you don't just have an axe to grind? Because that is an exceedingly uncommon edge case. Typically you only have a few threads and you aren't inundating the allocator with requests thus it is unlikely to make any practical difference.
If we do decide to concern ourselves with performance TLS has zero overhead and doesn't suffer from contention while rseq (at minimum) carries a penalty if preempted and involves setting a flag plus exhibits a data dependence for the address offset (the latter since AFAIK compilers don't natively support it as they do TLS). So while I'm certainly open to benchmarks to me it very much looks like a mixed bag that only comes up when you're already in questionable territory to begin with. In the event that we do step outside the norm I'd guess that a handful of threads with contention is a much more common scenario than thousands of threads per physical core exhibiting only minimal preemption.
I also expect something like a web server servicing thousands of requests in parallel to use an event loop instead of spawning an equivalent number of threads. I'm struggling to come up with a scenario where you haven't already fatally shot yourself in the foot and this remains a useful optimization to make. It's certainly relevant if you're using fibers (green threads, whatever you want to call them) but at that point you aren't in c calling malloc and your language runtime will (one hopes) already be taking care of all this for you.
> Are you sure you don't just have an axe to grind? Because that is an exceedingly uncommon edge case. Typically you only have a few threads and you aren't inundating the allocator with requests thus it is unlikely to make any practical difference.
Totally fair, and I agree that you should only have a few threads (or TPC) and shouldn’t be inundating the allocator with requests. But I’m only grinding this axe because I’ve personally had to deal with a system that went against most of that guidance.
We ran far too many threads in a memory-constrained environment. Thread count was many multiples of core count.
I totally agree that this is “questionable territory”, but honestly, any application that’s outgrown the basic glibc malloc has made a few mistakes.
skavi · · focus · HN ↗
rwmj · · focus · HN ↗
skavi · · focus · HN ↗
Someone · · focus · HN ↗
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)
skavi · · focus · HN ↗
i don’t believe rseq based cpu local caches require memory barriers on the fast path.
fc417fc802 · · focus · HN ↗
Meanwhile the better the scheduler performs the more competitive the thread local approach becomes.
skavi · · focus · HN ↗
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.
fc417fc802 · · focus · HN ↗
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.
skavi · · focus · HN ↗
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
fc417fc802 · · focus · HN ↗
If we do decide to concern ourselves with performance TLS has zero overhead and doesn't suffer from contention while rseq (at minimum) carries a penalty if preempted and involves setting a flag plus exhibits a data dependence for the address offset (the latter since AFAIK compilers don't natively support it as they do TLS). So while I'm certainly open to benchmarks to me it very much looks like a mixed bag that only comes up when you're already in questionable territory to begin with. In the event that we do step outside the norm I'd guess that a handful of threads with contention is a much more common scenario than thousands of threads per physical core exhibiting only minimal preemption.
I also expect something like a web server servicing thousands of requests in parallel to use an event loop instead of spawning an equivalent number of threads. I'm struggling to come up with a scenario where you haven't already fatally shot yourself in the foot and this remains a useful optimization to make. It's certainly relevant if you're using fibers (green threads, whatever you want to call them) but at that point you aren't in c calling malloc and your language runtime will (one hopes) already be taking care of all this for you.
skavi · · focus · HN ↗
Totally fair, and I agree that you should only have a few threads (or TPC) and shouldn’t be inundating the allocator with requests. But I’m only grinding this axe because I’ve personally had to deal with a system that went against most of that guidance.
We ran far too many threads in a memory-constrained environment. Thread count was many multiples of core count.
I totally agree that this is “questionable territory”, but honestly, any application that’s outgrown the basic glibc malloc has made a few mistakes.