From bf5886b790f8f386ed425f543506a4bebb48448c Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?John=20H=C3=B6gberg?= <john@erlang.org>
Date: Mon, 15 Oct 2018 18:17:12 +0200
Subject: Optimize operator '--' and yield on large inputs

The removal set now uses a red-black tree instead of an array on
large inputs, decreasing runtime complexity from `n*n` to
`n*log(n)`. It will also exit early when there are no more items
left in the removal set, drastically improving performance and
memory use when the items to be removed are present near the head
of the list.

This got a lot more complicated than before as the overhead of
always using a red-black tree was unacceptable when either of the
inputs were small, but this compromise has okay-to-decent
performance regardless of input size.

Co-authored-by: Dmytro Lytovchenko <dmytro.lytovchenko@erlang-solutions.com>
---
 lib/stdlib/doc/src/lists.xml | 8 --------
 1 file changed, 8 deletions(-)

(limited to 'lib/stdlib/doc')

diff --git a/lib/stdlib/doc/src/lists.xml b/lib/stdlib/doc/src/lists.xml
index 7efafedc82..55227aaee5 100644
--- a/lib/stdlib/doc/src/lists.xml
+++ b/lib/stdlib/doc/src/lists.xml
@@ -838,14 +838,6 @@ splitwith(Pred, List) ->
 > <input>lists:subtract("123212", "212").</input>
 "312".</pre>
         <p><c>lists:subtract(A, B)</c> is equivalent to <c>A -- B</c>.</p>
-        <warning>
-          <p>The complexity of <c>lists:subtract(A, B)</c> is proportional to
-            <c>length(A)*length(B)</c>, meaning that it is very slow if both
-            <c>A</c> and <c>B</c> are long lists. (If both lists are long, it
-            is a much better choice to use ordered lists and
-            <seealso marker="ordsets#subtract/2">
-            <c>ordsets:subtract/2</c></seealso>.</p>
-        </warning>
       </desc>
     </func>
 
-- 
cgit v1.2.3


From f5313be396144700acff451279062dab9674e436 Mon Sep 17 00:00:00 2001
From: Erlang/OTP <otp@erlang.org>
Date: Mon, 5 Nov 2018 10:48:29 +0100
Subject: Prepare release

---
 lib/stdlib/doc/src/notes.xml | 15 +++++++++++++++
 1 file changed, 15 insertions(+)

(limited to 'lib/stdlib/doc')

diff --git a/lib/stdlib/doc/src/notes.xml b/lib/stdlib/doc/src/notes.xml
index e26c4aba74..3c7c8bf400 100644
--- a/lib/stdlib/doc/src/notes.xml
+++ b/lib/stdlib/doc/src/notes.xml
@@ -31,6 +31,21 @@
   </header>
   <p>This document describes the changes made to the STDLIB application.</p>
 
+<section><title>STDLIB 3.4.5.1</title>
+
+    <section><title>Improvements and New Features</title>
+      <list>
+        <item>
+	    <p>List subtraction (The <c>--</c> operator) will now
+	    yield properly on large inputs.</p>
+          <p>
+	    Own Id: OTP-15371</p>
+        </item>
+      </list>
+    </section>
+
+</section>
+
 <section><title>STDLIB 3.4.5</title>
 
     <section><title>Fixed Bugs and Malfunctions</title>
-- 
cgit v1.2.3