3 ms·

Is this code locality what makes functional style programming perform well?

• colanderman 12y ago
  As someone who's programmed extensively in both C and OCaml, I wish my functional programs could approach the performance of my C programs. Although I doubt code locality differs much between the two (although FP might fare worse due to the code space overhead imposed by polymorphism), data locality is generally much worse in FP languages due to poorer control over data layout. (Garbage collection, run-time type tagging, excessive indirection, and inability to specify structure layout all contribute to this.) The purported benefits of FP performance generally stem from either (a) the ability to ignore pointer aliasing effects when optimizing, which is not unique to FP (see Fortran, or C's restrict keyword), (b) the ability to automatically parallelize code due to immutability of data, which is generally far less a benefit than it sounds, or (c) the ability for the compiler or runtime to optimize away computations which are never used, which, while easier with a pure FP language, is again not unique to FP (see most modern C compilers).
• Athas 12y ago
  No. There are only a few properties of functional programming that help performance, and they are mostly spent compensating for the overhead typically imposed by high-level languages: * Easier parallelisation (although compiler auto-parallelisation has turned out to not work well in practice). * Compacting garbage collectors can mimimise fragmentation, and thus improve locality. This is not specific to functional languages, though, but a general benefit of automatic memory management. * For pure languages, you may be able to implement generational garbage collectors slightly more efficiently, as no object of an older generation will have references to objects in a young generation. This is a very fragile property though - even laziness breaks it - and I'm not sure anyone has tried to use it in practice. * Purity means that the compiler has to be less careful about optimisations and can make more assumptions about the code. This is part of what makes automatic (or semi-automatic) loop fusion practical in functional languages. In general, I would not say that functional-style languages "perform well". They perform "well enough", but naive performance is not the reason to pick a functional language over an imperative one.
  • m0th87 12y ago
    > For pure languages, you may be able to implement generational garbage collectors slightly more efficiently, as no object of an older generation will have references to objects in a young generation. This is a very fragile property though - even laziness breaks it - and I'm not sure anyone has tried to use it in practice. That's how it works in Haskell, despite the laziness: https://www.haskell.org/haskellwiki/GHC/Memory_Management https://www.haskell.org/haskellwiki/GHC/Memory_Management
    • Athas 12y ago
      Huh - how can that work? Take some partially evaluated object 'F <thunk>', where F is a data constructor. This object is old and thus stored in the oldest generation. When we force the thunk, we have to update the reference in the object to point to the resulting value - which, as it is newly allocated, should be in the nursery. Is the trick simply to allocate in whichever generation our referencing pointer belongs? As I see it, the basic problem is that lazy evaluation requires mutation at the heap-level.
• pron 12y ago
  As others have said, functional-style programs usually perform worse than imperative ones, large because they have worse (data) memory locality due to their use of persistent data structures that don't normally reuse memory addresses (and thus cache lines), so every "mutation" is a cache-miss.