<html><head><meta http-equiv="Content-Type" content="text/html charset=iso-8859-1"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><br><div><div>On 30 Aug 2013, at 14:13, Dan Berindei <<a href="mailto:dan.berindei@gmail.com">dan.berindei@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div dir="ltr"><div><div><div><div><div>We will still have a division in the consistent hash, because the "number of segments" in some ways replaces . We just didn't add it to the HotRod protocol yet...<br><br>
</div>I have thought about replacing division, and I was considering 2 options:<br></div>1. Hide the power of 2 restriction in the consistent hash implementation - allow the user to specify any number of segments, but round it up internally.<br></div></div></div></div></blockquote><div><br></div><div>^^ This is the technique I've seen in most place.</div><br><blockquote type="cite"><div dir="ltr"><div><div><div>
</div>2. Compute the multiplicative inverse of the number of segments and use multiplication instead - multiplication should be just as fast as addition on modern machines.<br><br></div>However, the division didn't particularly stick out as a hotspot back when I implemented DefaultConsistentHash, so I didn't pursue it further.<br>
<br>Cheers<br></div>Dan<br><div><div class="gmail_extra"><br><br><div class="gmail_quote">On Thu, Aug 29, 2013 at 5:29 PM, Manik Surtani <span dir="ltr"><<a href="mailto:msurtani@redhat.com" target="_blank">msurtani@redhat.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Pls ignore. I've just been informed that hash space is to be dropped from the protocol anyway.<br>
<div class="im"><br>
On 29 Aug 2013, at 13:35, Manik Surtani <<a href="mailto:msurtani@redhat.com">msurtani@redhat.com</a>> wrote:<br>
<br>
> The Hot Rod protocol current passes the size of the hash space used to clients, so that clients are able to create a consistent hash and perform smart routing.<br>
><br>
> <a href="https://docs.jboss.org/author/display/ISPN/Hot+Rod+Protocol+-+Version+1.0#HotRodProtocol-Version1.0-HashDistributionAwareClientTopologyChangeHeader" target="_blank">https://docs.jboss.org/author/display/ISPN/Hot+Rod+Protocol+-+Version+1.0#HotRodProtocol-Version1.0-HashDistributionAwareClientTopologyChangeHeader</a><br>
> <a href="https://docs.jboss.org/author/display/ISPN/Hot+Rod+Protocol+-+Version+1.2#HotRodProtocol-Version1.2-HashDistributionAwareClientTopologyChangeHeader" target="_blank">https://docs.jboss.org/author/display/ISPN/Hot+Rod+Protocol+-+Version+1.2#HotRodProtocol-Version1.2-HashDistributionAwareClientTopologyChangeHeader</a><br>
><br>
> However there are no rules as to what this hash space is, and this forces clients to use the remainder operation when performing modular arithmetic. This has been proven to be inefficient [1] [2] [3], and can be greatly improved if we made a simple assumption that the hash space will always be a power of two.<br>
><br>
> Perhaps something we can add in v1.3 of the protocol, so that clients talking to a server using Hot Rod 1.3 can make the assumption that the hash space is a power of 2?<br>
><br>
> WDYT?<br>
><br>
> - Manik<br>
><br>
><br>
> [1] <a href="http://dhruba.name/2011/07/12/performance-pattern-modulo-and-powers-of-two/" target="_blank">http://dhruba.name/2011/07/12/performance-pattern-modulo-and-powers-of-two/</a><br>
> [2] <a href="http://scicomp.stackexchange.com/questions/187/why-is-division-so-much-more-complex-than-other-arithmetic-operations" target="_blank">http://scicomp.stackexchange.com/questions/187/why-is-division-so-much-more-complex-than-other-arithmetic-operations</a><br>
> [3] <a href="http://disruptor.googlecode.com/files/Disruptor-1.0.pdf" target="_blank">http://disruptor.googlecode.com/files/Disruptor-1.0.pdf</a> (Page 5, last paragraph)<br>
><br>
><br>
<br>
</div>--<br>
Manik Surtani<br>
<div class=""><div class="h5"><br>
<br>
<br>
<br>
_______________________________________________<br>
infinispan-dev mailing list<br>
<a href="mailto:infinispan-dev@lists.jboss.org">infinispan-dev@lists.jboss.org</a><br>
<a href="https://lists.jboss.org/mailman/listinfo/infinispan-dev" target="_blank">https://lists.jboss.org/mailman/listinfo/infinispan-dev</a><br>
</div></div></blockquote></div><br></div></div></div>
_______________________________________________<br>infinispan-dev mailing list<br><a href="mailto:infinispan-dev@lists.jboss.org">infinispan-dev@lists.jboss.org</a><br>https://lists.jboss.org/mailman/listinfo/infinispan-dev</blockquote></div><br><div>
<div style="color: rgb(0, 0, 0); font-family: Helvetica; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; border-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; font-size: medium; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; border-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; font-size: medium; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; border-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; font-size: medium; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div>--</div><div>Manik Surtani</div><div><br></div></div></span></div></span></div></span></div><br class="Apple-interchange-newline">
</div>
<br></body></html>