[couchdb] 04/05: Optimize umerge_members

[da...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

davisp pushed a commit to branch prototype/fdb-layer
in repository https://gitbox.apache.org/repos/asf/couchdb.git

commit 2dd85afd59d409617b974ca07924c22ec2979c50
Author: Paul J. Davis <pa...@gmail.com>
AuthorDate: Thu Aug 27 11:26:33 2020 -0500

    Optimize umerge_members
    
    Using lists:umerge/3 adds extra invocations of the collation algorithm
    because its using `=<` semantics when ebtree collations are capable of
    producing `lt, eq, gt` results.
---
 src/ebtree/src/ebtree.erl | 24 ++++++++++++++++++++----
 1 file changed, 20 insertions(+), 4 deletions(-)

diff --git a/src/ebtree/src/ebtree.erl b/src/ebtree/src/ebtree.erl
index 680bf1d..ea445ea 100644
--- a/src/ebtree/src/ebtree.erl
+++ b/src/ebtree/src/ebtree.erl
@@ -1161,13 +1161,29 @@ collate(#tree{} = Tree, A, B, Allowed) ->
 
 
 umerge_members(#tree{} = Tree, Level, List1, List2) ->
-    CollateWrapper = fun
+    Collate = fun
         ({K1, _V1}, {K2, _V2}) when Level == 0 ->
-            collate(Tree, K1, K2, [lt, eq]);
+            collate(Tree, K1, K2);
         ({_F1, L1, _V1, _R1}, {_F2, L2, _V2, _R2}) when Level > 0 ->
-            collate(Tree, L1, L2, [lt, eq])
+            collate(Tree, L1, L2)
     end,
-    lists:umerge(CollateWrapper, List1, List2).
+    umerge_members_int(Collate, List1, List2, []).
+
+
+umerge_members_int(Collate, [], [H2 | T2], [HAcc | _] = Acc) ->
+    case Collate(H2, HAcc) of
+        lt -> erlang:error(unsorted_members);
+        eq -> lists:reverse(Acc, T2);
+        gt -> lists:reverse(Acc, [H2 | T2])
+    end;
+umerge_members_int(_Collate, List1, [], Acc) ->
+    lists:reverse(Acc, List1);
+umerge_members_int(Collate, [H1 | T1], [H2 | T2], Acc) ->
+    case Collate(H1, H2) of
+        lt -> umerge_members_int(Collate, T1, [H2 | T2], [H1 | Acc]);
+        eq -> umerge_members_int(Collate, T1, [H2 | T2], [H1 | Acc]);
+        gt -> umerge_members_int(Collate, [H1 | T1], T2, [H2 | Acc])
+    end.
 
 
 sort_keys(#tree{} = Tree, List) ->