Editing Functional programming (section)

=== Efficiency issues ===
Functional programming languages are typically less efficient in their use of [[central processing unit|CPU]] and memory than imperative languages such as [[C (programming language)|C]] and [[Pascal (programming language)|Pascal]].<ref>{{cite book |first=Larry C. |last=Paulson |author-link=Lawrence Paulson |title=ML for the Working Programmer|url=https://books.google.com/books?id=XppZdaDs7e0C|access-date=10 February 2013|date=28 June 1996|publisher=Cambridge University Press|isbn=978-0-521-56543-1}}</ref> <!-- Paulson mentions the reputation for inefficiency in Sec. 1.5; perhaps a more in-depth discussion could be found. --> This is related to the fact that some mutable data structures like arrays have a very straightforward implementation using present hardware. Flat arrays may be accessed very efficiently with deeply pipelined CPUs, prefetched efficiently through caches (with no complex [[pointer chasing]]), or handled with SIMD instructions. <!-- perhaps this could be formulated by someone who knows the subject, I was simply curious about unexplained statement "logarithmic slowdown" --> It is also not easy to create their equally efficient general-purpose immutable counterparts. For purely functional languages, the worst-case slowdown is logarithmic in the number of memory cells used, because mutable memory can be represented by a purely functional data structure with logarithmic access time (such as a balanced tree).<ref name="Spiewak"/> However, such slowdowns are not universal. For programs that perform intensive numerical computations, functional languages such as [[OCaml]] and [[Clean (programming language)|Clean]] are only slightly slower than C according to [[The Computer Language Benchmarks Game]].<ref>{{cite web |url=http://benchmarksgame.alioth.debian.org/u32/which-programs-are-fastest.php?gcc=on&ghc=on&clean=on&ocaml=on&sbcl=on&fsharp=on&racket=on&clojure=on&hipe=on&calc=chart |title=Which programs are fastest? &#124; Computer Language Benchmarks Game |publisher=benchmarksgame.alioth.debian.org |access-date=2011-06-20 |archive-url=https://web.archive.org/web/20130520162513/http://benchmarksgame.alioth.debian.org/u32/which-programs-are-fastest.php?gcc=on&ghc=on&clean=on&ocaml=on&sbcl=on&fsharp=on&racket=on&clojure=on&hipe=on&calc=chart |archive-date=2013-05-20 |url-status=dead}}</ref> For programs that handle large [[matrix (mathematics)|matrices]] and multidimensional [[database]]s, [[array programming|array]] functional languages (such as [[J (programming language)|J]] and [[K (programming language)|K]]) were designed with speed optimizations.

Immutability of data can in many cases lead to execution efficiency by allowing the compiler to make assumptions that are unsafe in an imperative language, thus increasing opportunities for [[inline expansion]].<ref>{{cite journal |title=Immutability specification and its applications |author1=Igor Pechtchanski |author2=Vivek Sarkar |journal=Concurrency and Computation: Practice and Experience |volume=17 |issue=5–6 |pages=639–662 |year=2005 |doi=10.1002/cpe.853 |s2cid=34527406}}</ref> Even if the involved copying that may seem implicit when dealing with persistent immutable data structures might seem computationally costly, some functional programming languages, like [[Clojure]] solve this issue by implementing mechanisms for safe memory sharing between ''formally'' ''immutable'' data.<ref>{{Cite web |title=An In-Depth Look at Clojure Collections |url=https://www.infoq.com/articles/in-depth-look-clojure-collections/ |access-date=2024-04-29 |website=InfoQ |language=en}}</ref> [[Rust (programming language)|Rust]] distinguishes itself by its approach to data immutability which involves immutable [[Reference (computer science)|references]]<ref>{{Cite web |title=References and Borrowing - The Rust Programming Language |url=https://doc.rust-lang.org/book/ch04-02-references-and-borrowing.html |access-date=2024-04-29 |website=doc.rust-lang.org}}</ref> and a concept called ''lifetimes.''<ref>{{Cite web |title=Validating References with Lifetimes - The Rust Programming Language |url=https://doc.rust-lang.org/book/ch10-03-lifetime-syntax.html |access-date=2024-04-29 |website=doc.rust-lang.org}}</ref>

Immutable data with separation of identity and state and [[Shared-nothing architecture|shared-nothing]] schemes can also potentially be more well-suited for [[Parallel computing|concurrent and parallel]] programming by the virtue of reducing or eliminating the risk of certain concurrency hazards, since concurrent operations are usually [[Linearizability|atomic]] and this allows eliminating the need for locks. This is how for example <code>java.util.concurrent</code> classes are implemented, where some of them are immutable variants of the corresponding classes that are not suitable for concurrent use.<ref>{{Cite web |title=Concurrent Collections (The Java™ Tutorials > Essential Java Classes > Concurrency) |url=https://docs.oracle.com/javase/tutorial/essential/concurrency/collections.html |access-date=2024-04-29 |website=docs.oracle.com}}</ref> Functional programming languages often have a concurrency model that instead of shared state and synchronization, leverages [[message passing]] mechanisms (such as the [[actor model]], where each actor is a container for state, behavior, child actors and a message queue).<ref>{{Cite web |date=2023-01-28 |title=Understanding The Actor Model To Build Non-blocking, High-throughput Distributed Systems - Scaleyourapp |url=https://scaleyourapp.com/actor-model/ |access-date=2024-04-29 |website=scaleyourapp.com |language=en-US}}</ref><ref>{{Cite book |last1=Cesarini |first1=Francesco |title=Erlang programming: a concurrent approach to software development |last2=Thompson |first2=Simon |publisher=O'Reilly Media, Inc. |year=2009 |isbn=978-0-596-55585-6 |edition=1st |publication-date=2009-06-11 |page=6 |language=en}}</ref> This approach is common in [[Erlang (programming language)|Erlang]]/[[Elixir (programming language)|Elixir]] or [[Akka (toolkit)|Akka]].

[[Lazy evaluation]] may also speed up the program, even asymptotically, whereas it may slow it down at most by a constant factor (however, it may introduce [[memory leak]]s if used improperly). Launchbury 1993<ref name=launchbury1993/> discusses theoretical issues related to memory leaks from lazy evaluation, and O'Sullivan ''et al.'' 2008<ref>{{cite web |url=http://book.realworldhaskell.org/read/profiling-and-optimization.html#x_eK1 |title=Chapter 25. Profiling and optimization |publisher=Book.realworldhaskell.org |access-date=2011-06-20}}</ref> give some practical advice for analyzing and fixing them.
However, the most general implementations of lazy evaluation making extensive use of dereferenced code and data perform poorly on modern processors with deep pipelines and multi-level caches (where a cache miss may cost hundreds of cycles) {{Citation needed|date=June 2014}}.

==== Abstraction cost ====

Some functional programming languages might not optimize abstractions such as higher order functions like "[[Map (higher-order function)|map]]" or "[[Filter (higher-order function)|filter]]" as efficiently as the underlying imperative operations. Consider, as an example, the following two ways to check if 5 is an even number in [[Clojure]]:
<syntaxhighlight lang="clojure">
(even? 5)
(.equals (mod 5 2) 0)
</syntaxhighlight>
When [[Benchmarking|benchmarked]] using the [https://clojars.org/criterium Criterium] tool on a [[Zen 3|Ryzen 7900X]] GNU/Linux PC in a [[Leiningen (software)|Leiningen]] [[REPL]] 2.11.2, running on [[JVM|Java VM]] version 22 and Clojure version 1.11.1, the first implementation, which is implemented as:
<syntaxhighlight lang="clojure>
(defn even?
  "Returns true if n is even, throws an exception if n is not an integer"
  {:added "1.0"
   :static true}
   [n] (if (integer? n)
        (zero? (bit-and (clojure.lang.RT/uncheckedLongCast n) 1))
        (throw (IllegalArgumentException. (str "Argument must be an integer: " n)))))
</syntaxhighlight>

has the mean execution time of 4.76 ms, while the second one, in which <syntaxhighlight lang="clojure" inline>.equals</syntaxhighlight> is a direct invocation of the underlying [[Java (programming language)|Java]] method, has a mean execution time of 2.8 μs – roughly 1700 times faster. Part of that can be attributed to the type checking and exception handling involved in the implementation of <syntaxhighlight lang="clojure" inline>even?</syntaxhighlight>. For instance the [https://github.com/samber/lo lo library] for [[Go (programming language)|Go]], which implements various higher-order functions common in functional programming languages using [[Generic programming|generics]]. In a benchmark provided by the library's author, calling <code>map</code> is 4% slower than an equivalent <code>for</code> loop and has the same [[Memory management|allocation]] profile,<ref>{{Citation |last=Berthe |first=Samuel |title=samber/lo |date=2024-04-29 |url=https://github.com/samber/lo |access-date=2024-04-29}}</ref> which can be attributed to various compiler optimizations, such as [[inlining]].<ref>{{Cite web |title=Go Wiki: Compiler And Runtime Optimizations - The Go Programming Language |url=https://go.dev/wiki/CompilerOptimizations |access-date=2024-04-29 |website=go.dev |language=en}}</ref>

One distinguishing feature of [[Rust (programming language)|Rust]] are ''zero-cost abstractions''. This means that using them imposes no additional runtime overhead. This is achieved thanks to the compiler using [[loop unrolling]], where each iteration of a loop, be it imperative or using iterators, is converted into a standalone [[Assembly language|Assembly]] instruction, without the overhead of the loop controlling code. If an iterative operation writes to an array, the resulting array's elements [[Register allocation|will be stored in specific CPU registers]], allowing for [[Time complexity|constant-time access]] at runtime.<ref>{{Cite web |title=Comparing Performance: Loops vs. Iterators - The Rust Programming Language |url=https://doc.rust-lang.org/book/ch13-04-performance.html |access-date=2024-04-29 |website=doc.rust-lang.org}}</ref>