News for hackers. Stuff that matters.
Re:CDC File Transfer by dark-star on Sunday January 08, 2023 @07:57PM (#34305365)
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
Re:CDC File Transfer by lathiat on Sunday January 08, 2023 @08:50PM (#34305749)
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.
Re:CDC File Transfer by ljusten on Monday January 09, 2023 @04:51AM (#34308592)
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.
Re:CDC File Transfer by ljusten on Monday January 09, 2023 @04:54AM (#34308602)
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.