Rediscovering the Rsync Algorithm
blog.incubaid.com
blog.incubaid.com
An adaptive protocol that matches to the systems load dynamically whether its cpu/disk/network. Anyone know of what happened to this?
Tarsnap does this. My project (ddar) does the same.
How does ddar do it?
Blocks whose boundaries are determined by this algorithm are hashed (SHA256 currently). The hash is used to key each block in a reference-counted key/value store.
Then each archive member is just a list of block hashes.
There are implementations in Lua, Java, and C.
Joey found [0] that running rsync once in dry-run mode to find what files have been changed, copying them each with cp, then running rsync a second time to handle things like deletions and file permissions resulted in a major speedup.
[0] http://kitenet.net/~joey/blog/entry/local_rsync_accelerator/
If I just tell rsync to syncronise between two directories, what does it do internally? I might have assumed that it does the more naive option, but in practice it seems to do a lot of upfront calculation that suggests it's doing something more sophisticated.
Rsync can also compare hashes if you don't trust the size and time on the files.
Do you know how and where dropbox uses rsync?
There have been some tries to port the rsync program to other languages/platforms [1], but they are usually not in sync with the current rsync program. I am talking about ports of the program, not new implementations of the algorithm.
[0] http://librsync.sourceforge.net [1] http://duplicity.nongnu.org
An interesting article, but I don't have time nor the inclination to understand the code, which is the core of it.
My exemplar for mathematical elegance is page 3 of Serre's A Course in Arithmetic. In a tidy page of text, it proves what takes many textbooks a long and tedious chapter, introducing important concepts like the Frobenius. It's so short and neat I can reproduce it here in full:
Let K be a field. The image of Z in K is an integral domain, hence isomorphic to Z or to Z/pZ, where p is a prime; its field of fractions is isomorphic to Q or to Z/pZ = F_p. In the first case, one says that K is of characteristic zero; in the second case, that K is of characteristic p.
The characteristic of K is denoted by char(K). If char(K) = p != 0, p is also the smallest integer n > 0 such that n 1 = 0.
Lemma. If char(K) = p, the map sigma : x -> x^p is an isomorphism of K onto one of its subfields K^p.
We have sigma(xy) = sigma(x) sigma(y). Moreover, the binomial coefficient (p choose k) is congruent to 0 (mod p) if 0 < k < p. From this it follows that sigma(x + y) = sigma(x) + sigma(y); hence sigma is a homomorphism. Furthermore, sigma is clearly injective.
Theorem 1. (i) The characteristic of a finite field K is a prime number p != 0; if f = [K:F_p], the number of elements of K is q = p^f. (ii) Let p be a prime number and let q = p^f (f >= 1) be a power of p. Let Omega be an algebraically closed field of characteristic p. There exists a unique subfield F_q of Omega which has q elements. It is the set of roots of the polynomial X^q - X. (iii) All finite fields with q = p^f elements are isomorphic to F_q.
If K is finite, it does not contain the field Q. Hence its characteristic is a prime number p. If f is the degree of the extension K/F_p, it is clear that Card(K) = p^f, and (i) follows.
On the other hand, if Omega is algebraically closed of characteristic p, the above lemma shows that the map x -> x^q (where q = p^f, f >= 1) is an automorphism of Omega; indeed, this map is the f-th iterate of the automorphism sigma : x -> x^p (note that sigma is surjective since Omega is algebraically closed). Therefore, the elements in Omega invariant under x -> x^q form a subfield F_q of Omega. The derivative of the polynomial X^q - X is q X^(q-1) - 1 = p p^(f-1) X^(q-1) - 1 = -1, and is not zero. This implies (since Omega is algebraically closed) that X^q - X has q distinct roots, hence Card(F_q) = q. Conversely, if K is a subfield of Omega with q elements, the multiplicative group K* of nonzero elements in K has q-1 elements. Then x^(q-1) = 1 if x in K* and x^q = x if x in K. This proves that K is contained in F_q. Since Card(K) = Card(F_q) we have K = F_q which completes the proof of (ii).
Assertion (iii) follows from (ii) and from the fact that all fields with p^f elements can be embedded in Omega since Omega is algebraically closed.
> proof courses
I can't think of a single course I took, starting with the first semester, that wasn't a "proof course".
ODE, Cal 1-3 and their labs, Multivariate, Matrix methods. Congrats to you for being able to skip 8 courses, not all of us are that talented.
I take it my experience was atypical?
Compare e.g.
Transcendental functions, techniques and applications of integration, indeterminate forms, improper integrals, infinite series.
with
Algebraic and topological structure of the real number system; rigorous development of one-variable calculus including continuous, differentiable, and Riemann integrable functions and the Fundamental Theorem of Calculus; uniform convergence of a sequence of functions; contributions of Newton, Leibniz, Cauchy, Riemann, and Weierstrass.
That is, if you aren't willing to read this article, then I have my doubts that you would have worked through any free standing code.
Let's be honest here, very few people practice a good literate style.
It really just comes down to adding a narrative to what you're doing. I think the README convention that github has helped push out there is doing more to get people using each other's codes than any amount of variable naming.
Well… the README file is an ancient convention that probably stretches all the way back to the 70s.
IMHO, no, not at all. Github is helping people cos it lowered the cost of publishing code by 1) making it easy and 2) putting code at the forefront of the project.
In my ideal world, we would all use something like Docco - http://jashkenas.github.com/docco/ - but in my day to day I count myself lucky if I find the barest amount of class documentation, let alone a literate style.
So: people will do what is easy. Everyone should start by having meaningful variable names.
I think this is possibly my being jaded with Java's documentation conventions. It can be great for index level documentation, but is absolutely terrible at showing use cases and why things were done the way they are.
http://www.amazon.com/Clean-Code-Handbook-Software-Craftsman...
I'm not saying I don't ever use one and two-letter variables names; they're useful where their meaning is unambiguous, as with small inner loops. But when your goal is to educate others, better to err on the side of verbosity. That to me is more literate than the alternative.
I have no problem with his use of a procedure with the signature "let rec loop acc s .... in" when it is fundamentally a placeholder recursive control structure. Such a signature is as much a common boilerplate pattern in OCaml as "for (i = 0; i < length; i++) { ... }" in a C-like language.
That said, his top level procedures are named things like "apply" and "updates" which are possibly too generic, but OCaml has a nice module system so the names need only convey meaning unambiguous with relation to each other; there is no global namespace to pollute.
This is a common problem of clean functional languages: their declarations can be unambiguously correct with less specificacy. Function declarations need not specify subject and object of the sentences they represent since these can be inferred, they must only specify the verb. But this means skimming becomes less fruitful: one must read everything to understand anything.