David Gerard:
You mean, something closer to keeping diffs rather than each revision in its entirety? Have you tested using diff rather than this custom diff-like thing?
Diff compresses well ([1], Consecutive forward diffs). And it is probably fast as well, if you want to access all consecutive revisions. I developed the algorithm I proposed primarily for compressing history blobs [2]. This would not be possible with diffs, because if someone wants to get the 20th revision in a blob, the server would have to apply 19 patches, which would be very slow.
I don't know if my SplitMergeGzipHistoryBlobs will be used some day, but if so, the generation of dumps would certainly be faster if the same logical structure would be used.
[1] http://meta.wikimedia.org/wiki/History_compression [2] http://bugzilla.wikipedia.org/show_bug.cgi?id=2310