28 ms·

Auto-Threading Is Actually About Mutability And Safety

45 points by tkellogg 14y ago

lucian1900 14y ago
It's what people have been saying for a while now: mutable state is problematic. Very cool, of course. Interestingly, Rust is moving to a similar model, where the (im)mutability of a data structure is "inherited" from the (im)mutability of the thing that references it. So it's trivial to determine something like "for this section, this object is immutable and not referenced from anywhere else".
- cobrausn 14y ago
  Problematic but absolutely necessary. I'm reminded of a quote from John Carmack from an article where he was advocating FP in C++. In almost all cases, directly mutating blocks of memory is the speed-of-light optimal case, and avoiding this is spending some performance. Most of the time this is of only theoretical interest; we trade performance for productivity all the time. Programming with pure functions will involve more copying of data, and in some cases this clearly makes it the incorrect implementation strategy due to performance considerations. As an extreme example, you can write a pure DrawTriangle() function that takes a framebuffer as a parameter and returns a completely new framebuffer with the triangle drawn into it as a result. Don’t do that. http://www.altdevblogaday.com/2012/04/26/functional-programming-in-c/ http://www.altdevblogaday.com/2012/04/26/functional-programm...
  - simcop2387 14y ago
    I may have accidentally down-voted you, sorry for that, I cant find any way to undo it.
  - lucian1900 14y ago
    Not absolutely necessary. One could use a persistent data structure, where the copy shares structure with the original. Of course even this has its cost, but it makes mutable state much, much less necessary.
    - DanWaterworth 14y ago
      It's also true that what looks like creating a new value may be optimized by the compiler to update in place.
    - bunderbunder 14y ago
      For simple structures or situations with low performance needs, yes definitely. But the classic example of a data type for which persistent structures have a hard time cutting the mustard is an associative array. With mutability you get hash tables, which I assume need no introduction. With persistent data structures you're generally stuck with some sort of balanced tree that has O(log n) lookup time in the best case, O(log n) insert time (and memory allocations) in the average case, a lot of pointer overhead, and absolutely depressing locality of reference.
      - DanWaterworth 14y ago
        Or a HAMT with O(1) time operations.
      - dllthomas 14y ago
        > absolutely depressing locality of reference. If a hashtable gives you good locality of reference, your hash function isn't working :-P But yes, obviously you're hitting more nodes in the tree typically, so you're paying a larger price for being cache-unfriendly.
  - kibwen 14y ago
    I agree, though in Rust this isn't the case. Rust encourages you to directly mutate memory and avoid copies wherever you can, and forces you to be explicit about which bits of memory you're going to mutate. It's trivial to create something as immutable and then "thaw" it later to make it deeply mutable for a while, and then "freeze" when you're done so that you regain the safety guarantees of immutable data. It's not about "purity", it's about getting the best of both speed and safety in one system. It's actually very neat.
  - zxcdw 14y ago
    Can't understand the downvote for this reply... Also what Carmack said is definitely true within the domain he works in, performance is a major concern and whatever cripples it, is not a good solution.
    - RyanZAG 14y ago
      Performance isn't just a major concern in his domain - it's a concern in every domain. Why are you even trying to make an auto-threading compiler? Performance. If using immutable blocks that can be run in parallel performs worse than using mutable blocks in a single thread, then your auto-threading compiler is useless for its primary purpose: performance.
      - marshray 14y ago
        It's important to be aware of performance in every domain, but there are few domains where performance is always the overriding consideration. As Carmack said: Most of the time this is of only theoretical interest; we trade performance for productivity all the time
        RyanZAG 14y ago
        I agree, but the idea of switching to immutable blocks in this case is so you can use auto-threading on the blocks. ie. you're switching to immutable blocks to increase performance through threading. If the immutable blocks don't increase performance through threading in excess of the loss from just using mutable blocks, then the whole exercise is wasted. Bolting on immutable blocks into C# is unlikely to have the same effect for readability as designed-around-immutability of Haskel.
  - dllthomas 14y ago
    Welllll... alternative pure-ish functional approaches would be: 1) Build a description of the scene made up of draw-triangles (built lazily, if you need information back from the frame buffer in the middle of drawing), which is packaged up in something that can be shipped off to the graphics card and sent in an IO action. This is going to still be more expensive than building vertex arrays in place, but nowhere near as expensive as copying the whole vertex buffer each time, and possibly even practical. 2) Run with the DrawTriangle frame-buffer passing silliness, but let the compiler perform some kind of fusion operation on drawing commands. But yes, "don't do that" in anything production until you've been able to make it work well in a toy. Having said that, building that toy might be informative and potentially even useful.
  - mistercow 14y ago
    In principle, though, a smart compiler could take a program written in terms of pure functions and transform it into a program using mutable state for better performance. The advantage would be to start with a program about which you can make strong claims, and then break apply transformations that invalidate those claims, replacing them with weaker claims in a predictable, methodical fashion. Languages like C allow programmers to easily write programs that are hard to reason about mechanically, and the programmer can use that power to hand-tune the program to be very fast. The programmer can also use that power to crank out fragile programs without thinking through all of the edge cases. An ideal compiler working on pure functions could say "No, listen, write this so I can understand it, and then I'll start using shortcuts to make it run quick". Of course, even if your compiler is smart enough to actually beat competent hand-optimization, there are some negative side effects. If you have optimized a program by hand, you know what properties your optimizations rely on, and so you'll know when a new feature requires that code to be rewritten at a performance cost. You can take that cost into account making the decision about adding that feature. But if the optimization is done automatically without your involvement, you'll just see a sudden performance hit when you add a feature, and figuring out why will involve arcane knowledge of compiler internals.
- gav 14y ago
  > It's what people have been saying for a while now: mutable state is problematic. Local mutable state is fine, it's when it leaks across boundaries things start to get problematic.
bunderbunder 14y ago
As far as the practical value of an auto-parallelizing compiler goes, I'd like to see it before I believe it. I've got no doubt that the compiler is pulling it off. But with how young the technology is, I'd be downright amazed if they've got something that can reliably outdo what a knowledgeable human can manage with a reasonable amount of effort. Not that I wouldn't like to see things get to that point. For now, though, what's really interesting to me is the idea of language-level support for managing mutability. I agree with the author that that's something that both functional and imperative languages have generally fail to provide much help with. And I think there really is a need for language-level support for it. It's always possible to pass in a mutable subtype or a non-pure function as an argument to a procedure at run-time. So without some way to say, "This parameter requires pure arguments," it may not even be possible for a programmer to verify that a module can, e.g., cope with concurrency in code that uses any degree of inversion of control.
- spectre 14y ago
  A programmer is always capable of writing better parallel code then such a compiler but writing safe and correct parallel code is beyond the skills of many programmers. A good analogy is that a good programmer can hand write assembly that out performs compiled code but that is too hard for most programmers to achieve. There is some interesting research into languages that explicitly control mutability and object reachability (A set of objects don't need to be immutable if we can guarantee that only one thread has access to them). http://ecs.victoria.ac.nz/foswiki/pub/Main/TechnicalReportSeries/ECSTR12-18.pdf http://ecs.victoria.ac.nz/foswiki/pub/Main/TechnicalReportSe...
tikhonj 14y ago
This article's author seems to be very dismissive of Haskell. Which is a little odd because, at least as described in the article (I haven't had time to look at the paper yet), the approach taken by this compiler is actually very similar to what is already done in Haskell. In particular, Haskell already supports initializing data structures mutably and then "freezing" them. I know this technique is used in the Vector library, for example. Additionally, "pockets of imperative mutability" perfectly describes Haskell's "State Threads" (ST). Programming in Haskell already allows you to have arbitrary state constrained to a particular scope and controlled by the type system. Using things like ST with immutability by default is just tracking state in the type system. And--as long as you don't worry about how it's implemented under the hood--ST isn't terribly difficult to use. I'm sure the auto-threading compiler is very novel and interesting research, and I'm sure it's very useful. However, I think that you shouldn't be this dismissive of Haskell, especially because Haskell already does essentially everything described in the article.
- DanWaterworth 14y ago
  I agree with this. The article also contains this excerpt: Even though there are significant benefits to programming with immutability, programming without state is also tricky and usually requires workarounds in FP. 'Workarounds' links to a page that describe Haskell's state monad, but Haskell's state monad only uses immutable state. It's just a wrapper around an ordinary function with the type: (s -> (o, s)) . As far as workarounds go, this is not a good example.
- bascule 14y ago
  I think they're working on a language for mere mortals instead of FP wizards. Seems cool to me. I mean, you could respond to claims like: > This addresses problems under which functional programming (FP) labors, like creating cycles of immutable objects. ...that in Haskell we can create cyclical data structures using laziness via tying the knot. But uhh, wouldn't it just be a whole lot easier to build cyclical relationships using mutable state then freeze the whole thing? I guess what I'm saying is Haskell is hard, let's go shopping... for sufficiently smart compilers!
- bunderbunder 14y ago
rgbrgb 14y ago
Does anybody know of experiments with using auto-threading in the Haskell compiler? Is there work underway to do this?
- marshray 14y ago
  To some degree "it just works" today. For example, see the end of http://gisli.hamstur.is/2012/12/network-programming-in-haskell/ http://gisli.hamstur.is/2012/12/network-programming-in-haske... By using Haskell you get multi-core support for free, so if you want to distribute the request handling over the cores in your machine you simply execute the server like so. Substitute x in -Nx with the number of cores you want to use. $ ./network-server +RTS -Nx I don't think this gets you the same kind of fine-grained parallelism as the research compiler. But I could be wrong.
  - jfoutz 14y ago
    If you only have one thread, you'll only use 1 core (maybe 2 with gc) A network application is a great use case. Usually you'll have one thread per connection. In a more "normal" application you'll need to make threads. one very easy way to do that is pmap, map a function over data and spark a thread for each function invocation. But then you need to worry about the cost of creating threads vs the amount of work done, etc. there are always tradeoffs.
rbanffy 14y ago
I remember something like this in a Sun compiler. I don't remember exactly what was being optimized, but it gave a significant boost to single threaded program.
dschiptsov 14y ago
Mutability? Safety? Ah, it is drdobbs.com..)
ef4 14y ago
''The ability to have "pockets of imperative mutability"... connected by a "functional tissue," is not only clarifying, but works quite well in practice for building large and complex concurrent systems.'' That's always been a winning combination, and if you look for it you'll see that many examples of well-written code hold to the pattern: large swaths of code that are referentially transparent, with smaller chunks of imperative code piping them together. This can be done in almost any language, but of course support from the toolchain is nice to have.

45 points by tkellogg 14y ago

lucian1900 14y ago

It's what people have been saying for a while now: mutable state is problematic. Very cool, of course. Interestingly, Rust is moving to a similar model, where the (im)mutability of a data structure is "inherited" from the (im)mutability of the thing that references it. So it's trivial to determine something like "for this section, this object is immutable and not referenced from anywhere else".

cobrausn 14y ago
Problematic but absolutely necessary. I'm reminded of a quote from John Carmack from an article where he was advocating FP in C++. In almost all cases, directly mutating blocks of memory is the speed-of-light optimal case, and avoiding this is spending some performance. Most of the time this is of only theoretical interest; we trade performance for productivity all the time. Programming with pure functions will involve more copying of data, and in some cases this clearly makes it the incorrect implementation strategy due to performance considerations. As an extreme example, you can write a pure DrawTriangle() function that takes a framebuffer as a parameter and returns a completely new framebuffer with the triangle drawn into it as a result. Don’t do that. http://www.altdevblogaday.com/2012/04/26/functional-programming-in-c/ http://www.altdevblogaday.com/2012/04/26/functional-programm...
- simcop2387 14y ago
  I may have accidentally down-voted you, sorry for that, I cant find any way to undo it.
- lucian1900 14y ago
  Not absolutely necessary. One could use a persistent data structure, where the copy shares structure with the original. Of course even this has its cost, but it makes mutable state much, much less necessary.
  - DanWaterworth 14y ago
    It's also true that what looks like creating a new value may be optimized by the compiler to update in place.
  - bunderbunder 14y ago
    For simple structures or situations with low performance needs, yes definitely. But the classic example of a data type for which persistent structures have a hard time cutting the mustard is an associative array. With mutability you get hash tables, which I assume need no introduction. With persistent data structures you're generally stuck with some sort of balanced tree that has O(log n) lookup time in the best case, O(log n) insert time (and memory allocations) in the average case, a lot of pointer overhead, and absolutely depressing locality of reference.
    - DanWaterworth 14y ago
      Or a HAMT with O(1) time operations.
    - dllthomas 14y ago
      > absolutely depressing locality of reference. If a hashtable gives you good locality of reference, your hash function isn't working :-P But yes, obviously you're hitting more nodes in the tree typically, so you're paying a larger price for being cache-unfriendly.
- kibwen 14y ago
  I agree, though in Rust this isn't the case. Rust encourages you to directly mutate memory and avoid copies wherever you can, and forces you to be explicit about which bits of memory you're going to mutate. It's trivial to create something as immutable and then "thaw" it later to make it deeply mutable for a while, and then "freeze" when you're done so that you regain the safety guarantees of immutable data. It's not about "purity", it's about getting the best of both speed and safety in one system. It's actually very neat.
- zxcdw 14y ago
  Can't understand the downvote for this reply... Also what Carmack said is definitely true within the domain he works in, performance is a major concern and whatever cripples it, is not a good solution.
  - RyanZAG 14y ago
    Performance isn't just a major concern in his domain - it's a concern in every domain. Why are you even trying to make an auto-threading compiler? Performance. If using immutable blocks that can be run in parallel performs worse than using mutable blocks in a single thread, then your auto-threading compiler is useless for its primary purpose: performance.
    - marshray 14y ago
      It's important to be aware of performance in every domain, but there are few domains where performance is always the overriding consideration. As Carmack said: Most of the time this is of only theoretical interest; we trade performance for productivity all the time
      - RyanZAG 14y ago
        I agree, but the idea of switching to immutable blocks in this case is so you can use auto-threading on the blocks. ie. you're switching to immutable blocks to increase performance through threading. If the immutable blocks don't increase performance through threading in excess of the loss from just using mutable blocks, then the whole exercise is wasted. Bolting on immutable blocks into C# is unlikely to have the same effect for readability as designed-around-immutability of Haskel.
- dllthomas 14y ago
  Welllll... alternative pure-ish functional approaches would be: 1) Build a description of the scene made up of draw-triangles (built lazily, if you need information back from the frame buffer in the middle of drawing), which is packaged up in something that can be shipped off to the graphics card and sent in an IO action. This is going to still be more expensive than building vertex arrays in place, but nowhere near as expensive as copying the whole vertex buffer each time, and possibly even practical. 2) Run with the DrawTriangle frame-buffer passing silliness, but let the compiler perform some kind of fusion operation on drawing commands. But yes, "don't do that" in anything production until you've been able to make it work well in a toy. Having said that, building that toy might be informative and potentially even useful.
- mistercow 14y ago
  In principle, though, a smart compiler could take a program written in terms of pure functions and transform it into a program using mutable state for better performance. The advantage would be to start with a program about which you can make strong claims, and then break apply transformations that invalidate those claims, replacing them with weaker claims in a predictable, methodical fashion. Languages like C allow programmers to easily write programs that are hard to reason about mechanically, and the programmer can use that power to hand-tune the program to be very fast. The programmer can also use that power to crank out fragile programs without thinking through all of the edge cases. An ideal compiler working on pure functions could say "No, listen, write this so I can understand it, and then I'll start using shortcuts to make it run quick". Of course, even if your compiler is smart enough to actually beat competent hand-optimization, there are some negative side effects. If you have optimized a program by hand, you know what properties your optimizations rely on, and so you'll know when a new feature requires that code to be rewritten at a performance cost. You can take that cost into account making the decision about adding that feature. But if the optimization is done automatically without your involvement, you'll just see a sudden performance hit when you add a feature, and figuring out why will involve arcane knowledge of compiler internals.
gav 14y ago
> It's what people have been saying for a while now: mutable state is problematic. Local mutable state is fine, it's when it leaks across boundaries things start to get problematic.

bunderbunder 14y ago

As far as the practical value of an auto-parallelizing compiler goes, I'd like to see it before I believe it. I've got no doubt that the compiler is pulling it off. But with how young the technology is, I'd be downright amazed if they've got something that can reliably outdo what a knowledgeable human can manage with a reasonable amount of effort. Not that I wouldn't like to see things get to that point. For now, though, what's really interesting to me is the idea of language-level support for managing mutability. I agree with the author that that's something that both functional and imperative languages have generally fail to provide much help with. And I think there really is a need for language-level support for it. It's always possible to pass in a mutable subtype or a non-pure function as an argument to a procedure at run-time. So without some way to say, "This parameter requires pure arguments," it may not even be possible for a programmer to verify that a module can, e.g., cope with concurrency in code that uses any degree of inversion of control.

spectre 14y ago
A programmer is always capable of writing better parallel code then such a compiler but writing safe and correct parallel code is beyond the skills of many programmers. A good analogy is that a good programmer can hand write assembly that out performs compiled code but that is too hard for most programmers to achieve. There is some interesting research into languages that explicitly control mutability and object reachability (A set of objects don't need to be immutable if we can guarantee that only one thread has access to them). http://ecs.victoria.ac.nz/foswiki/pub/Main/TechnicalReportSeries/ECSTR12-18.pdf http://ecs.victoria.ac.nz/foswiki/pub/Main/TechnicalReportSe...

tikhonj 14y ago

This article's author seems to be very dismissive of Haskell. Which is a little odd because, at least as described in the article (I haven't had time to look at the paper yet), the approach taken by this compiler is actually very similar to what is already done in Haskell. In particular, Haskell already supports initializing data structures mutably and then "freezing" them. I know this technique is used in the Vector library, for example. Additionally, "pockets of imperative mutability" perfectly describes Haskell's "State Threads" (ST). Programming in Haskell already allows you to have arbitrary state constrained to a particular scope and controlled by the type system. Using things like ST with immutability by default is just tracking state in the type system. And--as long as you don't worry about how it's implemented under the hood--ST isn't terribly difficult to use. I'm sure the auto-threading compiler is very novel and interesting research, and I'm sure it's very useful. However, I think that you shouldn't be this dismissive of Haskell, especially because Haskell already does essentially everything described in the article.

DanWaterworth 14y ago
I agree with this. The article also contains this excerpt: Even though there are significant benefits to programming with immutability, programming without state is also tricky and usually requires workarounds in FP. 'Workarounds' links to a page that describe Haskell's state monad, but Haskell's state monad only uses immutable state. It's just a wrapper around an ordinary function with the type: (s -> (o, s)) . As far as workarounds go, this is not a good example.
bascule 14y ago
I think they're working on a language for mere mortals instead of FP wizards. Seems cool to me. I mean, you could respond to claims like: > This addresses problems under which functional programming (FP) labors, like creating cycles of immutable objects. ...that in Haskell we can create cyclical data structures using laziness via tying the knot. But uhh, wouldn't it just be a whole lot easier to build cyclical relationships using mutable state then freeze the whole thing? I guess what I'm saying is Haskell is hard, let's go shopping... for sufficiently smart compilers!
bunderbunder 14y ago

rgbrgb 14y ago

Does anybody know of experiments with using auto-threading in the Haskell compiler? Is there work underway to do this?

marshray 14y ago
To some degree "it just works" today. For example, see the end of http://gisli.hamstur.is/2012/12/network-programming-in-haskell/ http://gisli.hamstur.is/2012/12/network-programming-in-haske... By using Haskell you get multi-core support for free, so if you want to distribute the request handling over the cores in your machine you simply execute the server like so. Substitute x in -Nx with the number of cores you want to use. $ ./network-server +RTS -Nx I don't think this gets you the same kind of fine-grained parallelism as the research compiler. But I could be wrong.
- jfoutz 14y ago
  If you only have one thread, you'll only use 1 core (maybe 2 with gc) A network application is a great use case. Usually you'll have one thread per connection. In a more "normal" application you'll need to make threads. one very easy way to do that is pmap, map a function over data and spark a thread for each function invocation. But then you need to worry about the cost of creating threads vs the amount of work done, etc. there are always tradeoffs.

rbanffy 14y ago

I remember something like this in a Sun compiler. I don't remember exactly what was being optimized, but it gave a significant boost to single threaded program.

dschiptsov 14y ago

Mutability? Safety? Ah, it is drdobbs.com..)

ef4 14y ago

''The ability to have "pockets of imperative mutability"... connected by a "functional tissue," is not only clarifying, but works quite well in practice for building large and complex concurrent systems.'' That's always been a winning combination, and if you look for it you'll see that many examples of well-written code hold to the pattern: large swaths of code that are referentially transparent, with smaller chunks of imperative code piping them together. This can be done in almost any language, but of course support from the toolchain is nice to have.