<div dir="ltr"><div><div><div>Hello,<br><br></div>I tested the gen_server implementation and the results of a lookup are in average 0.1 ms so are pretty nice .<br></div>In case the gen_server becomes a problem I night use multiple gen_server instances. <a href="https://github.com/inaka/worker_pool">https://github.com/inaka/worker_pool</a><br><br></div>Silviu<br><div><div><br></div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Oct 23, 2015 at 3:20 PM, Anders Nygren <span dir="ltr"><<a href="mailto:anders.nygren@gmail.com" target="_blank">anders.nygren@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Since it is number analysis You want I think I should mention <a href="https://github.com/nygge/number_analysis" target="_blank">https://github.com/nygge/number_analysis</a><div>Originally written by Klacke. It builds a trie in an ETS table.</div><span class="HOEnZb"><font color="#888888"><div><br></div><div>/Anders</div></font></span></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Oct 22, 2015 at 3:54 PM, Caragea Silviu <span dir="ltr"><<a href="mailto:silviu.cpp@gmail.com" target="_blank">silviu.cpp@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><span style="background-color:rgb(228,228,255)">Hello,<br><br>@Michael I'm using btree only because of btrie:find_prefix_longest .<br><br>Basically
this is the main functionality I need. As I already posted if you have a
btrie with the following elements ["aa", "a", "b", "bb", "aaa"] and you
call: btrie:find_prefix_longest("aaawhatever") will return the associated value to the key "aaa".<br><br>I
need this for a long table with calling breakouts (prefixes and rate
per prefix) - around 50 k breakouts and basically I call
btrie:find_prefix_longest(<<"phonenumber">>) and it
returns me the prefix and the rate I need to bill for that destination.
Lookup operation seems ok from 1-2.5 ms 95% of time is spent in
ets:lookup. As somebody already pointed out is because ets is doing a
copy. I will change with gen_server state and benchmark again.<br><br>Thanks everyone for suggestions !<div><div><img src="https://ssl.gstatic.com/ui/v1/icons/mail/images/cleardot.gif"></div></div></span><div><div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Oct 22, 2015 at 11:38 PM, Michael Truog <span dir="ltr"><<a href="mailto:mjtruog@gmail.com" target="_blank">mjtruog@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000"><span>
<div>On 10/22/2015 01:29 AM, Caragea Silviu
wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr">
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<div>Hello.<br>
<br>
</div>
In one of my projects I need to use a radix tree.
I found out a very nice library :<br>
<a href="https://github.com/okeuday/trie" target="_blank">https://github.com/okeuday/trie</a><br>
<br>
</div>
Lookup performances are great. But I have one
problem.<br>
<br>
</div>
Basically my tree has around 100 000 elements so
building it it's an extremely operation. For this
reason I'm building it once and all processes that
needs to do lookups need to share the btrie object
(created using btrie:new/1). <br>
<br>
</div>
Here I see several options:<br>
<br>
</div>
1. Use a gen server and store the btrie object on the
state or process dictionary. - I didn't tried this<br>
</div>
2. Use a ets table and store the tire object on a public
table where all processes can read and write.<br>
</div>
</div>
</div>
</blockquote></span>
It is easier to scale and is more natural in Erlang if you pursue #1
(using the state, not the process dictionary). The #2 path
(including mochiglobal) is typical in imperative programming
(mutating global state). With #1 you can manage the reliability of
individual processes for fault-tolerance concerns and you would
probably start with a single locally registered process name. Then
if there is too much contention for the single process that has the
btrie, you would switch to using a process group, to share the load
with replicated data.<br>
<br>
The btrie usage is probably slower than using the newer maps data
structure. The trie repo was mainly created for string keys, not
binary keys, due to the memory access details in Erlang (i.e., it is
easier to have more efficient lookups with string keys, when using
process heap data, which includes being more efficient than maps in
some cases).<br>
<br>
You could also store the key/value lookup as a single large binary
that you reference (in multiple processes, since large binaries are
reference counted) with something like
<a href="https://github.com/knutin/bisect" target="_blank">https://github.com/knutin/bisect</a> which may work too.<br>
<br>
Best Regards,<br>
Michael<br>
<blockquote type="cite"><span>
<div dir="ltr">
<div>
<div><br>
</div>
Doing some benchmarks I see that lookup-ing for the longest
prefix (btrie:<span style="background-color:rgb(228,228,255)">find_prefix_longest</span>)
in around 100 K elements by prefix it's around 2- 5 ms and 95%
of the time is spent in the ets:<span style="background-color:rgb(228,228,255)">lookup.<br>
<br>
</span></div>
<div>I think the time spent there is so big because also my term
stored there is very big. <br>
<br>
</div>
<div>Any other suggestions ?<br>
<br>
</div>
<div>Silviu<br>
</div>
<div><span style="background-color:rgb(228,228,255)"><br>
</span></div>
</div>
<br>
<fieldset></fieldset>
<br>
</span><span><pre>_______________________________________________
erlang-questions mailing list
<a href="mailto:erlang-questions@erlang.org" target="_blank">erlang-questions@erlang.org</a>
<a href="http://erlang.org/mailman/listinfo/erlang-questions" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a>
</pre>
</span></blockquote>
<br>
</div>
</blockquote></div><br></div></div></div></div>
<br>_______________________________________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org" target="_blank">erlang-questions@erlang.org</a><br>
<a href="http://erlang.org/mailman/listinfo/erlang-questions" rel="noreferrer" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
<br></blockquote></div><br></div>
</div></div></blockquote></div><br></div>