You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@couchdb.apache.org by ko...@apache.org on 2018/05/30 21:48:07 UTC
[couchdb-hyper] branch remove-bisect updated (55724d7 -> 53a5679)
This is an automated email from the ASF dual-hosted git repository.
kocolosk pushed a change to branch remove-bisect
in repository https://gitbox.apache.org/repos/asf/couchdb-hyper.git.
discard 55724d7 Remove bisect implementation
new 53a5679 Remove bisect implementation
This update added new revisions after undoing existing revisions.
That is to say, some revisions that were in the old version of the
branch are not in the new version. This situation occurs
when a user --force pushes a change and generates a repository
containing something like this:
* -- * -- B -- O -- O -- O (55724d7)
\
N -- N -- N refs/heads/remove-bisect (53a5679)
You should already have received notification emails for all of the O
revisions, and so the following emails describe only the N revisions
from the common base, B.
Any revisions marked "omit" are not gone; other references still
refer to them. Any revisions marked "discard" are gone forever.
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
Summary of changes:
src/hyper_binary.erl | 318 +++++++++++++++++++++++++++++++++++++++++++++++++++
src/hyper_bisect.erl | 250 ----------------------------------------
2 files changed, 318 insertions(+), 250 deletions(-)
create mode 100644 src/hyper_binary.erl
delete mode 100644 src/hyper_bisect.erl
--
To stop receiving notification emails like this one, please contact
kocolosk@apache.org.
[couchdb-hyper] 01/01: Remove bisect implementation
Posted by ko...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
kocolosk pushed a commit to branch remove-bisect
in repository https://gitbox.apache.org/repos/asf/couchdb-hyper.git
commit 53a5679168a85ef11974817de83671135835465a
Author: Adam Kocoloski <ko...@apache.org>
AuthorDate: Wed May 30 17:42:38 2018 -0400
Remove bisect implementation
We're not using this backend, and it requires R17 (we are still
supporting R16 as of this writing).
---
rebar-test.config | 2 -
rebar.config | 5 --
src/hyper_bisect.erl | 250 ---------------------------------------------------
3 files changed, 257 deletions(-)
diff --git a/rebar-test.config b/rebar-test.config
index 170844e..160b729 100644
--- a/rebar-test.config
+++ b/rebar-test.config
@@ -2,8 +2,6 @@
{deps, [
{basho_stats, "",
{git, "https://github.com/knutin/basho_stats.git", {branch, "master"}}},
- {bisect, "",
- {git, "https://github.com/knutin/bisect.git", {branch, "master"}}},
{proper, "",
{git,"https://github.com/manopapad/proper.git", "master"}},
{stdlib2, "",
diff --git a/rebar.config b/rebar.config
index 5cf51a1..0382632 100644
--- a/rebar.config
+++ b/rebar.config
@@ -1,9 +1,4 @@
{cover_enabled, true}.
-{deps, [
- {bisect, "",
- {git, "https://github.com/knutin/bisect.git", {branch, "master"}}}
- ]}.
-
{port_specs, [
{"priv/hyper_carray.so", ["c_src/hyper_carray.c"]}
diff --git a/src/hyper_bisect.erl b/src/hyper_bisect.erl
deleted file mode 100644
index 2c31521..0000000
--- a/src/hyper_bisect.erl
+++ /dev/null
@@ -1,250 +0,0 @@
--module(hyper_bisect).
--include_lib("eunit/include/eunit.hrl").
--behaviour(hyper_register).
-
--export([new/1,
- set/3,
- max_merge/1,
- max_merge/2,
- reduce_precision/2,
- bytes/1,
- register_sum/1,
- zero_count/1,
- encode_registers/1,
- decode_registers/2,
- compact/1]).
-
-
--define(KEY_SIZE, 16).
--define(VALUE_SIZE, 8).
-
-%%
-%% BEHAVIOUR
-%%
-
-new(P) ->
- DenseSize = trunc(math:pow(2, P)),
- EntrySize = (?KEY_SIZE + ?VALUE_SIZE) div 8,
- Threshold = DenseSize div EntrySize,
- {sparse, bisect:new(?KEY_SIZE div 8, ?VALUE_SIZE div 8), P, Threshold}.
-
-
-set(Index, Value, {sparse, B, P, Threshold}) ->
- V = <<Value:?VALUE_SIZE/integer>>,
- UpdateF = fun (OldValue) when OldValue >= V -> OldValue;
- (OldValue) when OldValue < V -> V
- end,
- NewB = bisect:update(B, <<Index:?KEY_SIZE/integer>>, V, UpdateF),
-
- case bisect:num_keys(NewB) < Threshold of
- true ->
- {sparse, NewB, P, Threshold};
- false ->
- {dense, bisect2dense(NewB, P)}
- end;
-
-set(Index, Value, {dense, B} = D) ->
- case binary:at(B, Index) of
- R when R > Value ->
- D;
- _ ->
- <<Left:Index/binary, _:?VALUE_SIZE, Right/binary>> = B,
- {dense, iolist_to_binary([Left, <<Value:?VALUE_SIZE/integer>>, Right])}
- end.
-
-
-
-fold(F, Acc, {sparse, B, _, _}) ->
- InterfaceF = fun (<<Index:?KEY_SIZE/integer>>,
- <<Value:?VALUE_SIZE/integer>>,
- A) ->
- F(Index, Value, A)
- end,
- bisect:foldl(B, InterfaceF, Acc);
-fold(F, Acc, {dense, B}) ->
- do_dense_fold(F, Acc, B).
-
-
-max_merge(Registers) ->
- [First | Rest] = Registers,
- lists:foldl(fun max_merge/2, First, Rest).
-
-
-
-max_merge({sparse, Small, P, T}, {sparse, Big, P, T}) ->
- ToInsert = bisect:foldl(Small,
- fun (Index, Value, Acc) ->
- case bisect:find(Big, Index) of
- not_found ->
- [{Index, Value} | Acc];
- V when V >= Value ->
- Acc;
- V when V < Value ->
- [{Index, Value} | Acc]
- end
- end,
- []),
- Merged = bisect:bulk_insert(Big, lists:sort(ToInsert)),
- {sparse, Merged, P, T};
-
-
-max_merge({dense, Left}, {dense, Right}) ->
- Merged = iolist_to_binary(
- do_dense_merge(Left, Right)),
- {dense, Merged};
-
-max_merge({dense, Dense}, {sparse, Sparse, P, _}) ->
- {dense, iolist_to_binary(
- do_dense_merge(Dense, bisect2dense(Sparse, P)))};
-
-max_merge({sparse, Sparse, P, _}, {dense, Dense}) ->
- {dense, iolist_to_binary(
- do_dense_merge(Dense, bisect2dense(Sparse, P)))}.
-
-reduce_precision(_NewP, _B) ->
- throw(not_implemented).
-
-compact(B) ->
- B.
-
-bytes({sparse, Sparse, _, _}) -> bisect:size(Sparse);
-bytes({dense, Dense}) -> erlang:byte_size(Dense).
-
-
-register_sum(B) ->
- M = case B of
- {dense, Bytes} -> erlang:byte_size(Bytes);
- {sparse, _, P, _} -> trunc(math:pow(2, P))
- end,
-
- {MaxI, Sum} = fold(fun (Index, Value, {I, Acc}) ->
- Zeros = Index - I - 1,
- {Index, Acc + math:pow(2, -Value)
- + (math:pow(2, -0) * Zeros)}
- end, {-1, 0}, B),
- Sum + (M - 1 - MaxI) * math:pow(2, -0).
-
-zero_count({dense, _} = B) ->
- fold(fun (_, 0, Acc) -> Acc + 1;
- (_, _, Acc) -> Acc
- end, 0, B);
-zero_count({sparse, B, P, _}) ->
- M = trunc(math:pow(2, P)),
- M - bisect:num_keys(B).
-
-encode_registers({dense, B}) ->
- B;
-encode_registers({sparse, B, P, _}) ->
- M = trunc(math:pow(2, P)),
- iolist_to_binary(
- do_encode_registers(M-1, B, [])).
-
-
-
-decode_registers(AllBytes, P) ->
- M = DenseSize = trunc(math:pow(2, P)),
- EntrySize = (?KEY_SIZE + ?VALUE_SIZE) div 8,
- Threshold = DenseSize div EntrySize,
-
- Bytes = case AllBytes of
- <<B:M/binary>> -> B;
- <<B:M/binary, 0>> -> B
- end,
-
- L = do_decode_registers(Bytes, 0),
- case length(L) < Threshold of
- true ->
- New = bisect:new(?KEY_SIZE div 8, ?VALUE_SIZE div 8),
- {sparse, bisect:from_orddict(New, L), P, Threshold};
- false ->
- {dense, Bytes}
- end.
-
-
-%%
-%% INTERNAL
-%%
-
-do_dense_merge(<<>>, <<>>) ->
- [];
-do_dense_merge(<<Left:?VALUE_SIZE/integer, LeftRest/binary>>,
- <<Right:?VALUE_SIZE/integer, RightRest/binary>>) ->
- [max(Left, Right) | do_dense_merge(LeftRest, RightRest)].
-
-
-
-do_dense_fold(F, Acc, B) ->
- do_dense_fold(F, Acc, B, 0).
-
-do_dense_fold(_, Acc, <<>>, _) ->
- Acc;
-do_dense_fold(F, Acc, <<Value, Rest/binary>>, Index) ->
- do_dense_fold(F, F(Index, Value, Acc), Rest, Index+1).
-
-
-
-bisect2dense(B, P) ->
- M = trunc(math:pow(2, P)),
- {LastI, L} = lists:foldl(fun ({<<Index:?KEY_SIZE/integer>>, V}, {I, Acc}) ->
- Index < M orelse throw(index_too_high),
-
- Fill = case Index - I of
- 0 ->
- [];
- ToFill ->
- binary:copy(<<0>>, ToFill - 1)
- end,
-
- {Index, [V, Fill | Acc]}
-
- end, {-1, []}, bisect:to_orddict(B)),
- %% Fill last
- Filled = [binary:copy(<<0>>, M - LastI - 1) | L],
-
- iolist_to_binary(lists:reverse(Filled)).
-
-do_encode_registers(I, _B, ByteEncoded) when I < 0 ->
- ByteEncoded;
-do_encode_registers(I, B, ByteEncoded) when I >= 0 ->
- Byte = case bisect:find(B, <<I:?KEY_SIZE/integer>>) of
- not_found ->
- <<0>>;
- V ->
- V % already encoded
- end,
- do_encode_registers(I - 1, B, [Byte | ByteEncoded]).
-
-
-do_decode_registers(<<>>, _) ->
- [];
-do_decode_registers(<<0, Rest/binary>>, I) ->
- do_decode_registers(Rest, I+1);
-do_decode_registers(<<Value:?VALUE_SIZE, Rest/binary>>, I) ->
- [{<<I:?KEY_SIZE/integer>>, <<Value:?VALUE_SIZE/integer>>}
- | do_decode_registers(Rest, I+1)].
-
-
-
-%%
-%% TESTS
-%%
-
-bisect2dense_test() ->
- P = 4,
- M = 16, % pow(2, P)
-
- {sparse, B, _, _} =
- lists:foldl(fun ({I, V}, Acc) ->
- set(I, V, Acc)
- end, new(P), [{2, 1}, {1, 1}, {4, 4}, {15, 5}]),
-
- Dense = bisect2dense(B, P),
- ?assertEqual(M, size(Dense)),
-
-
- Expected = <<0, 1, 1, 0,
- 4, 0, 0, 0,
- 0, 0, 0, 0,
- 0, 0, 0, 5>>,
- ?assertEqual(M, size(Expected)),
- ?assertEqual(Expected, Dense).
--
To stop receiving notification emails like this one, please contact
kocolosk@apache.org.