Content deleted Content added
Rescuing 17 sources and tagging 0 as dead.) #IABot (v2.0.9.5 |
m Changed "it's" to the correct possessive form "its" |
||
Line 203:
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? | 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
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 |last=Cesarini |first=Francesco |title=Erlang programming: a concurrent approach to software development |last2=Thompson |first2=Simon |publisher=O'Reilly Media, Inc. |year=2009 |isbn=0596555857, 9780596555856 |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]].
Line 230:
has the mean execution time of 4.76 nanoseconds, 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 1200 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>, so let's take 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>
=== Functional programming in non-functional languages ===
| |||