Concurrency in Haskell: Fast, Simple, Correct

https://bitbashing.io/haskell-concurrency.html

by ingve • 1 year ago

193 122 1 year ago

It's maybe interesting to note that the `async` library in use here is very simple and easy to understand. Nearly every function is one or two lines. Likewise `TQueue` is extremely simple (and easy to prove correct) thanks to STM, and also generally has good performance.

zozbot2342• 1 year ago

A lot of the complexity here is just hidden in Haskell's runtime, which implements async processing based on green threads, besides other features such as GC. Though to be fair, the software transactional memory (STM) featureset is quite unique to Haskell since it relies on the availability of pure functions to ensure correctness. It's kind of hard to imagine a full equivalent to it in other well-known languages.

juliangamble• 1 year ago

Quibble: Both Clojure and Scala have a Software Transactional Memory implementation, and the original Clojure Ant demo showed this.

mikojan• 1 year ago

In another life I will be a Haskell programmer

Avicebron• 1 year ago

Yeah me too, I'll invest in bitcoin early, live like a hermit off a coast somewhere, and school kids on HN, "cabal hell! I'll scream, no, Conda hell with powershell hooks in vscode you ingrates, my llm"

revskill2• 1 year ago

Why not python ?

linguae• 1 year ago

I’m not the OP, but static types, Hindley-Milner type inference, algebraic data types, and pattern matching can be quite ergonomic. I have also come to appreciate functional programming and how it makes reasoning about and testing code easier.

tasuki5• 1 year ago

No one wants to be a python programmer. It's a practical language to get things done. It isn't a language to make you feel proud of yourself nor about the current state of our industry.

whateveracct7• 1 year ago

It's a lot of fun!

runeks• 1 year ago

I fear that in another life I will be a JavaScript programmer

kreetx• 1 year ago

Choose this life instead!

cosmic_quanta5• 1 year ago

There's no time like the present. Feel free to reach out if I can help you along your journey

tasuki5• 1 year ago

Not the person you're replying to, but I'll bite:

I've written low thousands of lines of Haskell. Similar to mikojan, I love Haskell in theory, but ended up not enjoying it as much in practice.

1. The multitude of string-y types. I end up converting between String, Text, Lazy Text, ByteString, Lazy ByteString, and I forget what else. Each library wants me to pass in a specific string type, and each other library returns a different string type. LLMs are good at this, also for a while I had a ton of helper functions to convert between any two string types. Still, perhaps there's a better way?

2. The error messages. I come from Elm, so I'm spoiled. Yes, I understand a language with HKTs will never have as nice error messages. Yes, LLMs are pretty good at explaining GHC error messages.

3. The stdlib. Haskell gets a lot of credit for safety, but a `head` blows up instead of returning a `Maybe`. I know there are other - safer - preludes, but I don't know how to choose between them. I don't know how using a different prelude would impact my projects.

I feel like my next step is either towards Idris, with its polished standard library (and dependent types baked into the language!), or towards something simpler and more Elm-like (Gleam perhaps, or Roc). But if you can sell me on Haskell, I'm all ears!

ilrwbwrkhv• 1 year ago

Rust has a bunch of these while being maintainable.

whateveracct7• 1 year ago

What about Haskell concurrency isn't maintainable?

The concurrency stuff in the stdlib + the mainstays in the ecosystem are pretty stable and noncontroversial..there's stuff in Haskell that churn but this is not one of them.

mrkeen9• 1 year ago

STM is Haskell's feature for safe shared&mutable state.

What is Rust's feature for safe shared&mutable state?

speed_spread2• 1 year ago

That would be Arc<Mutex<T>>, which works but is no STM.

zozbot2342• 1 year ago

Relevant: https://github.com/Marthog/rust-stm which has usage instructions. It's memory safe as defined in Safe Rust, but unlike the Haskell implementation it's not "safe" in a correctness sense, because Rust does not afford the same control about mutability and purity. (At least, not yet - future additions to the language may improve this somewhat.)

ykonstant• 1 year ago

Isn't concurrency in Rust a notorious pain point? Or am I confusing it with async which is different? [I am stuck in an era before parallelism, so I don't really understand these things]

mrkeen9• 1 year ago

This why I haven't fully embraced Rust yet. Whenever I ask about safely mutating shared state (see sibling comment), I'm met with silence, or some comment like: Rust guarantees that you aren't mutating shared state.

speed_spread2• 1 year ago

Correctness in concurrency is actually one of Rust's strong suit. Any pain felt is because Rust is low level and does not prescribe a single concurrency mechanism, leaving each coder to figure out the benefits and constraints of each library.

butterisgood4• 1 year ago

Rust is nearly the answer if anyone understood the question.

FuckButtons• 1 year ago

I thought it was a bit odd that the author claims there’s no mutexes in sight, the TVar is effectively a mutex guard unless I’m misunderstanding this? (I’ve written exactly 0 lines of Haskel). Or is the claim that the lack of ceremony and accidental complexity around threading is the real win for concurrency here?

chongli• 1 year ago

No, a TVar is not a mutex guard. A TVar is a software transactional memory (STM) variable. STM works just like a database: you batch together a sequence of operations into a transaction and then execute them. During execution of a transaction, all changes made to the contents of the TVar are stored in a transaction log. If some other transaction occurs during the execution then the whole thing is aborted and re-run.

This can take any ordinary Haskell data structure and give you a lock-free concurrent data structure with easy-to-use transactional semantics. How it performs is another matter! That depends on the amount of contention and the cost of re-playing transactions.

whateveracct7• 1 year ago

https://hackage.haskell.org/package/stm-containers

This library is full of STM-oriented data structures. They perform better than a simple `TVar (Map k v)`.

It's kind of a fun trick actually. The stock Map is just a tree. The STM Map is also a tree [1] but with TVars at each node. So this helps a lot with contention - you only contend along a "spine" instead of across the whole tree, which is O(log n).

[1] Technically a HAMT a la unordered-containers - trie, tree, you get the idea :)

quibono• 1 year ago

How it performs is another matter!

I know you say it depends on how much contention one sees but I'm interested in the performance hit. Also, is STM the "standard" (or accepted) way to do async in Haskell?

dsign• 1 year ago

You are correct, Haskell has quite a few mutex-like types. MVar is one of them.

However, if memory serves me right, TVar is a building block for the transactional memory subsystem. The guard on TVar with, say, modifyTVar is not really stopping execution at entrance but simply indicating that the block modifies the variable. In my mental model, some magic happens in an STM block that checks if two concurrent STM blocks acted upon the same data at the same time, and if so, it reverts the computations of one of the blocks and repeats them with new data.

To my knowledge, Haskell is the only programming language (+runtime) that has a working transactional memory subsystem. It has been in the language for about 20 years, and in that time many have tried (and failed) to also implement STM.

dionian2• 1 year ago

https://zio.dev/reference/stm/

whateveracct7• 1 year ago

I think Clojure has some kind of STM too?

Haskell's STM is pretty world-class though. That's fair to say :)

dwohnitmok4• 1 year ago

No a TVar isn't a mutex guard. As a sibling comment points out it gives you transactional semantics similar to most relational databases.

Here's an example in perhaps more familiar pseudocode.

  var x = "y is greater than 0"
  var y = 1
  
  forkAndRun {() =>
    y = y - 1
    if (y <= 0) {
      x = "y is less than or equal to 0"
    }
  }
  
  forkAndRun {() =>
    y = y + 1
    if (y > 0) {
      x = "y is greater than 0"
    }
  }

In the above example, it's perfectly possible, depending on how the forked code blocks interact with each other, to end up with

  x = "y is less than or equal to 0"
  y = 1

because we have no guarantee of atomicity/transactionality in what runs within the `forkAndRun` blocks.

The equivalent of what that Haskell code is doing is replacing `var` with a new keyword `transactional_var` and introducing another keyword `atomically` such that we can do

  transactional_var x = "y is greater than 0"
  transactional_var y = 1
  
  forkAndRun {
    atomically {() =>
      y = y - 1
      if (y <= 0) {
        x = "y is less than or equal to 0"
      }
    }
  }
  
  forkAndRun {
    atomically {() =>
      y = y + 1
      if (y > 0) {
        x = "y is greater than 0"
      }
    }
  }

and never end up with a scenario where `x` and `y` disagree with each other, because all their actions are done atomically together and `x` and `y` are specifically marked so that in an atomic block all changes to the variables either happen together or are all rolled back together (and tried again), just like in a database.

`transactional_var` is the equivalent of a `TVar` and `atomically` is just `atommically`.

mrkeen9• 1 year ago

Mutexes lock code, TVars lock data.

If you lock a section of code (to protect data), there's no guarantee against mutations of that data from other sections of code.

If you lock the data itself, you can freely pass it around and anyone can operate on it concurrently (and reason about it as if it were single-threaded).

It's the same approach as a transactional database, where you share one gigantic bucket of mutable state with many callers, yet no-one has to put acquire/release/synchronise into their SQL statements.

ghusbands• 1 year ago

As siblings note, TVar is a transactional variable. However, it's not just protective against concurrent writes but also against concurrent reads of altered variables, so it offers true atomicity across any accessed state in a transaction.

So if you have a thread altering `foo` and checking that `foo+bar` isn't greater than 5 and a thread altering `bar` and checking the same, then it's guaranteed that `foo+bar` does not exceed 5. Whereas if only write conflicts were detected (as is default with most databases) then `foo+bar` could end up greater than 5 through parallel changes.

jes5199• 1 year ago

I love Haskell because I can write provably correct code that still doesn’t work

declan_roberts• 1 year ago

I love it because I can spend all my time noodling over types and never ship a product that would have been great shipped in a late night wine-fueled session of 1999 PHP.

anonzzzies• 1 year ago

Now you would vibe it and ship it during the ol' drink.

kqr2• 1 year ago

If that is what you want to do, you can do that in any language. It's just that when you do it in e.g. Java, you have to spend a lot longer proving correctness before discovering that it doesn't work.

jiggawatts2• 1 year ago

A Haskell quote I like is: “I’ve only proven this correct, I haven’t tried it.”

neilwilson• 1 year ago

Isn’t that one of Dijkstra’s supposed comments?

michalsustr3• 1 year ago

I’m not familiar with Haskell concurrency. The combination of green threads and large memory allocations due to immutable data structures sounds like it would be hard to implement a web server handling 10k+ concurrent requests on commodity hardware?

Btw. too bad author talks about microsecond guarantees usage but does not provide a link, that would be interesting reading.

eru6• 1 year ago

[...] large memory allocations due to immutable data structures sounds [...]

Why would there be large memory allocations because of immutable data structures? Btw, you can also use immutable data structure in eg Rust fairly easily. And Haskell also supports mutation and mutable data structures.

However, Haskell can use a lot of memory, but that's more to do with pervasive 'boxing' by default, and perhaps laziness.

nesarkvechnep3• 1 year ago

No reason. OC probably thinks that immutable data structures are always copied when being operated on.

stevan• 1 year ago

Warp is a high-performance HTTP server library written in Haskell, a purely functional programming language. Both Yesod, a web application framework, and mighty, an HTTP server, are implemented over Warp. According to our throughput benchmark, mighty provides performance on a par with nginx.

Source: https://aosabook.org/en/posa/warp.html

nesarkvechnep3• 1 year ago

You obviously haven’t ran anything on the BEAM (Erlang’s VM).

michalsustr3• 1 year ago

Correct. Erlang also uses green threads?

lemper• 1 year ago

nah bro, warp is quite performant. think there were some consultancies that wrote haskal web app for their clients.

_jackdk_2• 1 year ago

The interaction of laziness and purity means that the memory costs are not always what you think. Purity means that it's a lot safer to share structure between old and new versions of a data structure where an imperative language would have to do defensive copying, and laziness means that you can incrementally amortise the cost of expensive rebalancing operations (Okasaki is the standard reference for this).

cosmic_quanta5• 1 year ago

sounds like it would be hard to implement a web server handling 10k+ concurrent requests on commodity hardware?

In practice, it is not. The canonical Haskell compiler, GHC, is excellent at transforming operations on immutable data, as Haskell programs are written, into efficient mutations, at the runtime level. Also, since web development is quite popular in the Haskell community, lots of people have spent many hours optimizing this precise use-case.

In my experience, the real downside is that compilation times are a bit long -- the compiler is doing a LOT of work after all.

eru6• 1 year ago

The canonical Haskell compiler, GHC, is excellent at transforming operations on immutable data, as Haskell programs are written, into efficient mutations, at the runtime level.

Yes, at the level of native machine code and memory cells, there's not that much of a difference between immutability + garbage collection, and higher level source code that mutates. Thanks to GC you are going to overwrite the same memory locations over and over again, too.

whateveracct7• 1 year ago

It doesn't actually have "large memory allocations" due to immutable data structures. This is a meme that isn't true. Immutable data structures, especially at small scale, do not have huge performance penalties. You don't copy the entire structure over and over...you copy the O(log n) spine.

Haskell's GC is also fast when you are mostly generating garbage, which is inherently true for web server handlers.

butterisgood4• 1 year ago

Deforestation helps with that

A composition of catamorphic and anamorphic functions can eliminate a lot of the in-between allocations (a hylomorphism)

Basically it looks like you’re building a ton of intermediate structure then consuming it - meaning much of the in-between stuff can be eliminated.

Interesting optimizations and a little mind blowing when you see it.

internet_points• 1 year ago

https://www.oreilly.com/library/view/parallel-and-concurrent... is a great resource for those who want to go deeper into this

alatriste• 1 year ago

I read that book many years ago, but I haven't looked into Haskell for a long time. Is it still relevant today? I imagine many things have changed in 12 years!

valcron1000• 1 year ago

The fundamentals are the same, and `async` is as relevant as it was back then. The ecosystem is extremely stable in that regard.

cosmic_quanta5• 1 year ago

The author is thinking of updating the book to a second edition as well. Looking forward to it

ahel• 1 year ago

noice

thih9• 1 year ago

After reading the title I was expecting a "pick two". From my anecdotal experience haskell is usually far from simple, but other configurations are possible too.

wodenokoto• 1 year ago

I don't know how async is in other languages but I find Pythons async incredibly difficult to use, and I kinda feel validated about how poor chatGPT is at it as well.

Is it because it is just a very hard thing, or is it because its a synchronous language, with async bolted on? (I'm talking about a purely language point of view, not from a python VM / GIL point of view)

aeonik• 1 year ago

The easiest language I’ve used for async is Clojure—mostly because the language is immutable by default and ~99% of the code is referentially transparent. That doesn’t magically solve async, but it removes an entire class of headaches by nudging you away from shared state and side effects. You don’t need locks if there’s nothing to lock.

Async is hard, no doubt—but some languages are designed to reduce the surface area of what can go wrong. I’ve heard great things about Erlang, Elixir, and BEAM-based languages in general. They treat async not as an add-on, but as a core architectural principle.

Starlevel004• 1 year ago

It's because ``asyncio`` is a dogwater library that's barely functional and full of footguns. The ecosystem is about the same quality too.

gpderetta• 1 year ago

Indeed, as much as I dislike async in general, asyncio is its own special hell.

_jackdk_2• 1 year ago

From the footnotes:

It gets weirder: in Haskell, exceptions can be thrown to other threads!

What's really interesting is that because of purity, you have to have asynchronous exceptions otherwise you give up a lot of modularity. At least that's what Simons Marlow and Peyton Jones argue in Asynchronous Exceptions in Haskell (2006): https://www.microsoft.com/en-us/research/wp-content/uploads/...

While the semi-asynchronous approach avoids breaking synchronization abstractions, it is non-modular in that the target code must be written to use the signalling mechanism. Worse still (for us), the semi-asynchronous approach is simply incompatible with a purely-functional language, such as Concurrent Haskell. The problem is that polling a global flag is not a functional operation, yet in a Concurrent Haskell program, most of the time is spent in purely-functional code. On the other hand, since there is absolutely no problem with abandoning a purely-functional computation at any point, asynchronous exceptions are safe in a functional setting. In short, in a functional setting, fully-asynchronous exceptions are both necessary and safe — whereas in an imperative context fully-asynchronous exceptions are not the only solution and are unsafe.

If you can read PLTese, it's really quite a nice paper.

kamalhm• 1 year ago

Oh so this could be the inspiration on Virtual Threads and Structured Concurrency in Java

cosmic_quanta5• 1 year ago

My favourite thing about Haskell concurrency is that there are no colored functions [0]. Writing code in IO, or Async, or the next big thing (asychronous higher-order effect system of the future??), doesn't require language support like Python or Rust.

The one construct that unlocks this lack of colored functions, STM, did require runtime support (as opposed to language support), which at least is transparent to downstream developers

[0] https://journal.stuffwithstuff.com/2015/02/01/what-color-is-...

grandempire• 1 year ago

This is also an advantage of blocking code. It’s just regular code. The async stuff is handled by the operating system.

mrkeen9• 1 year ago

Coloured functions are a feature - not a bug, Haskell is full of them, and they are exactly what make STM safe in Haskell, but abandonware in other languages which have tried.

  2. The way you call a function depends on its color.

`<-` or `>>=` vs `=`

  3. You can only call a red function from within another red function.

This should sound pretty familiar! You can only call an IO function from within another IO function. STM in this case makes a third colour:

  IO can call IO functions.
  IO can call STM functions. (*)
  IO can call pure functions.

  STM can call STM functions.
  STM can call pure functions.

  pure functions can call pure functions.

(*) calling into an STM block from IO is what makes it 'happen for real': it's the `atomically` which has type STM a -> IO a.

Having these coloured functions is what made STM achievable back in the mid-late 2000s, since the mechanism to prevent STM or pure functions from calling IO was already in-place.

Other languages either tried to figure out how to contain the side-effects and gave up, or just released STM and put the onus on the user not to use side effects.

UlisesAC4• 1 year ago

It is a shame that the people you are answering is being downvoted, I also understand the importance of coloring functions, but look at the examples that person put, python and rust. In those, executing a colored function (at least the async related ones) propagates up to the top of the program, that is a cost that we have to interiorize, but I would be lying if I told you I wouldn't he happy with such behavior. I do a lot of js/ts and I would love to just be able to "inline" await without making my current scope recursively to the top of the program like it can be done with F# with the Async.StartAsTask operation.

kookamamie2• 1 year ago

1. Compose the program into several threads of execution, traditionally scheduled and ran by the operating system

The step 0 is missing:

Compose the program into several lanes of execution, traditionally executed via SIMD.

This is a massive piece of performance left on the table on modern computer architectures, by assuming threading is the first manifestation of concurrency.

jayd16• 1 year ago

SIMD has been somewhat of a massive failure in this regard. Unlike threads, most languages seem to ignore its existence and abdicate its usage to the sufficiently complex compiler.

I wish there was better author time feedback to the developer on where they're getting such a perf boost. As far as I'm aware there's no popular linting or blue squiggle to guide you in the right direction.

In games it seems like the popular pattern is to rewrite everything entirely in an entity component system framework.

kookamamie2• 1 year ago

Agreed completely. Most auto-vectorization approaches are hit-miss and you still cannot have big-binaries, where instruction set is decided dynamically, trivially.

ISPC comes close, but does come with a learning curve.

thuanao• 1 year ago

Correct? Anyone who has worked with concurrency in Haskell is probably laughing... :)

Haskell's IO type system doesn't model concurrency at all. `IO a` could be a fork and join, an infinite event loop, really anything, it's a black box in terms of "correctness". Better than using JavaScript maybe, but hardly "correct" in any sort of formal, tractable sense.

throwaway17_17• 1 year ago

From the footnotes:

In bare-metal embedded systems or inside the operating system, it’s not unusual to manually break computation into state machines, driven by interrupts.

Although not the topic of TFA, in fact, the footnotes that this is "a whole different ball game." Does anyone have any good source for this aspect of 'low-level'/OS development? I'm more than capable of chasing down sources from a more high level introduction or overview, so anything would be helpful. This concept seems like it may just be a more pragmatic description of embedded/OS development than what I've read previously.

ackfoobar• 1 year ago

"Fast" in title. But I don't see any benchmarks, or discussion on how to reason about the performance of STM code.

Concurrency in Haskell: Fast, Simple, Correct

Related Stories