From bf5886b790f8f386ed425f543506a4bebb48448c Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= 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 --- lib/stdlib/doc/src/lists.xml | 8 -------- lib/stdlib/test/lists_SUITE.erl | 42 +++++++++++++++++++++++++++++++++++++++++ 2 files changed, 42 insertions(+), 8 deletions(-) (limited to 'lib') 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) -> > lists:subtract("123212", "212"). "312".

lists:subtract(A, B) is equivalent to A -- B.

- -

The complexity of lists:subtract(A, B) is proportional to - length(A)*length(B), meaning that it is very slow if both - A and B are long lists. (If both lists are long, it - is a much better choice to use ordered lists and - - ordsets:subtract/2.

- diff --git a/lib/stdlib/test/lists_SUITE.erl b/lib/stdlib/test/lists_SUITE.erl index 7c99244b36..c380b3bba1 100644 --- a/lib/stdlib/test/lists_SUITE.erl +++ b/lib/stdlib/test/lists_SUITE.erl @@ -2597,6 +2597,13 @@ subtract(Config) when is_list(Config) -> {'EXIT',_} = (catch sub([a|b], [])), {'EXIT',_} = (catch sub([a|b], [a])), + %% Trapping, both crashing and otherwise. + [sub_trapping(N) || N <- lists:seq(0, 18)], + + %% The current implementation chooses which algorithm to use based on + %% certain thresholds, and we need proper coverage for all corner cases. + [sub_thresholds(N) || N <- lists:seq(0, 32)], + ok. sub_non_matching(A, B) -> @@ -2606,6 +2613,41 @@ sub(A, B) -> Res = A -- B, Res = lists:subtract(A, B). +sub_trapping(N) -> + List = lists:duplicate(N + (1 bsl N), gurka), + ImproperList = List ++ crash, + + {'EXIT',_} = (catch sub_trapping_1(ImproperList, [])), + {'EXIT',_} = (catch sub_trapping_1(List, ImproperList)), + + List = List -- lists:duplicate(N + (1 bsl N), gaffel), + ok = sub_trapping_1(List, []). + +sub_trapping_1([], _) -> ok; +sub_trapping_1(L, R) -> sub_trapping_1(L -- R, [gurka | R]). + +sub_thresholds(N) -> + %% This needs to be long enough to cause trapping. + OtherLen = 1 bsl 18, + Other = lists:seq(0, OtherLen - 1), + + Disjoint = lists:seq(-N, -1), + Subset = lists:seq(1, N), + + %% LHS is disjoint from RHS, so all elements must be retained. + Disjoint = Disjoint -- Other, + + %% LHS is covered by RHS, so all elements must be removed. + [] = Subset -- Other, + + %% RHS is disjoint from LHS, so all elements must be retained. + Other = Other -- Disjoint, + + %% RHS is covered by LHS, so N elements must be removed. + N = OtherLen - length(Other -- Subset), + + ok. + %% Test lists:droplast/1 droplast(Config) when is_list(Config) -> [] = lists:droplast([x]), -- cgit v1.2.3 From f5313be396144700acff451279062dab9674e436 Mon Sep 17 00:00:00 2001 From: Erlang/OTP Date: Mon, 5 Nov 2018 10:48:29 +0100 Subject: Prepare release --- lib/ssl/doc/src/notes.xml | 17 +++++++++++++++++ lib/ssl/vsn.mk | 2 +- lib/stdlib/doc/src/notes.xml | 15 +++++++++++++++ lib/stdlib/vsn.mk | 2 +- 4 files changed, 34 insertions(+), 2 deletions(-) (limited to 'lib') diff --git a/lib/ssl/doc/src/notes.xml b/lib/ssl/doc/src/notes.xml index b2a774adf0..04fc3e1492 100644 --- a/lib/ssl/doc/src/notes.xml +++ b/lib/ssl/doc/src/notes.xml @@ -27,6 +27,23 @@

This document describes the changes made to the SSL application.

+
SSL 8.2.6.3 + +
Fixed Bugs and Malfunctions + + +

+ Extend check for undelivered data at closing, could under + some circumstances fail to deliverd all data that was + acctualy recivied.

+

+ Own Id: OTP-15412

+ + +
+ +
+
SSL 8.2.6.2
Fixed Bugs and Malfunctions diff --git a/lib/ssl/vsn.mk b/lib/ssl/vsn.mk index b46c1334cf..08fb667f83 100644 --- a/lib/ssl/vsn.mk +++ b/lib/ssl/vsn.mk @@ -1 +1 @@ -SSL_VSN = 8.2.6.2 +SSL_VSN = 8.2.6.3 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 @@

This document describes the changes made to the STDLIB application.

+
STDLIB 3.4.5.1 + +
Improvements and New Features + + +

List subtraction (The -- operator) will now + yield properly on large inputs.

+

+ Own Id: OTP-15371

+ + +
+ +
+
STDLIB 3.4.5
Fixed Bugs and Malfunctions diff --git a/lib/stdlib/vsn.mk b/lib/stdlib/vsn.mk index 09a4d6fb50..34ba8c083d 100644 --- a/lib/stdlib/vsn.mk +++ b/lib/stdlib/vsn.mk @@ -1 +1 @@ -STDLIB_VSN = 3.4.5 +STDLIB_VSN = 3.4.5.1 -- cgit v1.2.3