aboutsummaryrefslogtreecommitdiffstats
path: root/system
diff options
context:
space:
mode:
authorJohn Högberg <[email protected]>2018-11-02 09:38:40 +0100
committerJohn Högberg <[email protected]>2018-11-02 09:38:40 +0100
commitf668717abf3a28692b7aa096ad7a776eb8738c7a (patch)
tree3ceb3a335f26361011de997e26740b37b1d5657e /system
parent69797ce56c590125a664b24e16e4e6691d948883 (diff)
parent7999ddad6121db7d1b7fe44b3c6a80a8d7ff70f3 (diff)
downloadotp-f668717abf3a28692b7aa096ad7a776eb8738c7a.tar.gz
otp-f668717abf3a28692b7aa096ad7a776eb8738c7a.tar.bz2
otp-f668717abf3a28692b7aa096ad7a776eb8738c7a.zip
Merge branch 'maint'
* maint: Optimize operator '--' and yield on large inputs Inline erts_cmp Clarify a magical allocation size Fix trapping in lists:reverse/2
Diffstat (limited to 'system')
-rw-r--r--system/doc/efficiency_guide/commoncaveats.xml48
-rw-r--r--system/doc/efficiency_guide/retired_myths.xml14
2 files changed, 14 insertions, 48 deletions
diff --git a/system/doc/efficiency_guide/commoncaveats.xml b/system/doc/efficiency_guide/commoncaveats.xml
index b41ffc3902..367da09ba3 100644
--- a/system/doc/efficiency_guide/commoncaveats.xml
+++ b/system/doc/efficiency_guide/commoncaveats.xml
@@ -169,53 +169,5 @@ multiple_setelement(T0) ->
{Bin1,Bin2} = split_binary(Bin, Num)</code>
</section>
- <section>
- <title>Operator "--"</title>
- <p>The "<c>--</c>" operator has a complexity
- proportional to the product of the length of its operands.
- This means that the operator is very slow if both of its operands
- are long lists:</p>
-
- <p><em>DO NOT</em></p>
- <code type="none"><![CDATA[
- HugeList1 -- HugeList2]]></code>
-
- <p>Instead use the <seealso marker="stdlib:ordsets">ordsets</seealso>
- module in STDLIB:</p>
-
- <p><em>DO</em></p>
- <code type="none">
- HugeSet1 = ordsets:from_list(HugeList1),
- HugeSet2 = ordsets:from_list(HugeList2),
- ordsets:subtract(HugeSet1, HugeSet2)</code>
-
- <p>Obviously, that code does not work if the original order
- of the list is important. If the order of the list must be
- preserved, do as follows:</p>
-
- <p><em>DO</em></p>
- <code type="none"><![CDATA[
- Set = gb_sets:from_list(HugeList2),
- [E || E <- HugeList1, not gb_sets:is_element(E, Set)]]]></code>
-
- <note><p>This code behaves differently from "<c>--</c>"
- if the lists contain duplicate elements (one occurrence
- of an element in HugeList2 removes <em>all</em>
- occurrences in HugeList1.)</p>
- <p>Also, this code compares lists elements using the
- "<c>==</c>" operator, while "<c>--</c>" uses the "<c>=:=</c>" operator.
- If that difference is important, <c>sets</c> can be used instead of
- <c>gb_sets</c>, but <c>sets:from_list/1</c> is much
- slower than <c>gb_sets:from_list/1</c> for long lists.</p></note>
-
- <p>Using the "<c>--</c>" operator to delete an element
- from a list is not a performance problem:</p>
-
- <p><em>OK</em></p>
- <code type="none">
- HugeList1 -- [Element]</code>
-
- </section>
-
</chapter>
diff --git a/system/doc/efficiency_guide/retired_myths.xml b/system/doc/efficiency_guide/retired_myths.xml
index 9b914a3b6e..144c942c2b 100644
--- a/system/doc/efficiency_guide/retired_myths.xml
+++ b/system/doc/efficiency_guide/retired_myths.xml
@@ -60,4 +60,18 @@
That leads us to the myth that tail-recursive functions are faster
than body-recursive functions.</p>
</section>
+
+ <section>
+ <title>Myth: List subtraction ("--" operator) is slow</title>
+
+ <p>List subtraction used to have a run-time complexity proportional to the
+ product of the length of its operands, so it was extremely slow when both
+ lists were long.</p>
+
+ <p>As of OTP 22 the run-time complexity is "n log n" and the operation will
+ complete quickly even when both lists are very long. In fact, it is
+ faster and uses less memory than the commonly used workaround to convert
+ both lists to ordered sets before subtracting them with
+ <c>ordsets:subtract/2</c>.</p>
+ </section>
</chapter>