<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> <html xmlns:fn="http://www.w3.org/2005/02/xpath-functions"> <head> <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> <link rel="stylesheet" href="../otp_doc.css" type="text/css"> <title>Erlang -- The Eight Myths of Erlang Performance</title> </head> <body bgcolor="white" text="#000000" link="#0000ff" vlink="#ff00ff" alink="#ff0000"><div id="container"> <script id="js" type="text/javascript" language="JavaScript" src="../js/flipmenu/flipmenu.js"></script><script id="js2" type="text/javascript" src="../js/erlresolvelinks.js"></script><script language="JavaScript" type="text/javascript"> <!-- function getWinHeight() { var myHeight = 0; if( typeof( window.innerHeight ) == 'number' ) { //Non-IE myHeight = window.innerHeight; } else if( document.documentElement && ( document.documentElement.clientWidth || document.documentElement.clientHeight ) ) { //IE 6+ in 'standards compliant mode' myHeight = document.documentElement.clientHeight; } else if( document.body && ( document.body.clientWidth || document.body.clientHeight ) ) { //IE 4 compatible myHeight = document.body.clientHeight; } return myHeight; } function setscrollpos() { var objf=document.getElementById('loadscrollpos'); document.getElementById("leftnav").scrollTop = objf.offsetTop - getWinHeight()/2; } function addEvent(obj, evType, fn){ if (obj.addEventListener){ obj.addEventListener(evType, fn, true); return true; } else if (obj.attachEvent){ var r = obj.attachEvent("on"+evType, fn); return r; } else { return false; } } addEvent(window, 'load', setscrollpos); //--></script><div id="leftnav"><div class="innertube"> <img alt="Erlang logo" src="../erlang-logo.png"><br><small><a href="users_guide.html">User's Guide</a><br><a href="../pdf/otp-system-documentation-5.9.3.1.pdf">PDF</a><br><a href="../index.html">Top</a></small><p><strong>Efficiency Guide</strong><br><strong>User's Guide</strong><br><small>Version 5.9.3.1</small></p> <br><a href="javascript:openAllFlips()">Expand All</a><br><a href="javascript:closeAllFlips()">Contract All</a><p><small><strong>Chapters</strong></small></p> <ul class="flipMenu" imagepath="../js/flipmenu"> <li id="no" title="Introduction" expanded="false">Introduction<ul> <li><a href="introduction.html"> Top of chapter </a></li> <li title="Purpose"><a href="introduction.html#id62954">Purpose</a></li> <li title="Prerequisites"><a href="introduction.html#id65420">Prerequisites</a></li> </ul> </li> <li id="loadscrollpos" title="The Eight Myths of Erlang Performance" expanded="true">The Eight Myths of Erlang Performance<ul> <li><a href="myths.html"> Top of chapter </a></li> <li title="Myth: Funs are slow"><a href="myths.html#id64448">Myth: Funs are slow</a></li> <li title="Myth: List comprehensions are slow"><a href="myths.html#id61406">Myth: List comprehensions are slow</a></li> <li title="Myth: Tail-recursive functions are MUCH faster than recursive functions"><a href="myths.html#id62291">Myth: Tail-recursive functions are MUCH faster than recursive functions</a></li> <li title="Myth: '++' is always bad"><a href="myths.html#id60058">Myth: '++' is always bad</a></li> <li title="Myth: Strings are slow"><a href="myths.html#id62534">Myth: Strings are slow</a></li> <li title="Myth: Repairing a Dets file is very slow"><a href="myths.html#id61135">Myth: Repairing a Dets file is very slow</a></li> <li title="Myth: BEAM is a stack-based byte-code virtual machine (and therefore slow)"><a href="myths.html#id64006">Myth: BEAM is a stack-based byte-code virtual machine (and therefore slow)</a></li> <li title="Myth: Use '_' to speed up your program when a variable is not used"><a href="myths.html#id64026">Myth: Use '_' to speed up your program when a variable is not used</a></li> </ul> </li> <li id="no" title="Common Caveats" expanded="false">Common Caveats<ul> <li><a href="commoncaveats.html"> Top of chapter </a></li> <li title="The timer module"><a href="commoncaveats.html#id62547">The timer module</a></li> <li title="list_to_atom/1"><a href="commoncaveats.html#id61885">list_to_atom/1</a></li> <li title="length/1"><a href="commoncaveats.html#id60806">length/1</a></li> <li title="setelement/3"><a href="commoncaveats.html#id58300">setelement/3</a></li> <li title="size/1"><a href="commoncaveats.html#id65402">size/1</a></li> <li title="split_binary/2"><a href="commoncaveats.html#id60836">split_binary/2</a></li> <li title="The '--' operator"><a href="commoncaveats.html#id61766">The '--' operator</a></li> </ul> </li> <li id="no" title="Constructing and matching binaries" expanded="false">Constructing and matching binaries<ul> <li><a href="binaryhandling.html"> Top of chapter </a></li> <li title="How binaries are implemented"><a href="binaryhandling.html#id62932">How binaries are implemented</a></li> <li title="Constructing binaries"><a href="binaryhandling.html#id66066">Constructing binaries</a></li> <li title="Matching binaries"><a href="binaryhandling.html#id63610">Matching binaries</a></li> </ul> </li> <li id="no" title="List handling" expanded="false">List handling<ul> <li><a href="listHandling.html"> Top of chapter </a></li> <li title="Creating a list"><a href="listHandling.html#id66709">Creating a list</a></li> <li title="List comprehensions"><a href="listHandling.html#id66805">List comprehensions</a></li> <li title="Deep and flat lists"><a href="listHandling.html#id66875">Deep and flat lists</a></li> <li title="Why you should not worry about recursive lists functions"><a href="listHandling.html#id67017">Why you should not worry about recursive lists functions</a></li> </ul> </li> <li id="no" title="Functions" expanded="false">Functions<ul> <li><a href="functions.html"> Top of chapter </a></li> <li title="Pattern matching"><a href="functions.html#id67142">Pattern matching</a></li> <li title="Function Calls "><a href="functions.html#id67362">Function Calls </a></li> <li title="Memory usage in recursion"><a href="functions.html#id67506">Memory usage in recursion</a></li> </ul> </li> <li id="no" title="Tables and databases" expanded="false">Tables and databases<ul> <li><a href="tablesDatabases.html"> Top of chapter </a></li> <li title="Ets, Dets and Mnesia"><a href="tablesDatabases.html#id67596">Ets, Dets and Mnesia</a></li> <li title="Ets specific"><a href="tablesDatabases.html#id67983">Ets specific</a></li> <li title="Mnesia specific"><a href="tablesDatabases.html#id68087">Mnesia specific</a></li> </ul> </li> <li id="no" title="Processes" expanded="false">Processes<ul> <li><a href="processes.html"> Top of chapter </a></li> <li title="Creation of an Erlang process"><a href="processes.html#id68191">Creation of an Erlang process</a></li> <li title="Process messages"><a href="processes.html#id68339">Process messages</a></li> <li title="The SMP emulator"><a href="processes.html#id68531">The SMP emulator</a></li> </ul> </li> <li id="no" title="Drivers" expanded="false">Drivers<ul> <li><a href="drivers.html"> Top of chapter </a></li> <li title="Drivers and concurrency"><a href="drivers.html#id68634">Drivers and concurrency</a></li> <li title="Avoiding copying of binaries when calling a driver"><a href="drivers.html#id68675">Avoiding copying of binaries when calling a driver</a></li> <li title="Returning small binaries from a driver"><a href="drivers.html#id68743">Returning small binaries from a driver</a></li> <li title="Returning big binaries without copying from a driver"><a href="drivers.html#id68777">Returning big binaries without copying from a driver</a></li> </ul> </li> <li id="no" title="Advanced" expanded="false">Advanced<ul> <li><a href="advanced.html"> Top of chapter </a></li> <li title="Memory"><a href="advanced.html#id68919">Memory</a></li> <li title="System limits"><a href="advanced.html#id69276">System limits</a></li> </ul> </li> <li id="no" title="Profiling" expanded="false">Profiling<ul> <li><a href="profiling.html"> Top of chapter </a></li> <li title="Do not guess about performance - profile"><a href="profiling.html#id69579">Do not guess about performance - profile</a></li> <li title="Big systems"><a href="profiling.html#id69661">Big systems</a></li> <li title="What to look for"><a href="profiling.html#id69681">What to look for</a></li> <li title="Tools"><a href="profiling.html#id69738">Tools</a></li> <li title="Benchmarking"><a href="profiling.html#id70245">Benchmarking</a></li> </ul> </li> </ul> </div></div> <div id="content"> <div class="innertube"> <h1>2 The Eight Myths of Erlang Performance</h1> <p>Some truths seem to live on well beyond their best-before date, perhaps because "information" spreads more rapidly from person-to-person faster than a single release note that notes, for instance, that funs have become faster.</p> <p>Here we try to kill the old truths (or semi-truths) that have become myths.</p> <h3><a name="id64448">2.1 Myth: Funs are slow</a></h3> <p>Yes, funs used to be slow. Very slow. Slower than <span class="code">apply/3</span>. Originally, funs were implemented using nothing more than compiler trickery, ordinary tuples, <span class="code">apply/3</span>, and a great deal of ingenuity.</p> <p>But that is ancient history. Funs was given its own data type in the R6B release and was further optimized in the R7B release. Now the cost for a fun call falls roughly between the cost for a call to local function and <span class="code">apply/3</span>.</p> <h3><a name="id61406">2.2 Myth: List comprehensions are slow</a></h3> <p>List comprehensions used to be implemented using funs, and in the bad old days funs were really slow.</p> <p>Nowadays the compiler rewrites list comprehensions into an ordinary recursive function. Of course, using a tail-recursive function with a reverse at the end would be still faster. Or would it? That leads us to the next myth.</p> <h3><a name="id62291">2.3 Myth: Tail-recursive functions are MUCH faster than recursive functions</a></h3> <p><a name="tail_recursive"></a>According to the myth, recursive functions leave references to dead terms on the stack and the garbage collector will have to copy all those dead terms, while tail-recursive functions immediately discard those terms.</p> <p>That used to be true before R7B. In R7B, the compiler started to generate code that overwrites references to terms that will never be used with an empty list, so that the garbage collector would not keep dead values any longer than necessary.</p> <p>Even after that optimization, a tail-recursive function would still most of the time be faster than a body-recursive function. Why?</p> <p>It has to do with how many words of stack that are used in each recursive call. In most cases, a recursive function would use more words on the stack for each recursion than the number of words a tail-recursive would allocate on the heap. Since more memory is used, the garbage collector will be invoked more frequently, and it will have more work traversing the stack.</p> <p>In R12B and later releases, there is an optimization that will in many cases reduces the number of words used on the stack in body-recursive calls, so that a body-recursive list function and tail-recursive function that calls <span class="bold_code"><a href="javascript:erlhref('../../','stdlib','lists.html#reverse-1');">lists:reverse/1</a></span> at the end will use exactly the same amount of memory. <span class="code">lists:map/2</span>, <span class="code">lists:filter/2</span>, list comprehensions, and many other recursive functions now use the same amount of space as their tail-recursive equivalents.</p> <p>So which is faster?</p> <p>It depends. On Solaris/Sparc, the body-recursive function seems to be slightly faster, even for lists with very many elements. On the x86 architecture, tail-recursion was up to about 30 percent faster.</p> <p>So the choice is now mostly a matter of taste. If you really do need the utmost speed, you must <strong>measure</strong>. You can no longer be absolutely sure that the tail-recursive list function will be the fastest in all circumstances.</p> <p>Note: A tail-recursive function that does not need to reverse the list at the end is, of course, faster than a body-recursive function, as are tail-recursive functions that do not construct any terms at all (for instance, a function that sums all integers in a list).</p> <h3><a name="id60058">2.4 Myth: '++' is always bad</a></h3> <p>The <span class="code">++</span> operator has, somewhat undeservedly, got a very bad reputation. It probably has something to do with code like</p> <p><strong>DO NOT</strong></p> <div class="example"><pre> naive_reverse([H|T]) -> naive_reverse(T)++[H]; naive_reverse([]) -> [].</pre></div> <p>which is the most inefficient way there is to reverse a list. Since the <span class="code">++</span> operator copies its left operand, the result will be copied again and again and again... leading to quadratic complexity.</p> <p>On the other hand, using <span class="code">++</span> like this</p> <p><strong>OK</strong></p> <div class="example"><pre> naive_but_ok_reverse([H|T], Acc) -> naive_but_ok_reverse(T, [H]++Acc); naive_but_ok_reverse([], Acc) -> Acc.</pre></div> <p>is not bad. Each list element will only be copied once. The growing result <span class="code">Acc</span> is the right operand for the <span class="code">++</span> operator, and it will <strong>not</strong> be copied.</p> <p>Of course, experienced Erlang programmers would actually write</p> <p><strong>DO</strong></p> <div class="example"><pre> vanilla_reverse([H|T], Acc) -> vanilla_reverse(T, [H|Acc]); vanilla_reverse([], Acc) -> Acc.</pre></div> <p>which is slightly more efficient because you don't build a list element only to directly copy it. (Or it would be more efficient if the the compiler did not automatically rewrite <span class="code">[H]++Acc</span> to <span class="code">[H|Acc]</span>.)</p> <h3><a name="id62534">2.5 Myth: Strings are slow</a></h3> <p>Actually, string handling could be slow if done improperly. In Erlang, you'll have to think a little more about how the strings are used and choose an appropriate representation and use the <span class="bold_code"><a href="javascript:erlhref('../../','stdlib','re.html');">re</a></span> module instead of the obsolete <span class="code">regexp</span> module if you are going to use regular expressions.</p> <h3><a name="id61135">2.6 Myth: Repairing a Dets file is very slow</a></h3> <p>The repair time is still proportional to the number of records in the file, but Dets repairs used to be much, much slower in the past. Dets has been massively rewritten and improved.</p> <h3><a name="id64006">2.7 Myth: BEAM is a stack-based byte-code virtual machine (and therefore slow)</a></h3> <p>BEAM is a register-based virtual machine. It has 1024 virtual registers that are used for holding temporary values and for passing arguments when calling functions. Variables that need to survive a function call are saved to the stack.</p> <p>BEAM is a threaded-code interpreter. Each instruction is word pointing directly to executable C-code, making instruction dispatching very fast.</p> <h3><a name="id64026">2.8 Myth: Use '_' to speed up your program when a variable is not used</a></h3> <p>That was once true, but since R6B the BEAM compiler is quite capable of seeing itself that a variable is not used.</p> </div> <div class="footer"> <hr> <p>Copyright © 2001-2012 Ericsson AB. All Rights Reserved.</p> </div> </div> </div></body> </html>