3 ms·

You totally can hide latency with auto-prefetching. But there are a few problems. - This depends on correct branch prediction, otherwise you could easily wind

You totally can hide latency with auto-prefetching. But there are a few problems. - This depends on correct branch prediction, otherwise you could easily wind up having fetched the wrong fork - L2 latency is, what, 12 cyles? L3 is 28? (Sandy Bridge). To completely hide this latency, we would need the prefetcher to run 28 cycles ahead. Considering caches work in cachelines and not instructions, this means we have to run potentially hundreds of instructions ahead of execution, without mispredicting one branch... Whether your code is going to bottleneck all depends on size and code patterns. If your software fits in the L1 icache, you will only miss when context-switching. If your software is 100MB and does not exhibit good code locality, you might be stalling all over the place.

ganzuul 12y ago
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.
deleted 12y ago
[deleted]

ganzuul 12y ago

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.

deleted 12y ago

[deleted]