1. 2

    I love this entire series. If you haven’t read the first 2 parts, I’d recommend.

    1. 1

      Thank you for the kind words, Sean!

    1. 3

      Interesting to see a more modern Java concurrency approach compared to what I remember from The Art of Multiprocessor Programming.

      What wasn’t clear to me on reading is how the example Atom satisfies the property stated by the author:

      Every operation will succeed after the finite number of tries

      For example, two threads could execute the swap function.

      Thread 1            Thread 2
      =======================================
      oldv = get()
                          oldv = get()
                          newv = swapOp(old)
                          cas(oldv, newv)
      newv = swapOp(old)
      cas(oldv, newv)
      oldv = get()
                          oldv = get()
                          newv = swapOp(old)
                          cas(oldv, newv)
                    ...
      

      If this repeats infinitely then thread 1’s swap never succeeds. Did I miss something? I’m never too confident of pen-and-pencil proofs of concurrent programs.

      What I always thought was a subtle design challenge for concurrent data structures is that you can have “bugs” in your API. For example, if you expose a read() operation and a write() operation on your lock-free data-structure then you open the user to do something like:

      if (read()) {
         write()
      }
      

      Allowing an atomicity violation to creep in.

      1. 1

        the only exit condition from swap is a successful swap, so it has to succeed: there’s a for loop out there. This is pretty much the whole point of Atoms: to allow async swaps using the unary function.

        If you want more guarantees, you can add a counter and make sure you exit after a certain amount of retries.

        As regards API design: you’re absolutely right. It’s always hard. Luckily, Atom doesn’t have this problem, since old value is always explicitly passed, and it’s user’s responsibility to make sure he doesn’t leak the modifiable state.

        1. 1

          Yeah, the author is not terribly precise here. My impression is that lock-free algorithms guarantee over-all system progress, but won’t prevent per-thread starvation. As you’ve noticed, an Atom can always starve–in particular, optimistic concurrency often does poorly under extremely high concurrency, as many threads may do work simultaneously, but only one will have its work actually be used.

          I think one possible next step from using AtomicRefs together is something like STM, where you can combine several separate atomic operations into a single larger atomic operation. I’ve heard mixed things about how well it performs in general though, so I’m not sure that it’s the next step.

          1. 1

            All the JVM-based implementations of STM that I have seen so far are using lots of locks internally, so wouldn’t say it’s a progressing step against contention.

            Although what could help is to design a system the way all the writes are going through the single writer.

            1. 2

              Locks don’t necessarily mean you suffer more from contention. If you are contended the vast majority of the time, programming with locks can be much faster than optimistic locking. In this way, programming with locks can ensure much higher throughput.

              Well, if we’re really looking at implementations, java compare and swap uses LOCK before CMPXCHG on x86, so we are all sinners. I think correct implementations of STM, even if they rely on locks eventually, can’t run into deadlocks, and are guaranteed to always make system-wide progress.

              Note that lock-freedom doesn’t mean you can’t use locks, it just means that at least one thread must always be able to make progress, even if individual threads starve.

              Single-threading your writes is OK if you don’t have to do a lot of writes, but it’s in no way a silver bullet, and can add latency unnecessarily, especially since you need to do locked bus traffic anyway if you want to read safely.

        1. 5

          As somebody that loses hours per workday to fixing problems related to not having types, I am going to disagree, language is important.

          The author of the post tried to dive into learning Haskell without asking for help or doing any exercises by writing a time series database. I asked him to at least try asking a question on the mailing list because I believed he’d get good help there, he refused to even try. His attitude was that either he could it without help or he couldn’t do it.

          I have to wonder if modern civilization (bridges, video games, clean water) would exist if everybody had that attitude.

          This is a pretty typical flame-out that occurs when you attempt a complicated project without having learnt the language first. This article is me exactly 3 years ago, after having attempted similar without having learnt Haskell first.

          You have to humble yourself, do the work, learn the language. Then tackle a project.

          1. 21

            @bitemyapp

            I didn’t want to post anything like that into the blog post, but since you’ve started going personal, I have to defend myself.

            a) when I have started, I was searching for help. But since the most basic concepts were rather clear for me, I was left all by myself in majority of times. I can bring up all the occurrences of myself asking questions about things like thunk leaks, about monadic order swapping. How many times they were answered? Correct, zero.

            Once a very kind person helped me to understand Monadic Transformers. I will never forget his kindness.

            b) I refuse to try posting things to the mailing lists because there were multiple times when people from Haskell community were responding my questions with simple “this is Functorial, everyone should know that”, or “you should be smart enough to figure that out” and other humbling things.

            c) There is a false assumption that I am having problems with Haskell. I do not have any problems with Haskell. Assuming that if other people do not like something, they automatically do not know something is false and misleading. I’m saying that Haskell will take a long time to learn. I did learn it (read several books, and caught up on theory), and I have no problem programming it.

            I have to wonder if modern civilization (bridges, video games, clean water) would exist if everybody had that attitude.

            This is exactly the point I had. You say that Haskell is “next level”. I say no. There’s absolutely nothing special about Haskell. And we all should live with it.

            It’s very easy to say what I’ve done was a recipe for failure: https://twitter.com/bitemyapp/status/541962675488452608 Although I can’t say it’s a failure due to two reasons:

            • I’m still writing the DB, and in Haskell
            • I’ve learned a bunch of stuff, including how to profile Haskell apps, hunting thunk-leaks, crafted FFI tutorial that has already helped a lot of people, and contributed 2 patches to GHC.

            As for me, even if I had to drop the DB itself it was a success.

            1. 7

              I think that his tone is positive in the sense that one has to know how an algorithm works in order to be able to implement it in any language for example.

              I do not think that he disagrees that learning the language itself is important since there are languages that allow certain algorithms to be implemented nicely and others that do not. However the true beauty of functional languages is how closely they are related to the abstract concepts behind commonplace constructs we use in different (even imperative) languages.

              In that case, languages like Haskell are in an advantage respect to languages that are more clumsy in their functional characteristics, so yes, the language is important in that respect. But the notions behind what you do are more important in order to use it efficiently.

              1. 3

                That was exactly what i have originally intended to say :)