From d180def6cec2e5967a788c2b3161c191719b3fd0 Mon Sep 17 00:00:00 2001 From: Magnus Ahltorp Date: Sat, 25 Oct 2014 15:22:09 +0200 Subject: Optimize db:get_by_indices by not fetching entry and implementing index:getrange Conflicts: src/index.erl src/plop.erl --- src/db.erl | 12 +++++++----- src/index.erl | 41 ++++++++++++++++++++++++----------------- src/plop.erl | 8 +++++++- 3 files changed, 38 insertions(+), 23 deletions(-) (limited to 'src') diff --git a/src/db.erl b/src/db.erl index 6315ae5..a0855b9 100644 --- a/src/db.erl +++ b/src/db.erl @@ -108,6 +108,9 @@ index_for_leafhash(LeafHash) -> leafhash_for_index(Index) -> index:get(index_path(), Index). +leafhash_for_indices(Start, End) -> + index:getrange(index_path(), Start, End). + leafhash_for_entryhash(EntryHash) -> perm:readfile(entryhash_root_path(), EntryHash). @@ -117,11 +120,10 @@ get_by_indices_helper(Start, End) -> EndBound = min(End, size() - 1), case Start =< EndBound of true -> - lists:map(fun (Index) -> - LeafHash = leafhash_for_index(Index), - Entry = entry_for_leafhash(LeafHash), - {Index, LeafHash, Entry} - end, lists:seq(Start, EndBound)); + lists:map(fun ({LeafHash, Index}) -> + {Index, LeafHash, notfetched} + end, lists:zip(leafhash_for_indices(Start, EndBound), + lists:seq(Start, EndBound))); false -> [] end. diff --git a/src/index.erl b/src/index.erl index 7871215..a2b5c4a 100644 --- a/src/index.erl +++ b/src/index.erl @@ -11,7 +11,7 @@ %% TODO: Checksums -module(index). --export([get/2, add/3, addlast/2, truncate/2]). +-export([get/2, getrange/3, add/3, addlast/2, truncate/2]). -define(ENTRYSIZE, 32). -define(ENTRYSIZEINFILE, (?ENTRYSIZE*2+1)). @@ -54,31 +54,38 @@ truncate(Basepath, Index) -> addlast(Basepath, Entry) -> add(Basepath, last, Entry). -%% From lib/stdlib/src/lists.erl. For supporting < R17. --spec droplast(nonempty_list()) -> list(). -droplast([_T]) -> []; -droplast([H|T]) -> [H|droplast(T)]. +decodedata(Binary) -> + lists:reverse(decodedata(Binary, [])). -decodedata(EntryText) when length(EntryText) == ?ENTRYSIZEINFILE -> - case [lists:last(EntryText)] of - "\n" -> - hex:hexstr_to_bin(droplast(EntryText)); - _ -> - util:exit_with_error(badformat, readindex, - "Index line not ending with linefeed") - end. +decodedata(<<>>, Acc) -> + Acc; +decodedata(<>, Acc) -> + decodedata(Rest, [mochihex:to_bin(binary_to_list(Entry)) | Acc]); +decodedata(<<_:?ENTRYSIZE/binary-unit:16, _>>, _Acc) -> + util:exit_with_error(badformat, readindex, + "Index line not ending with linefeed"). -spec get(string(), integer()) -> binary(). get(Basepath, Index) -> + case getrange(Basepath, Index, Index) of + noentry -> + noentry; + [Entry] -> + Entry + end. + +-spec getrange(string(), integer(), integer()) -> [binary()]. +getrange(Basepath, Start, End) when Start =< End -> case file:open(Basepath, [read, binary]) of {ok, File} -> {ok, Filesize} = file:position(File, eof), if - Index * ?ENTRYSIZEINFILE + ?ENTRYSIZEINFILE =< Filesize -> + End * ?ENTRYSIZEINFILE + ?ENTRYSIZEINFILE =< Filesize -> {ok, _Position} = file:position(File, - Index * ?ENTRYSIZEINFILE), - {ok, EntryText} = file:read(File, ?ENTRYSIZEINFILE), - Entry = decodedata(binary_to_list(EntryText)), + Start * ?ENTRYSIZEINFILE), + {ok, EntryText} = + file:read(File, ?ENTRYSIZEINFILE * (End - Start + 1)), + Entry = decodedata(EntryText), file:close(File), Entry; true -> diff --git a/src/plop.erl b/src/plop.erl index 0b101be..5244144 100644 --- a/src/plop.erl +++ b/src/plop.erl @@ -131,12 +131,18 @@ get_logid() -> gen_server:call(?MODULE, {get, logid}). testing_get_pubkey() -> gen_server:call(?MODULE, {test, pubkey}). + +fill_in_entry({_Index, LeafHash, notfetched}) -> + db:get_by_leaf_hash(LeafHash). + %%%%%%%%%%%%%%%%%%%% handle_call(stop, _From, Plop) -> {stop, normal, stopped, Plop}; handle_call({get, {index, Start, End}}, _From, Plop) -> - {reply, db:get_by_indices(Start, End, {sorted, false}), Plop}; + {reply, lists:map(fun (E) -> fill_in_entry(E) end, + db:get_by_indices(Start, End, {sorted, false})), + Plop}; handle_call({get, {hash, EntryHash}}, _From, Plop) -> {reply, db:get_by_entry_hash(EntryHash), Plop}; -- cgit v1.1 From bfc8c81b18967ad5bb58e6bd1ea55b5b969e24d8 Mon Sep 17 00:00:00 2001 From: Magnus Ahltorp Date: Mon, 27 Oct 2014 01:32:24 +0100 Subject: Optimize ts by storing tree in array of arrays. --- src/ts.erl | 51 ++++++++++++++++++++++++--------------------------- 1 file changed, 24 insertions(+), 27 deletions(-) (limited to 'src') diff --git a/src/ts.erl b/src/ts.erl index cf71ff5..07edbf6 100644 --- a/src/ts.erl +++ b/src/ts.erl @@ -9,56 +9,53 @@ -export_type([tree_store/0]). -export([new/0, add/3, delete/2, retrieve/2, count/2]). -%% FIXME: Keep the entries in binaries instead of lists? Hashes do -%% have fixed lenght. --record(tree_store, {layers :: list()}). % orddict of lists, keyed on layer. +-record(tree_store, {layers :: array:array(array:array(binary()))}). % array of arrays, keyed on layer. -type tree_store() :: #tree_store{}. %%%%%%%%%%%%%%%%%%%% %% Public. new() -> - #tree_store{layers = orddict:new()}. + #tree_store{layers = array:new()}. -spec add(tree_store(), non_neg_integer(), binary()) -> tree_store(). add(S = #tree_store{layers = Layers}, Layer, Entry) -> - {NewLayers, List} = layer(Layers, rw, Layer), - NewList = [Entry | List], - S#tree_store{layers = orddict:store(Layer, NewList, NewLayers)}. + {NewLayers, List} = layer_rw(Layers, Layer), + NewList = array:set(array:size(List), Entry, List), + S#tree_store{layers = array:set(Layer, NewList, NewLayers)}. -spec delete(tree_store(), non_neg_integer()) -> tree_store(). delete(S = #tree_store{layers = Layers}, Layer) -> - List = layer(Layers, ro, Layer), - [_ | NewList] = List, - S#tree_store{layers = orddict:store(Layer, NewList, Layers)}. + List = layer_ro(Layers, Layer), + NewList = array:resize(array:size(List) - 1, List), + S#tree_store{layers = array:set(Layer, NewList, Layers)}. -spec retrieve(tree_store(), tuple()) -> binary() | undefined. retrieve(#tree_store{layers = Layers}, {Layer, Index}) -> - List = layer(Layers, ro, Layer), - Len = length(List), + List = layer_ro(Layers, Layer), + Len = array:size(List), case Index < Len of - true -> lists:nth(Len - Index, List); + true -> array:get(Index, List); false -> undefined end. -spec count(tree_store(), non_neg_integer()) -> non_neg_integer(). count(#tree_store{layers = Layers}, Layer) -> - length(layer(Layers, ro, Layer)). + array:size(layer_ro(Layers, Layer)). %%%%%%%%%%%%%%%%%%%% %% Private. --spec layer(list(), rw | ro, non_neg_integer()) -> list() | {list(), list()}. -layer(Layers, Access, Layer) -> - case Access of - rw -> - case orddict:find(Layer, Layers) of - error -> {orddict:store(Layer, [], Layers), []}; - {ok, List} -> {Layers, List} - end; - ro -> - case orddict:find(Layer, Layers) of - error -> []; - {ok, List} -> List - end +-spec layer_ro(array:array(array:array(binary())), non_neg_integer()) -> array:array(binary). +layer_ro(Layers, Layer) -> + case array:get(Layer, Layers) of + undefined -> array:new(); + List -> List + end. + +-spec layer_rw(array:array(array:array(binary())), non_neg_integer()) -> {array:array(), array:array(binary)}. +layer_rw(Layers, Layer) -> + case array:get(Layer, Layers) of + undefined -> {array:set(Layer, array:new(), Layers), array:new()}; + List -> {Layers, List} end. %%%%%%%%%%%%%%%%%%%% -- cgit v1.1 From f06372dd199442110329ed8869d87c76cb16eef1 Mon Sep 17 00:00:00 2001 From: Linus Nordberg Date: Tue, 28 Oct 2014 15:02:04 +0100 Subject: Change names with 'List' to names with 'Array'. Also, split some long lines. --- src/ts.erl | 32 ++++++++++++++++++-------------- 1 file changed, 18 insertions(+), 14 deletions(-) (limited to 'src') diff --git a/src/ts.erl b/src/ts.erl index 07edbf6..c69519c 100644 --- a/src/ts.erl +++ b/src/ts.erl @@ -9,7 +9,9 @@ -export_type([tree_store/0]). -export([new/0, add/3, delete/2, retrieve/2, count/2]). --record(tree_store, {layers :: array:array(array:array(binary()))}). % array of arrays, keyed on layer. +%% #tree_store{} has one member, layers, holding an array of arrays +%% with binaries, keyed on layer. +-record(tree_store, {layers :: array:array(array:array(binary()))}). -type tree_store() :: #tree_store{}. %%%%%%%%%%%%%%%%%%%% @@ -19,22 +21,22 @@ new() -> -spec add(tree_store(), non_neg_integer(), binary()) -> tree_store(). add(S = #tree_store{layers = Layers}, Layer, Entry) -> - {NewLayers, List} = layer_rw(Layers, Layer), - NewList = array:set(array:size(List), Entry, List), - S#tree_store{layers = array:set(Layer, NewList, NewLayers)}. + {NewLayers, Array} = layer_rw(Layers, Layer), + NewArray = array:set(array:size(Array), Entry, Array), + S#tree_store{layers = array:set(Layer, NewArray, NewLayers)}. -spec delete(tree_store(), non_neg_integer()) -> tree_store(). delete(S = #tree_store{layers = Layers}, Layer) -> - List = layer_ro(Layers, Layer), - NewList = array:resize(array:size(List) - 1, List), - S#tree_store{layers = array:set(Layer, NewList, Layers)}. + Array = layer_ro(Layers, Layer), + NewArray = array:resize(array:size(Array) - 1, Array), + S#tree_store{layers = array:set(Layer, NewArray, Layers)}. -spec retrieve(tree_store(), tuple()) -> binary() | undefined. retrieve(#tree_store{layers = Layers}, {Layer, Index}) -> - List = layer_ro(Layers, Layer), - Len = array:size(List), + Array = layer_ro(Layers, Layer), + Len = array:size(Array), case Index < Len of - true -> array:get(Index, List); + true -> array:get(Index, Array); false -> undefined end. @@ -44,18 +46,20 @@ count(#tree_store{layers = Layers}, Layer) -> %%%%%%%%%%%%%%%%%%%% %% Private. --spec layer_ro(array:array(array:array(binary())), non_neg_integer()) -> array:array(binary). +-spec layer_ro(array:array(array:array(binary())), non_neg_integer()) -> + array:array(binary). layer_ro(Layers, Layer) -> case array:get(Layer, Layers) of undefined -> array:new(); - List -> List + Array -> Array end. --spec layer_rw(array:array(array:array(binary())), non_neg_integer()) -> {array:array(), array:array(binary)}. +-spec layer_rw(array:array(array:array(binary())), non_neg_integer()) -> + {array:array(), array:array(binary)}. layer_rw(Layers, Layer) -> case array:get(Layer, Layers) of undefined -> {array:set(Layer, array:new(), Layers), array:new()}; - List -> {Layers, List} + Array -> {Layers, Array} end. %%%%%%%%%%%%%%%%%%%% -- cgit v1.1