Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
On the nature of non-blocking techniques...
52 views
Skip to first unread message
Chris M. Thomasson
Mar 22, 2017, 4:35:42 PM3/22/17
to
First of all, these are very specialized, exotic type of sync algorithms
indeed! Keep that in the front of your mind wrt ever thinking about
using them directly: Think about danger when using them. Trust me, it
will keep you safer. However, by all means, if interested, learn all
about C++'s ability to provide the ability to implement these things
_before_ you use them for anything other than a "toy example test program".
I am sorry Bonita if my writings in some of my most recent threads came
across as if I am some sort of lock-free religious nut: I am not. If the
mutex version is working fine, by all means: keep using it!
Do not use these exotic algorithms unless you know what you are doing,
or perhaps just experimenting, for learning and fun. They can sometimes
come in handy when you need to scale up, think commercial database type
of loads...
Sorry for not making this clearer to Bonita. It seems as if I really
annoyed her! Sorry for the fact that I did not point these dangers out
for it seemed to make her teeth want to itch. I remember hearing that
phrase on this group when I posted some code with hardcore macros years
ago. ;^o
Now, on a side note: There are many ways to integrate locking and
non-blocking techniques that can be beneficial:
An Effective Marriage between Lock-Free and Lock-Based Algorithms
Can be a Good Thing!
One example is adding the ability of conditional blocking for basically
any lock-free algorithm, the eventcount, or sometimes even a fast-pathed
semaphore can accomplish this goal...
Fwiw, perhaps I should switch from posting the rest of my queue/stack
algorithms here, and go ahead and focus on how we can code a RCU like
mechanism in pure std C++. Instead of producer/consumer problem, I
should focus on the reader/writer problem. Thank you for challenging me
to begin with Bonita. :^)
FWIW, the RCU like std C++ algorithm I have in mind, coded as a Relacy
unit test:
http://www.1024cores.net/home/relacy-race-detector
(here is Relacy)
can be found here:
http://pastebin.com/raw/f71480694
https://groups.google.com/d/topic/lock-free/X3fuuXknQF0/discussion
(here is the discussion where I present the algorithm, please take the
time to read all)
Fwiw, here is a proxy collector I created with custom asm, older code:
http://webpages.charter.net/appcore/misc/pc_sample_h_v1.html
Again, sorry Bonita for not pointing out all of the caveats!
;^o
Can you forgive me?
indeed! Keep that in the front of your mind wrt ever thinking about
using them directly: Think about danger when using them. Trust me, it
will keep you safer. However, by all means, if interested, learn all
about C++'s ability to provide the ability to implement these things
_before_ you use them for anything other than a "toy example test program".
I am sorry Bonita if my writings in some of my most recent threads came
across as if I am some sort of lock-free religious nut: I am not. If the
mutex version is working fine, by all means: keep using it!
Do not use these exotic algorithms unless you know what you are doing,
or perhaps just experimenting, for learning and fun. They can sometimes
come in handy when you need to scale up, think commercial database type
of loads...
Sorry for not making this clearer to Bonita. It seems as if I really
annoyed her! Sorry for the fact that I did not point these dangers out
for it seemed to make her teeth want to itch. I remember hearing that
phrase on this group when I posted some code with hardcore macros years
ago. ;^o
Now, on a side note: There are many ways to integrate locking and
non-blocking techniques that can be beneficial:
An Effective Marriage between Lock-Free and Lock-Based Algorithms
Can be a Good Thing!
One example is adding the ability of conditional blocking for basically
any lock-free algorithm, the eventcount, or sometimes even a fast-pathed
semaphore can accomplish this goal...
Fwiw, perhaps I should switch from posting the rest of my queue/stack
algorithms here, and go ahead and focus on how we can code a RCU like
mechanism in pure std C++. Instead of producer/consumer problem, I
should focus on the reader/writer problem. Thank you for challenging me
to begin with Bonita. :^)
FWIW, the RCU like std C++ algorithm I have in mind, coded as a Relacy
unit test:
http://www.1024cores.net/home/relacy-race-detector
(here is Relacy)
can be found here:
http://pastebin.com/raw/f71480694
https://groups.google.com/d/topic/lock-free/X3fuuXknQF0/discussion
(here is the discussion where I present the algorithm, please take the
time to read all)
Fwiw, here is a proxy collector I created with custom asm, older code:
http://webpages.charter.net/appcore/misc/pc_sample_h_v1.html
Again, sorry Bonita for not pointing out all of the caveats!
;^o
Can you forgive me?
Chris M. Thomasson
Mar 22, 2017, 4:53:09 PM3/22/17
to
On 3/22/2017 1:35 PM, Chris M. Thomasson wrote:
> First of all, these are very specialized, exotic type of sync algorithms
> indeed! Keep that in the front of your mind wrt ever thinking about
> using them directly: Think about danger when using them. Trust me, it
> will keep you safer. However, by all means, if interested, learn all
> about C++'s ability to provide the ability to implement these things
> _before_ you use them for anything other than a "toy example test program".
[...]
> First of all, these are very specialized, exotic type of sync algorithms
> indeed! Keep that in the front of your mind wrt ever thinking about
> using them directly: Think about danger when using them. Trust me, it
> will keep you safer. However, by all means, if interested, learn all
> about C++'s ability to provide the ability to implement these things
> _before_ you use them for anything other than a "toy example test program".
> An Effective Marriage between Lock-Free and Lock-Based Algorithms
>
> Can be a Good Thing!
>
>
> One example is adding the ability of conditional blocking for basically
> any lock-free algorithm, the eventcount, or sometimes even a fast-pathed
^^^^^^^^^^^^^^^^^^^^^^^^^
>
> Can be a Good Thing!
>
>
> One example is adding the ability of conditional blocking for basically
> any lock-free algorithm, the eventcount, or sometimes even a fast-pathed
algorithm, _via_ an eventcount
> semaphore can accomplish this goal...
PATENTS! I posted a couple of links in the following thread:
https://groups.google.com/d/topic/comp.lang.c++/yt27gw0cbyo/discussion
(read all for context...)
YIKES!
Chris M. Thomasson
Apr 1, 2017, 5:17:34 PM4/1/17
to
On 3/22/2017 1:35 PM, Chris M. Thomasson wrote:
> First of all, these are very specialized, exotic type of sync algorithms
> indeed! Keep that in the front of your mind wrt ever thinking about
> using them directly: Think about danger when using them. Trust me, it
> will keep you safer. However, by all means, if interested, learn all
> about C++'s ability to provide the ability to implement these things
> _before_ you use them for anything other than a "toy example test program".
[...]
> indeed! Keep that in the front of your mind wrt ever thinking about
> using them directly: Think about danger when using them. Trust me, it
> will keep you safer. However, by all means, if interested, learn all
> about C++'s ability to provide the ability to implement these things
> _before_ you use them for anything other than a "toy example test program".
How many people in this group are actually interested in this type of
ability provided by C++?
[...]
Ian Collins
Apr 1, 2017, 6:35:16 PM4/1/17
to
been post about lock-free for many years, you'll probably be able to
converse with people other than your self before too long!
As a point of reference, there are a small group of us on the large
project team I am currently working with who are investigation how we
can incorporate this stuff into the existing code.
--
Ian
Chris M. Thomasson
Apr 2, 2017, 9:29:33 PM4/2/17
to
On 4/1/2017 3:35 PM, Ian Collins wrote:
> On 04/ 2/17 09:17 AM, Chris M. Thomasson wrote:
>> On 3/22/2017 1:35 PM, Chris M. Thomasson wrote:
>>> First of all, these are very specialized, exotic type of sync algorithms
>>> indeed! Keep that in the front of your mind wrt ever thinking about
>>> using them directly: Think about danger when using them. Trust me, it
>>> will keep you safer. However, by all means, if interested, learn all
>>> about C++'s ability to provide the ability to implement these things
>>> _before_ you use them for anything other than a "toy example test
>>> program".
>> [...]
>>
>> How many people in this group are actually interested in this type of
>> ability provided by C++?
>
> More mow the idea are becoming mainstream. I appreciate that you have
> been post about lock-free for many years, you'll probably be able to
> converse with people other than your self before too long!
Very nice. I am looking forward to this time Ian. Thank you.
> On 04/ 2/17 09:17 AM, Chris M. Thomasson wrote:
>> On 3/22/2017 1:35 PM, Chris M. Thomasson wrote:
>>> First of all, these are very specialized, exotic type of sync algorithms
>>> indeed! Keep that in the front of your mind wrt ever thinking about
>>> using them directly: Think about danger when using them. Trust me, it
>>> will keep you safer. However, by all means, if interested, learn all
>>> about C++'s ability to provide the ability to implement these things
>>> _before_ you use them for anything other than a "toy example test
>>> program".
>> [...]
>>
>> How many people in this group are actually interested in this type of
>> ability provided by C++?
>
> More mow the idea are becoming mainstream. I appreciate that you have
> been post about lock-free for many years, you'll probably be able to
> converse with people other than your self before too long!
>
> As a point of reference, there are a small group of us on the large
> project team I am currently working with who are investigation how we
> can incorporate this stuff into the existing code.
wrt using some of this stuff because it can make a part of the engine
more powerful. This enhancement will cast its increased performance on
other parts of the system, in the form of more load. Might end up making
a set of locks contend more than they ever had before...
Ian Collins
Apr 3, 2017, 1:10:40 AM4/3/17
to
On 04/ 3/17 01:29 PM, Chris M. Thomasson wrote:
> On 4/1/2017 3:35 PM, Ian Collins wrote:
>> On 04/ 2/17 09:17 AM, Chris M. Thomasson wrote:
>>> On 3/22/2017 1:35 PM, Chris M. Thomasson wrote:
>>>> First of all, these are very specialized, exotic type of sync algorithms
>>>> indeed! Keep that in the front of your mind wrt ever thinking about
>>>> using them directly: Think about danger when using them. Trust me, it
>>>> will keep you safer. However, by all means, if interested, learn all
>>>> about C++'s ability to provide the ability to implement these things
>>>> _before_ you use them for anything other than a "toy example test
>>>> program".
>>> [...]
>>>
>>> How many people in this group are actually interested in this type of
>>> ability provided by C++?
>>
>> More mow the idea are becoming mainstream. I appreciate that you have
>> been post about lock-free for many years, you'll probably be able to
>> converse with people other than your self before too long!
>
> Very nice. I am looking forward to this time Ian. Thank you.
>
>>
>> As a point of reference, there are a small group of us on the large
>> project team I am currently working with who are investigation how we
>> can incorporate this stuff into the existing code.
>
> What type of project?
Embedded Linux controller.
> On 4/1/2017 3:35 PM, Ian Collins wrote:
>> On 04/ 2/17 09:17 AM, Chris M. Thomasson wrote:
>>> On 3/22/2017 1:35 PM, Chris M. Thomasson wrote:
>>>> First of all, these are very specialized, exotic type of sync algorithms
>>>> indeed! Keep that in the front of your mind wrt ever thinking about
>>>> using them directly: Think about danger when using them. Trust me, it
>>>> will keep you safer. However, by all means, if interested, learn all
>>>> about C++'s ability to provide the ability to implement these things
>>>> _before_ you use them for anything other than a "toy example test
>>>> program".
>>> [...]
>>>
>>> How many people in this group are actually interested in this type of
>>> ability provided by C++?
>>
>> More mow the idea are becoming mainstream. I appreciate that you have
>> been post about lock-free for many years, you'll probably be able to
>> converse with people other than your self before too long!
>
> Very nice. I am looking forward to this time Ian. Thank you.
>
>>
>> As a point of reference, there are a small group of us on the large
>> project team I am currently working with who are investigation how we
>> can incorporate this stuff into the existing code.
>
> What type of project?
> I am interested in any use patterns. Be careful
> wrt using some of this stuff because it can make a part of the engine
> more powerful. This enhancement will cast its increased performance on
> other parts of the system, in the form of more load. Might end up making
> a set of locks contend more than they ever had before...
--
Ian
Jorgen Grahn
Apr 3, 2017, 8:27:23 AM4/3/17
to
processes.
I used lock-free data structures in one project, but got the feeling
that noone on the project (me included) could spot the bugs, and that
such bugs would mostly show up in production.
/Jorgen
--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .
Chris M. Thomasson
Apr 3, 2017, 4:36:29 PM4/3/17
to
On 4/3/2017 5:27 AM, Jorgen Grahn wrote:
> On Sat, 2017-04-01, Chris M. Thomasson wrote:
>> On 3/22/2017 1:35 PM, Chris M. Thomasson wrote:
>>> First of all, these are very specialized, exotic type of sync algorithms
>>> indeed! Keep that in the front of your mind wrt ever thinking about
>>> using them directly: Think about danger when using them. Trust me, it
>>> will keep you safer. However, by all means, if interested, learn all
>>> about C++'s ability to provide the ability to implement these things
>>> _before_ you use them for anything other than a "toy example test program".
>> [...]
>>
>> How many people in this group are actually interested in this type of
>> ability provided by C++?
>
> I'm honestly more interested in keeping concurrency a thing between
> processes.
That can be a great way to use the hornets nest Jorgen, in the sense
> On Sat, 2017-04-01, Chris M. Thomasson wrote:
>> On 3/22/2017 1:35 PM, Chris M. Thomasson wrote:
>>> First of all, these are very specialized, exotic type of sync algorithms
>>> indeed! Keep that in the front of your mind wrt ever thinking about
>>> using them directly: Think about danger when using them. Trust me, it
>>> will keep you safer. However, by all means, if interested, learn all
>>> about C++'s ability to provide the ability to implement these things
>>> _before_ you use them for anything other than a "toy example test program".
>> [...]
>>
>> How many people in this group are actually interested in this type of
>> ability provided by C++?
>
> I'm honestly more interested in keeping concurrency a thing between
> processes.
that the noexcept variety are basically immune to random failures. We
rely on the atomic instructions provided by the underlying hardware, to
be atomic. Also, we can use some of them in interrupt/signal handlers.
This makes them ideal for inter-process communication. Thread crash will
destroy its process. However, a processes dying should be handled, and
almost, "expected to happen" when dealing with inter-process sync.
Mutexs can play major role here, and should not be overlooked. I have
used Pthreads robust mutexs wrt EOWNERDEAD, and windows WAIT_ABANDONED
states before. Very nice. Fwiw, these states mean the calling thread has
access, but the shared data-structure needs to be validated, and
possible corrected.
In certain compatible lock-free algorithms, this correction does not
need to happen, and failures are fine!
> I used lock-free data structures in one project, but got the feeling
> that noone on the project (me included) could spot the bugs, and that
> such bugs would mostly show up in production.
a bug. For the random nature of a race condition can be very bad!
https://groups.google.com/d/topic/comp.lang.c++/7u_rLgQe86k/discussion
(read all if interested... ;^)
It might crash the program 42 years from now! However, it might give
slightly wrong results a several of times a month, if it feels like
it... Wow.
Very scary.
Give Relacy at try:
http://www.1024cores.net/home/relacy-race-detector
:^)
Chris M. Thomasson
Apr 3, 2017, 4:49:13 PM4/3/17
to
on said project... On this type of device, I would take strong interest
in the single-producer/consumer relationship. No atomic RMW's!. A lot of
audio applications use this.
>
>> I am interested in any use patterns. Be careful
>> wrt using some of this stuff because it can make a part of the engine
>> more powerful. This enhancement will cast its increased performance on
>> other parts of the system, in the form of more load. Might end up making
>> a set of locks contend more than they ever had before...
>
> We are taking small steps and measuring as we go!
Thank you Ian.
:^)
Chris M. Thomasson
Apr 3, 2017, 4:49:52 PM4/3/17
to
0 new messages