<html>
<head>
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">On 10/22/2015 01:29 AM, Caragea Silviu
wrote:<br>
</div>
<blockquote
cite="mid:CAJsc=ouoQaHi709te75w42tJiux1ad2EZFkZ6mhP9rBhpa6yeQ@mail.gmail.com"
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 moz-do-not-send="true"
href="https://github.com/okeuday/trie">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>
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 class="moz-txt-link-freetext" href="https://github.com/knutin/bisect">https://github.com/knutin/bisect</a> which may work too.<br>
<br>
Best Regards,<br>
Michael<br>
<blockquote
cite="mid:CAJsc=ouoQaHi709te75w42tJiux1ad2EZFkZ6mhP9rBhpa6yeQ@mail.gmail.com"
type="cite">
<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 class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
erlang-questions mailing list
<a class="moz-txt-link-abbreviated" href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a>
<a class="moz-txt-link-freetext" href="http://erlang.org/mailman/listinfo/erlang-questions">http://erlang.org/mailman/listinfo/erlang-questions</a>
</pre>
</blockquote>
<br>
</body>
</html>