From 1cc8044ffc6073749e34dcf1434f02272fe4b457 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Tue, 7 Jun 2016 15:14:16 +0200 Subject: Retire two myths --- system/doc/efficiency_guide/myths.xml | 31 ++----------- system/doc/efficiency_guide/part.xml | 1 + system/doc/efficiency_guide/retired_myths.xml | 63 +++++++++++++++++++++++++++ 3 files changed, 67 insertions(+), 28 deletions(-) create mode 100644 system/doc/efficiency_guide/retired_myths.xml (limited to 'system/doc/efficiency_guide') diff --git a/system/doc/efficiency_guide/myths.xml b/system/doc/efficiency_guide/myths.xml index 5d3ad78b23..7e2f3c8465 100644 --- a/system/doc/efficiency_guide/myths.xml +++ b/system/doc/efficiency_guide/myths.xml @@ -24,7 +24,7 @@ The Initial Developer of the Original Code is Ericsson AB. - The Eight Myths of Erlang Performance + The Six Myths of Erlang Performance Bjorn Gustavsson 2007-11-10 @@ -35,37 +35,12 @@

Some truths seem to live on well beyond their best-before date, perhaps because "information" spreads faster from person-to-person - than a single release note that says, for example, that funs - have become faster.

+ than a single release note that says, for example, that body-recursive + calls have become faster.

This section tries to kill the old truths (or semi-truths) that have become myths.

-
- Myth: Funs are Slow -

Funs used to be very slow, slower than apply/3. - Originally, funs were implemented using nothing more than - compiler trickery, ordinary tuples, apply/3, and a great - deal of ingenuity.

- -

But that is history. Funs was given its own data type - in R6B and was further optimized in R7B. - Now the cost for a fun call falls roughly between the cost for a call - to a local function and apply/3.

-
- -
- Myth: List Comprehensions are Slow - -

List comprehensions used to be implemented using funs, and in the - old days funs were indeed slow.

- -

Nowadays, the compiler rewrites list comprehensions into an ordinary - recursive function. 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.

-
-
Myth: Tail-Recursive Functions are Much Faster Than Recursive Functions diff --git a/system/doc/efficiency_guide/part.xml b/system/doc/efficiency_guide/part.xml index 6e10a0c031..5673ddd320 100644 --- a/system/doc/efficiency_guide/part.xml +++ b/system/doc/efficiency_guide/part.xml @@ -39,5 +39,6 @@ + diff --git a/system/doc/efficiency_guide/retired_myths.xml b/system/doc/efficiency_guide/retired_myths.xml new file mode 100644 index 0000000000..37f46566cd --- /dev/null +++ b/system/doc/efficiency_guide/retired_myths.xml @@ -0,0 +1,63 @@ + + + + +
+ + 2016 + 2016 + Ericsson AB, All Rights Reserved + + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. + + The Initial Developer of the Original Code is Ericsson AB. + + + Retired Myths + Bjorn Gustavsson + + 2016-06-07 + + retired_myths.xml +
+ +

We belive that the truth finally has caught with the following, + retired myths.

+ +
+ Myth: Funs are Slow +

Funs used to be very slow, slower than apply/3. + Originally, funs were implemented using nothing more than + compiler trickery, ordinary tuples, apply/3, and a great + deal of ingenuity.

+ +

But that is history. Funs was given its own data type + in R6B and was further optimized in R7B. + Now the cost for a fun call falls roughly between the cost for a call + to a local function and apply/3.

+
+ +
+ Myth: List Comprehensions are Slow + +

List comprehensions used to be implemented using funs, and in the + old days funs were indeed slow.

+ +

Nowadays, the compiler rewrites list comprehensions into an ordinary + recursive function. Using a tail-recursive function with + a reverse at the end would be still faster. Or would it? + That leads us to the myth that tail-recursive functions are faster + than body-recursive functions.

+
+ -- cgit v1.2.3 From 1c82039a53fa0885fc8a292a841c6939e04a0da2 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Tue, 7 Jun 2016 16:16:26 +0200 Subject: Add a myth about NIFs Thanks to Max Lapshin for suggesting this myth. --- system/doc/efficiency_guide/myths.xml | 20 +++++++++++++++++++- 1 file changed, 19 insertions(+), 1 deletion(-) (limited to 'system/doc/efficiency_guide') diff --git a/system/doc/efficiency_guide/myths.xml b/system/doc/efficiency_guide/myths.xml index 7e2f3c8465..d6cb27ddf0 100644 --- a/system/doc/efficiency_guide/myths.xml +++ b/system/doc/efficiency_guide/myths.xml @@ -24,7 +24,7 @@ The Initial Developer of the Original Code is Ericsson AB. - The Six Myths of Erlang Performance + The Seven Myths of Erlang Performance Bjorn Gustavsson 2007-11-10 @@ -175,5 +175,23 @@ vanilla_reverse([], Acc) ->

That was once true, but from R6B the BEAM compiler can see that a variable is not used.

+ +
+ Myth: A NIF Always Speeds Up Your Program + +

Rewriting Erlang code to a NIF to make it faster should be + seen as a last resort. It is only guaranteed to be dangerous, + but not guaranteed to speed up the program.

+ +

Doing too much work in each NIF call will + degrade responsiveness + of the VM. Doing too little work may mean that + the gain of the faster processing in the NIF is eaten up by + the overhead of calling the NIF and checking the arguments.

+ +

Be sure to read about + Long-running NIFs + before writing a NIF.

+
-- cgit v1.2.3 From 15da52e7c74d3a0406efdfd469a040a5a226704e Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Tue, 13 Dec 2016 14:02:34 +0100 Subject: Shorten the tail-recursion myth The myth about tail recursion being faster than body recursion still seems to be alive, but we don't need to spend that much space discussing it as we needed earlier. Shorten the discussion and include a link to to Fred Hebert's excellent blog post. --- system/doc/efficiency_guide/myths.xml | 54 +++++++++++------------------------ 1 file changed, 16 insertions(+), 38 deletions(-) (limited to 'system/doc/efficiency_guide') diff --git a/system/doc/efficiency_guide/myths.xml b/system/doc/efficiency_guide/myths.xml index d6cb27ddf0..168aa3d35c 100644 --- a/system/doc/efficiency_guide/myths.xml +++ b/system/doc/efficiency_guide/myths.xml @@ -46,44 +46,22 @@ Than Recursive Functions

According to the myth, - recursive functions leave references - to dead terms on the stack and the garbage collector has to copy - all those dead terms, while tail-recursive functions immediately - discard those terms.

- -

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.

- -

Even after that optimization, a tail-recursive function is - still most of the times faster than a body-recursive function. Why?

- -

It has to do with how many words of stack that are used in each - recursive call. In most cases, a recursive function uses more words - on the stack for each recursion than the number of words a tail-recursive - would allocate on the heap. As more memory is used, the garbage - collector is invoked more frequently, and it has more work traversing - the stack.

- -

In R12B and later releases, there is an optimization that - in many cases reduces the number of words used on the stack in - body-recursive calls. A body-recursive list function and a - tail-recursive function that calls lists:reverse/1 at - the end will use the same amount of memory. - lists:map/2, lists:filter/2, list comprehensions, - and many other recursive functions now use the same amount of space - as their tail-recursive equivalents.

- -

So, which is faster? - It depends. On Solaris/Sparc, the body-recursive function seems to - be slightly faster, even for lists with a lot of elements. On the x86 - architecture, tail-recursion was up to about 30% faster.

- -

So, the choice is now mostly a matter of taste. If you really do need - the utmost speed, you must measure. You can no longer be - sure that the tail-recursive list function always is the fastest.

+ using a tail-recursive function that builds a list in reverse + followed by a call to lists:reverse/1 is faster than + a body-recursive function that builds the list in correct order; + the reason being that body-recursive functions use more memory than + tail-recursive functions.

+ +

That was true to some extent before R12B. It was even more true + before R7B. Today, not so much. A body-recursive function + generally uses the same amount of memory as a tail-recursive + function. It is generally not possible to predict whether the + tail-recursive or the body-recursive version will be + faster. Therefore, use the version that makes your code cleaner + (hint: it is usually the body-recursive version).

+ +

For a more thorough discussion about tail and body recursion, + see Erlang's Tail Recursion is Not a Silver Bullet.

A tail-recursive function that does not need to reverse the list at the end is faster than a body-recursive function, -- cgit v1.2.3 From 6ecbfdcce4dc8b1c58a4f34e2edd8eaabd54793f Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Tue, 13 Dec 2016 14:17:03 +0100 Subject: Extend the text for "_" myth Thanks to Joe Armstrong for the suggestion. --- system/doc/efficiency_guide/myths.xml | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'system/doc/efficiency_guide') diff --git a/system/doc/efficiency_guide/myths.xml b/system/doc/efficiency_guide/myths.xml index 168aa3d35c..778cd06c09 100644 --- a/system/doc/efficiency_guide/myths.xml +++ b/system/doc/efficiency_guide/myths.xml @@ -152,6 +152,11 @@ vanilla_reverse([], Acc) ->

That was once true, but from R6B the BEAM compiler can see that a variable is not used.

+ +

Similarly, trivial transformations on the source-code level + such as converting a case statement to clauses at the + top-level of the function seldom makes any difference to the + generated code.

-- cgit v1.2.3