Hi I have just picked this up again after some months of downtime, I will be pushing out an updated document shortly taking into account hopefully all of the comments in this thread.<br><br>One idea just occured to me as a compromise between CRC-64-ISO and crc32c, we could calculate twice the actual number of hashes with crc32c and then match them in pairs, this would create the equivalent of a 64bit hash in most cases while allowing use of the more standardised algorithms.<br>
<br>This of course comes at the cost of greater complexity in the implementation.<br><br>I guess there are multiple options down this route, <br>-match only in 32bit hash pairs<br>-match any two sequential hashes<br>-match any two matches with no literals in between<br>
-...<br><br>Does this make sense to anyone, or is it just crazy ideas brought on by getting up too early in the morning?<br><br>Toby<br><br><div class="gmail_quote">2009/8/3 Alex Wulms <span dir="ltr"><<a href="mailto:alex.wulms@scarlet.be">alex.wulms@scarlet.be</a>></span><br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">All,<br>
<br>
Cool. So let's settle for CRC-64-ISO then for the time being and still leave<br>
the 'negotation' option in the protocol for future extensions, like discussed<br>
before. I'll update the document with the various protocol refinements.<br>
<br>
<br>
Hi Rusty,<br>
<br>
Assuming you are still following this list: does your library currently use<br>
the CRC-64-ISO polynomial when the client selects 64-bit CRC or does this<br>
require some code change?<br>
<br>
<br>
Cheers,<br>
Alex<br>
<br>
<br>
Op vrijdag 31 juli 2009, schreef Patrick McManus:<br>
<div><div></div><div class="h5">> Alex, thanks for giving this some thought and experiments.<br>
><br>
> Some thoughts of mine in no particular order:<br>
><br>
> * 64 is way better than 60 in terms of giving people implementation<br>
> options. Personally I'd still go with 32, but I promise not to launch<br>
> further long rants in its defense.<br>
><br>
> * the letters olpc should probably appear in the document as part of the<br>
> requirements. That was really interesting information to me, and it<br>
> isn't obvious that low bandwidth, high latency, low power environments<br>
> are the target of this without that mention.<br>
><br>
> * your timing calculations are likely way off because you don't consider<br>
> tcp effects in a high latency env other than adding a 25% fudge factor<br>
> over the bit transfer rate. In a high latency environment short<br>
> transfers are totally dominated by rtt, not bandwidth. Slow start kills<br>
> you on cell based wireless networks (i.e. olpc).. think 256kbit at 500ms<br>
> latency being "good". You don't get to use the full 256kb/s bandwidth<br>
> until the 5th round trip that scenario... so you can just count transfer<br>
> time as rtt's * rtt-ms.. in the case of a 19KB document that's 4 rtt's<br>
> (2 seconds) compared to 3 rtt's for a 19/2KB document... and due to the<br>
> exponential growth of slow start that 1rtt is basically what you're<br>
> going to save in time vs 50% in bytes at any size until you fill up the<br>
> congestion window - and lots of cell-based-wireless environments require<br>
> a lot more than 5rtt's to fill the window. This is a big part of the<br>
> reason I think the 50% delta is completely uninteresting (well, I also<br>
> don't think it really happens in the wild very often).. I'm interested<br>
> in dividing the world into "really really good deltas" and "just send<br>
> everything else identity-compressed" because I really don't think there<br>
> is a signficant performance distinction between members of the second<br>
> group.. in which case crc32 would do just fine if aborting after finding<br>
> a solid run of hash misses.<br>
><br>
> but crc64 makes that more or less an implementation decision rather than<br>
> something necessitated by the false positive rate of the protocol. And<br>
> that's a good thing.<br>
><br>
> -Patrick<br>
<br>
<br>
</div></div></blockquote></div><br>