5 ms·

One time someone posted a "concurrency challenge", and I spent a couple minutes typing out the STM calls that solved it. They balked, for some combination of: t

One time someone posted a "concurrency challenge", and I spent a couple minutes typing out the STM calls that solved it. They balked, for some combination of: that doesn't work in C++, you're not really following the spirit of the challenge, etc. Later they posted a 100+ line solution using condition variables. Lesson: the "real requirements" typically include that the solution doesn't require learning anything new or weird.

mpweiher 10y ago
Yes, that is true, and I sympathize, I am also often in the position of having a solution that is simpler than seems possible to the "less enlightened". However, "real requirements" often do include relevant things that aren't stated. I don't know if this was the case here, but "concurrency" is often something you need because of "performance", and so a Haskell STM solution may not be what your C++ hacker is looking for. The prime example of this is the Haskell "Quicksort" implementation, which is, of course, not actually quick and only vaguely related to the idea of Quicksort. Another example was SPJ's talk about parallel programming in Haskell, where the result was that a 6 core Haskell version was equivalent to a single core C solution. In the same talk he also boasted that "this is only possible with Haskell", to which an audience member replied that the HPC community had been doing this for well over a decade with FORTRAN. The problem with the FP community is that there is so much of the latter examples going on that the true cases of the former tend to be less believable.
- dualogy 10y ago
  > The prime example of this is the Haskell "Quicksort" implementation, which is, of course, not actually quick and only vaguely related to the idea of Quicksort. Yeah but at least it's lazy! ;) If you only ask to (sort) because from the result you're going to (take) the say 4 (smallest/latest/whatever-est), it'll only just sort-enough to give you these 4 sorted, unneeded values being discarded (usually) partially unsorted --- no matter the size of the total. (Still, there may no doubt well be better quicksorts for Haskell out there..) Of course you can write this sort of specific short-cutting in any language manually, but with lazy-evaluation it's just the standard behaviour for any naive `(take 4 (sortBy mysorter mydata))`-type expression. (Takeaway regarding "quick" above: everything regarding performance and efficiency in lazily-evaluated pure functional languages depends to a large degree on the current live data; predictability gets harder here consequently.)
  - mpweiher 10y ago
    > Yeah but at least it's lazy! ;) ;) Yeah, except that the overhead of lazy is often (usually?) more than the "overhead" of doing the whole computation eagerly. > just sort-enough to give you these 4 sorted And how is that going to work in a sort? The 4 first elements can be located anywhere and have to brought into position. There are "first k of n" algorithms, but these are (last I checked) quite different from generic sorting algorithms, and I doubt that a lazy sort in Haskell actually magically turns into one of those algorithms. Happy to be proved wrong!
    - fmap 10y ago
      Well, you do get an (expected time) asymptotically efficient algorithm for sorting the first k elements of an array by running quicksort without recursing on the last n-k elements. This is what you get in Haskell with "take k (sort xs)". But, as you mentioned the constant factors involved are ridiculously high and this is not going to give you a practical solution.
- copx 10y ago
  > Another example was SPJ's talk about parallel programming in Haskell, where the result was that a 6 core Haskell version was equivalent to a single core C solution. Reminds me of a Rich Hickey talk were he proudly declared that a Clojure solution based on its persistent vector type running on four cores was as fast as the Java/mutable vector solution running on one! The point there was supposed to be that Clojure's inefficiency is more than counterbalanced by the fact that it makes writing parallel code easier. I was not convinced, though. > In the same talk he also boasted that "this is only possible with Haskell", to which an audience member replied that the HPC community had been doing this for well over a decade with FORTRAN. The FP advocates always seem to use examples which show non-interactive processing of "embarrassingly parallel" vector data. And yes, that is trivial in any language. Even in C land all you need to do is to add one keyword / annotation to your for-loop and you are good.
  - nickpsecurity 10y ago
    Case in point: https://en.wikipedia.org/wiki/Cilk https://en.wikipedia.org/wiki/Cilk
- eklavya 10y ago
  I was under the impression that STM, being an opportunistic (success biased) concurrency primitive, was faster than explicit locking. Isn't it more performant? I remember I saw in a talk given where in that benchmark STM was as fast as no locking at all !
davidtgoldblatt 10y ago
Hah, I think I'm that person you're referring to. I would characterize my response differently. Stripping out the specifics, the problem was: "write some code that blocks until one of a set of memory locations changes its value". The Haskell/STM API provides exactly that interface (where the memory locations you block on are those that you looked at in the transaction). Rephrasing then, the question was "how would you implement a simplified version of the Haskell STM blocking mechanism?", and your solution was "I would use the Haskell STM blocking mechanism", answering the question as though it were one of API usage rather than of API implementation. That's probably fine as a question of workaday engineering (and maybe an argument for Haskell over C++ on the basis that it has more extensive libraries built-in), but somebody's gotta write that STM implementation, and that's what the challenge was trying to get at. (In fact, the GHC STM implementation does exactly what the solution I outlined does: with each TVar, it keeps a pointer to threads parked waiting for the TVar's value to change, and unparks all those threads when a transaction modifying the TVar commits).
- oconnore 10y ago
  Fair. Sorry for misrepresenting you.

mpweiher 10y ago

Yes, that is true, and I sympathize, I am also often in the position of having a solution that is simpler than seems possible to the "less enlightened". However, "real requirements" often do include relevant things that aren't stated. I don't know if this was the case here, but "concurrency" is often something you need because of "performance", and so a Haskell STM solution may not be what your C++ hacker is looking for. The prime example of this is the Haskell "Quicksort" implementation, which is, of course, not actually quick and only vaguely related to the idea of Quicksort. Another example was SPJ's talk about parallel programming in Haskell, where the result was that a 6 core Haskell version was equivalent to a single core C solution. In the same talk he also boasted that "this is only possible with Haskell", to which an audience member replied that the HPC community had been doing this for well over a decade with FORTRAN. The problem with the FP community is that there is so much of the latter examples going on that the true cases of the former tend to be less believable.

dualogy 10y ago
> The prime example of this is the Haskell "Quicksort" implementation, which is, of course, not actually quick and only vaguely related to the idea of Quicksort. Yeah but at least it's lazy! ;) If you only ask to (sort) because from the result you're going to (take) the say 4 (smallest/latest/whatever-est), it'll only just sort-enough to give you these 4 sorted, unneeded values being discarded (usually) partially unsorted --- no matter the size of the total. (Still, there may no doubt well be better quicksorts for Haskell out there..) Of course you can write this sort of specific short-cutting in any language manually, but with lazy-evaluation it's just the standard behaviour for any naive `(take 4 (sortBy mysorter mydata))`-type expression. (Takeaway regarding "quick" above: everything regarding performance and efficiency in lazily-evaluated pure functional languages depends to a large degree on the current live data; predictability gets harder here consequently.)
- mpweiher 10y ago
  > Yeah but at least it's lazy! ;) ;) Yeah, except that the overhead of lazy is often (usually?) more than the "overhead" of doing the whole computation eagerly. > just sort-enough to give you these 4 sorted And how is that going to work in a sort? The 4 first elements can be located anywhere and have to brought into position. There are "first k of n" algorithms, but these are (last I checked) quite different from generic sorting algorithms, and I doubt that a lazy sort in Haskell actually magically turns into one of those algorithms. Happy to be proved wrong!
  - fmap 10y ago
    Well, you do get an (expected time) asymptotically efficient algorithm for sorting the first k elements of an array by running quicksort without recursing on the last n-k elements. This is what you get in Haskell with "take k (sort xs)". But, as you mentioned the constant factors involved are ridiculously high and this is not going to give you a practical solution.
copx 10y ago
> Another example was SPJ's talk about parallel programming in Haskell, where the result was that a 6 core Haskell version was equivalent to a single core C solution. Reminds me of a Rich Hickey talk were he proudly declared that a Clojure solution based on its persistent vector type running on four cores was as fast as the Java/mutable vector solution running on one! The point there was supposed to be that Clojure's inefficiency is more than counterbalanced by the fact that it makes writing parallel code easier. I was not convinced, though. > In the same talk he also boasted that "this is only possible with Haskell", to which an audience member replied that the HPC community had been doing this for well over a decade with FORTRAN. The FP advocates always seem to use examples which show non-interactive processing of "embarrassingly parallel" vector data. And yes, that is trivial in any language. Even in C land all you need to do is to add one keyword / annotation to your for-loop and you are good.
- nickpsecurity 10y ago
  Case in point: https://en.wikipedia.org/wiki/Cilk https://en.wikipedia.org/wiki/Cilk
eklavya 10y ago
I was under the impression that STM, being an opportunistic (success biased) concurrency primitive, was faster than explicit locking. Isn't it more performant? I remember I saw in a talk given where in that benchmark STM was as fast as no locking at all !

davidtgoldblatt 10y ago

Hah, I think I'm that person you're referring to. I would characterize my response differently. Stripping out the specifics, the problem was: "write some code that blocks until one of a set of memory locations changes its value". The Haskell/STM API provides exactly that interface (where the memory locations you block on are those that you looked at in the transaction). Rephrasing then, the question was "how would you implement a simplified version of the Haskell STM blocking mechanism?", and your solution was "I would use the Haskell STM blocking mechanism", answering the question as though it were one of API usage rather than of API implementation. That's probably fine as a question of workaday engineering (and maybe an argument for Haskell over C++ on the basis that it has more extensive libraries built-in), but somebody's gotta write that STM implementation, and that's what the challenge was trying to get at. (In fact, the GHC STM implementation does exactly what the solution I outlined does: with each TVar, it keeps a pointer to threads parked waiting for the TVar's value to change, and unparks all those threads when a transaction modifying the TVar commits).

oconnore 10y ago
Fair. Sorry for misrepresenting you.