# Notes on lock-free programming
**URL:** https://discourse.julialang.org/t/notes-on-lock-free-programming/61510
**Category:** Teaching & Outreach
**Created:** [May 20, 2021, 12:18pm UTC](https://discourse.julialang.org/t/notes-on-lock-free-programming/61510 "2021-05-20T12:18:07Z")
**Posts on this page:** 7
**Page:** 1
### Author:  [@eaubanel](https://discourse.julialang.org/u/eaubanel)
#### Post date: [May 20, 2021, 12:18pm UTC](https://discourse.julialang.org/t/notes-on-lock-free-programming/61510/1 "2021-05-20T12:18:07Z")
I used Julia as the language in my intro to parallel computing course this year, and it went quite well. Over the past year I’ve created some [notes on Julia parallel computing topics](http://cs.unb.ca/~aubanel/), which may be of interest to the community. The latest are [Notes on Lock-Free Programming with Atomics with Julia](http://www.cs.unb.ca/~aubanel/JuliaLockFreeBelmanFord.html) and [Notes on Distributed Parallel Computing with Julia](http://www.cs.unb.ca/~aubanel/JuliaDistributedParallelNotes.html).
---
### Author:  [@carstenbauer](https://discourse.julialang.org/u/carstenbauer)
#### Post date: [May 20, 2021, 1:20pm UTC](https://discourse.julialang.org/t/notes-on-lock-free-programming/61510/2 "2021-05-20T13:20:53Z")
Thanks for sharing!
When can we expect a Julia-version of your Elements of Parallel Programming book? 😁
---
### Author:  [@eaubanel](https://discourse.julialang.org/u/eaubanel)
#### Post date: [May 20, 2021, 7:13pm UTC](https://discourse.julialang.org/t/notes-on-lock-free-programming/61510/3 "2021-05-20T19:13:07Z")
My book is language-neutral, and uses pseudocode. I’ll have to start adding Julia implementations to the book’s github site.
---
### Author:  [@tkf](https://discourse.julialang.org/u/tkf)
#### Post date: [May 20, 2021, 9:03pm UTC](https://discourse.julialang.org/t/notes-on-lock-free-programming/61510/4 "2021-05-20T21:03:28Z")
I only skimmed the code, so I apologise if I missed something. But I find the line `atomic_min!(D[j], D[i][] + g.weights[j,i]) > D[j][]` in the parallel `relax` function very tricky because I suspect the following scenario is possible
```julia
lhs1 = atomic_min!(D[j], D[i1][] + g.weights[j,i1]) # thread 1 (no update)
lhs2 = atomic_min!(D[j], D[i2][] + g.weights[j,i2]) # thread 2 (updated)
rhs1 = D[j][] # thread 1
lhs1 > rhs1 # thread 1
```
That is to say, `>` evaluates to `true` in thread 1 since thread 2 updates `D[j]` in the middle.
My guess is that it’s still OK since all that matters is if `j` is in the list or not ? Maybe you discussed this in your book or consider it obvious for the readers at this stage, but I wonder if it makes sense to add a quick note for the correctness argument of the lock-free algorithm.
(I’d also suggest non-atomics approach for `subList` accumulation, but maybe that’s not the theme of this chapter.)
---
### Author:  [@eaubanel](https://discourse.julialang.org/u/eaubanel)
#### Post date: [May 21, 2021, 12:44pm UTC](https://discourse.julialang.org/t/notes-on-lock-free-programming/61510/5 "2021-05-21T12:44:43Z")
You’re correct that this scenario doesn’t matter; what matters is that D[j] is updated atomically, and that j is inserted in a thread’s list once. Your comments make me think that I will expand the discussion to examine different thread orderings. As far as `subList` accumulation, that is already being done without atomics, however the atomic\_cas is needed for updating `inList` to ensure all accesses are atomic.
---
### Author:  [@tkf](https://discourse.julialang.org/u/tkf)
#### Post date: [May 21, 2021, 9:32pm UTC](https://discourse.julialang.org/t/notes-on-lock-free-programming/61510/6 "2021-05-21T21:32:25Z")
Thanks for the confirmation. Yes, it’d be nice if non-trivial uses (e.g., not just incrementing a single counter) of atomics come with some discussion on its correctness.
> [@eaubanel](#):
>
> As far as `subList` accumulation, that is already being done without atomics, however the atomic\_cas is needed for updating `inList` to ensure all accesses are atomic.
IIUC, the `relax` algorithm is essentially `mapreduce(j -> Set([j]), union!, indices)` fused with filtering based on `atomic_min!(D[j], D[i][] + g.weights[j,i]) > D[j][]`. Since `reduce` can be done without atomics, there is no need to use `atomic_cas!` in principle. But the performance depends on how much contention the algorithm has on `InList[j]` and it’s conceivable that `atomic_cas!` is useful in algorithms like this.
---
### Author:  [@eaubanel](https://discourse.julialang.org/u/eaubanel)
#### Post date: [May 27, 2021, 1:08pm UTC](https://discourse.julialang.org/t/notes-on-lock-free-programming/61510/7 "2021-05-27T13:08:25Z")
I’ve updated the webpage to include a more detailed discussion of atomic\_min and atomic\_cas, and also to discuss the point you raised, @tkf, about the comparison `atomic_min!(D[j], D[i][] + g.weights[j,i]) > D[j][]` not being atomic.