[TUHS] SCCS

On Thu, Sep 12, 2019 at 08:49:35AM +1000, Dave Horsfall wrote: Marc Rochkind is on the list, I believe I invited him, but he can spell check what I'm about to say. SCCS is awesome. People have no idea how good it is as a version control system because Walter Tichy got his PhD for writing RCS and claiming it was better (don't get me started on how wrong that was). Let me start with how RCS works. You all know about diff and patch, someone does a diff, produces a patch, and Larry Wall wrote patch(1) that takes the patch and file and applies it. In a straight line history here is how RCS works. The most recent version of the file is stored in whole, the delta behind that is a reverse patch to get to that, same for the next delta behind that and so on. Branches in RCS are forward patches. Sort of. You start with the whole file that is the most recent version, reverse patch your way back to the branch point, and then forward patch your way down to the most recent version on the branch. Yeah, branches in RCS suck, very expensive. So why is SCCS awesome? It is an entirely different approach. SCCS is a set based system, for any version, there is a set of deltas that are in that version and you apply them to the file part of the data. Huh? What does that mean? OK, you've all seen SCCS revisions, 1.1, 1.2, 1.3, 1.3.1.1, etc. Yeah, that's for humans (and truth be told those revs are not that great). For SCCS internally there are serial numbers. All those are are a monotonically increasing number, doesn't matter if you are on the trunk or on a branch, each time you add a delta the internal number, or serial, is the last serial plus 1. When you go to check out a version of the file, that's the set. It's the set of serials that make up that file. If you wanted 1.3 and there are no branches, the set is the serial of 1.3 (3) and the parent of 1.3 which is 1.2 (2) and 1.1 (1). So your set is 1,2,3. Here is the awesome part. The way the data is stored in SCCS is nothing like patches, it's what we call a weave. All versions of the file are woven together in the following way. There are 3 operators: insert: ^AI <serial> delete: ^AD <serial> end: ^AE <serial> So if you checked in a file that looked like I love TUHS The weave would be ^AI 1 I love TUHS ^AE 1 Lets say that Clem changed that to I really love TUHS The new weave would look like: ^AI 1 I ^AI 2 really ^AE 2 love TUHS ^AE 1 and if I changed it to I *really* love TUHS the weave looks like ^AI 1 I ^AD 3 ^AI 2 really ^AE 2 ^AE 3 ^AI 3 *really* ^AE 3 love TUHS ^AE 1 So a checkout is 2 things, build up the set of serials that need to be active for this checkout, and walk the weave. For each serial you see you are either in this set and I need to do what it says, or this is not in my set and I need to do the opposite of what it says. So that is really really fast compared to RCS. RCS reads the whole file and has to do compute, SCCS reads the whole file and does a very tiny fraction of that compute, so tiny that you can't measure it compared to reading the file. But wait, it gets better, much better. Lets talk about branches and merges. RCS is copy by value across a merge, SCCS is copy by reference. Marc thought about the set stuff enough to realize wouldn't be cool if you could manipulate the set. He added include and exclude operators. Imagine if you and I were having an argument about some video being checked in. You checked it in, I deleted it, you checked it in, I deleted it. Suppose that was a 1GB video. In RCS, each time we argued that is another GB, we did that 4 times, there 4GB of diffs in the history. In SCCS, you could do that with includes and excludes, those 4 times would be about 30 bytes because all they are doing is saying "In the set", "Not in the set". Cool I guess but what is the real life win? Merges. In a weave based system like SCCS you can add 1GB on a branch and I can merge that onto the trunk and all I did was say "include your serials". I didn't copy your work, I referenced it. Tiny meta data to do so. That has more implications than you might think. Think annotations. git blame, know that? It shows who did what? Yeah, well git is copy by value just like RCS. It's not just about the space used, it is also about who did what. If bwk did one thing and dmr did another thing and little old lm merged dmr's stuff into the bwk trunk, in a copy by value system, all of dmr's work will look like I wrote it in bwk's trunk. SCCS avoids that. If I merged dmr's work into bwk's tree, if it all automerged, annotations would show it all as dmr's work, yeah, I did the merge but I didn't do anything so I don't show up in annotations. If there was a conflict and I had to resolve that conflict, then that, and that alone, would show up as my work. For Marc, I worked with Rick Smith, he found me after I had done a reimplentation of SCCS. He has forgotten more about weaves than I will ever know. But he was really impressed with my code (which you can go see at bitkeeper.org, and it is not my code, it is my teams code, Rick bugfixed all my mistakes) because I embraced the set thing and the way I wrote the code you could have N of my data structures and pulled out N versions of the file in one pass. He had not seen that before, to me it just seemed the most natural way to do it. SCCS is awesome, Marc should be held up as a hero for that. Most people have no idea how much better it is as a format, to this day people still do it wrong. The hg people at facebook sort of got it, they did an import of SCCS (it was BitKeeper which is SCCS on super steriods). But it is rare that someone gets it. I wanted Marc to know we got it. --lm