5 ms·

and for the whole picture vis-a-vis game dev: "I do believe that there is real value in pursuing functional programming, but it would be irresponsible to exhor

• m_mueller 12y ago
  I'm doing HPC work for a few years now and I'm familiar with FP concepts, use it (albeit never purely so far) in non performance critical code where maintainability and testability is more important. My question: How could it even work in performance critical domains? Most of the time memory bandwidth is the limiting factor, thus copying memory and cleaning up unused memory are very expensive. With pure FP, all I can do is hope the compiler won't create all the copies I'm instructing it to do and optimize it back to procedural in-place update. When that doesn't work all I can do is reimplement it procedurally. How does anyone think that this programming concept can be applied for high performance domains? What am I missing?
  • Athas 12y ago
    A possible solution would be to devise a language with a type system that tracks allocation, such that a garbage collector is not needed, and that all allocation deterministic, and yet safe. Some work has been done on this already, in the form of region inference systems, although they have to my knowledge only been used to compile functional languages to run without a garbage collector, and not been exposed in the user-visible type system. The MLkit compiler for Standard ML is the most prominent region-user I am aware of.
    • codygman 12y ago
      I believe that ATS[0] has/can do this, perhaps I'm confusing another feature. Anywho, there's also a very comprehensive ATS book[1]. 0: http://www.ats-lang.org/ http://www.ats-lang.org/ 1: http://ats-lang.sourceforge.net/DOCUMENT/INT2PROGINATS/HTML/INT2PROGINATS-BOOK.html http://ats-lang.sourceforge.net/DOCUMENT/INT2PROGINATS/HTML/...
    • twic 12y ago
      Obligatory Rust comment: Rust's type system relates allocation to variable lifetime in such a way that garbage collection is not needed, and almost all deallocation is deterministic, and yet safe. Rust is still in flux, and its documentation is a bit all over the place, but here are some references: http://doc.rust-lang.org/guide-lifetimes.html http://doc.rust-lang.org/guide-lifetimes.html http://pcwalton.github.io/blog/2013/03/18/an-overview-of-memory-management-in-rust/ http://pcwalton.github.io/blog/2013/03/18/an-overview-of-mem... (warning: contains old syntax and defunct features!)
  • orbifold 12y ago
    Well if you are in HPC you are probably familiar withhttp://en.wikipedia.org/wiki/SISAL http://en.wikipedia.org/wiki/SISAL, what primarily necessitates garbage collection in modern functional programming languages is the insistence on functions as first class values (essentially they want to live in a cartesian closed category). If you look at something like Intel Thread Building Blocks or even CUDA, you will recognise that at its heart it really is a functional programming model. I mean sure in the case of CUDA you can try to write the same variable multiple times, but in reality to preserve parallelism you would not implement for example matrix multiplication by overwriting one of the matrices in the process. Moreover a more functional / mathematical view on most HPC actually yields additional insight on how to parallelise a problem.
    • robmccoll 12y ago
      TBB and CUDA seem like odd choices to me for an example case. They are based much more heavily around vectorized / SIMD style for regular more general purpose operations. The in-place vs not thing making those functional is a stretch. Very much bulk parallel procedural.
    • m_mueller 12y ago
      One of the pitfalls when analyzing HPC requirements is to start with a model that's too simplistic - and matrix multiplication is typical for that. What you usually want to run is a solver or simulation. These have timesteps and numerical approximation algorithms (e.g. Runge-Kutta) where you want to make sure that intermediate values live only exactly as long as they need. The reason being that when you distribute your main memory to your threads, especially for GPGPU, you only have a few hundred kilobytes per thread if you want to achieve saturation. So what do you do? In C you typically see the inner timestep functions being called with output and input pointers, then these are swapped for the next step - no allocation, no copying, no overhead, very simple code and nothing that any compiler could screw up. That's just one example of a trick that makes a HPC programmer's life easy, not just because it performs optimally 100% of the times it's used, but because it doesn't complicate performance analysis. In order to be able to analyse code performance properly, one must be able to understand to device code that comes out of the compiler, and how it will interact with the pipeline, the cache etc. If there's too much of a mismatch, it becomes near impossible to understand what's going on. In theory compilers could always achieve the optimum for you and a programmer wouldn't have to care about hardware at all, and just live in his logical bubble. Experience shows that this ideal is pretty far off in the future.
  • lmm 12y ago
    You know how GCC compiles mutable C code? It converts it into immutable SSA form, optimizes it in this form, and it's only at the register allocation stage that things become mutable again - if two different reassignments of your variable end up compiling to the same register, at some level it's only coincidence that they did so. So unless you're doing handwritten assembly, you're already relying on the compiler's ability to optimize away redundant copies. Why does GCC do it like this? For the same reason FP systems do: because it's easier to reason about immutable values, and easier to optimize things you can reason about. In general the closer we can get to telling the compiler our intent, the better the performance we should ultimately be able to unlock. If we tell the compiler to create a loop variable and increment it, it has to do that (or at least, has to simulate the effects of doing that). If we just tell the compiler to apply this function to every element of this list, it has the option of being smarter about it. There's an argument that this will be much more important as the world becomes ever more multicore. In a multicore environment immutable values become much easier to work with because they can be safely copied around; with mutable variables your program can end up spending more time on synchronization overhead than actually doing things. I'm not sure how much I believe this, but it could explain the recent rise in popularity of functional languages.
    • ansible 12y ago
      The world is already pretty multi-core. I was recently spec'ing out a high-end system for simulation work. You can now get Intel Xeons with up to 14 cores now, and soon 18. Talking about 36 high-end cores (dual-socket system) used to be the realm of Sun E10Ks and other very expensive systems. This is amazing to me.
    • the_why_of_y 12y ago
      Indeed, here's an interesting paper arguing this point: SSA is Functional Programming. Andrew W. Appel. http://www.cs.princeton.edu/~appel/papers/ssafun.ps http://www.cs.princeton.edu/~appel/papers/ssafun.ps What is omitted there however is a discussion of pointer parameters and call-by-reference; probably these cannot be treated in the same way as local variables since they point to a fixed address passed in by the caller, so at that point SSA can't be functional, unless I'm missing something.
• thesteamboat 12y ago
  Another possible reason we haven't heard a peep from Carmack on the subject since is that he joined OculusVR and has a bunch of interesting hardware problems to work on.