* [TUHS] About SCCS (and PWB) @ 2015-11-09 23:02 Marc Rochkind 2015-11-09 23:05 ` Larry McVoy 0 siblings, 1 reply; 5+ messages in thread From: Marc Rochkind @ 2015-11-09 23:02 UTC (permalink / raw) I just got on this list today, and I see that Larry McVoy asks: "I wish Marc was on this list, be fun to chat." I'd be happy to chime in on SCCS or early PWB questions, to the extent I remember anything. I did see a thread about PWB contributions in which people are trying to sort out what came from research and what from the PWB group (under Evan Ivie). As I recall, PWB was always based on research. Dick Haight would install the latest research system from time-to-time, and then the so-called "PWB UNIX" was whatever he had taken from research plus stuff we were developing, such as SCCS. Unlike, say, Columbus UNIX, our kernel always matched research at the system call level, so there never was such a thing as a PWB-kernel dependency. (I think the USG system was run quite differently: They had their own system, and would merge improvements from research into it. I could be wrong about this, as I never worked in the USG group.) --Marc -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20151109/fdb8db68/attachment.html> ^ permalink raw reply [flat|nested] 5+ messages in thread
* [TUHS] About SCCS (and PWB) 2015-11-09 23:02 [TUHS] About SCCS (and PWB) Marc Rochkind @ 2015-11-09 23:05 ` Larry McVoy 2015-11-09 23:49 ` Marc Rochkind 0 siblings, 1 reply; 5+ messages in thread From: Larry McVoy @ 2015-11-09 23:05 UTC (permalink / raw) On Mon, Nov 09, 2015 at 04:02:44PM -0700, Marc Rochkind wrote: > I just got on this list today, and I see that Larry McVoy asks: > > "I wish Marc was on this list, be fun to chat." > > I'd be happy to chime in on SCCS or early PWB questions, to the extent I > remember anything. Awesome! How about a start of how you came up with the SCCS design, in particular the interleaved delta format (we internally call it "the weave")? ^ permalink raw reply [flat|nested] 5+ messages in thread
* [TUHS] About SCCS (and PWB) 2015-11-09 23:05 ` Larry McVoy @ 2015-11-09 23:49 ` Marc Rochkind 2015-11-10 1:09 ` Clem Cole 0 siblings, 1 reply; 5+ messages in thread From: Marc Rochkind @ 2015-11-09 23:49 UTC (permalink / raw) Since you asked, here's the true story of how I came up with the delta encoding, a story never before told. I was living in a garden apartment in Sayreville, NJ, and at night would walk my girlfriend's dog along a hillside just outside our front door. It was usually cold, I didn't like the dog (still don't like dogs), and hated dodging the piles of dog shit while he tugged on the leash. So, as a coping mechanism, I used to let my mind wander, and one evening it was wandering and wondering about a problem I was struggling with, which was how to store the source and the deltas all in the same file. (It was a "data set," on the IBM OS/360 system we were using--we weren't on UNIX yet.) Anyway, no doubt simultaneously with this unpleasant animal taking a shit, I came up with idea of surrounding pieces of text with markers. (The algorithm itself is documented in my original 1975 paper, which you can read about here: http://basepath.com/aup/talks/SCCS-Slideshow.pdf.) (Wouldn't this be an even better story if I said that the little piles of dog poop on the hillside looked like markers in the soft glow of a full moon? It's not true, but perhaps I'll tell it that way if the occasion arises in the future.) When I got inside, I started to sketch out how the markers might work, and came up with interesting observation that insertion start/end markers obviously nested, but deletion start/end markers did not nest with insert start/end markers. This is obvious if you think about it the right way: When you delete, the text you're deleting could have been added at various times, but when you insert, the inserted text is always added at the same time. I didn't have replacement markers; insert and delete were enough, I thought. I kept fooling around with the idea until I had an algorithm that I thought would work to retrieve any version with a single pass. (It's in the paper, referenced above.) To prove the algorithm to be correct, I enumerated all possible cases of insertions mixed in with deletions. I don't recall how many cases I had, but I think it was around 20 or 30. Then I painstakingly went though every case, making sure the algorithm produced the right answer. This was a rare example of me doing actual work. Coding it up, as I remember, was very easy, as the scheme is pretty simple. I'm sure I had it running in SNOBOL4 in a day or two. Redesigning SCCS in C for UNIX came maybe a year or so later, but the algorithm remained the same. Larry very kindly says: "SCCS has interleaved deltas. It's a brilliant design that has far far better performance than anything else out there." Maybe it was brilliant, but I can tell you that I was just trying to pass the time while that stupid dog did his business. --Marc On Mon, Nov 9, 2015 at 4:05 PM, Larry McVoy <lm at mcvoy.com> wrote: > On Mon, Nov 09, 2015 at 04:02:44PM -0700, Marc Rochkind wrote: > > I just got on this list today, and I see that Larry McVoy asks: > > > > "I wish Marc was on this list, be fun to chat." > > > > I'd be happy to chime in on SCCS or early PWB questions, to the extent I > > remember anything. > > Awesome! How about a start of how you came up with the SCCS design, > in particular the interleaved delta format (we internally call it > "the weave")? > -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20151109/48873390/attachment.html> ^ permalink raw reply [flat|nested] 5+ messages in thread
* [TUHS] About SCCS (and PWB) 2015-11-09 23:49 ` Marc Rochkind @ 2015-11-10 1:09 ` Clem Cole 2015-11-10 1:27 ` Marc Rochkind 0 siblings, 1 reply; 5+ messages in thread From: Clem Cole @ 2015-11-10 1:09 UTC (permalink / raw) Outstanding. I love it. You can use emoji's today and have the scatological references inline. Clem On Mon, Nov 9, 2015 at 6:49 PM, Marc Rochkind <rochkind at basepath.com> wrote: > Since you asked, here's the true story of how I came up with the delta > encoding, a story never before told. > > I was living in a garden apartment in Sayreville, NJ, and at night would > walk my girlfriend's dog along a hillside just outside our front door. It > was usually cold, I didn't like the dog (still don't like dogs), and hated > dodging the piles of dog shit while he tugged on the leash. So, as a coping > mechanism, I used to let my mind wander, and one evening it was wandering > and wondering about a problem I was struggling with, which was how to store > the source and the deltas all in the same file. (It was a "data set," on > the IBM OS/360 system we were using--we weren't on UNIX yet.) > > Anyway, no doubt simultaneously with this unpleasant animal taking a shit, > I came up with idea of surrounding pieces of text with markers. (The > algorithm itself is documented in my original 1975 paper, which you can > read about here: http://basepath.com/aup/talks/SCCS-Slideshow.pdf.) > > (Wouldn't this be an even better story if I said that the little piles of > dog poop on the hillside looked like markers in the soft glow of a full > moon? It's not true, but perhaps I'll tell it that way if the occasion > arises in the future.) > > When I got inside, I started to sketch out how the markers might work, and > came up with interesting observation that insertion start/end markers > obviously nested, but deletion start/end markers did not nest with insert > start/end markers. This is obvious if you think about it the right way: > When you delete, the text you're deleting could have been added at various > times, but when you insert, the inserted text is always added at the same > time. > > I didn't have replacement markers; insert and delete were enough, I > thought. > > I kept fooling around with the idea until I had an algorithm that I > thought would work to retrieve any version with a single pass. (It's in the > paper, referenced above.) > > To prove the algorithm to be correct, I enumerated all possible cases of > insertions mixed in with deletions. I don't recall how many cases I had, > but I think it was around 20 or 30. Then I painstakingly went though every > case, making sure the algorithm produced the right answer. This was a rare > example of me doing actual work. > > Coding it up, as I remember, was very easy, as the scheme is pretty > simple. I'm sure I had it running in SNOBOL4 in a day or two. Redesigning > SCCS in C for UNIX came maybe a year or so later, but the algorithm > remained the same. > > Larry very kindly says: "SCCS has interleaved deltas. It's a brilliant > design that has far far better performance than anything else out there." > > Maybe it was brilliant, but I can tell you that I was just trying to pass > the time while that stupid dog did his business. > > --Marc > > On Mon, Nov 9, 2015 at 4:05 PM, Larry McVoy <lm at mcvoy.com> wrote: > >> On Mon, Nov 09, 2015 at 04:02:44PM -0700, Marc Rochkind wrote: >> > I just got on this list today, and I see that Larry McVoy asks: >> > >> > "I wish Marc was on this list, be fun to chat." >> > >> > I'd be happy to chime in on SCCS or early PWB questions, to the extent I >> > remember anything. >> >> Awesome! How about a start of how you came up with the SCCS design, >> in particular the interleaved delta format (we internally call it >> "the weave")? >> > > > _______________________________________________ > TUHS mailing list > TUHS at minnie.tuhs.org > https://minnie.tuhs.org/mailman/listinfo/tuhs > > -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20151109/89afb3f1/attachment.html> ^ permalink raw reply [flat|nested] 5+ messages in thread
* [TUHS] About SCCS (and PWB) 2015-11-10 1:09 ` Clem Cole @ 2015-11-10 1:27 ` Marc Rochkind 0 siblings, 0 replies; 5+ messages in thread From: Marc Rochkind @ 2015-11-10 1:27 UTC (permalink / raw) [-- Warning: decoded text below may be mangled, UTF-8 assumed --] [-- Attachment #1: Type: text/plain, Size: 4061 bytes --] 💩 On Nov 9, 2015 6:09 PM, "Clem Cole" <clemc at ccc.com> wrote: > Outstanding. I love it. You can use emoji's today and have the > scatological references inline. > > Clem > > On Mon, Nov 9, 2015 at 6:49 PM, Marc Rochkind <rochkind at basepath.com> > wrote: > >> Since you asked, here's the true story of how I came up with the delta >> encoding, a story never before told. >> >> I was living in a garden apartment in Sayreville, NJ, and at night would >> walk my girlfriend's dog along a hillside just outside our front door. It >> was usually cold, I didn't like the dog (still don't like dogs), and hated >> dodging the piles of dog shit while he tugged on the leash. So, as a coping >> mechanism, I used to let my mind wander, and one evening it was wandering >> and wondering about a problem I was struggling with, which was how to store >> the source and the deltas all in the same file. (It was a "data set," on >> the IBM OS/360 system we were using--we weren't on UNIX yet.) >> >> Anyway, no doubt simultaneously with this unpleasant animal taking a >> shit, I came up with idea of surrounding pieces of text with markers. (The >> algorithm itself is documented in my original 1975 paper, which you can >> read about here: http://basepath.com/aup/talks/SCCS-Slideshow.pdf.) >> >> (Wouldn't this be an even better story if I said that the little piles of >> dog poop on the hillside looked like markers in the soft glow of a full >> moon? It's not true, but perhaps I'll tell it that way if the occasion >> arises in the future.) >> >> When I got inside, I started to sketch out how the markers might work, >> and came up with interesting observation that insertion start/end markers >> obviously nested, but deletion start/end markers did not nest with insert >> start/end markers. This is obvious if you think about it the right way: >> When you delete, the text you're deleting could have been added at various >> times, but when you insert, the inserted text is always added at the same >> time. >> >> I didn't have replacement markers; insert and delete were enough, I >> thought. >> >> I kept fooling around with the idea until I had an algorithm that I >> thought would work to retrieve any version with a single pass. (It's in the >> paper, referenced above.) >> >> To prove the algorithm to be correct, I enumerated all possible cases of >> insertions mixed in with deletions. I don't recall how many cases I had, >> but I think it was around 20 or 30. Then I painstakingly went though every >> case, making sure the algorithm produced the right answer. This was a rare >> example of me doing actual work. >> >> Coding it up, as I remember, was very easy, as the scheme is pretty >> simple. I'm sure I had it running in SNOBOL4 in a day or two. Redesigning >> SCCS in C for UNIX came maybe a year or so later, but the algorithm >> remained the same. >> >> Larry very kindly says: "SCCS has interleaved deltas. It's a brilliant >> design that has far far better performance than anything else out there." >> >> Maybe it was brilliant, but I can tell you that I was just trying to pass >> the time while that stupid dog did his business. >> >> --Marc >> >> On Mon, Nov 9, 2015 at 4:05 PM, Larry McVoy <lm at mcvoy.com> wrote: >> >>> On Mon, Nov 09, 2015 at 04:02:44PM -0700, Marc Rochkind wrote: >>> > I just got on this list today, and I see that Larry McVoy asks: >>> > >>> > "I wish Marc was on this list, be fun to chat." >>> > >>> > I'd be happy to chime in on SCCS or early PWB questions, to the extent >>> I >>> > remember anything. >>> >>> Awesome! How about a start of how you came up with the SCCS design, >>> in particular the interleaved delta format (we internally call it >>> "the weave")? >>> >> >> >> _______________________________________________ >> TUHS mailing list >> TUHS at minnie.tuhs.org >> https://minnie.tuhs.org/mailman/listinfo/tuhs >> >> > -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20151109/6acd29fd/attachment.html> ^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2015-11-10 1:27 UTC | newest] Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2015-11-09 23:02 [TUHS] About SCCS (and PWB) Marc Rochkind 2015-11-09 23:05 ` Larry McVoy 2015-11-09 23:49 ` Marc Rochkind 2015-11-10 1:09 ` Clem Cole 2015-11-10 1:27 ` Marc Rochkind
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).