4 ms·

Does memory really bottleneck instruction throughput though? I've never ever seen code that stalled on an instruction fetch. CPUs generally hide latency by au

Does memory really bottleneck instruction throughput though? I've never ever seen code that stalled on an instruction fetch. CPUs generally hide latency by auto-prefetching the instruction stream into cache, and memory bandwidth has been keeping up just fine with CPU speed. Hence memory latency rarely hinders instruction throughput, unless your code jumps around unpredictably every few instructions (most doesn't; the only common class of program I can think of which does are emulators/interpreters). Probably the only differences in ISA design/implementation between this universe and one where memory latency tracked CPU speed would be that (a) instructions would need not be prefetched into cache (possibly there'd be no cache), and (b) we'd still have wacky instructions like the TMS9900's X instruction, which executes the instruction at a given memory address. [1] [1] http://en.wikipedia.org/wiki/Texas_Instruments_TMS9900#Instruction_set_and_addressing http://en.wikipedia.org/wiki/Texas_Instruments_TMS9900#Instr...

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

sliverstorm 12y ago

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