Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #122453 > unrolled thread
| Started by | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| First post | 2025-07-29 22:54 -0700 |
| Last post | 2025-08-07 21:08 -0700 |
| Articles | 20 on this page of 90 — 6 participants |
Back to article view | Back to comp.lang.c++
fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-07-29 22:54 -0700
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-02 12:58 -0700
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-02 13:00 -0700
Re: fun with a mutex... Muttley@DastardlyHQ.org - 2025-08-04 08:48 +0000
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-04 12:34 -0700
Re: fun with a mutex... Muttley@DastardlyHQ.org - 2025-08-05 07:27 +0000
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-05 16:10 -0700
Re: fun with a mutex... cross@spitfire.i.gajendra.net (Dan Cross) - 2025-08-06 00:38 +0000
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-05 19:14 -0700
Re: fun with a mutex... cross@spitfire.i.gajendra.net (Dan Cross) - 2025-08-06 11:29 +0000
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-06 15:43 -0700
Re: fun with a mutex... cross@spitfire.i.gajendra.net (Dan Cross) - 2025-08-08 01:41 +0000
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-07 20:52 -0700
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-05 19:16 -0700
Re: fun with a mutex... cross@spitfire.i.gajendra.net (Dan Cross) - 2025-08-06 12:04 +0000
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-06 15:47 -0700
Re: fun with a mutex... cross@spitfire.i.gajendra.net (Dan Cross) - 2025-08-08 01:49 +0000
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-07 20:59 -0700
Re: fun with a mutex... cross@spitfire.i.gajendra.net (Dan Cross) - 2025-08-09 09:17 +0000
Re: fun with a mutex... Bonita Montero <Bonita.Montero@gmail.com> - 2025-08-09 11:52 +0200
Re: fun with a mutex... cross@spitfire.i.gajendra.net (Dan Cross) - 2025-08-09 16:08 +0000
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-09 10:48 -0700
Re: fun with a mutex... cross@spitfire.i.gajendra.net (Dan Cross) - 2025-08-10 03:08 +0000
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-11 13:37 -0700
Re: fun with a mutex... cross@spitfire.i.gajendra.net (Dan Cross) - 2025-08-13 11:41 +0000
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-15 17:28 -0700
Re: fun with a mutex... cross@spitfire.i.gajendra.net (Dan Cross) - 2025-08-18 20:25 +0000
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-18 13:34 -0700
Re: fun with a mutex... cross@spitfire.i.gajendra.net (Dan Cross) - 2025-08-18 20:39 +0000
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-18 14:06 -0700
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-18 14:28 -0700
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-18 14:33 -0700
Re: fun with a mutex... cross@spitfire.i.gajendra.net (Dan Cross) - 2025-08-18 22:56 +0000
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-18 16:09 -0700
Re: fun with a mutex... cross@spitfire.i.gajendra.net (Dan Cross) - 2025-08-18 23:44 +0000
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-18 16:55 -0700
Re: fun with a mutex... cross@spitfire.i.gajendra.net (Dan Cross) - 2025-08-18 23:57 +0000
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-19 13:25 -0700
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-15 17:30 -0700
Re: fun with a mutex... cross@spitfire.i.gajendra.net (Dan Cross) - 2025-08-18 20:26 +0000
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-18 13:39 -0700
Re: fun with a mutex... cross@spitfire.i.gajendra.net (Dan Cross) - 2025-08-18 20:44 +0000
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-18 14:08 -0700
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-18 16:11 -0700
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-18 16:20 -0700
Re: fun with a mutex... Bonita Montero <Bonita.Montero@gmail.com> - 2025-08-11 11:04 +0200
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-11 13:30 -0700
Re: fun with a mutex... Bonita Montero <Bonita.Montero@gmail.com> - 2025-08-12 10:23 +0200
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-12 01:31 -0700
Re: fun with a mutex... Bonita Montero <Bonita.Montero@gmail.com> - 2025-08-12 10:39 +0200
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-12 01:45 -0700
Re: fun with a mutex... Bonita Montero <Bonita.Montero@gmail.com> - 2025-08-12 10:56 +0200
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-12 02:14 -0700
Re: fun with a mutex... Bonita Montero <Bonita.Montero@gmail.com> - 2025-08-12 15:08 +0200
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-15 21:36 -0700
Re: fun with a mutex... Bonita Montero <Bonita.Montero@gmail.com> - 2025-08-16 10:13 +0200
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-16 01:56 -0700
Re: fun with a mutex... Bonita Montero <Bonita.Montero@gmail.com> - 2025-08-16 11:05 +0200
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-16 13:31 -0700
Re: fun with a mutex... Bonita Montero <Bonita.Montero@gmail.com> - 2025-08-17 14:50 +0200
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-17 13:43 -0700
Re: fun with a mutex... cross@spitfire.i.gajendra.net (Dan Cross) - 2025-08-13 11:45 +0000
Re: fun with a mutex... Bonita Montero <Bonita.Montero@gmail.com> - 2025-08-13 19:07 +0200
Re: fun with a mutex... scott@slp53.sl.home (Scott Lurndal) - 2025-08-13 17:31 +0000
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-15 10:00 -0700
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-13 12:41 -0700
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-09 10:44 -0700
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-09 11:00 -0700
Re: fun with a mutex... "Fred. Zwarts" <F.Zwarts@HetNet.nl> - 2025-08-05 10:27 +0200
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-05 16:07 -0700
Re: fun with a mutex... "Fred. Zwarts" <F.Zwarts@HetNet.nl> - 2025-08-06 10:56 +0200
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-06 15:36 -0700
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-04 12:38 -0700
Re: fun with a mutex... Muttley@DastardlyHQ.org - 2025-08-05 07:29 +0000
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-05 16:08 -0700
Re: fun with a mutex... Bonita Montero <Bonita.Montero@gmail.com> - 2025-08-06 15:51 +0200
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-06 15:34 -0700
Re: fun with a mutex... Bonita Montero <Bonita.Montero@gmail.com> - 2025-08-07 06:44 +0200
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-07 12:17 -0700
Re: fun with a mutex... Bonita Montero <Bonita.Montero@gmail.com> - 2025-08-07 21:51 +0200
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-07 12:52 -0700
Re: fun with a mutex... Bonita Montero <Bonita.Montero@gmail.com> - 2025-08-16 11:21 +0200
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-16 13:22 -0700
Re: fun with a mutex... Bonita Montero <Bonita.Montero@gmail.com> - 2025-08-17 03:59 +0200
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-16 23:53 -0700
Re: fun with a mutex... Bonita Montero <Bonita.Montero@gmail.com> - 2025-08-17 10:37 +0200
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-07 12:32 -0700
Re: fun with a mutex... cross@spitfire.i.gajendra.net (Dan Cross) - 2025-08-08 01:51 +0000
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-07 21:01 -0700
Re: fun with a mutex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-08-07 21:08 -0700
Page 1 of 5 [1] 2 3 4 5 Next page →
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2025-07-29 22:54 -0700 |
| Subject | fun with a mutex... |
| Message-ID | <106cc2f$31ti3$1@dont-email.me> |
This is using the idea of trying to do other work while a mutex is
contended. Why spin or wait when we don't really have to? The per-thread
random numbers in this experiment are only there to try to simulate when
a contended thread has any other work to do. This can be check
per-thread stacks, queues, ect... Here is my example code. Can you get
it to run, and can you show me the output? Now, this can work in real
world environments. It's a stare to an adaptive mutex that just spins
doing nothing... lol... ;^)
I compiled it using c++20
(read all...)
____________________________________
// A Fun Mutex Pattern? Or, a Nightmare? Humm...
// By: Chris M. Thomasson
//___________________________________________________
#include <iostream>
#include <random>
#include <numeric>
#include <algorithm>
#include <thread>
#include <atomic>
#include <mutex>
#define CT_WORKERS (42)
#define CT_ITERS (996699)
#define CT_BACKOFFS (42)
#define CT_RAND_MAX (20)
#define CT_RAND_THRESHOLD (5)
struct ct_shared
{
std::mutex m_fun_mutex;
std::atomic<unsigned long> m_other_work = { 0 };
int m_test_count0 = 0;
void
sanity_check_dump() const
{
std::cout << "(ct_shared:" << this << ")->" <<
"m_test_count0 = " << m_test_count0 << ", " <<
"m_other_work = " <<
m_other_work.load(std::memory_order_relaxed) << "\n";
}
bool
sanity_check_validate() const
{
return (m_test_count0 == CT_ITERS * CT_WORKERS);
}
};
void
ct_worker_entry(
ct_shared& shared
) {
//std::cout << "ct_worker_entry" << std::endl; // testing thread
race for sure...
// Thread Local...
std::random_device rnd_seed = { };
std::mt19937 rnd_gen(rnd_seed());
std::uniform_int_distribution<unsigned long> rnd_dist(0, CT_RAND_MAX);
for (unsigned long i = 0; i < CT_ITERS; ++i)
{
// Lock logic...
{
unsigned long backoff = 0;
while (! shared.m_fun_mutex.try_lock())
{
unsigned long rnd0 = rnd_dist(rnd_gen);
if (rnd0 > CT_RAND_THRESHOLD || backoff > CT_BACKOFFS)
{
shared.m_fun_mutex.lock();
break;
}
// do other work... :^)
shared.m_other_work.fetch_add(1,
std::memory_order_relaxed);
// but not too much work... ;^o
++backoff;
}
}
// Critical Section...
{
shared.m_test_count0 = shared.m_test_count0 + 1;
}
// Unlock
{
shared.m_fun_mutex.unlock();
}
}
}
int main()
{
// Hello... :^)
{
std::cout << "Hello ct_fun_mutex... lol? ;^) ver:(0.0.0)\n";
std::cout << "By: Chris M. Thomasson\n";
std::cout <<
"____________________________________________________\n";
std::cout.flush();
}
// Create our fun things... ;^)
ct_shared shared = { };
std::thread workers[CT_WORKERS] = { };
// Lanuch...
{
std::cout << "Launching Threads...\n";
std::cout.flush();
for (unsigned long i = 0; i < CT_WORKERS; ++i)
{
workers[i] = std::thread(ct_worker_entry, std::ref(shared));
}
}
// Join...
{
std::cout << "Joining Threads... (computing :^)\n";
std::cout.flush();
for (unsigned long i = 0; i < CT_WORKERS; ++i)
{
workers[i].join();
}
}
// Sanity Check...
{
shared.sanity_check_dump();
if (! shared.sanity_check_validate())
{
std::cout << "\n\n**** Pardon my French, but FUCK!!!!!
****\n" << std::endl;
}
else
{
std::cout << "\nWe are Sane!\n\n";
std::cout << "We completed " <<
shared.m_other_work.load(std::memory_order_relaxed) <<
" work items while waiting for the mutex..." << std::endl;
}
}
// Fin...
{
std::cout <<
"____________________________________________________\n";
std::cout << "Fin... :^)\n" << std::endl;
}
return 0;
}
____________________________________
Any luck? Its fun to see how many work items were completed when the
mutex was contended...
[toc] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2025-08-02 12:58 -0700 |
| Message-ID | <106lql0$18eak$2@dont-email.me> |
| In reply to | #122453 |
On 7/29/2025 10:54 PM, Chris M. Thomasson wrote: > This is using the idea of trying to do other work while a mutex is > contended. Why spin or wait when we don't really have to? The per-thread > random numbers in this experiment are only there to try to simulate when > a contended thread has any other work to do. This can be check per- > thread stacks, queues, ect... Here is my example code. Can you get it to > run, and can you show me the output? Now, this can work in real world > environments. It's a stare to an adaptive mutex that just spins doing > nothing... lol... ;^) > > I compiled it using c++20 > > (read all...) [snip code] > Any luck? Its fun to see how many work items were completed when the > mutex was contended... I guess the main point is that if a try_lock() fails, then we can _try_ to do "other" work... That can be checking thread local queues, stacks, even try to get an io completion (think GetQueuedCompletionStatus() with a timeout of 0), if there is no other work to do, then we fallback to a lock(). If we are doing other work, we have to limit it via CT_BACKOFFS, then fall back to lock(). So, it allows for a so-called "productive backoff", instead of a run of the mill adaptive mutex that spins in userspace doing nothing before it goes to the kernel to wait on a contended mutex. Sound okay?
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2025-08-02 13:00 -0700 |
| Message-ID | <106lqo0$18eak$3@dont-email.me> |
| In reply to | #122454 |
On 8/2/2025 12:58 PM, Chris M. Thomasson wrote:
> On 7/29/2025 10:54 PM, Chris M. Thomasson wrote:
>> This is using the idea of trying to do other work while a mutex is
>> contended. Why spin or wait when we don't really have to? The per-
>> thread random numbers in this experiment are only there to try to
>> simulate when a contended thread has any other work to do. This can be
>> check per- thread stacks, queues, ect... Here is my example code. Can
>> you get it to run, and can you show me the output? Now, this can work
>> in real world environments. It's a stare to an adaptive mutex that
>> just spins doing nothing... lol... ;^)
>>
>> I compiled it using c++20
>>
>> (read all...)
> [snip code]
>> Any luck? Its fun to see how many work items were completed when the
>> mutex was contended...
>
> I guess the main point is that if a try_lock() fails, then we can _try_
> to do "other" work... That can be checking thread local queues, stacks,
> even try to get an io completion (think GetQueuedCompletionStatus() with
^^^^^^^^^^^^^^^^^^^^^^
Oh shit. That should be GetQueuedCompletionStatusEx(), its much better.
https://learn.microsoft.com/en-us/windows/win32/fileio/getqueuedcompletionstatusex-func
> a timeout of 0), if there is no other work to do, then we fallback to a
> lock(). If we are doing other work, we have to limit it via CT_BACKOFFS,
> then fall back to lock(). So, it allows for a so-called "productive
> backoff", instead of a run of the mill adaptive mutex that spins in
> userspace doing nothing before it goes to the kernel to wait on a
> contended mutex. Sound okay?
[toc] | [prev] | [next] | [standalone]
| From | Muttley@DastardlyHQ.org |
|---|---|
| Date | 2025-08-04 08:48 +0000 |
| Message-ID | <106ps51$22kjs$1@dont-email.me> |
| In reply to | #122454 |
On Sat, 2 Aug 2025 12:58:23 -0700 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> wibbled: >On 7/29/2025 10:54 PM, Chris M. Thomasson wrote: >> This is using the idea of trying to do other work while a mutex is >> contended. Why spin or wait when we don't really have to? The per-thread >> random numbers in this experiment are only there to try to simulate when >> a contended thread has any other work to do. This can be check per- >> thread stacks, queues, ect... Here is my example code. Can you get it to >> run, and can you show me the output? Now, this can work in real world >> environments. It's a stare to an adaptive mutex that just spins doing >> nothing... lol... ;^) >> >> I compiled it using c++20 >> >> (read all...) >[snip code] >> Any luck? Its fun to see how many work items were completed when the >> mutex was contended... > >I guess the main point is that if a try_lock() fails, then we can _try_ >to do "other" work... That can be checking thread local queues, stacks, I never really understood the point of this semi-sequential paradigm. If you have other work to do then do it in another thread, thats the whole point of threading! Meanwhile if a thread needs to wait for a lock then just let it wait.
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2025-08-04 12:34 -0700 |
| Message-ID | <106r1vh$2bkpn$3@dont-email.me> |
| In reply to | #122456 |
On 8/4/2025 1:48 AM, Muttley@DastardlyHQ.org wrote: > On Sat, 2 Aug 2025 12:58:23 -0700 > "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> wibbled: >> On 7/29/2025 10:54 PM, Chris M. Thomasson wrote: >>> This is using the idea of trying to do other work while a mutex is >>> contended. Why spin or wait when we don't really have to? The per-thread >>> random numbers in this experiment are only there to try to simulate when >>> a contended thread has any other work to do. This can be check per- >>> thread stacks, queues, ect... Here is my example code. Can you get it to >>> run, and can you show me the output? Now, this can work in real world >>> environments. It's a stare to an adaptive mutex that just spins doing >>> nothing... lol... ;^) >>> >>> I compiled it using c++20 >>> >>> (read all...) >> [snip code] >>> Any luck? Its fun to see how many work items were completed when the >>> mutex was contended... >> >> I guess the main point is that if a try_lock() fails, then we can _try_ >> to do "other" work... That can be checking thread local queues, stacks, > > I never really understood the point of this semi-sequential paradigm. If you > have other work to do then do it in another thread, thats the whole point of > threading! This already works with multiple threads, no problem. But, if a thread fails to acquire the mutex, it can check to see if it has any other work to do instead of just waiting in the kernel doing nothing, or spinning doing nothing... Make sense to you? > Meanwhile if a thread needs to wait for a lock then just let it wait. > The idea is instead of letting it wait, why not let it try to do some other work? Think of an adaptive mutex. On contention it will spin for a bounded number of times in user space before having to wait in the kernel. Well, instead of spinning, try to do something else, some real work? It will keep the thread hot, doing work instead of just waiting...
[toc] | [prev] | [next] | [standalone]
| From | Muttley@DastardlyHQ.org |
|---|---|
| Date | 2025-08-05 07:27 +0000 |
| Message-ID | <106sbol$2kchv$1@dont-email.me> |
| In reply to | #122457 |
On Mon, 4 Aug 2025 12:34:08 -0700 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> wibbled: >On 8/4/2025 1:48 AM, Muttley@DastardlyHQ.org wrote: >> I never really understood the point of this semi-sequential paradigm. If you >> have other work to do then do it in another thread, thats the whole point of >> threading! > >This already works with multiple threads, no problem. But, if a thread >fails to acquire the mutex, it can check to see if it has any other work >to do instead of just waiting in the kernel doing nothing, or spinning >doing nothing... Make sense to you? Yes, I understand the concept, its not rocket science. >> Meanwhile if a thread needs to wait for a lock then just let it wait. >> > >The idea is instead of letting it wait, why not let it try to do some >other work? Think of an adaptive mutex. On contention it will spin for a >bounded number of times in user space before having to wait in the >kernel. Well, instead of spinning, try to do something else, some real >work? It will keep the thread hot, doing work instead of just waiting... Because while its doing something else the lock maybe become free then become acquired again leading to a kind of race condition of some threads constantly bouncing off locks, checking for other work (which takes cpu cycles) , finding nothing then going back to the lock, rinse and repeat. Far simpler to have thread waiting on locks while other threads get on with work. Its not only more efficient it also leads to simpler code.
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2025-08-05 16:10 -0700 |
| Message-ID | <106u31a$31k65$2@dont-email.me> |
| In reply to | #122460 |
On 8/5/2025 12:27 AM, Muttley@DastardlyHQ.org wrote: > On Mon, 4 Aug 2025 12:34:08 -0700 > "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> wibbled: >> On 8/4/2025 1:48 AM, Muttley@DastardlyHQ.org wrote: >>> I never really understood the point of this semi-sequential paradigm. If you >>> have other work to do then do it in another thread, thats the whole point of >>> threading! >> >> This already works with multiple threads, no problem. But, if a thread >> fails to acquire the mutex, it can check to see if it has any other work >> to do instead of just waiting in the kernel doing nothing, or spinning >> doing nothing... Make sense to you? > > Yes, I understand the concept, its not rocket science. > >>> Meanwhile if a thread needs to wait for a lock then just let it wait. >>> >> >> The idea is instead of letting it wait, why not let it try to do some >> other work? Think of an adaptive mutex. On contention it will spin for a >> bounded number of times in user space before having to wait in the >> kernel. Well, instead of spinning, try to do something else, some real >> work? It will keep the thread hot, doing work instead of just waiting... > > Because while its doing something else the lock maybe become free then > become acquired again leading to a kind of race condition of some threads Nope. A thread can only do something else for a bounded number of times. So, its starvation free. No race condition. > constantly bouncing off locks, checking for other work (which takes cpu > cycles) , finding nothing then going back to the lock, rinse and repeat. > Far simpler to have thread waiting on locks while other threads get on with > work. Its not only more efficient it also leads to simpler code. > >
[toc] | [prev] | [next] | [standalone]
| From | cross@spitfire.i.gajendra.net (Dan Cross) |
|---|---|
| Date | 2025-08-06 00:38 +0000 |
| Message-ID | <106u86u$t1c$1@reader1.panix.com> |
| In reply to | #122467 |
In article <106u31a$31k65$2@dont-email.me>, Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote: >On 8/5/2025 12:27 AM, Muttley@DastardlyHQ.org wrote: >> On Mon, 4 Aug 2025 12:34:08 -0700 >> "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> wibbled: >>> [snip] >>> This already works with multiple threads, no problem. But, if a thread >>> fails to acquire the mutex, it can check to see if it has any other work >>> to do instead of just waiting in the kernel doing nothing, or spinning >>> doing nothing... Make sense to you? The idea behind what you're trying to do is well-understood. In fact, this is what generally happens when you try to acquire a contended, blocking mutex: if the mutex is currently locked by some other thread, you mark the acquiring thread as blocked waiting on the mutex, and then yield control back to a scheduler or something; eventually the other thread will finish what it was doing and release the mutex, but part of releasing the mutex and making it available again is marking threads that were blocked on it runnable, thus opening them up to be scheduled again, where they can once again try to acquire the mutex. The twist here seems to be that, instead of immediately yielding, for some bounded number of times, you look at a work queue and try to find something else for the acquiring thread to do while the lock you want is unavailable. Regardless, the effect is more or less the same. Personally, I see little benefit, and a number of potential pitfalls. In particular, I see no reason why the bundled bits of work in this scheme can't cause any number of lock ordering violations and lead to all sorts of deadlock scenarios. Suppose for example, that I acquire some mutex, A, and then go to acquire a second mutex, B: B is currently held by some other thread, so I begin to spin, but I see that there is an item in my work queue, so I go to do that. The first thing that work item does is try to acquire mutex A, which I'm currently holding, leading to deadlock against A. One could perhaps assert that these work items are not allowed to take or hold locks, which could address this particular failure mode, but it's unclear how one might enforce this in general, and there may well be other, similar failure modes. >>> [snip] >>> The idea is instead of letting it wait, why not let it try to do some >>> other work? Think of an adaptive mutex. On contention it will spin for a >>> bounded number of times in user space before having to wait in the >>> kernel. Well, instead of spinning, try to do something else, some real >>> work? It will keep the thread hot, doing work instead of just waiting... >> >> Because while its doing something else the lock maybe become free then >> become acquired again leading to a kind of race condition of some threads > >Nope. A thread can only do something else for a bounded number of times. >So, its starvation free. No race condition. This is simply not true. Suppose that the "something else" is computationally intensive, or blocks the thread somehow (say, by executing a blocking system call). What if the "something else" just spins in an infinte loop, waiting for some event? Just because you bound the number of times you do "something else" does not mean you are free of starvation, because what the other thing actual does matters. - Dan C.
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2025-08-05 19:14 -0700 |
| Message-ID | <106udpt$3400b$1@dont-email.me> |
| In reply to | #122468 |
On 8/5/2025 5:38 PM, Dan Cross wrote: > In article <106u31a$31k65$2@dont-email.me>, > Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote: >> On 8/5/2025 12:27 AM, Muttley@DastardlyHQ.org wrote: >>> On Mon, 4 Aug 2025 12:34:08 -0700 >>> "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> wibbled: >>>> [snip] >>>> This already works with multiple threads, no problem. But, if a thread >>>> fails to acquire the mutex, it can check to see if it has any other work >>>> to do instead of just waiting in the kernel doing nothing, or spinning >>>> doing nothing... Make sense to you? > > The idea behind what you're trying to do is well-understood. > > In fact, this is what generally happens when you try to acquire > a contended, blocking mutex: if the mutex is currently locked by > some other thread, you mark the acquiring thread as blocked > waiting on the mutex, and then yield control back to a scheduler > or something; eventually the other thread will finish what it > was doing and release the mutex, but part of releasing the mutex > and making it available again is marking threads that were > blocked on it runnable, thus opening them up to be scheduled > again, where they can once again try to acquire the mutex. > > The twist here seems to be that, instead of immediately > yielding, for some bounded number of times, you look at a work > queue and try to find something else for the acquiring thread to > do while the lock you want is unavailable. Regardless, the > effect is more or less the same. > > Personally, I see little benefit, and a number of potential > pitfalls. In particular, I see no reason why the bundled bits > of work in this scheme can't cause any number of lock ordering > violations and lead to all sorts of deadlock scenarios. Suppose > for example, that I acquire some mutex, A, and then go to > acquire a second mutex, B: B is currently held by some other > thread, so I begin to spin, but I see that there is an item in > my work queue, so I go to do that. The first thing that work > item does is try to acquire mutex A, which I'm currently > holding, leading to deadlock against A. > > One could perhaps assert that these work items are not allowed > to take or hold locks, which could address this particular > failure mode, but it's unclear how one might enforce this in > general, and there may well be other, similar failure modes. > >>>> [snip] >>>> The idea is instead of letting it wait, why not let it try to do some >>>> other work? Think of an adaptive mutex. On contention it will spin for a >>>> bounded number of times in user space before having to wait in the >>>> kernel. Well, instead of spinning, try to do something else, some real >>>> work? It will keep the thread hot, doing work instead of just waiting... >>> >>> Because while its doing something else the lock maybe become free then >>> become acquired again leading to a kind of race condition of some threads >> >> Nope. A thread can only do something else for a bounded number of times. >> So, its starvation free. No race condition. > > This is simply not true. Suppose that the "something else" is > computationally intensive, or blocks the thread somehow (say, by > executing a blocking system call). This is where try to do other work, well. Also, this is where the nightmare condition can occur. Try to do other work, non-blocking. Say trying to take a IOCP completion using a timeout of zero? If we got data, we add it to a local queue or something. No blocking. What if the "something else" > just spins in an infinte loop, waiting for some event? Just > because you bound the number of times you do "something else" > does not mean you are free of starvation, because what the other > thing actual does matters. No. If there is no other work to do, it falls back to lock(). If if did too much work, it falls back to lock.
[toc] | [prev] | [next] | [standalone]
| From | cross@spitfire.i.gajendra.net (Dan Cross) |
|---|---|
| Date | 2025-08-06 11:29 +0000 |
| Message-ID | <106veb1$eha$1@reader1.panix.com> |
| In reply to | #122470 |
In article <106udpt$3400b$1@dont-email.me>, Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote: >On 8/5/2025 5:38 PM, Dan Cross wrote: >> In article <106u31a$31k65$2@dont-email.me>, >> Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote: >>> On 8/5/2025 12:27 AM, Muttley@DastardlyHQ.org wrote: >>>> On Mon, 4 Aug 2025 12:34:08 -0700 >>>> "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> wibbled: >>>>> [snip] >>>>> This already works with multiple threads, no problem. But, if a thread >>>>> fails to acquire the mutex, it can check to see if it has any other work >>>>> to do instead of just waiting in the kernel doing nothing, or spinning >>>>> doing nothing... Make sense to you? >> >> The idea behind what you're trying to do is well-understood. >> >> In fact, this is what generally happens when you try to acquire >> a contended, blocking mutex: if the mutex is currently locked by >> some other thread, you mark the acquiring thread as blocked >> waiting on the mutex, and then yield control back to a scheduler >> or something; eventually the other thread will finish what it >> was doing and release the mutex, but part of releasing the mutex >> and making it available again is marking threads that were >> blocked on it runnable, thus opening them up to be scheduled >> again, where they can once again try to acquire the mutex. >> >> The twist here seems to be that, instead of immediately >> yielding, for some bounded number of times, you look at a work >> queue and try to find something else for the acquiring thread to >> do while the lock you want is unavailable. Regardless, the >> effect is more or less the same. >> >> Personally, I see little benefit, and a number of potential >> pitfalls. In particular, I see no reason why the bundled bits >> of work in this scheme can't cause any number of lock ordering >> violations and lead to all sorts of deadlock scenarios. Suppose >> for example, that I acquire some mutex, A, and then go to >> acquire a second mutex, B: B is currently held by some other >> thread, so I begin to spin, but I see that there is an item in >> my work queue, so I go to do that. The first thing that work >> item does is try to acquire mutex A, which I'm currently >> holding, leading to deadlock against A. >> >> One could perhaps assert that these work items are not allowed >> to take or hold locks, which could address this particular >> failure mode, but it's unclear how one might enforce this in >> general, and there may well be other, similar failure modes. >> >>>>> [snip] >>>>> The idea is instead of letting it wait, why not let it try to do some >>>>> other work? Think of an adaptive mutex. On contention it will spin for a >>>>> bounded number of times in user space before having to wait in the >>>>> kernel. Well, instead of spinning, try to do something else, some real >>>>> work? It will keep the thread hot, doing work instead of just waiting... >>>> >>>> Because while its doing something else the lock maybe become free then >>>> become acquired again leading to a kind of race condition of some threads >>> >>> Nope. A thread can only do something else for a bounded number of times. >>> So, its starvation free. No race condition. >> >> This is simply not true. Suppose that the "something else" is >> computationally intensive, or blocks the thread somehow (say, by >> executing a blocking system call). > >This is where try to do other work, well. Also, this is where the >nightmare condition can occur. Try to do other work, non-blocking. If you are talking about some kind of general mechanism, how would you even know in advance what the "something else" is? >Say >trying to take a IOCP completion using a timeout of zero? If we got >data, we add it to a local queue or something. No blocking. You're talking about Win32, consider how `GetQueuedCompletionStatus` might be implemented. You may well be taking a round-trip through the kernel to do that, which is very expensive compared to, say, incrementing a register. >> What if the "something else" >> just spins in an infinte loop, waiting for some event? Just >> because you bound the number of times you do "something else" >> does not mean you are free of starvation, because what the other >> thing actual does matters. > >No. If there is no other work to do, it falls back to lock(). If if did >too much work, it falls back to lock. You're missing the point: there's no good way to determine whether _any_ amount of work is "too much". - Dan C.
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2025-08-06 15:43 -0700 |
| Message-ID | <1070lq1$3lg2n$3@dont-email.me> |
| In reply to | #122473 |
On 8/6/2025 4:29 AM, Dan Cross wrote: > In article <106udpt$3400b$1@dont-email.me>, > Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote: >> On 8/5/2025 5:38 PM, Dan Cross wrote: >>> In article <106u31a$31k65$2@dont-email.me>, >>> Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote: >>>> On 8/5/2025 12:27 AM, Muttley@DastardlyHQ.org wrote: >>>>> On Mon, 4 Aug 2025 12:34:08 -0700 >>>>> "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> wibbled: >>>>>> [snip] >>>>>> This already works with multiple threads, no problem. But, if a thread >>>>>> fails to acquire the mutex, it can check to see if it has any other work >>>>>> to do instead of just waiting in the kernel doing nothing, or spinning >>>>>> doing nothing... Make sense to you? >>> >>> The idea behind what you're trying to do is well-understood. >>> >>> In fact, this is what generally happens when you try to acquire >>> a contended, blocking mutex: if the mutex is currently locked by >>> some other thread, you mark the acquiring thread as blocked >>> waiting on the mutex, and then yield control back to a scheduler >>> or something; eventually the other thread will finish what it >>> was doing and release the mutex, but part of releasing the mutex >>> and making it available again is marking threads that were >>> blocked on it runnable, thus opening them up to be scheduled >>> again, where they can once again try to acquire the mutex. >>> >>> The twist here seems to be that, instead of immediately >>> yielding, for some bounded number of times, you look at a work >>> queue and try to find something else for the acquiring thread to >>> do while the lock you want is unavailable. Regardless, the >>> effect is more or less the same. >>> >>> Personally, I see little benefit, and a number of potential >>> pitfalls. In particular, I see no reason why the bundled bits >>> of work in this scheme can't cause any number of lock ordering >>> violations and lead to all sorts of deadlock scenarios. Suppose >>> for example, that I acquire some mutex, A, and then go to >>> acquire a second mutex, B: B is currently held by some other >>> thread, so I begin to spin, but I see that there is an item in >>> my work queue, so I go to do that. The first thing that work >>> item does is try to acquire mutex A, which I'm currently >>> holding, leading to deadlock against A. >>> >>> One could perhaps assert that these work items are not allowed >>> to take or hold locks, which could address this particular >>> failure mode, but it's unclear how one might enforce this in >>> general, and there may well be other, similar failure modes. >>> >>>>>> [snip] >>>>>> The idea is instead of letting it wait, why not let it try to do some >>>>>> other work? Think of an adaptive mutex. On contention it will spin for a >>>>>> bounded number of times in user space before having to wait in the >>>>>> kernel. Well, instead of spinning, try to do something else, some real >>>>>> work? It will keep the thread hot, doing work instead of just waiting... >>>>> >>>>> Because while its doing something else the lock maybe become free then >>>>> become acquired again leading to a kind of race condition of some threads >>>> >>>> Nope. A thread can only do something else for a bounded number of times. >>>> So, its starvation free. No race condition. >>> >>> This is simply not true. Suppose that the "something else" is >>> computationally intensive, or blocks the thread somehow (say, by >>> executing a blocking system call). >> >> This is where try to do other work, well. Also, this is where the >> nightmare condition can occur. Try to do other work, non-blocking. > > If you are talking about some kind of general mechanism, how > would you even know in advance what the "something else" is? > >> Say >> trying to take a IOCP completion using a timeout of zero? If we got >> data, we add it to a local queue or something. No blocking. > > You're talking about Win32, consider how > `GetQueuedCompletionStatus` might be implemented. You may well > be taking a round-trip through the kernel to do that, which is > very expensive compared to, say, incrementing a register. > >>> What if the "something else" >>> just spins in an infinte loop, waiting for some event? Just >>> because you bound the number of times you do "something else" >>> does not mean you are free of starvation, because what the other >>> thing actual does matters. >> >> No. If there is no other work to do, it falls back to lock(). If if did >> too much work, it falls back to lock. > > You're missing the point: there's no good way to determine > whether _any_ amount of work is "too much". Fair enough. But, there is a chance to hit the fast path, so to speak. try_lock fails, then the thread does a call to say, GetQueuedCompletionStatusEx with a timeout of zero, (aka try), if it succeeds, it can push the batch into thread local queues, then try the try_lock again and succeeds. So, instead of waiting in the kernel for the mutex it did actual work, and god knows how many other threads got the mutex in the mean time. So, forward progress is guaranteed. The nature of the "tried" work must be known, and if its compatible, so be it. If not, so be it. Fair enough?
[toc] | [prev] | [next] | [standalone]
| From | cross@spitfire.i.gajendra.net (Dan Cross) |
|---|---|
| Date | 2025-08-08 01:41 +0000 |
| Message-ID | <1073kkb$mpg$1@reader1.panix.com> |
| In reply to | #122479 |
In article <1070lq1$3lg2n$3@dont-email.me>, Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote: >On 8/6/2025 4:29 AM, Dan Cross wrote: >> In article <106udpt$3400b$1@dont-email.me>, >> Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote: >>> [snip] >>> No. If there is no other work to do, it falls back to lock(). If if did >>> too much work, it falls back to lock. >> >> You're missing the point: there's no good way to determine >> whether _any_ amount of work is "too much". > >Fair enough. But, there is a chance to hit the fast path, so to speak. You literally have no way of knowing that beforehand. >try_lock fails, then the thread does a call to say, >GetQueuedCompletionStatusEx with a timeout of zero, (aka try), if it >succeeds, it can push the batch into thread local queues, then try the >try_lock again and succeeds. You are, again, missing the point. Not only does making a call to `GetQueuedCompletionStatusEx` involve a round trip through the kernel, in which case you may as well just block in the kernel and let another thread run, you seem to be missing the specific that IOCP completion is irrelevant, because it is just one example. >So, instead of waiting in the kernel for >the mutex it did actual work, and god knows how many other threads got >the mutex in the mean time. So, forward progress is guaranteed. The >nature of the "tried" work must be known, and if its compatible, so be >it. If not, so be it. Fair enough? No. You keep saying that "forward progress is guaranteed" because you bound the total number of times that your locking thread can do "something else." But again, the point that you are missing is that any given "something else" can itself be completely unbounded, possibly in a way that is totally unknowable at the time you go to do it; see the lock ordering constraint violation I gave earlier as an example: there's no way you can know whether that will be problematic until runtime, and there's no way you can meaningfully assess "compatibility" in general. So even if you bound the number of times you'll do "something else", since you have no guarantee that ANY instance of other work is itself bounded, you can't make any guarantees about whether the scheme as a whole is bounded. And if it's really just, "for this specific critical section, if you fail to immediately acquire the lock, go try this other, very specific thing known to be safe in this specific context, and then try again...." then as I've said, this is well-known, but is also wholly unoriginal and thus uninteresting. - Dan C.
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2025-08-07 20:52 -0700 |
| Message-ID | <1073s9j$en4a$2@dont-email.me> |
| In reply to | #122492 |
On 8/7/2025 6:41 PM, Dan Cross wrote: > In article <1070lq1$3lg2n$3@dont-email.me>, > Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote: >> On 8/6/2025 4:29 AM, Dan Cross wrote: >>> In article <106udpt$3400b$1@dont-email.me>, >>> Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote: >>>> [snip] >>>> No. If there is no other work to do, it falls back to lock(). If if did >>>> too much work, it falls back to lock. >>> >>> You're missing the point: there's no good way to determine >>> whether _any_ amount of work is "too much". >> >> Fair enough. But, there is a chance to hit the fast path, so to speak. > > You literally have no way of knowing that beforehand. > >> try_lock fails, then the thread does a call to say, >> GetQueuedCompletionStatusEx with a timeout of zero, (aka try), if it >> succeeds, it can push the batch into thread local queues, then try the >> try_lock again and succeeds. > > You are, again, missing the point. Not only does making a call > to `GetQueuedCompletionStatusEx` involve a round trip through > the kernel, in which case you may as well just block in the > kernel and let another thread run, you seem to be missing the > specific that IOCP completion is irrelevant, because it is just > one example. > >> So, instead of waiting in the kernel for >> the mutex it did actual work, and god knows how many other threads got >> the mutex in the mean time. So, forward progress is guaranteed. The >> nature of the "tried" work must be known, and if its compatible, so be >> it. If not, so be it. Fair enough? > > No. You keep saying that "forward progress is guaranteed" > because you bound the total number of times that your locking > thread can do "something else." But again, the point that you > are missing is that any given "something else" can itself be > completely unbounded, possibly in a way that is totally > unknowable at the time you go to do it; see the lock ordering > constraint violation I gave earlier as an example: there's no > way you can know whether that will be problematic until runtime, > and there's no way you can meaningfully assess "compatibility" > in general. > > So even if you bound the number of times you'll do "something > else", since you have no guarantee that ANY instance of other > work is itself bounded, you can't make any guarantees about > whether the scheme as a whole is bounded. > > And if it's really just, "for this specific critical section, if > you fail to immediately acquire the lock, go try this other, > very specific thing known to be safe in this specific context, > and then try again...." then as I've said, this is well-known, > but is also wholly unoriginal and thus uninteresting. So be it. That's fine. I just thought it might be, sometimes, beneficial in "certain", rather rare, scenarios. Well, shit happens.
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2025-08-05 19:16 -0700 |
| Message-ID | <106udu9$3400b$2@dont-email.me> |
| In reply to | #122468 |
On 8/5/2025 5:38 PM, Dan Cross wrote: > In article <106u31a$31k65$2@dont-email.me>, > Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote: >> On 8/5/2025 12:27 AM, Muttley@DastardlyHQ.org wrote: >>> On Mon, 4 Aug 2025 12:34:08 -0700 >>> "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> wibbled: >>>> [snip] >>>> This already works with multiple threads, no problem. But, if a thread >>>> fails to acquire the mutex, it can check to see if it has any other work >>>> to do instead of just waiting in the kernel doing nothing, or spinning >>>> doing nothing... Make sense to you? > > The idea behind what you're trying to do is well-understood. > > In fact, this is what generally happens when you try to acquire > a contended, blocking mutex: if the mutex is currently locked by > some other thread, you mark the acquiring thread as blocked > waiting on the mutex, and then yield control back to a scheduler > or something; eventually the other thread will finish what it > was doing and release the mutex, but part of releasing the mutex > and making it available again is marking threads that were > blocked on it runnable, thus opening them up to be scheduled > again, where they can once again try to acquire the mutex. > > The twist here seems to be that, instead of immediately > yielding, for some bounded number of times, you look at a work > queue and try to find something else for the acquiring thread to > do while the lock you want is unavailable. Regardless, the > effect is more or less the same. > > Personally, I see little benefit, and a number of potential > pitfalls. In particular, I see no reason why the bundled bits > of work in this scheme can't cause any number of lock ordering > violations and lead to all sorts of deadlock scenarios. Suppose > for example, that I acquire some mutex, A, and then go to > acquire a second mutex, B: B is currently held by some other > thread, so I begin to spin, but I see that there is an item in > my work queue, so I go to do that. The first thing that work > item does is try to acquire mutex A, which I'm currently > holding, leading to deadlock against A. > > One could perhaps assert that these work items are not allowed > to take or hold locks, which could address this particular > failure mode, but it's unclear how one might enforce this in > general, and there may well be other, similar failure modes. > >>>> [snip] >>>> The idea is instead of letting it wait, why not let it try to do some >>>> other work? Think of an adaptive mutex. On contention it will spin for a >>>> bounded number of times in user space before having to wait in the >>>> kernel. Well, instead of spinning, try to do something else, some real >>>> work? It will keep the thread hot, doing work instead of just waiting... >>> >>> Because while its doing something else the lock maybe become free then >>> become acquired again leading to a kind of race condition of some threads >> >> Nope. A thread can only do something else for a bounded number of times. >> So, its starvation free. No race condition. > > This is simply not true. Suppose that the "something else" is > computationally intensive, or blocks the thread somehow (say, by > executing a blocking system call). What if the "something else" > just spins in an infinte loop, waiting for some event? Just > because you bound the number of times you do "something else" > does not mean you are free of starvation, because what the other > thing actual does matters. > > - Dan C. > Using this pattern, well, can be a nightmare, but can be somewhat beneficial at the same time? If a programmer knew that a class of functions are compatible with the try_lock failed condition, well, why not give them a go? Better than spinning doing nothing, or god forbid, waiting in the kernel?
[toc] | [prev] | [next] | [standalone]
| From | cross@spitfire.i.gajendra.net (Dan Cross) |
|---|---|
| Date | 2025-08-06 12:04 +0000 |
| Message-ID | <106vgd1$5pk$1@reader1.panix.com> |
| In reply to | #122471 |
In article <106udu9$3400b$2@dont-email.me>, Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote: >On 8/5/2025 5:38 PM, Dan Cross wrote: >> In article <106u31a$31k65$2@dont-email.me>, >> Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote: >>> On 8/5/2025 12:27 AM, Muttley@DastardlyHQ.org wrote: >>>> On Mon, 4 Aug 2025 12:34:08 -0700 >>>> "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> wibbled: >>>>> [snip] >>>>> This already works with multiple threads, no problem. But, if a thread >>>>> fails to acquire the mutex, it can check to see if it has any other work >>>>> to do instead of just waiting in the kernel doing nothing, or spinning >>>>> doing nothing... Make sense to you? >> >> The idea behind what you're trying to do is well-understood. >> >> In fact, this is what generally happens when you try to acquire >> a contended, blocking mutex: if the mutex is currently locked by >> some other thread, you mark the acquiring thread as blocked >> waiting on the mutex, and then yield control back to a scheduler >> or something; eventually the other thread will finish what it >> was doing and release the mutex, but part of releasing the mutex >> and making it available again is marking threads that were >> blocked on it runnable, thus opening them up to be scheduled >> again, where they can once again try to acquire the mutex. >> >> The twist here seems to be that, instead of immediately >> yielding, for some bounded number of times, you look at a work >> queue and try to find something else for the acquiring thread to >> do while the lock you want is unavailable. Regardless, the >> effect is more or less the same. >> >> Personally, I see little benefit, and a number of potential >> pitfalls. In particular, I see no reason why the bundled bits >> of work in this scheme can't cause any number of lock ordering >> violations and lead to all sorts of deadlock scenarios. Suppose >> for example, that I acquire some mutex, A, and then go to >> acquire a second mutex, B: B is currently held by some other >> thread, so I begin to spin, but I see that there is an item in >> my work queue, so I go to do that. The first thing that work >> item does is try to acquire mutex A, which I'm currently >> holding, leading to deadlock against A. >> >> One could perhaps assert that these work items are not allowed >> to take or hold locks, which could address this particular >> failure mode, but it's unclear how one might enforce this in >> general, and there may well be other, similar failure modes. >> >>>>> [snip] >>>>> The idea is instead of letting it wait, why not let it try to do some >>>>> other work? Think of an adaptive mutex. On contention it will spin for a >>>>> bounded number of times in user space before having to wait in the >>>>> kernel. Well, instead of spinning, try to do something else, some real >>>>> work? It will keep the thread hot, doing work instead of just waiting... >>>> >>>> Because while its doing something else the lock maybe become free then >>>> become acquired again leading to a kind of race condition of some threads >>> >>> Nope. A thread can only do something else for a bounded number of times. >>> So, its starvation free. No race condition. >> >> This is simply not true. Suppose that the "something else" is >> computationally intensive, or blocks the thread somehow (say, by >> executing a blocking system call). What if the "something else" >> just spins in an infinte loop, waiting for some event? Just >> because you bound the number of times you do "something else" >> does not mean you are free of starvation, because what the other >> thing actual does matters. > >Using this pattern, well, can be a nightmare, but can be somewhat >beneficial at the same time? Yeah, so beneficial that it's been codified many times over: acquiring a contended blocking mutex yields, so that something else can run instead. >If a programmer knew that a class of >functions are compatible with the try_lock failed condition, well, why >not give them a go? Better than spinning doing nothing, or god forbid, >waiting in the kernel? The whole premise of a spinlock is that the critical section that it protects is short (like, a few instructions), so the overhead of spinning is smaller than the overhead of context switching to something else. If that is not true, you shouldn't be using a spinlock as your mutex primitive in the first place, and a blocking or adaptive mutex is more appropriate. By the way, there's nothing at all wrong with blocking in the kernel; given a reasonable OS, it's not like if *YOUR THREAD* isn't running the CPU will be idle or something. But if you still want to avoid blocking when a mutex is unavailable, then you've got the idea inverted. Focusing on the locking protocol as some kind of generic place to do "other work" is too general to be useful, as has been shown. To be truly useful, this sort of approach must be coupled with knowledge of what a thread can safely do in context, which means that you really need to specialize the behavior for the _critical section_, not the _mutex_: the programmer knows why the thread is trying to acquire a mutex in that case, and what other work may or may not be acceptable to do if the mutex isn't immediately available. So they can craft the critical section to take advantage of that knowledge themselves. This sort of technique is well-known, by the way. But then it's not going to be particularly general. And you may argue that the critical section might be buried deep down in a call stack, very far away from the place where the programmer can reasonably make a decision about whether it's safe to do something or not, so that's a more appropriate place: but that reinforces the objections: if the critical section is so far away from the point where the programmer knows whether it's safe for the thread to do something else, then the programmer doesn't really know whether that thing is safe, because the intervening calls might have changed conditions so that it's not, so trying to plumb that knowledge down to the mutex code is again too dangerous to be useful. But even if the programmer could safely interpose doing "something else" in this way, they may not have full knowledge to know whether or not that will cause the thread to block. Consider, for example, a program that tries to do something innocuous, like zero a a few byte's worth of memory while trying to take a lock; what if the page holding the memory to be zero'ed has been stolen by the OS in the meantime, and now the program (totally unbeknownst to it) incurs a page fault that requires reading data from secondary storage to resolve? Not only has a single store now blocked your thread in the big scary kernel, but it's blocked it for many, many cycles. So while this technique is known and used in existing systems, it must be done so carefully that it really isn't appropriate as a general mechanism. - Dan C.
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2025-08-06 15:47 -0700 |
| Message-ID | <1070m2s$3lg2n$4@dont-email.me> |
| In reply to | #122474 |
On 8/6/2025 5:04 AM, Dan Cross wrote: > In article <106udu9$3400b$2@dont-email.me>, > Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote: >> On 8/5/2025 5:38 PM, Dan Cross wrote: >>> In article <106u31a$31k65$2@dont-email.me>, >>> Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote: >>>> On 8/5/2025 12:27 AM, Muttley@DastardlyHQ.org wrote: >>>>> On Mon, 4 Aug 2025 12:34:08 -0700 >>>>> "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> wibbled: >>>>>> [snip] >>>>>> This already works with multiple threads, no problem. But, if a thread >>>>>> fails to acquire the mutex, it can check to see if it has any other work >>>>>> to do instead of just waiting in the kernel doing nothing, or spinning >>>>>> doing nothing... Make sense to you? >>> >>> The idea behind what you're trying to do is well-understood. >>> >>> In fact, this is what generally happens when you try to acquire >>> a contended, blocking mutex: if the mutex is currently locked by >>> some other thread, you mark the acquiring thread as blocked >>> waiting on the mutex, and then yield control back to a scheduler >>> or something; eventually the other thread will finish what it >>> was doing and release the mutex, but part of releasing the mutex >>> and making it available again is marking threads that were >>> blocked on it runnable, thus opening them up to be scheduled >>> again, where they can once again try to acquire the mutex. >>> >>> The twist here seems to be that, instead of immediately >>> yielding, for some bounded number of times, you look at a work >>> queue and try to find something else for the acquiring thread to >>> do while the lock you want is unavailable. Regardless, the >>> effect is more or less the same. >>> >>> Personally, I see little benefit, and a number of potential >>> pitfalls. In particular, I see no reason why the bundled bits >>> of work in this scheme can't cause any number of lock ordering >>> violations and lead to all sorts of deadlock scenarios. Suppose >>> for example, that I acquire some mutex, A, and then go to >>> acquire a second mutex, B: B is currently held by some other >>> thread, so I begin to spin, but I see that there is an item in >>> my work queue, so I go to do that. The first thing that work >>> item does is try to acquire mutex A, which I'm currently >>> holding, leading to deadlock against A. >>> >>> One could perhaps assert that these work items are not allowed >>> to take or hold locks, which could address this particular >>> failure mode, but it's unclear how one might enforce this in >>> general, and there may well be other, similar failure modes. >>> >>>>>> [snip] >>>>>> The idea is instead of letting it wait, why not let it try to do some >>>>>> other work? Think of an adaptive mutex. On contention it will spin for a >>>>>> bounded number of times in user space before having to wait in the >>>>>> kernel. Well, instead of spinning, try to do something else, some real >>>>>> work? It will keep the thread hot, doing work instead of just waiting... >>>>> >>>>> Because while its doing something else the lock maybe become free then >>>>> become acquired again leading to a kind of race condition of some threads >>>> >>>> Nope. A thread can only do something else for a bounded number of times. >>>> So, its starvation free. No race condition. >>> >>> This is simply not true. Suppose that the "something else" is >>> computationally intensive, or blocks the thread somehow (say, by >>> executing a blocking system call). What if the "something else" >>> just spins in an infinte loop, waiting for some event? Just >>> because you bound the number of times you do "something else" >>> does not mean you are free of starvation, because what the other >>> thing actual does matters. >> >> Using this pattern, well, can be a nightmare, but can be somewhat >> beneficial at the same time? > > Yeah, so beneficial that it's been codified many times over: > acquiring a contended blocking mutex yields, so that something > else can run instead. > >> If a programmer knew that a class of >> functions are compatible with the try_lock failed condition, well, why >> not give them a go? Better than spinning doing nothing, or god forbid, >> waiting in the kernel? > > The whole premise of a spinlock is that the critical section > that it protects is short (like, a few instructions), so the > overhead of spinning is smaller than the overhead of context > switching to something else. If that is not true, you shouldn't > be using a spinlock as your mutex primitive in the first place, > and a blocking or adaptive mutex is more appropriate. By the > way, there's nothing at all wrong with blocking in the kernel; > given a reasonable OS, it's not like if *YOUR THREAD* isn't > running the CPU will be idle or something. My try other work thing still works with short and/or long critical sections. Try other work replaces the spin aspect of an adaptive mutex with trying to do other "compatible" work. If no other work can be found to do, it falls back to a lock() anyway. If it does "too much" work, say 5 or 10 work items, it locks. try_lock is just there to keep the pump running, so to speak... > But if you still want to avoid blocking when a mutex is > unavailable, then you've got the idea inverted. Focusing on the > locking protocol as some kind of generic place to do "other > work" is too general to be useful, as has been shown. To be > truly useful, this sort of approach must be coupled with > knowledge of what a thread can safely do in context, which means > that you really need to specialize the behavior for the > _critical section_, not the _mutex_: the programmer knows why > the thread is trying to acquire a mutex in that case, and what > other work may or may not be acceptable to do if the mutex isn't > immediately available. So they can craft the critical section > to take advantage of that knowledge themselves. This sort of > technique is well-known, by the way. > > But then it's not going to be particularly general. And you may > argue that the critical section might be buried deep down in a > call stack, very far away from the place where the programmer > can reasonably make a decision about whether it's safe to do > something or not, so that's a more appropriate place: but that > reinforces the objections: if the critical section is so far > away from the point where the programmer knows whether it's safe > for the thread to do something else, then the programmer doesn't > really know whether that thing is safe, because the intervening > calls might have changed conditions so that it's not, so trying > to plumb that knowledge down to the mutex code is again too > dangerous to be useful. > > But even if the programmer could safely interpose doing > "something else" in this way, they may not have full knowledge > to know whether or not that will cause the thread to block. > Consider, for example, a program that tries to do something > innocuous, like zero a a few byte's worth of memory while > trying to take a lock; what if the page holding the memory to be > zero'ed has been stolen by the OS in the meantime, and now the > program (totally unbeknownst to it) incurs a page fault that > requires reading data from secondary storage to resolve? Not > only has a single store now blocked your thread in the big scary > kernel, but it's blocked it for many, many cycles. > > So while this technique is known and used in existing systems, > it must be done so carefully that it really isn't appropriate as > a general mechanism. carefully is the key concept! Yikes... Shit... However, basically, it still boils down to trying other "work" on a spin can keep the thread "hot" doing other work, instead of spinning on an adaptive logic of a mutex, nothing nothing?
[toc] | [prev] | [next] | [standalone]
| From | cross@spitfire.i.gajendra.net (Dan Cross) |
|---|---|
| Date | 2025-08-08 01:49 +0000 |
| Message-ID | <1073l39$mpg$2@reader1.panix.com> |
| In reply to | #122480 |
In article <1070m2s$3lg2n$4@dont-email.me>, Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote: >On 8/6/2025 5:04 AM, Dan Cross wrote: >> In article <106udu9$3400b$2@dont-email.me>, >> Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote: >>> On 8/5/2025 5:38 PM, Dan Cross wrote: >>>> In article <106u31a$31k65$2@dont-email.me>, >>>> Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote: >>>>> On 8/5/2025 12:27 AM, Muttley@DastardlyHQ.org wrote: >>>>>> On Mon, 4 Aug 2025 12:34:08 -0700 >>>>>> "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> wibbled: >>>>>>> [snip] >>>>>>> This already works with multiple threads, no problem. But, if a thread >>>>>>> fails to acquire the mutex, it can check to see if it has any other work >>>>>>> to do instead of just waiting in the kernel doing nothing, or spinning >>>>>>> doing nothing... Make sense to you? >>>> >>>> The idea behind what you're trying to do is well-understood. >>>> >>>> In fact, this is what generally happens when you try to acquire >>>> a contended, blocking mutex: if the mutex is currently locked by >>>> some other thread, you mark the acquiring thread as blocked >>>> waiting on the mutex, and then yield control back to a scheduler >>>> or something; eventually the other thread will finish what it >>>> was doing and release the mutex, but part of releasing the mutex >>>> and making it available again is marking threads that were >>>> blocked on it runnable, thus opening them up to be scheduled >>>> again, where they can once again try to acquire the mutex. >>>> >>>> The twist here seems to be that, instead of immediately >>>> yielding, for some bounded number of times, you look at a work >>>> queue and try to find something else for the acquiring thread to >>>> do while the lock you want is unavailable. Regardless, the >>>> effect is more or less the same. >>>> >>>> Personally, I see little benefit, and a number of potential >>>> pitfalls. In particular, I see no reason why the bundled bits >>>> of work in this scheme can't cause any number of lock ordering >>>> violations and lead to all sorts of deadlock scenarios. Suppose >>>> for example, that I acquire some mutex, A, and then go to >>>> acquire a second mutex, B: B is currently held by some other >>>> thread, so I begin to spin, but I see that there is an item in >>>> my work queue, so I go to do that. The first thing that work >>>> item does is try to acquire mutex A, which I'm currently >>>> holding, leading to deadlock against A. >>>> >>>> One could perhaps assert that these work items are not allowed >>>> to take or hold locks, which could address this particular >>>> failure mode, but it's unclear how one might enforce this in >>>> general, and there may well be other, similar failure modes. >>>> >>>>>>> [snip] >>>>>>> The idea is instead of letting it wait, why not let it try to do some >>>>>>> other work? Think of an adaptive mutex. On contention it will spin for a >>>>>>> bounded number of times in user space before having to wait in the >>>>>>> kernel. Well, instead of spinning, try to do something else, some real >>>>>>> work? It will keep the thread hot, doing work instead of just waiting... >>>>>> >>>>>> Because while its doing something else the lock maybe become free then >>>>>> become acquired again leading to a kind of race condition of some threads >>>>> >>>>> Nope. A thread can only do something else for a bounded number of times. >>>>> So, its starvation free. No race condition. >>>> >>>> This is simply not true. Suppose that the "something else" is >>>> computationally intensive, or blocks the thread somehow (say, by >>>> executing a blocking system call). What if the "something else" >>>> just spins in an infinte loop, waiting for some event? Just >>>> because you bound the number of times you do "something else" >>>> does not mean you are free of starvation, because what the other >>>> thing actual does matters. >>> >>> Using this pattern, well, can be a nightmare, but can be somewhat >>> beneficial at the same time? >> >> Yeah, so beneficial that it's been codified many times over: >> acquiring a contended blocking mutex yields, so that something >> else can run instead. >> >>> If a programmer knew that a class of >>> functions are compatible with the try_lock failed condition, well, why >>> not give them a go? Better than spinning doing nothing, or god forbid, >>> waiting in the kernel? >> >> The whole premise of a spinlock is that the critical section >> that it protects is short (like, a few instructions), so the >> overhead of spinning is smaller than the overhead of context >> switching to something else. If that is not true, you shouldn't >> be using a spinlock as your mutex primitive in the first place, >> and a blocking or adaptive mutex is more appropriate. By the >> way, there's nothing at all wrong with blocking in the kernel; >> given a reasonable OS, it's not like if *YOUR THREAD* isn't >> running the CPU will be idle or something. > >My try other work thing still works with short and/or long critical >sections. Try other work replaces the spin aspect of an adaptive mutex >with trying to do other "compatible" work. If no other work can be found >to do, it falls back to a lock() anyway. If it does "too much" work, say >5 or 10 work items, it locks. try_lock is just there to keep the pump >running, so to speak... Again, just bounding the number of times you do "other work" is insufficient to guarantee forward progress. See the example of trying to recursively acquire a held mutex, leading to deadlock. The issue here is not that you only do things 5, 10, or 1000 times, but that there is no meaningful way you could assess "compatibility" (not without solving the halting problem anyway) and so any given bit of "other work" could basically deadlock the whole thing. If your "other work" can take arbitrarily long, how is this mechanism any better than just letting the thread that wants to acquire the mutex block and letting another thread chew through your work queue? >> But if you still want to avoid blocking when a mutex is >> unavailable, then you've got the idea inverted. Focusing on the >> locking protocol as some kind of generic place to do "other >> work" is too general to be useful, as has been shown. To be >> truly useful, this sort of approach must be coupled with >> knowledge of what a thread can safely do in context, which means >> that you really need to specialize the behavior for the >> _critical section_, not the _mutex_: the programmer knows why >> the thread is trying to acquire a mutex in that case, and what >> other work may or may not be acceptable to do if the mutex isn't >> immediately available. So they can craft the critical section >> to take advantage of that knowledge themselves. This sort of >> technique is well-known, by the way. >> >> But then it's not going to be particularly general. And you may >> argue that the critical section might be buried deep down in a >> call stack, very far away from the place where the programmer >> can reasonably make a decision about whether it's safe to do >> something or not, so that's a more appropriate place: but that >> reinforces the objections: if the critical section is so far >> away from the point where the programmer knows whether it's safe >> for the thread to do something else, then the programmer doesn't >> really know whether that thing is safe, because the intervening >> calls might have changed conditions so that it's not, so trying >> to plumb that knowledge down to the mutex code is again too >> dangerous to be useful. >> >> But even if the programmer could safely interpose doing >> "something else" in this way, they may not have full knowledge >> to know whether or not that will cause the thread to block. >> Consider, for example, a program that tries to do something >> innocuous, like zero a a few byte's worth of memory while >> trying to take a lock; what if the page holding the memory to be >> zero'ed has been stolen by the OS in the meantime, and now the >> program (totally unbeknownst to it) incurs a page fault that >> requires reading data from secondary storage to resolve? Not >> only has a single store now blocked your thread in the big scary >> kernel, but it's blocked it for many, many cycles. >> >> So while this technique is known and used in existing systems, >> it must be done so carefully that it really isn't appropriate as >> a general mechanism. > >carefully is the key concept! Yikes... Shit... However, basically, it >still boils down to trying other "work" on a spin can keep the thread >"hot" doing other work, instead of spinning on an adaptive logic of a >mutex, nothing nothing? Keeping a thread "hot" without being able to make any sort of meaningful guarantee about the viability of the scheme as a general mechanism is not useful, when considering the scheme as a general mechanism. - Dan C.
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2025-08-07 20:59 -0700 |
| Message-ID | <1073snp$en4a$3@dont-email.me> |
| In reply to | #122493 |
On 8/7/2025 6:49 PM, Dan Cross wrote: > In article <1070m2s$3lg2n$4@dont-email.me>, > Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote: >> On 8/6/2025 5:04 AM, Dan Cross wrote: >>> In article <106udu9$3400b$2@dont-email.me>, >>> Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote: >>>> On 8/5/2025 5:38 PM, Dan Cross wrote: >>>>> In article <106u31a$31k65$2@dont-email.me>, >>>>> Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote: >>>>>> On 8/5/2025 12:27 AM, Muttley@DastardlyHQ.org wrote: >>>>>>> On Mon, 4 Aug 2025 12:34:08 -0700 >>>>>>> "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> wibbled: >>>>>>>> [snip] >>>>>>>> This already works with multiple threads, no problem. But, if a thread >>>>>>>> fails to acquire the mutex, it can check to see if it has any other work >>>>>>>> to do instead of just waiting in the kernel doing nothing, or spinning >>>>>>>> doing nothing... Make sense to you? >>>>> >>>>> The idea behind what you're trying to do is well-understood. >>>>> >>>>> In fact, this is what generally happens when you try to acquire >>>>> a contended, blocking mutex: if the mutex is currently locked by >>>>> some other thread, you mark the acquiring thread as blocked >>>>> waiting on the mutex, and then yield control back to a scheduler >>>>> or something; eventually the other thread will finish what it >>>>> was doing and release the mutex, but part of releasing the mutex >>>>> and making it available again is marking threads that were >>>>> blocked on it runnable, thus opening them up to be scheduled >>>>> again, where they can once again try to acquire the mutex. >>>>> >>>>> The twist here seems to be that, instead of immediately >>>>> yielding, for some bounded number of times, you look at a work >>>>> queue and try to find something else for the acquiring thread to >>>>> do while the lock you want is unavailable. Regardless, the >>>>> effect is more or less the same. >>>>> >>>>> Personally, I see little benefit, and a number of potential >>>>> pitfalls. In particular, I see no reason why the bundled bits >>>>> of work in this scheme can't cause any number of lock ordering >>>>> violations and lead to all sorts of deadlock scenarios. Suppose >>>>> for example, that I acquire some mutex, A, and then go to >>>>> acquire a second mutex, B: B is currently held by some other >>>>> thread, so I begin to spin, but I see that there is an item in >>>>> my work queue, so I go to do that. The first thing that work >>>>> item does is try to acquire mutex A, which I'm currently >>>>> holding, leading to deadlock against A. >>>>> >>>>> One could perhaps assert that these work items are not allowed >>>>> to take or hold locks, which could address this particular >>>>> failure mode, but it's unclear how one might enforce this in >>>>> general, and there may well be other, similar failure modes. >>>>> >>>>>>>> [snip] >>>>>>>> The idea is instead of letting it wait, why not let it try to do some >>>>>>>> other work? Think of an adaptive mutex. On contention it will spin for a >>>>>>>> bounded number of times in user space before having to wait in the >>>>>>>> kernel. Well, instead of spinning, try to do something else, some real >>>>>>>> work? It will keep the thread hot, doing work instead of just waiting... >>>>>>> >>>>>>> Because while its doing something else the lock maybe become free then >>>>>>> become acquired again leading to a kind of race condition of some threads >>>>>> >>>>>> Nope. A thread can only do something else for a bounded number of times. >>>>>> So, its starvation free. No race condition. >>>>> >>>>> This is simply not true. Suppose that the "something else" is >>>>> computationally intensive, or blocks the thread somehow (say, by >>>>> executing a blocking system call). What if the "something else" >>>>> just spins in an infinte loop, waiting for some event? Just >>>>> because you bound the number of times you do "something else" >>>>> does not mean you are free of starvation, because what the other >>>>> thing actual does matters. >>>> >>>> Using this pattern, well, can be a nightmare, but can be somewhat >>>> beneficial at the same time? >>> >>> Yeah, so beneficial that it's been codified many times over: >>> acquiring a contended blocking mutex yields, so that something >>> else can run instead. >>> >>>> If a programmer knew that a class of >>>> functions are compatible with the try_lock failed condition, well, why >>>> not give them a go? Better than spinning doing nothing, or god forbid, >>>> waiting in the kernel? >>> >>> The whole premise of a spinlock is that the critical section >>> that it protects is short (like, a few instructions), so the >>> overhead of spinning is smaller than the overhead of context >>> switching to something else. If that is not true, you shouldn't >>> be using a spinlock as your mutex primitive in the first place, >>> and a blocking or adaptive mutex is more appropriate. By the >>> way, there's nothing at all wrong with blocking in the kernel; >>> given a reasonable OS, it's not like if *YOUR THREAD* isn't >>> running the CPU will be idle or something. >> >> My try other work thing still works with short and/or long critical >> sections. Try other work replaces the spin aspect of an adaptive mutex >> with trying to do other "compatible" work. If no other work can be found >> to do, it falls back to a lock() anyway. If it does "too much" work, say >> 5 or 10 work items, it locks. try_lock is just there to keep the pump >> running, so to speak... > > Again, just bounding the number of times you do "other work" is > insufficient to guarantee forward progress. See the example of > trying to recursively acquire a held mutex, leading to deadlock. > The issue here is not that you only do things 5, 10, or 1000 > times, but that there is no meaningful way you could assess > "compatibility" (not without solving the halting problem anyway) > and so any given bit of "other work" could basically deadlock > the whole thing. > > If your "other work" can take arbitrarily long, how is this > mechanism any better than just letting the thread that wants to > acquire the mutex block and letting another thread chew through > your work queue? > >>> But if you still want to avoid blocking when a mutex is >>> unavailable, then you've got the idea inverted. Focusing on the >>> locking protocol as some kind of generic place to do "other >>> work" is too general to be useful, as has been shown. To be >>> truly useful, this sort of approach must be coupled with >>> knowledge of what a thread can safely do in context, which means >>> that you really need to specialize the behavior for the >>> _critical section_, not the _mutex_: the programmer knows why >>> the thread is trying to acquire a mutex in that case, and what >>> other work may or may not be acceptable to do if the mutex isn't >>> immediately available. So they can craft the critical section >>> to take advantage of that knowledge themselves. This sort of >>> technique is well-known, by the way. >>> >>> But then it's not going to be particularly general. And you may >>> argue that the critical section might be buried deep down in a >>> call stack, very far away from the place where the programmer >>> can reasonably make a decision about whether it's safe to do >>> something or not, so that's a more appropriate place: but that >>> reinforces the objections: if the critical section is so far >>> away from the point where the programmer knows whether it's safe >>> for the thread to do something else, then the programmer doesn't >>> really know whether that thing is safe, because the intervening >>> calls might have changed conditions so that it's not, so trying >>> to plumb that knowledge down to the mutex code is again too >>> dangerous to be useful. >>> >>> But even if the programmer could safely interpose doing >>> "something else" in this way, they may not have full knowledge >>> to know whether or not that will cause the thread to block. >>> Consider, for example, a program that tries to do something >>> innocuous, like zero a a few byte's worth of memory while >>> trying to take a lock; what if the page holding the memory to be >>> zero'ed has been stolen by the OS in the meantime, and now the >>> program (totally unbeknownst to it) incurs a page fault that >>> requires reading data from secondary storage to resolve? Not >>> only has a single store now blocked your thread in the big scary >>> kernel, but it's blocked it for many, many cycles. >>> >>> So while this technique is known and used in existing systems, >>> it must be done so carefully that it really isn't appropriate as >>> a general mechanism. >> >> carefully is the key concept! Yikes... Shit... However, basically, it >> still boils down to trying other "work" on a spin can keep the thread >> "hot" doing other work, instead of spinning on an adaptive logic of a >> mutex, nothing nothing? > > Keeping a thread "hot" without being able to make any sort of > meaningful guarantee about the viability of the scheme as a > general mechanism is not useful, when considering the scheme as > a general mechanism. general mechanism? No. Oh no. I am no trying to do that at all. How about a sometimes it might be okay type of scenario? Argh! My mind keeps on thinking of other work that will not spin off into never never land, the nightmare thing I mentioned. It will not deadlock, actually, not sure how it could deadlock in this highly special realm, anyway... That call to a try IOCP means that is has the "chance" to gain data, checking a thread local queues has a chance to have other work while the mutex is in contention anyway via try_lock fail? Oh my.... I am grasping at straws here.. But, it still might be okay for certain scenarios? Actually, way back, 20-25 years ago when I was messing around with proxy collectors... I had a base case that used mutexes only. No fancy atomics, ect... Pre C++11, ect... It worked. If a per thread mutex try_lock failed it meant a reaper thread got a hold of it, and it should lock its next generation of mutexes. all per thread. This would allow for a RCU type of setup using mutexes only. Pretty fun.
[toc] | [prev] | [next] | [standalone]
| From | cross@spitfire.i.gajendra.net (Dan Cross) |
|---|---|
| Date | 2025-08-09 09:17 +0000 |
| Message-ID | <10773n5$7vd$1@reader1.panix.com> |
| In reply to | #122496 |
In article <1073snp$en4a$3@dont-email.me>, Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote: >On 8/7/2025 6:49 PM, Dan Cross wrote: >> In article <1070m2s$3lg2n$4@dont-email.me>, >> Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote: >>> [snip] >>> carefully is the key concept! Yikes... Shit... However, basically, it >>> still boils down to trying other "work" on a spin can keep the thread >>> "hot" doing other work, instead of spinning on an adaptive logic of a >>> mutex, nothing nothing? >> >> Keeping a thread "hot" without being able to make any sort of >> meaningful guarantee about the viability of the scheme as a >> general mechanism is not useful, when considering the scheme as >> a general mechanism. > >general mechanism? No. Oh no. I am no trying to do that at all. How >about a sometimes it might be okay type of scenario? Argh! My mind keeps >on thinking of other work that will not spin off into never never land, >the nightmare thing I mentioned. It will not deadlock, actually, not >sure how it could deadlock in this highly special realm, anyway... That >call to a try IOCP means that is has the "chance" to gain data, checking >a thread local queues has a chance to have other work while the mutex is >in contention anyway via try_lock fail? Oh my.... I am grasping at >straws here.. But, it still might be okay for certain scenarios? Yes, you are grasping at straws. People have written code that tries to take a lock, and if that fails, does something else, for decades. The idea is neither new, nor terribly interesting. Sorry. >Actually, way back, 20-25 years ago when I was messing around with proxy >collectors... I had a base case that used mutexes only. No fancy >atomics, ect... Pre C++11, ect... It worked. If a per thread mutex >try_lock failed it meant a reaper thread got a hold of it, and it should >lock its next generation of mutexes. all per thread. This would allow >for a RCU type of setup using mutexes only. Pretty fun. That vague, incomplete description sounds nothing like how RCU works. - Dan C.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2025-08-09 11:52 +0200 |
| Message-ID | <10775om$17ms4$1@raubtier-asyl.eternal-september.org> |
| In reply to | #122500 |
Am 09.08.2025 um 11:17 schrieb Dan Cross: > People have written code that tries to take a lock, and if that > fails, does something else, for decades. The idea is neither > new, nor terribly interesting. Sorry. I think this pattern is extremely rare because the task that needs to be done elsewhere must be able to be omitted completely if necessary, and if not, it must be short enough that it doesn't interfere with waiting for the mutex.
[toc] | [prev] | [next] | [standalone]
Page 1 of 5 [1] 2 3 4 5 Next page →
Back to top | Article view | comp.lang.c++
csiph-web