[TUHS] SCCS

Larry McVoy lm at mcvoy.com
Thu Sep 12 13:43:46 AEST 2019


On Thu, Sep 12, 2019 at 08:49:35AM +1000, Dave Horsfall wrote:
> On Wed, 11 Sep 2019, Larry McVoy wrote:
> 
> >SCCS is awesome, I'll post why in a different thread.  It is light years
> >better than RCS, Tichy lied.
> 
> Agreed; I used it for years, then was forced to use RCS in my next job :-(

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


More information about the TUHS mailing list