[PATCH] Add atomic-box-update! function to (ice-9 atomic)

[PATCH] Add atomic-box-update! function to (ice-9 atomic)

[Andrew Tropin]

[-- Attachment #1: Type: text/plain, Size: 1750 bytes --]


* module/ice-9/atomic.scm (atomic-box-update!): New variable.
---
I was implementing some concurrent code and started to use (ice-9
atomic), when found out that there is no procedure for updating the
value of the atom using another function.

IMHO, atomic-box-update! fits well FP paradigm (which is widely used
across guile-based projects) in general and this module in particular
and should be provided out of the box.  Made a draft implementation.
LMKWYT.

 module/ice-9/atomic.scm | 14 +++++++++++++-
 1 file changed, 13 insertions(+), 1 deletion(-)

diff --git a/module/ice-9/atomic.scm b/module/ice-9/atomic.scm
index 2a8af901d..6bfa2e8ee 100644
--- a/module/ice-9/atomic.scm
+++ b/module/ice-9/atomic.scm
@@ -25,7 +25,8 @@
             atomic-box-ref
             atomic-box-set!
             atomic-box-swap!
-            atomic-box-compare-and-swap!))
+            atomic-box-compare-and-swap!
+            atomic-box-update!))
 
 (eval-when (expand load eval)
   (load-extension (string-append "libguile-" (effective-version))
@@ -36,3 +37,14 @@
   (add-interesting-primitive! 'atomic-box-set!)
   (add-interesting-primitive! 'atomic-box-swap!)
   (add-interesting-primitive! 'atomic-box-compare-and-swap!))
+
+(define (atomic-box-update! box proc . proc-args)
+  "Atomically updates value of BOX to (APPLY PROC BOX-VALUE PROC-ARGS),
+returns new value.  PROC may be called multiple times, and thus PROC
+should be free of side effects."
+  (let loop ()
+    (let* ((old-value (atomic-box-ref box))
+           (new-value (apply proc old-value proc-args)))
+      (if (eq? old-value (atomic-box-compare-and-swap! box old-value new-value))
+          new-value
+          (loop)))))
-- 
2.40.1

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 832 bytes --]

Re: [PATCH] Add atomic-box-update! function to (ice-9 atomic)

[Jean Abou Samra]

[-- Attachment #1.1: Type: text/plain, Size: 277 bytes --]

Le lundi 19 juin 2023 à 16:20 +0400, Andrew Tropin a écrit :
> +      (if (eq? old-value (atomic-box-compare-and-swap! box old-value new-value))


Are you sure eq? is a good idea here? (eq? 5 5) is unspecified, for example. Perhaps eqv? would be more appropriate.

[-- Attachment #1.2: Type: text/html, Size: 772 bytes --]

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 228 bytes --]

Re: [PATCH] Add atomic-box-update! function to (ice-9 atomic)

[Jean Abou Samra]

[-- Attachment #1.1: Type: text/plain, Size: 441 bytes --]

Le mercredi 21 juin 2023 à 11:06 +0200, Jean Abou Samra a écrit :
> Le lundi 19 juin 2023 à 16:20 +0400, Andrew Tropin a écrit :
> > +      (if (eq? old-value (atomic-box-compare-and-swap! box old-value new-value))
> 
> 
> Are you sure eq? is a good idea here? (eq? 5 5) is unspecified, for example. Perhaps eqv? would be more appropriate.

(P.S. And according to the manual, even (let ((a 5)) (eq? a a)) is unspecified.)

[-- Attachment #1.2: Type: text/html, Size: 1336 bytes --]

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 228 bytes --]

Re: [PATCH] Add atomic-box-update! function to (ice-9 atomic)

[Andrew Tropin]

[-- Attachment #1: Type: text/plain, Size: 1012 bytes --]

On 2023-06-21 11:06, Jean Abou Samra wrote:

> Le mercredi 21 juin 2023 à 11:06 +0200, Jean Abou Samra a écrit :
>> Le lundi 19 juin 2023 à 16:20 +0400, Andrew Tropin a écrit :
>> > +      (if (eq? old-value (atomic-box-compare-and-swap! box old-value new-value))
>> 
>> 
>> Are you sure eq? is a good idea here? (eq? 5 5) is unspecified, for example. Perhaps eqv? would be more appropriate.
>
> (P.S. And according to the manual, even (let ((a 5)) (eq? a a)) is unspecified.)

Make sense, but it's hard for me to say something valuable on this
topic.  Usually, I don't use eq? and don't have enough knowledge of its
internals.  I went the way suggested by the manual: "Returns the
previous value of the box in either case, so you can know if the swap
worked by checking if the return value is eq? to expected."

https://www.gnu.org/software/guile/manual/html_node/Atomics.html

CCed Andy, I guess he knows the right answer and can explain it.

-- 
Best regards,
Andrew Tropin

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 832 bytes --]

Re: [PATCH] Add atomic-box-update! function to (ice-9 atomic)

[Jean Abou Samra]

> Le 21 juin 2023 à 18:46, Andrew Tropin <andrew@trop.in> a écrit :
> 
> Make sense, but it's hard for me to say something valuable on this
> topic.  Usually, I don't use eq? and don't have enough knowledge of its
> internals.


*Currently*, it just checks whether the two C-level SCM values are the same bitwise, so even implicit copies of fixnums will remain eq?. In theory, Guile could make copies of bignums. I am not aware of it doing so.

However, all that is guaranteed is that (eq? a a) when a is a non-immediate (pair, string, vector, hashtable, etc) or one of a few constants like booleans, the empty list and *unspecified*. Notably, it isn't guaranteed for numbers or characters.


> I went the way suggested by the manual: "Returns the
> previous value of the box in either case, so you can know if the swap
> worked by checking if the return value is eq? to expected."
> 
> https://www.gnu.org/software/guile/manual/html_node/Atomics.html


As long as you use boxes for values for which eq? is well-defined, that is fine. I guess this would cover most cases, although I'm not familiar with this module.

But in general, eqv? seems saner.

Re: [PATCH] Add atomic-box-update! function to (ice-9 atomic)

[Andrew Tropin]

[-- Attachment #1: Type: text/plain, Size: 1841 bytes --]

On 2023-06-21 18:54, Jean Abou Samra wrote:

>> Le 21 juin 2023 à 18:46, Andrew Tropin <andrew@trop.in> a écrit :
>> 
>> Make sense, but it's hard for me to say something valuable on this
>> topic.  Usually, I don't use eq? and don't have enough knowledge of its
>> internals.
>
>
> *Currently*, it just checks whether the two C-level SCM values are the
> same bitwise, so even implicit copies of fixnums will remain eq?. In
> theory, Guile could make copies of bignums. I am not aware of it doing
> so.
>
> However, all that is guaranteed is that (eq? a a) when a is a
> non-immediate (pair, string, vector, hashtable, etc) or one of a few
> constants like booleans, the empty list and *unspecified*. Notably, it
> isn't guaranteed for numbers or characters.
>
>
>> I went the way suggested by the manual: "Returns the
>> previous value of the box in either case, so you can know if the swap
>> worked by checking if the return value is eq? to expected."
>> 
>> https://www.gnu.org/software/guile/manual/html_node/Atomics.html
>
>
> As long as you use boxes for values for which eq? is well-defined,
> that is fine. I guess this would cover most cases, although I'm not
> familiar with this module.

We don't compare boxes here, we compare the underlying values.  I'm
almost sure that we need eq? here as we need to make sure that the value
previously stored and returned atomic-box-compare-and-swap! is the same
object in memory, however this example from manual is indeed confusing:

--8<---------------cut here---------------start------------->8---
 (let ((n (+ 2 3)))
       (eq? n n))                           ==>  _unspecified_
--8<---------------cut here---------------end--------------->8---

So maybe you are right and it's better to use eqv? here.

-- 
Best regards,
Andrew Tropin

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 832 bytes --]

Re: [PATCH] Add atomic-box-update! function to (ice-9 atomic)

[Philip McGrath]

On Wed, Jun 21, 2023, at 11:59 PM, Andrew Tropin wrote:
> On 2023-06-21 18:54, Jean Abou Samra wrote:
>
>>> Le 21 juin 2023 à 18:46, Andrew Tropin <andrew@trop.in> a écrit :
>>> 
>>> Make sense, but it's hard for me to say something valuable on this
>>> topic.  Usually, I don't use eq? and don't have enough knowledge of its
>>> internals.
>>
>>
>> *Currently*, it just checks whether the two C-level SCM values are the
>> same bitwise, so even implicit copies of fixnums will remain eq?. In
>> theory, Guile could make copies of bignums. I am not aware of it doing
>> so.
>>
>> However, all that is guaranteed is that (eq? a a) when a is a
>> non-immediate (pair, string, vector, hashtable, etc) or one of a few
>> constants like booleans, the empty list and *unspecified*. Notably, it
>> isn't guaranteed for numbers or characters.
>>
> [...]  I'm
> almost sure that we need eq? here as we need to make sure that the value
> previously stored and returned atomic-box-compare-and-swap! is the same
> object in memory, however this example from manual is indeed confusing:
>
> --8<---------------cut here---------------start------------->8---
>  (let ((n (+ 2 3)))
>        (eq? n n))                           ==>  _unspecified_
> --8<---------------cut here---------------end--------------->8---
>
> So maybe you are right and it's better to use eqv? here.
>

The problem with eqv? is that it doesn't correspond well to machine-level atomic compare-and-set instructions, so using it would defeat the purpose of lightweight atomic boxes.

R6RS specifies that "the behavior of eq? on number objects and characters is implementation-dependent, but it always returns either #t or #f, and returns #t only when eqv? would also return #t." [1] I think the right thing to do here is for Guile to provide more guarantees about its implementation of eq?.

Guaranteeing that fixnums are eq? when they are = would be particularly reasonable and extremely unlikely to cause constrain any future port of Guile: the whole point of fixnums is to support efficient machine operations like this. I also think most Schemers would be quite surprised if (lambda (x) (eq? x x)) ever returned #f. More broadly, *The Scheme Programming Language* says at the beginning of its documentation for eq? that, "In most Scheme systems, two objects are considered identical if they are represented internally by the same pointer value and distinct (not identical) if they are represented internally by different pointer values, although other criteria, such as time-stamping, are possible."

In any case, the current documentation for atomic-box-compare-and-swap! is clear that the comparison is eq?: it just means that, when the behavior of eq? is unreliable, so is the behavior of atomic-box-compare-and-swap!.

Tangentially, does atomic-box-compare-and-swap! handle spurious failures on architectures like ARM, or does it expose machine semantics to the programmer? Maybe that's covered by details of the C11 memory model, but I don't think "sequential consistency" alone is enough to answer the question.

-Philip

[1]: https://www.r6rs.org/final/html/r6rs/r6rs-Z-H-14.html#node_sec_11.5
[2]: https://scheme.com/tspl4/objects.html#./objects:s10

Re: [PATCH] Add atomic-box-update! function to (ice-9 atomic)

[Andrew Tropin]

[-- Attachment #1: Type: text/plain, Size: 3651 bytes --]

On 2023-06-22 01:21, Philip McGrath wrote:

> On Wed, Jun 21, 2023, at 11:59 PM, Andrew Tropin wrote:
>> On 2023-06-21 18:54, Jean Abou Samra wrote:
>>
>>>> Le 21 juin 2023 à 18:46, Andrew Tropin <andrew@trop.in> a écrit :
>>>> 
>>>> Make sense, but it's hard for me to say something valuable on this
>>>> topic.  Usually, I don't use eq? and don't have enough knowledge of its
>>>> internals.
>>>
>>>
>>> *Currently*, it just checks whether the two C-level SCM values are the
>>> same bitwise, so even implicit copies of fixnums will remain eq?. In
>>> theory, Guile could make copies of bignums. I am not aware of it doing
>>> so.
>>>
>>> However, all that is guaranteed is that (eq? a a) when a is a
>>> non-immediate (pair, string, vector, hashtable, etc) or one of a few
>>> constants like booleans, the empty list and *unspecified*. Notably, it
>>> isn't guaranteed for numbers or characters.
>>>
>> [...]  I'm
>> almost sure that we need eq? here as we need to make sure that the value
>> previously stored and returned atomic-box-compare-and-swap! is the same
>> object in memory, however this example from manual is indeed confusing:
>>
>> --8<---------------cut here---------------start------------->8---
>>  (let ((n (+ 2 3)))
>>        (eq? n n))                           ==>  _unspecified_
>> --8<---------------cut here---------------end--------------->8---
>>
>> So maybe you are right and it's better to use eqv? here.
>>
>
> The problem with eqv? is that it doesn't correspond well to
> machine-level atomic compare-and-set instructions, so using it would
> defeat the purpose of lightweight atomic boxes.
>
> R6RS specifies that "the behavior of eq? on number objects and
> characters is implementation-dependent, but it always returns either
> #t or #f, and returns #t only when eqv? would also return #t." [1] I
> think the right thing to do here is for Guile to provide more
> guarantees about its implementation of eq?.
>
> Guaranteeing that fixnums are eq? when they are = would be
> particularly reasonable and extremely unlikely to cause constrain any
> future port of Guile: the whole point of fixnums is to support
> efficient machine operations like this. I also think most Schemers
> would be quite surprised if (lambda (x) (eq? x x)) ever returned
> #f. More broadly, *The Scheme Programming Language* says at the
> beginning of its documentation for eq? that, "In most Scheme systems,
> two objects are considered identical if they are represented
> internally by the same pointer value and distinct (not identical) if
> they are represented internally by different pointer values, although
> other criteria, such as time-stamping, are possible."

Thank you very much for in-depth explanation!

>
> In any case, the current documentation for
> atomic-box-compare-and-swap! is clear that the comparison is eq?: it
> just means that, when the behavior of eq? is unreliable, so is the
> behavior of atomic-box-compare-and-swap!.

Good.  Than implementation of atomic-box-update! looks correct to me.
Any thoughts on including it in (ice-9 atomic)?

>
> Tangentially, does atomic-box-compare-and-swap! handle spurious
> failures on architectures like ARM, or does it expose machine
> semantics to the programmer? Maybe that's covered by details of the
> C11 memory model, but I don't think "sequential consistency" alone is
> enough to answer the question.
>
> -Philip
>
> [1]: https://www.r6rs.org/final/html/r6rs/r6rs-Z-H-14.html#node_sec_11.5
> [2]: https://scheme.com/tspl4/objects.html#./objects:s10

-- 
Best regards,
Andrew Tropin

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 832 bytes --]

Re: [PATCH] Add atomic-box-update! function to (ice-9 atomic)

[Philip McGrath]

On Thu, Jun 22, 2023, at 5:02 AM, Andrew Tropin wrote:
> On 2023-06-22 01:21, Philip McGrath wrote:
>>
>> In any case, the current documentation for
>> atomic-box-compare-and-swap! is clear that the comparison is eq?: it
>> just means that, when the behavior of eq? is unreliable, so is the
>> behavior of atomic-box-compare-and-swap!.
>
> Good.  Than implementation of atomic-box-update! looks correct to me.
> Any thoughts on including it in (ice-9 atomic)?
>
>>
>> Tangentially, does atomic-box-compare-and-swap! handle spurious
>> failures on architectures like ARM, or does it expose machine
>> semantics to the programmer? Maybe that's covered by details of the
>> C11 memory model, but I don't think "sequential consistency" alone is
>> enough to answer the question.
>>

I think your implementation is correct. If atomic-box-compare-and-swap! does not handle spurious failures, I think your implementation is still correct, but a more efficient implementation could retry without an extra call to the update procedure.

Someone with a better sense of Guile performance might have a view about whether `apply` is likely to be expensive: alternatively, the update procedure could be restricted to a single argument, or `case-lambda` could provide a specialized entry-point.

-Philip

Re: [PATCH] Add atomic-box-update! function to (ice-9 atomic)

[Andrew Tropin]

[-- Attachment #1: Type: text/plain, Size: 1621 bytes --]

On 2023-06-22 17:42, Philip McGrath wrote:

> On Thu, Jun 22, 2023, at 5:02 AM, Andrew Tropin wrote:
>> On 2023-06-22 01:21, Philip McGrath wrote:
>>>
>>> In any case, the current documentation for
>>> atomic-box-compare-and-swap! is clear that the comparison is eq?: it
>>> just means that, when the behavior of eq? is unreliable, so is the
>>> behavior of atomic-box-compare-and-swap!.
>>
>> Good.  Than implementation of atomic-box-update! looks correct to me.
>> Any thoughts on including it in (ice-9 atomic)?
>>
>>>
>>> Tangentially, does atomic-box-compare-and-swap! handle spurious
>>> failures on architectures like ARM, or does it expose machine
>>> semantics to the programmer? Maybe that's covered by details of the
>>> C11 memory model, but I don't think "sequential consistency" alone is
>>> enough to answer the question.
>>>
>
> I think your implementation is correct. If
> atomic-box-compare-and-swap! does not handle spurious failures, I
> think your implementation is still correct, but a more efficient
> implementation could retry without an extra call to the update
> procedure.

How? If value was updated you need to recalculate new value.

>
> Someone with a better sense of Guile performance might have a view
> about whether `apply` is likely to be expensive: alternatively, the
> update procedure could be restricted to a single argument, or
> `case-lambda` could provide a specialized entry-point.

Original implementation was a single argument, but I thought that
variable number of arguments will be more convinient.

-- 
Best regards,
Andrew Tropin

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 832 bytes --]

Re: [PATCH] Add atomic-box-update! function to (ice-9 atomic)

[Andrew Tropin]

[-- Attachment #1: Type: text/plain, Size: 2118 bytes --]

On 2023-06-19 16:20, Andrew Tropin wrote:

> * module/ice-9/atomic.scm (atomic-box-update!): New variable.
> ---
> I was implementing some concurrent code and started to use (ice-9
> atomic), when found out that there is no procedure for updating the
> value of the atom using another function.
>
> IMHO, atomic-box-update! fits well FP paradigm (which is widely used
> across guile-based projects) in general and this module in particular
> and should be provided out of the box.  Made a draft implementation.
> LMKWYT.
>
>  module/ice-9/atomic.scm | 14 +++++++++++++-
>  1 file changed, 13 insertions(+), 1 deletion(-)
>
> diff --git a/module/ice-9/atomic.scm b/module/ice-9/atomic.scm
> index 2a8af901d..6bfa2e8ee 100644
> --- a/module/ice-9/atomic.scm
> +++ b/module/ice-9/atomic.scm
> @@ -25,7 +25,8 @@
>              atomic-box-ref
>              atomic-box-set!
>              atomic-box-swap!
> -            atomic-box-compare-and-swap!))
> +            atomic-box-compare-and-swap!
> +            atomic-box-update!))
>  
>  (eval-when (expand load eval)
>    (load-extension (string-append "libguile-" (effective-version))
> @@ -36,3 +37,14 @@
>    (add-interesting-primitive! 'atomic-box-set!)
>    (add-interesting-primitive! 'atomic-box-swap!)
>    (add-interesting-primitive! 'atomic-box-compare-and-swap!))
> +
> +(define (atomic-box-update! box proc . proc-args)
> +  "Atomically updates value of BOX to (APPLY PROC BOX-VALUE PROC-ARGS),
> +returns new value.  PROC may be called multiple times, and thus PROC
> +should be free of side effects."
> +  (let loop ()
> +    (let* ((old-value (atomic-box-ref box))
> +           (new-value (apply proc old-value proc-args)))
> +      (if (eq? old-value (atomic-box-compare-and-swap! box old-value new-value))
> +          new-value
> +          (loop)))))

Found one more example of the usage of this pattern in fibers
library.  Those lines by Christine Lemmer-Webber:
https://github.com/wingo/fibers/blob/581319ff13b97f2bb51dff713524aad696c5d52b/fibers/counter.scm#L37

-- 
Best regards,
Andrew Tropin

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 832 bytes --]

[PATCH v2] Add atomic-box-update! function to (ice-9 atomic)

[Andrew Tropin]

[-- Attachment #1: Type: text/plain, Size: 1413 bytes --]


* module/ice-9/atomic.scm (atomic-box-update!): New variable.
---
Changes since v1. Use single-argument proc to avoid potential perfomance
problems cause of call to apply.

 module/ice-9/atomic.scm | 14 +++++++++++++-
 1 file changed, 13 insertions(+), 1 deletion(-)

diff --git a/module/ice-9/atomic.scm b/module/ice-9/atomic.scm
index 2a8af901d..6bfa2e8ee 100644
--- a/module/ice-9/atomic.scm
+++ b/module/ice-9/atomic.scm
@@ -25,7 +25,8 @@
             atomic-box-ref
             atomic-box-set!
             atomic-box-swap!
-            atomic-box-compare-and-swap!))
+            atomic-box-compare-and-swap!
+            atomic-box-update!))
 
 (eval-when (expand load eval)
   (load-extension (string-append "libguile-" (effective-version))
@@ -36,3 +37,14 @@
   (add-interesting-primitive! 'atomic-box-set!)
   (add-interesting-primitive! 'atomic-box-swap!)
   (add-interesting-primitive! 'atomic-box-compare-and-swap!))
+
+(define (atomic-box-update! box proc)
+  "Atomically updates value of BOX to (PROC BOX-VALUE), returns new
+value.  PROC may be called multiple times, and thus PROC should be
+free of side effects."
+  (let loop ()
+    (let* ((old-value (atomic-box-ref box))
+           (new-value (proc old-value)))
+      (if (eq? old-value (atomic-box-compare-and-swap! box old-value new-value))
+          new-value
+          (loop)))))
-- 
2.40.1

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 832 bytes --]

Re: [PATCH v2] Add atomic-box-update! function to (ice-9 atomic)

[Maxime Devos]

[-- Attachment #1.1.1: Type: text/plain, Size: 3325 bytes --]



Op 22-08-2023 om 12:59 schreef Andrew Tropin:
> 
> * module/ice-9/atomic.scm (atomic-box-update!): New variable.
> ---
> Changes since v1. Use single-argument proc to avoid potential perfomance
> problems cause of call to apply.
> 
>   module/ice-9/atomic.scm | 14 +++++++++++++-
>   1 file changed, 13 insertions(+), 1 deletion(-)
> 
> diff --git a/module/ice-9/atomic.scm b/module/ice-9/atomic.scm
> index 2a8af901d..6bfa2e8ee 100644
> --- a/module/ice-9/atomic.scm
> +++ b/module/ice-9/atomic.scm
> @@ -25,7 +25,8 @@
>               atomic-box-ref
>               atomic-box-set!
>               atomic-box-swap!
> -            atomic-box-compare-and-swap!))
> +            atomic-box-compare-and-swap!
> +            atomic-box-update!))
>   
>   (eval-when (expand load eval)
>     (load-extension (string-append "libguile-" (effective-version))
> @@ -36,3 +37,14 @@
>     (add-interesting-primitive! 'atomic-box-set!)
>     (add-interesting-primitive! 'atomic-box-swap!)
>     (add-interesting-primitive! 'atomic-box-compare-and-swap!))
> +
> +(define (atomic-box-update! box proc)
> +  "Atomically updates value of BOX to (PROC BOX-VALUE), returns new
> +value.

* , returns new value -> and returns the new value

While descriptive works, for consistency with other atomics 
documentation, this imperative procedure needs to be documented in the 
imperative mood:

Atomically update the value of BOX to (PROC BOX-VALUE) and return the 
new value.

Alternatively, you can adjust the other documentation of atomics to the 
indicative mood and preserve the original docstring (except for the 
grammar correction mentioned in the beginning).

   PROC may be called multiple times, and thus PROC should be
> +free of side effects." > +  (let loop ()
> +    (let* ((old-value (atomic-box-ref box))
> +           (new-value (proc old-value)))
> +      (if (eq? old-value (atomic-box-compare-and-swap! box old-value new-value))
> +          new-value
> +          (loop)))))

This can be optimised, by using the return value of CAS as the new old 
value instead of calling atomic-box-ref again:

(let loop ((old-value (atomic-box-ref box)))
   (let* ((new-value (proc new-value))
          (new-old-value (atomic-box-compare-and-swap! box old-value 
new-value)))
     (if (eq? new-old-value old-value)
         new-value
         (loop new-old-value))))

Maybe there is some concurrency weirdness that can cause slower 
iterations to reduce the number of iterations (*); I'm assuming this 
isn't the case here.  But if it is, in fact, the case here, and the goal 
is to exploit this effect, I would think it's better to explicitly 
implement the back-off.

(I haven't benchmarked any of this, I'm purely going by the number of 
operations.)

(*) E.g., from Wikipedia: 
https://en.wikipedia.org/w/index.php?title=Compare-and-swap&oldid=1141385700

[...] Instead of immediately retrying after a CAS operation fails, 
researchers have found that total system performance can be improved in 
multiprocessor systems—where many threads constantly update some 
particular shared variable—if threads that see their CAS fail use 
exponential backoff—in other words, wait a little before retrying the 
CAS.[4]

Best regards,
Maxime Devos.

[-- Attachment #1.1.2: OpenPGP public key --]
[-- Type: application/pgp-keys, Size: 929 bytes --]

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 236 bytes --]

[PATCH v3] Add atomic-box-update! function to (ice-9 atomic)

[Andrew Tropin]

* module/ice-9/atomic.scm (atomic-box-update!): New variable.
---
Changes since v2: 
1. Removed unecessary atomic-box-ref.
2. Update docstring to imperative mood.

 module/ice-9/atomic.scm | 14 +++++++++++++-
 1 file changed, 13 insertions(+), 1 deletion(-)

diff --git a/module/ice-9/atomic.scm b/module/ice-9/atomic.scm
index 2a8af901d..aaa7238fc 100644
--- a/module/ice-9/atomic.scm
+++ b/module/ice-9/atomic.scm
@@ -25,7 +25,8 @@
             atomic-box-ref
             atomic-box-set!
             atomic-box-swap!
-            atomic-box-compare-and-swap!))
+            atomic-box-compare-and-swap!
+            atomic-box-update!))
 
 (eval-when (expand load eval)
   (load-extension (string-append "libguile-" (effective-version))
@@ -36,3 +37,14 @@
   (add-interesting-primitive! 'atomic-box-set!)
   (add-interesting-primitive! 'atomic-box-swap!)
   (add-interesting-primitive! 'atomic-box-compare-and-swap!))
+
+(define (atomic-box-update! box proc)
+  "Atomically update the value of BOX to (PROC BOX-VALUE) and return the
+new value.  PROC may be called multiple times, and thus PROC should be
+free of side effects."
+  (let loop ((old-value (atomic-box-ref box)))
+    (let* ((new-value (proc old-value proc-args))
+           (cas-value (atomic-box-compare-and-swap! box old-value new-value)))
+      (if (eq? old-value cas-value)
+          new-value
+          (loop cas-value)))))
-- 
2.41.0

Re: [PATCH v2] Add atomic-box-update! function to (ice-9 atomic)

[Andrew Tropin]

[-- Attachment #1: Type: text/plain, Size: 3573 bytes --]

On 2023-08-22 19:51, Maxime Devos wrote:

> Op 22-08-2023 om 12:59 schreef Andrew Tropin:
>> 
>> * module/ice-9/atomic.scm (atomic-box-update!): New variable.
>> ---
>> Changes since v1. Use single-argument proc to avoid potential perfomance
>> problems cause of call to apply.
>> 
>>   module/ice-9/atomic.scm | 14 +++++++++++++-
>>   1 file changed, 13 insertions(+), 1 deletion(-)
>> 
>> diff --git a/module/ice-9/atomic.scm b/module/ice-9/atomic.scm
>> index 2a8af901d..6bfa2e8ee 100644
>> --- a/module/ice-9/atomic.scm
>> +++ b/module/ice-9/atomic.scm
>> @@ -25,7 +25,8 @@
>>               atomic-box-ref
>>               atomic-box-set!
>>               atomic-box-swap!
>> -            atomic-box-compare-and-swap!))
>> +            atomic-box-compare-and-swap!
>> +            atomic-box-update!))
>>   
>>   (eval-when (expand load eval)
>>     (load-extension (string-append "libguile-" (effective-version))
>> @@ -36,3 +37,14 @@
>>     (add-interesting-primitive! 'atomic-box-set!)
>>     (add-interesting-primitive! 'atomic-box-swap!)
>>     (add-interesting-primitive! 'atomic-box-compare-and-swap!))
>> +
>> +(define (atomic-box-update! box proc)
>> +  "Atomically updates value of BOX to (PROC BOX-VALUE), returns new
>> +value.
>
> * , returns new value -> and returns the new value
>
> While descriptive works, for consistency with other atomics 
> documentation, this imperative procedure needs to be documented in the 
> imperative mood:
>
> Atomically update the value of BOX to (PROC BOX-VALUE) and return the 
> new value.

Went this way, thank you.

>
> Alternatively, you can adjust the other documentation of atomics to the 
> indicative mood and preserve the original docstring (except for the 
> grammar correction mentioned in the beginning).
>
>    PROC may be called multiple times, and thus PROC should be
>> +free of side effects." > +  (let loop ()
>> +    (let* ((old-value (atomic-box-ref box))
>> +           (new-value (proc old-value)))
>> +      (if (eq? old-value (atomic-box-compare-and-swap! box old-value new-value))
>> +          new-value
>> +          (loop)))))
>
> This can be optimised, by using the return value of CAS as the new old 
> value instead of calling atomic-box-ref again:
>
> (let loop ((old-value (atomic-box-ref box)))
>    (let* ((new-value (proc new-value))
>           (new-old-value (atomic-box-compare-and-swap! box old-value 
> new-value)))
>      (if (eq? new-old-value old-value)
>          new-value
>          (loop new-old-value))))

Make sense, updated the implementation.

> Maybe there is some concurrency weirdness that can cause slower 
> iterations to reduce the number of iterations (*); I'm assuming this 
> isn't the case here.  But if it is, in fact, the case here, and the goal 
> is to exploit this effect, I would think it's better to explicitly 
> implement the back-off.
>
> (I haven't benchmarked any of this, I'm purely going by the number of 
> operations.)
>
> (*) E.g., from Wikipedia: 
> https://en.wikipedia.org/w/index.php?title=Compare-and-swap&oldid=1141385700
>
> [...] Instead of immediately retrying after a CAS operation fails, 
> researchers have found that total system performance can be improved in 
> multiprocessor systems—where many threads constantly update some 
> particular shared variable—if threads that see their CAS fail use 
> exponential backoff—in other words, wait a little before retrying the 
> CAS.[4]

Sent v3.

-- 
Best regards,
Andrew Tropin

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 832 bytes --]

[PATCH v4] Add atomic-box-update! function to (ice-9 atomic)

[Andrew Tropin]

* module/ice-9/atomic.scm (atomic-box-update!): New variable.
---
Oops, v3 was incomplete, sending a new version.

Changes since v3:
Removed stale proc-args.

 module/ice-9/atomic.scm | 14 +++++++++++++-
 1 file changed, 13 insertions(+), 1 deletion(-)

diff --git a/module/ice-9/atomic.scm b/module/ice-9/atomic.scm
index 2a8af901d..c9d49112c 100644
--- a/module/ice-9/atomic.scm
+++ b/module/ice-9/atomic.scm
@@ -25,7 +25,8 @@
             atomic-box-ref
             atomic-box-set!
             atomic-box-swap!
-            atomic-box-compare-and-swap!))
+            atomic-box-compare-and-swap!
+            atomic-box-update!))
 
 (eval-when (expand load eval)
   (load-extension (string-append "libguile-" (effective-version))
@@ -36,3 +37,14 @@
   (add-interesting-primitive! 'atomic-box-set!)
   (add-interesting-primitive! 'atomic-box-swap!)
   (add-interesting-primitive! 'atomic-box-compare-and-swap!))
+
+(define (atomic-box-update! box proc)
+  "Atomically update the value of BOX to (PROC BOX-VALUE) and return the
+new value.  PROC may be called multiple times, and thus PROC should be
+free of side effects."
+  (let loop ((old-value (atomic-box-ref box)))
+    (let* ((new-value (proc old-value))
+           (cas-value (atomic-box-compare-and-swap! box old-value new-value)))
+      (if (eq? old-value cas-value)
+          new-value
+          (loop cas-value)))))
-- 
2.41.0