3

Functional languages seek to minimize accidental state (computationally-convenient but logically unnecessary data dependencies) by endorsing the most granularly modular, mathematically unambiguous constructs. Yet general-purpose register machines achieve the greatest time-/space-efficiency by maximizing data dependencies, because this allows for the CPU to use the data at hand rather than pay the cost of an extra context switch to the extracted procedure.

To turn the minimization of data-dependencies into a performance advantage, one would have to use these additional guarantees to pursue greater parallelism without punishing the extraction of small, anonymous procedures as in stack- (here and here) or queue-based (here and here) architectures. Chip design has not yet gone in these directions because Moore's law and Dennard scaling have historically made parallelization a losing game economically (though that may soon change).

Can functional languages like Haskell (or Kitten) ever outperform the mainstream when the performance advantages they are designed to offer are so at odds with the priorities of hardware makers?

  • 2
    There is only one way to find out - wait some years and observe the market development. Trying to give you an answer would end up in speculation and wild guessing, but we don't have a crystal ball, and this is not a discussion site, sorry. – Doc Brown Jul 1 '18 at 5:47
  • 1
    By the way, you were already given helpful advice for your last question, that it would be much more readable if it would be broken up into paragraphs with a logical flow to them instead of a single rambling wall of text. The same applies here. (That doesn't make the question any less off-topic, of course, but it would at least be readable and understandable.) – Jörg W Mittag Jul 1 '18 at 6:53
  • 1
    In the real world, IO inefficiency almost always makes computational inefficiency irrelevant. You might also look at the SPARC chip architecture before making statements about the direction that chip design took. – kdgregory Jul 1 '18 at 11:31
  • 1
    @JörgWMittag I was given "helpful" advice then the question was deleted before I could edit it, and then didn't receive any further consideration once I made it less than 1/5 the length (broadness was the problem, supposedly). I chose my words very carefully; I hope two more newlines makes all the difference from it being a "rambling wall of text." – Typist Jul 1 '18 at 16:18
4

Functional programming is not inherently inefficient. There is no reason why the language semantics have to closely match the underlying execution model, although a closer match certainly makes compilation easier.

For example, Haskell can already provide good performance right now, but optimization is a hit and miss affair: it's difficult to write Haskell code that will be reliably compiled to well-optimized machine code. The problem isn't that Haskell is a functional language, but that Haskell has fairly complex and very high-level semantics, in particular such unusual features like lazy evaluation. Other functional languages are very dynamic and don't feature a type system that would allow efficient code to be generated, for example JavaScript.

But FP languages don't have feature those complex semantics, e.g. the ML language family has very enjoyable statically typed imperative-functional languages like OCaml. Aside from having to deal with closures, compiling OCaml is not fundamentally different from compiling C. And C also has problematic features that limit its efficiency on current hardware, e.g. pointer aliasing.

If functional languages have a problematic feature w.r.t. efficient execution, it is the need for garbage collection. E.g. immutable data structures, closures, and continuations all benefit if:

  • unreferenced data can be cheaply garbage-collected
  • possibly: data can be copied cheaply, e.g. through copy-on-write (CoW)
  • an execution model that doesn't assume the existence of a stack

These are things that could in principle be moved into silicon, e.g. a MMU chip with hardware GC, and built-in virtual addressing that supports CoW. (Yes I'm aware of CoW pages, but that isn't granular enough here.) However, that would imply a radically different memory model than is used today. I doubt this would be more efficient than the current state of the art, but it might allow more efficient execution of functional and object-oriented programs than on current hardware.

But that is not going to happen, simply because economies of scale favour the status quo. Once upon a time there was functional-programming hardware: Lisp Machines. Those pretty much died out, because of declining Lisp demand, and because of microprocessors (like x86 chips): Microprocessors are already fast enough. Building great compilers is cheaper than developing competitive chips. For similar reasons, hardware JVMs never really caught (although Java platforms certainly did, see Android and many feature phones).

  • 1
    Azul have already figured out how to leverage the features in current (~5 years) MMUs that were originally intended for virtualization to make GC fast. The bottleneck is no longer the CPU, it is the OS's virtual memory subsystem, which either doesn't provide the necessary access to the underlying MMU features or isn't designed to scale up to the number of objects and down to the small sizes that is required. (If I understand that correctly, Azul basically creates a page per object, i.e. each object's instance variables get their own page, each GC domain its own page table. Something like it.) – Jörg W Mittag Jul 1 '18 at 21:40
  • That's the reason why Azul's JVM runs directly on the hypervisor beside the OS, not on the OS. Azul had an experimental patch for the Linux kernel that demonstrated that given sufficient support from the virtual memory subsystem, their JVM can run on top of Linux with the same GC performance as it did originally running on Azul's own OS on Azul's own CPU. Unfortunately, this patch was just a proof-of-concept and was never designed to be merged into the kernel. – Jörg W Mittag Jul 1 '18 at 21:41
  • Excellent, but you leave me wondering if there might be some small changes to architectures to improve GC performance, not simply radically different memory models. – Frank Hileman Jul 6 '18 at 1:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.