4 ms·

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, direct

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.

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.