Re: Musing about arcane (?) topics...
"David McClain (as dbm at refined-audiometrics dot com)" <[email protected]> Wed, 24 Jun 2026 12:25:51 -0700
| Newsgroups | gmane.lisp.lispworks.general |
|---|---|
| Message-ID | <[email protected]> |
--Apple-Mail=_062ABEC8-217F-46DA-9113-1137B2F48943
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
charset=utf-8
I think what may be getting lost in this conversation, and likely =
prevents me from seeing problems where they could actually occur=E2=80=A6
I assume people follow a CAS convention to try to gain exclusive use to =
a resource using something like this:
(defvar *global-list* nil)
(prog ((me (mp:get-current-process)))
TRY-AGAIN
(let ((old (symbol-value *global-list*)))
(if (sys:compare-and-swap (symbol-value *global-list*) old me)
;; Now we own the list in OLD. New contents are not a CONSP.
(...)
;; else
(go TRY-AGAIN))
))
What I actually do in my lock-free algorithms is a bit more elaborate, =
and instead of using my PROCESS pointer as an ownership indication, I =
use a structure filled in with the OLD value and a pointer to an update =
function that I will be using. =20
So if my thread gets delayed, and another thread needs that reference, =
it can finish up my modifications on my behalf, to arrive at the new =
value it should use.
The update function needs to be idempotent. But this method assures =
forward progress.
Now some people may really abuse the CAS protocol, like the example =
shown in the C++ code. And perhaps my discipline prevents me from seeing =
possible hazards in Common Lisp that I wouldn=E2=80=99t encounter.
> On Jun 24, 2026, at 12:00, David McClain =
<[email protected]> wrote:
>=20
> =E2=80=A6 and if you look carefully, the C++ code actually *deletes* =
an extant object. Thread 2 pops B, then deletes it, all while thread 1 =
has a reference to B.
>=20
> As I originally stated, no memory safe language would permit this. And =
Lisp is a memory safe language. So how can we suffer the same ABA =
problem as shown on the Wikipedia page?
>=20
>=20
>=20
>> On Jun 24, 2026, at 11:53, David McClain (as dbm at =
refined-audiometrics dot com) <[email protected]> wrote:
>>=20
>> Yes, I would argue that the C++ example is sloppy code. He isn=E2=80=99=
t even concerned with locking down the list at all. He just tries to =
pull a fast one by trying to unlink a CONS cell in the middle of the =
list without ever bothering to hold a lock on the list itself.
>>=20
>>=20
>>> On Jun 24, 2026, at 11:50, David McClain =
<[email protected]> wrote:
>>>=20
>>> Okay, I see that the C++ example is actually trying to use two =
separate items that really need to be used together. This is a case for =
DWCAS.=20
>>>=20
>>> How do we have that problem in Lisp? You shouldn=E2=80=99t start =
looking at CAR and CDR contents until you have a lock on the list head. =
Only then can you rely on CAR and CDR contents.
>>>=20
>>> The C++ example has optimistically (and incorrectly) looked deeper =
into the list before holding a lock on the list.
>>>=20
>>>=20
>>>=20
>>>> On Jun 24, 2026, at 11:43, David McClain =
<[email protected]> wrote:
>>>>=20
>>>> =E2=80=A6 and to expect even more, you would have to agree to =
perform only Functionally Pure coding, as visible by the rest of the =
world.=20
>>>> Internally, among local lexical bindings you can be as imperative =
as you like.=20
>>>>=20
>>>> As far as I can tell, it is impossible to enforce FPL conventions =
in Common Lisp. Just as it seems impossible to encode Copy On Write in =
Common Lisp.
>>>>=20
>>>>=20
>>>>> On Jun 24, 2026, at 11:40, David McClain =
<[email protected]> wrote:
>>>>>=20
>>>>> Oh yes, I absolutely agree with you and the article. (And I was =
considering only allocation problems.)=20
>>>>>=20
>>>>> But the Wikipedia example, I would contend, isn=E2=80=99t strictly =
an ABA problem. No history gets erased in this example.
>>>>>=20
>>>>> You have in hand, the pointer to the head of the list. That =
hasn=E2=80=99t changed, despite its content being changed. Why should =
that be a problem?=20
>>>>>=20
>>>>> You aren=E2=80=99t still pointing at the old list linkages, just =
at the list head. Whatever changed along the spine of the list is =
visible to you as you make your modifications.
>>>>>=20
>>>>> So, while technically, the absolute contents of the list may have =
changed, that shouldn=E2=80=99t be a problem for you once you get a lock =
on the object. You are locking access via the list head, and nothing =
more.
>>>>>=20
>>>>>=20
>>>>>> On Jun 24, 2026, at 10:52, Martin Simmons <[email protected]> =
wrote:
>>>>>>=20
>>>>>> Are you only considering ABA problems that involve allocation? =
The lock-free
>>>>>> stack example in https://en.wikipedia.org/wiki/ABA_problem could =
happen in
>>>>>> Lisp.
>>>>>>=20
>>>>>> --=20
>>>>>> Martin Simmons
>>>>>> LispWorks Ltd
>>>>>> http://www.lispworks.com/
>>>>>>=20
>>>>>>=20
>>>>>>=20
>>>>>>>>>>> On Wed, 24 Jun 2026 03:46:38 -0700, David McClain (as dbm at =
refined-audiometrics dot com) said:
>>>>>>>=20
>>>>>>> Even more fundamental result:=20
>>>>>>>=20
>>>>>>> ABA problems *cannot* happen in Common Lisp proper (excluding =
FLI), nor in any other =E2=80=9CMemory Safe=E2=80=9D system.=20
>>>>>>>=20
>>>>>>> Storage for A (the old value) being held for use in a CAS =
operation, cannot be discarded by the GC and reused by an MRU allocator =
to produce a C object with Addr(C) =3D Addr(A).
>>>>>>>=20
>>>>>>> An ABA problem arises when ABA could become ABC, with Addr(C) =3D =
Addr(A), just prior to the CAS operation. The CAS will succeed and =
produce ABX, where X =3D the locking value, thereby discarding C, and =
hence producing an =E2=80=9CABA Problem=E2=80=9D. When ABX later gets =
updated to ABA=E2=80=B2. The A=E2=80=B2 will have been produced using =
stale information, A, and history, in C, will have been discarded.
>>>>>>>=20
>>>>>>> There is no need to mandate immutability of data to avoid ABA =
problems in Lisp. They simply cannot ever happen.
>>>>>>>=20
>>>>>>>=20
>>>>>>>=20
>>>>>>> _______________________________________________
>>>>>>> Lisp Hug - the mailing list for LispWorks users
>>>>>>> [email protected]
>>>>>>> http://www.lispworks.com/support/lisp-hug.html
>>>>>>>=20
>>>>>>=20
>>>>>> _______________________________________________
>>>>>> Lisp Hug - the mailing list for LispWorks users
>>>>>> [email protected]
>>>>>> http://www.lispworks.com/support/lisp-hug.html
>>>>>=20
>>>>=20
>>>=20
>>=20
>>=20
>> _______________________________________________
>> Lisp Hug - the mailing list for LispWorks users
>> [email protected]
>> http://www.lispworks.com/support/lisp-hug.html
>=20
--Apple-Mail=_062ABEC8-217F-46DA-9113-1137B2F48943
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html;
charset=utf-8
<html aria-label=3D"message body"><head><meta http-equiv=3D"content-type" =
content=3D"text/html; charset=3Dutf-8"></head><body =
style=3D"overflow-wrap: break-word; -webkit-nbsp-mode: space; =
line-break: after-white-space;">I think what may be getting lost in this =
conversation, and likely prevents me from seeing problems where they =
could actually occur=E2=80=A6<div><br></div><div>I assume people follow =
a CAS convention to try to gain exclusive use to a resource using =
something like this:<br =
id=3D"lineBreakAtBeginningOfMessage"><div><br><div><font =
face=3D"Monaco">(defvar *global-list* nil)</font></div><div><font =
face=3D"Monaco"><br></font></div><div><font face=3D"Monaco">(prog ((me =
(mp:get-current-process)))</font></div><div><font =
face=3D"Monaco"> TRY-AGAIN</font></div><div><font =
face=3D"Monaco"> (let ((old (symbol-value =
*global-list*)))</font></div><div><font face=3D"Monaco"> =
(if (sys:compare-and-swap (symbol-value *global-list*) old =
me)</font></div><div><font face=3D"Monaco"> =
;; Now we own the list in OLD. New contents are not a =
CONSP.</font></div><div><font face=3D"Monaco"> =
(...)</font></div><div><font face=3D"Monaco"> =
;; else</font></div><div><font face=3D"Monaco"> (go =
TRY-AGAIN))</font></div><div><font face=3D"Monaco"> =
))</font></div><div><br></div><div>What I actually do in my lock-free =
algorithms is a bit more elaborate, and instead of using my PROCESS =
pointer as an ownership indication, I use a structure filled in with the =
OLD value and a pointer to an update function that I will be using. =
</div><div><br></div><div>So if my thread gets delayed, and =
another thread needs that reference, it can finish up my modifications =
on my behalf, to arrive at the new value it should =
use.</div><div><br></div><div>The update function needs to be =
idempotent. But this method assures forward =
progress.</div><div><br></div><div>Now some people may really abuse the =
CAS protocol, like the example shown in the C++ code. And perhaps my =
discipline prevents me from seeing possible hazards in Common Lisp that =
I wouldn=E2=80=99t =
encounter.</div><div><br></div><div><br></div><div><br></div><blockquote =
type=3D"cite"><div>On Jun 24, 2026, at 12:00, David McClain =
<[email protected]> wrote:</div><br =
class=3D"Apple-interchange-newline"><div><div>=E2=80=A6 and if you look =
carefully, the C++ code actually *deletes* an extant object. Thread 2 =
pops B, then deletes it, all while thread 1 has a reference to =
B.<br><br>As I originally stated, no memory safe language would permit =
this. And Lisp is a memory safe language. So how can we suffer the same =
ABA problem as shown on the Wikipedia page?<br><br><br><br><blockquote =
type=3D"cite">On Jun 24, 2026, at 11:53, David McClain (as dbm at =
refined-audiometrics dot com) <[email protected]> =
wrote:<br><br>Yes, I would argue that the C++ example is sloppy code. He =
isn=E2=80=99t even concerned with locking down the list at all. He just =
tries to pull a fast one by trying to unlink a CONS cell in the middle =
of the list without ever bothering to hold a lock on the list =
itself.<br><br><br><blockquote type=3D"cite">On Jun 24, 2026, at 11:50, =
David McClain <[email protected]> wrote:<br><br>Okay, I =
see that the C++ example is actually trying to use two separate items =
that really need to be used together. This is a case for DWCAS. =
<br><br>How do we have that problem in Lisp? You shouldn=E2=80=99t start =
looking at CAR and CDR contents until you have a lock on the list head. =
Only then can you rely on CAR and CDR contents.<br><br>The C++ example =
has optimistically (and incorrectly) looked deeper into the list before =
holding a lock on the list.<br><br><br><br><blockquote type=3D"cite">On =
Jun 24, 2026, at 11:43, David McClain =
<[email protected]> wrote:<br><br>=E2=80=A6 and to =
expect even more, you would have to agree to perform only Functionally =
Pure coding, as visible by the rest of the world. <br>Internally, among =
local lexical bindings you can be as imperative as you like. <br><br>As =
far as I can tell, it is impossible to enforce FPL conventions in Common =
Lisp. Just as it seems impossible to encode Copy On Write in Common =
Lisp.<br><br><br><blockquote type=3D"cite">On Jun 24, 2026, at 11:40, =
David McClain <[email protected]> wrote:<br><br>Oh yes, =
I absolutely agree with you and the article. (And I was considering only =
allocation problems.) <br><br>But the Wikipedia example, I would =
contend, isn=E2=80=99t strictly an ABA problem. No history gets erased =
in this example.<br><br>You have in hand, the pointer to the head of the =
list. That hasn=E2=80=99t changed, despite its content being changed. =
Why should that be a problem? <br><br>You aren=E2=80=99t still pointing =
at the old list linkages, just at the list head. Whatever changed along =
the spine of the list is visible to you as you make your =
modifications.<br><br>So, while technically, the absolute contents of =
the list may have changed, that shouldn=E2=80=99t be a problem for you =
once you get a lock on the object. You are locking access via the list =
head, and nothing more.<br><br><br><blockquote type=3D"cite">On Jun 24, =
2026, at 10:52, Martin Simmons <[email protected]> =
wrote:<br><br>Are you only considering ABA problems that involve =
allocation? The lock-free<br>stack example in =
https://en.wikipedia.org/wiki/ABA_problem could happen =
in<br>Lisp.<br><br>-- <br>Martin Simmons<br>LispWorks =
Ltd<br>http://www.lispworks.com/<br><br><br><br><blockquote =
type=3D"cite"><blockquote type=3D"cite"><blockquote =
type=3D"cite"><blockquote type=3D"cite"><blockquote type=3D"cite">On =
Wed, 24 Jun 2026 03:46:38 -0700, David McClain (as dbm at =
refined-audiometrics dot com) =
said:<br></blockquote></blockquote></blockquote></blockquote><br>Even =
more fundamental result: <br><br>ABA problems *cannot* happen in Common =
Lisp proper (excluding FLI), nor in any other =E2=80=9CMemory Safe=E2=80=9D=
system. <br><br>Storage for A (the old value) being held for use in a =
CAS operation, cannot be discarded by the GC and reused by an MRU =
allocator to produce a C object with Addr(C) =3D Addr(A).<br><br>An ABA =
problem arises when ABA could become ABC, with Addr(C) =3D Addr(A), just =
prior to the CAS operation. The CAS will succeed and produce ABX, where =
X =3D the locking value, thereby discarding C, and hence producing an =
=E2=80=9CABA Problem=E2=80=9D. When ABX later gets updated to ABA=E2=80=B2=
. The A=E2=80=B2 will have been produced using stale information, A, and =
history, in C, will have been discarded.<br><br>There is no need to =
mandate immutability of data to avoid ABA problems in Lisp. They simply =
cannot ever =
happen.<br><br><br><br>_______________________________________________<br>=
Lisp Hug - the mailing list for LispWorks =
users<br>[email protected]<br>http://www.lispworks.com/support/lisp-h=
ug.html<br><br></blockquote><br>__________________________________________=
_____<br>Lisp Hug - the mailing list for LispWorks =
users<br>[email protected]<br>http://www.lispworks.com/support/lisp-h=
ug.html<br></blockquote><br></blockquote><br></blockquote><br></blockquote=
><br><br>_______________________________________________<br>Lisp Hug - =
the mailing list for LispWorks =
users<br>[email protected]<br>http://www.lispworks.com/support/lisp-h=
ug.html<br></blockquote><br></div></div></blockquote></div><br></div></bod=
y></html>=
--Apple-Mail=_062ABEC8-217F-46DA-9113-1137B2F48943--
_______________________________________________
Lisp Hug - the mailing list for LispWorks users
[email protected]
http://www.lispworks.com/support/lisp-hug.html