<div dir="ltr">On Mon, Sep 2, 2013 at 7:24 AM, Xavier Hernandez <span dir="ltr"><<a href="mailto:xhernandez@datalab.es" target="_blank">xhernandez@datalab.es</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote">
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi,<br>
<br>
dict_t structures are widely used in glusterfs. I've some ideas that could improve its performance.<br>
<br>
* On delete operations, return the current value if it exists.<br>
<br>
This is very useful when we want to get a value and remove it from the dictionary. This way it can be done accessing and locking the dict_t only once (and it is atomic).<br></blockquote><div><br></div><div>Makes sense.</div>
<div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
* On add operations, return the previous value if it existed.<br>
<br>
This avoids to use a lookup and a conditional add (and it is atomic).<br></blockquote><div><br></div><div>Do you mean dict_set()? If so, how do you propose we differentiate between "failure" and "previous value did not exist"? Do you propose setting the previous value into a pointer to pointer, and retain the return value as is today?</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
* Always return the data_pair_t structure instead of data_t or the data itself.<br>
<br>
This can be useful to avoid future lookups or other operations on the same element. Macros can be created to simplify writing code to access the actual value.<br></blockquote><div><br></div><div>The use case is not clear. A more concrete example will help..</div>
<div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
* Use a trie instead of a hash.<br>
<br>
A trie structure is a bit more complex than a hash, but only processes the key once and does not need to compute the hash. A test implementation I made with a trie shows a significant improvement in dictionary operations.<br>
</blockquote><div><br></div><div>There is already an implementation of trie in libglusterfs/src/trie.c. Though it does not compact (collapse) single-child nodes upwards into the parent. In any case, let's avoid having two implementations of tries.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
* Implement dict_foreach() as a macro (similar to kernel's list_for_each()).<br>
<br>
This gives more control and avoids the need of helper functions.<br></blockquote><div><br></div><div>This makes sense too, but there are quite a few users of dict_foreach in the existing style. Moving them all over might be a pain.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Additionally, I think it's possible to redefine structures to reduce the number of allocations and pointers used for each element (actual data, data_t, data_pair_t and key).<br></blockquote><div><br></div><div>This is highly desirable. There was some effort from Amar in the past (<a href="http://review.gluster.org/3910">http://review.gluster.org/3910</a>) but it has been in need of attention for some time. It would be intersting to know if you were thinking along similar lines?</div>
<div><br></div><div><br></div><div>Avati</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
What do you think ?<br>
<br>
Best regards,<br>
<br>
Xavi<br>
<br>
______________________________<u></u>_________________<br>
Gluster-devel mailing list<br>
<a href="mailto:Gluster-devel@nongnu.org" target="_blank">Gluster-devel@nongnu.org</a><br>
<a href="https://lists.nongnu.org/mailman/listinfo/gluster-devel" target="_blank">https://lists.nongnu.org/<u></u>mailman/listinfo/gluster-devel</a><br>
</blockquote></div><br></div></div>