Hacker News Reader

Comment by dark-star | Hacker News Reader

Comparing it with rsync running on Cygwin is a bit unfair, as Cygwin is known to be terribly inefficient. I don't doubt that their CDC based algorithm is faster, but probably not by the margin they claim if Cygwin is taken out of the equation

View on HN

IIUC, rsync computes a relatively expensive Rabin-Karp rolling hash (https://librsync.github.io/rabinkarp_8c_source.html) and performs a hash map lookup for every byte. Hash map lookups might not be very cache friendly for larger data sets. In comparison, cdc_rsync only computes

  hash = (hash << 1) + random_table[data[n]];
  bool chunk_boundary = (hash & magic_pattern) == 0;

per byte. That's only a few ops and very cache friendly. The random table only has 256 entries, 8 bytes each, so it easily fits into L1.

I should also note that we used a fairly fast 100 MB/sec connection to upload the data, so the rsync diffing algorithm running at 50 MB/sec is actually a bottleneck. The difference would be smaller on a slower connection, where the network overhead would dominate the results.

They addressed that specifically in the README. They tested on Linux and it was worse but had a worse CPU so assumed it was comparable.

Reply on news.ycombinator.com