4 ms·

If you can't make a language fast, make it parallel

44 points by tophercyll 16y ago

malkia 16y ago
Let's face it - it's not the language that is the problem. It would help you, but it would help you only with some percentage of the problems out there. For example - there does not exist a practical language (or design) where you can implement the LZ compression (ZLIB, others) in parallel, so that it gives the same results as the sequential "c" version. It's just that certain algorithms, hence protocols, data structures, standards are not suited for parallel processing that well. Okay, in the first case, maybe you can split the incoming data by 128kb and process each other individually ... but that's not the same - you can't reuse the LZ window. Really the problem is the 13 dwarfs that university folks have identified - 13 stereotypical problems that relate to 99% of what's being done with a programming language - some of the dwarfs are just speedy parallel gnomes, some of them are old slow stubborn, like Gimli from LOTR. http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-183.html http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-18...
- pufuwozu 16y ago
  Isn't Pigz a parallel implementation of gzip which is itself based upon LZ77? http://www.zlib.net/pigz/ http://www.zlib.net/pigz/ Hasn't there been a few parallel implementations of bzip2? http://compression.ca/pbzip2/ http://compression.ca/pbzip2/ http://bzip2smp.sourceforge.net/ http://bzip2smp.sourceforge.net/ I understand that parallelism isn't suited for a lot of algorithms but from what I can tell, there's been heaps of successful work in compression. Could you give us some more information? It would really help me out - I'm doing an undergraduate class where I have to manually make an open-source project parallel. I've been looking into compression algorithms because I thought they were well suited. Please help me out if I'm going down the wrong path!
  - wmf 16y ago
    The key to malkia's strawman is that pigz does not give the same results as the sequential "c" version of gzip. AFAIK gzip is not parallelizable as-is because every symbol depends on the previous symbol; pigz breaks this dependency to get parallelism but gives up a little compression efficiency. In practice this does not matter, which is why LZ is not a good example.
  - astrange 16y ago
    Compression algorithms are poorly suited to parallelism, because they remove everything that isn't a data dependency in the input, and parallelism is nothing but a lack of data dependencies. The trick is to start at the largest chunk possible and go down until you find where they have left in some, uh, non-dependencies - like bzip2 which has independent x*100KB blocks, and video which (usually) has independent frames. You should be able to get 2-4 separate tasks out of that, which is good enough for CPUs.
- wmf 16y ago
  certain algorithms, hence protocols, data structures, standards are not suited for parallel processing that well. Sure, but for problems that can be parallelized you want a language to be able to express that parallelism. That may sound obvious, but many popular languages cannot do it. Let's not just give up on parallelism because it can't be used everywhere.
- kanak 16y ago
  > Let's face it - it's not the language that is the problem. It would help you, but it would help you only with some percentage of the problems out there. Let's not underestimate the help that a language can provide; writing interpreters for languages is almost trivial on a lisp because you can reuse pretty much every piece of machinery on a lisp for your ends. Similarly, there is an entire class of problems that is nearly trivial on prolog that is pretty difficult to get right on other languages simply because prolog makes it easy to express rules and specifications that need to be met. Just look at an implementation of a sudoku solver in prolog and compare it with some other language. I feel that a language designed with concurrency in mind would make it much simpler to write an entire class of problems. These languages are just gaining traction, so we are yet to see bigger and more significant examples. However, the "ants.clj" demo that Rich Hickey has written in Clojure, and some of the erlang demos in Joe Armstrong's book have made me a believer.
j_baker 16y ago
I'm not convinced that parallelism is something that needs support at the language level. The only languages that do this are Go and Erlang (off the top of my head). Others like Clojure and Scala have more support at the standard library level.
- X9 16y ago
  It might not need language level support, but anything to make it easier to leverage is a plus in my book. If the programmer doesn't have to concern themselves with extra parallelism-specific library calls and is still able to write a binary that can take advantage of multiple cores, that seems like a good idea to me.
- swannodette 16y ago
  ? Clojure has deep language support for concurrency - from syntactical constructs to it's core performant immutable data structures.
  - lukev 16y ago
    But the beauty is that because it's a Lisp, it's all implemented in terms of macros - Clojure's complete set of concurrency tools could be written as a library. The only exception is the deref reader macro "@", since Clojure doesn't allow user-defined reader macros by default.
    - kanak 16y ago
      > it's all implemented in terms of macros This is not true at present. The core data structures, and the STM machinery are implemented in java, not as macros.
  - plinkplonk 16y ago
    He probably meant "distributed". Erlang has a better "distributed" story than Clojure.
- jerf 16y ago
  Erlang gets a lot of good mileage out of it, though. You start to really miss the OTP system when you try to write actually-important code in any other language. And there are some aspects that are hard to get right at a later time when it's not in the language from day one, cross-process messaging in particular, which is a primitive used to build a lot of other features. I do not know where Clojure or Scala have a generic cross-process messaging ability, and I'm not saying it's impossible by any means, but it's much easier if you start from scratch with that in mind.
adamb 16y ago
It's worth noting we (the team that's building Skynet) didn't set out to build a parallel language, we set out to build a distributed one. It turns out that a lot of the things that make Spin a good distributed language also make it a good parallel one.
- philwelch 16y ago
  Yes, that's the story behind Erlang as well.
deleted 16y ago
[deleted]
nivertech 16y ago
tophercyll, can you give an invite to skynet? Nice blog post, but you need to give references/links for Spin and Skynet. Otherwise it's just an ad trick...
- tophercyll 16y ago
  Hi nivertech, I'm sharing one of the lessons we learned building our own programming language. I love how many language designers there are on HN! We're working on an invite system, so everyone can benefit from Skynet! Skynet is better when you use it with others, so the invites will work for groups of friends.
nivertech 16y ago
My favorite features of Erlang/OTP in descending order: 1. built-in distribution (i.e. Erlang distributed RPC) 2. bit-syntax 3. light-weight processes 4. pattern-matching
- reeses 16y ago
  2 combined with 4 is a secret weapon when parsing record-oriented files from old mainframes or minicomputers. Replace 500 lines of Java with one--very long--line of Erlang.

44 points by tophercyll 16y ago

Let's face it - it's not the language that is the problem. It would help you, but it would help you only with some percentage of the problems out there. For example - there does not exist a practical language (or design) where you can implement the LZ compression (ZLIB, others) in parallel, so that it gives the same results as the sequential "c" version. It's just that certain algorithms, hence protocols, data structures, standards are not suited for parallel processing that well. Okay, in the first case, maybe you can split the incoming data by 128kb and process each other individually ... but that's not the same - you can't reuse the LZ window. Really the problem is the 13 dwarfs that university folks have identified - 13 stereotypical problems that relate to 99% of what's being done with a programming language - some of the dwarfs are just speedy parallel gnomes, some of them are old slow stubborn, like Gimli from LOTR. http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-183.html http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-18...

pufuwozu 16y ago
Isn't Pigz a parallel implementation of gzip which is itself based upon LZ77? http://www.zlib.net/pigz/ http://www.zlib.net/pigz/ Hasn't there been a few parallel implementations of bzip2? http://compression.ca/pbzip2/ http://compression.ca/pbzip2/ http://bzip2smp.sourceforge.net/ http://bzip2smp.sourceforge.net/ I understand that parallelism isn't suited for a lot of algorithms but from what I can tell, there's been heaps of successful work in compression. Could you give us some more information? It would really help me out - I'm doing an undergraduate class where I have to manually make an open-source project parallel. I've been looking into compression algorithms because I thought they were well suited. Please help me out if I'm going down the wrong path!
- wmf 16y ago
  The key to malkia's strawman is that pigz does not give the same results as the sequential "c" version of gzip. AFAIK gzip is not parallelizable as-is because every symbol depends on the previous symbol; pigz breaks this dependency to get parallelism but gives up a little compression efficiency. In practice this does not matter, which is why LZ is not a good example.
- astrange 16y ago
  Compression algorithms are poorly suited to parallelism, because they remove everything that isn't a data dependency in the input, and parallelism is nothing but a lack of data dependencies. The trick is to start at the largest chunk possible and go down until you find where they have left in some, uh, non-dependencies - like bzip2 which has independent x*100KB blocks, and video which (usually) has independent frames. You should be able to get 2-4 separate tasks out of that, which is good enough for CPUs.
wmf 16y ago
certain algorithms, hence protocols, data structures, standards are not suited for parallel processing that well. Sure, but for problems that can be parallelized you want a language to be able to express that parallelism. That may sound obvious, but many popular languages cannot do it. Let's not just give up on parallelism because it can't be used everywhere.
kanak 16y ago
> Let's face it - it's not the language that is the problem. It would help you, but it would help you only with some percentage of the problems out there. Let's not underestimate the help that a language can provide; writing interpreters for languages is almost trivial on a lisp because you can reuse pretty much every piece of machinery on a lisp for your ends. Similarly, there is an entire class of problems that is nearly trivial on prolog that is pretty difficult to get right on other languages simply because prolog makes it easy to express rules and specifications that need to be met. Just look at an implementation of a sudoku solver in prolog and compare it with some other language. I feel that a language designed with concurrency in mind would make it much simpler to write an entire class of problems. These languages are just gaining traction, so we are yet to see bigger and more significant examples. However, the "ants.clj" demo that Rich Hickey has written in Clojure, and some of the erlang demos in Joe Armstrong's book have made me a believer.

j_baker 16y ago

I'm not convinced that parallelism is something that needs support at the language level. The only languages that do this are Go and Erlang (off the top of my head). Others like Clojure and Scala have more support at the standard library level.

X9 16y ago
It might not need language level support, but anything to make it easier to leverage is a plus in my book. If the programmer doesn't have to concern themselves with extra parallelism-specific library calls and is still able to write a binary that can take advantage of multiple cores, that seems like a good idea to me.
swannodette 16y ago
? Clojure has deep language support for concurrency - from syntactical constructs to it's core performant immutable data structures.
- lukev 16y ago
  But the beauty is that because it's a Lisp, it's all implemented in terms of macros - Clojure's complete set of concurrency tools could be written as a library. The only exception is the deref reader macro "@", since Clojure doesn't allow user-defined reader macros by default.
  - kanak 16y ago
    > it's all implemented in terms of macros This is not true at present. The core data structures, and the STM machinery are implemented in java, not as macros.
- plinkplonk 16y ago
  He probably meant "distributed". Erlang has a better "distributed" story than Clojure.
jerf 16y ago
Erlang gets a lot of good mileage out of it, though. You start to really miss the OTP system when you try to write actually-important code in any other language. And there are some aspects that are hard to get right at a later time when it's not in the language from day one, cross-process messaging in particular, which is a primitive used to build a lot of other features. I do not know where Clojure or Scala have a generic cross-process messaging ability, and I'm not saying it's impossible by any means, but it's much easier if you start from scratch with that in mind.

adamb 16y ago

It's worth noting we (the team that's building Skynet) didn't set out to build a parallel language, we set out to build a distributed one. It turns out that a lot of the things that make Spin a good distributed language also make it a good parallel one.

philwelch 16y ago
Yes, that's the story behind Erlang as well.

deleted 16y ago

[deleted]

nivertech 16y ago

tophercyll, can you give an invite to skynet? Nice blog post, but you need to give references/links for Spin and Skynet. Otherwise it's just an ad trick...

tophercyll 16y ago
Hi nivertech, I'm sharing one of the lessons we learned building our own programming language. I love how many language designers there are on HN! We're working on an invite system, so everyone can benefit from Skynet! Skynet is better when you use it with others, so the invites will work for groups of friends.

nivertech 16y ago

My favorite features of Erlang/OTP in descending order: 1. built-in distribution (i.e. Erlang distributed RPC) 2. bit-syntax 3. light-weight processes 4. pattern-matching

reeses 16y ago
2 combined with 4 is a secret weapon when parsing record-oriented files from old mainframes or minicomputers. Replace 500 lines of Java with one--very long--line of Erlang.