git slowness

Lots of coding in my checkin early and often style - I'm actually coding, rather than spending most of my time trying to figure out how somebody else's code works.

Unfortunately, git is becoming a real performance bottleneck. Especially compared to CVS.

Reason: I'm trying to use a single big repository. Logically there are many separate subprojects, but I found that using srparate git repos was a real hassle.

In CVS you can restrict the repository scans to a subtree. Apparently not so in git. Or, at least, I don't know how.

Full repo scans are great, but have a perf cost.

Towards my own git-like VC tool - user level filesystem in a directory tree, filesystem in a file.

I am not happy with git. I want to improve on it. It's depressing to think of how much good stuff would need to be duplicated, but anyway...

I want to explore my ideas on how branches, lines of development, tags, and subprojects work.

I think the filesystem oriented design is the way to go. Strictly speaking, I first saw this in svn, but Linus certainly took it further.

Think of it as an abstract interface to a filesystem - a filesystem embedded in a directory tree. Or possibly in a file. E.g. an XML file. I'll concentrate on the filesystem in a directory tree idea first, but want to always keep filesystem n a file, filesystem-in-XML, filesystem-in-tar-archive, etc., around at the back of my mind.

The API to such a user level filesystem is not UNIX kernel level open/read/write. In particular, we cannot assume file handles. No state apart from the filesystem itself.

The API must interface to an existing filesystem.

The API should be (a) in a scripting language, and (b) at the *IX command level. The mapping between them should be 1:1 as much as possible - i.e. I am lazy, and do not want to have to define both. I want to be able to automatically generate the command line tools from the scripting modules.

The filesystem should be layerable. E.g. for version control, I want a layer that handles my VC concepts - branches, tags, lines, etc. I want this layered on top of a contenht based, deduplicated, filesystem. And I want that layered on top of a compression layer, i.e. a packing layer. I want to be able to design these layers separately, and mix and match.

I want this layering so that, ideally, I can steal other people's implementations.
E.g. I might want to steal Linus' git packfiles, or bzr's packfiles.
E.g. I will probably write my own content based layer, deliberately using a hash that has lots of collisions, to prove that I can handle collisions. But I would like be able to use any other existying implementation.
E.g. I may want to implement things in a directory, or in some single file. If it is properly layered, that should just involve switching a layer. Although the performance considerations might be extreme.

I want the UNIX command line interface to support such layering. E.g. I may want to look at a filesystem in something like a .git directory tree as a VC level - or at the content based level, or at the raw pack level.

I want the API in the scripting language so that I can have the layering in the script language, somewhat efficiently. But if layering modules are written in different scripting languages, say Perl or Python or Ruby, or even in C/C++ like git, I want to be able to layer through tyhe command line as well.
I.e. command line layering required. Inside-script-language layering nice.

Given my hisory, I will probably start coding in object oriented perl. Hope to leverage lots of code out of CPAN. Call it PerlFS? No, that name is taken. How about FSinF or FSinD - FileSystem in a File and FileSystem in a Directory (Tree). Perl_FSinF, Perl_FSinD. FSinF being the generic name, since directories are just filesystems.

I'm not scared of using a scripting language. Bzr argues they have acheived good performance in Python. I like portability.
As usual, ultimately I would like the system to install as a single file. Likes scons.py. Or at least a directory.

Thoughts about the FSinF (FilesSystem in File/Directory) Interface

Can't have primitives like UNIX open/read/write/close. Thesed assume state - file descriptors.

Interface must specify both files on the FSinF filesystem, as well as data on the native filesystem.

Operations such as:

Copying

FSinF copy fileSrc fileDst
Copy fileSrc (in FSinF) to fileDst (in FSinF)

FSinF get fileSrc fileDst
get contents of fileSrc (in FSinF) and write to fileDst (in native filesystem)

FSinF put fileSrc fileDst
put contenhts of fioleSrc (in native filesystem) to fileDst (in FSinF)

If we have syntax to distinguish native and FSinF filesystem names, this might be a single command "copy", although get/put is nicely documenting.

Moving and Renaming

FSinF move fileSrc fileDst
move or rename fileSrc (in FSinF) to fileDst (in FSinF)

Again, syntax could allow moving and renaming between FSinF and the native filesystem.

Inter-filesystem operations

get and put are inter-filesystem operations. We don't need to limit ourselves to getting from the FSinF to the native filessytem. We could transfer between two different FSinFs, FSinF1 and FSinF2. Possibly might stage through the native filesystem, but not necessarily always.

Parts of Files

Don't want always to operate on whole files. Although that is natural.

May want to specify parts of files:

• byte offset regions
• line regions
• XML clauses
• record numbers

I don't think that we need to define these at the level of the FSinF API. They could be FSinF filesystem specific.

At the command line leve, these would be optional parameters.

E.g.

FSinF get -range "line 40:line 100" file


Hints and Requirements

Different filesystems have different semantics. E.g. "emove" may mean "remove completely", or "remove from current version, but keep earlier versions around".

Such semantics are FSinF specific. Optional arguments.

May want to indicate if the semantics are mandatory or optional. E.g. "remove from current version, but keep earlier versions around" motivated by desire to remove copyright infringing stuff is mandatory - and must be done. Or must receive an error if cannot be done.

E.g.

FSinF remove -require hard-removal file ...

FSinF remove -optional soft-removal file ...

Other Filesystem Operations

FSinF remove files ...

FSinF create files ....
Empty files created.
Possibler specify types.

FSinF mkdir dirname

FSinF mkfs fsinf-file-or-dirname

FSinF fsck fsinf-file-or-dirname

FSinF chperm files...
Changes permisions
Also used to change owner, group name, etc.
Expect to extend:
E.g.
May start off with UNIX permissions, or ACLs
May create my own extra permission classes and ACLs, more flexble than native OS.

FSinF metadata add file metadata...
FSinF metadata remove file metadata...
Manipulae extra metdata associated with files
Synchronization

FSinF get file1 file2 ...
atomically get consistent file versions

FSinF atomic compare-and-swap old-file oldcmpdata newfile

FSinF atomic compare-and-put old-file1 cmpdata1 newfile2

Have the "server" do the comparison, and then put/swap.

Possibly

FSinF lock file ...
FSinF unlock file ...
Although I dislike the stae implied by locking.

Layering, Access to

E.g. in a directory ~/myproject
with a subdirectory .git

I would want to be able t say

FSinF -type git move file1 file2

But, I might also want tio say, at the level of the conent based

FSinF -type git-sha-content-based-fs remove 0x6416fec17...

I might also have a .svn link, so I may want to say

FSinF -type svn get "-r4 file1 "
note how "-r4 file1" almost looks like a filename / specification to the svn filesystem.

I.e. I may want to have several different filesystems under a tree, such as .git / .cvn. Or even my old CVS / CVS.othr-reo stuff.

But I also want to be able to look at the layers in any of thenm.

Layers I want

Raw filesystem. I.e. basically a NOP.

FSinF pack:
Compacts the above.
Probably needs some form of delta specification, for delta compression.

FSinF content-based
Uses hashes to deduplicate.
Me, I want to be able to handle hash collisions. Want both stupid hashes, like UNIX compress, and fancier hashes almost guaranteed to be collsions free.

FSinF checksummed
Adds checksums, verifies integrity
Maybe even ECC

How about:
FSinF mirrored?

FSinF encrypted.

FSinF signed
bit not encrypted

FSinF version-conrol
version controlled
in my dreams, with my extended semantics.

FSinF dirtree, file, xml, tar ...

Version Control Checkout and Sharing of *Partially Populated* Subtrees

I'm on the version control tool warpath again.

I'm a damned good example of why VC tools need subprojects, nested trees, whatever... Never you mind Keith Packard (Mr X Consortium) saying that I shouldn't bother.

At the moment I am messing around with
a) at least 2 diverged CVS trees for my home directory, one on my laptop, one on Linux.
b) a simulator, which uses BitKeeper
c) my own main project, which uses CVS (fortunately, one site only)
d) various other tools at work, using CVS and SVN
e) my TWiki site at work, which uses RCS (although I can make it look like CVS if necessary)
f) friends and coworkers who use GIT

My contributions to b), c), d), and e) make extensive use of stuff from my personal library. But, these other projects do not want to import my whole personal library - rather, they want to import just the modules they need, and their dependences.

Part of my personal source tree is structured as follows:

~/src:

include
" debug.h
" lprintf.h
" MathConst.h
" ag.h
" debug.h
" lfile.h
" libag.h
" simplelock.h
" strfamily.h*
libag
" assert
" bitpattern
" bitvector
" builtin_initialization
" class_name
" code_location
" compile " component
" " SimpleScalar-libag-component
" error
" error_stream
" File_Slurp
" file_slurp
" fmt
" getopt
" getter_setter
" indented_ostream
" Inherit
" interval
" IO_converter
" libuarch
" " cache-array
" " " examples
" " memory_image
" " multilevel_cache
" " SimpleScalar-libag-libuarch
" Memory_Object
" misc
" new-libag-ideas
" " quantiles
" number
" old-stuff-trying-to-reuse
" regd_ptr
" smart_ptr
" stack_trace
" stdio-stream
" test
" thisprintf
" to_bitstring
" to_string
" typename
" types
" unindent
" xml

You get the picture: lots of little modules, each in their own directories or directory trees.

Way back when I started, I put multiple header files in the same directory, like include/debug.h, include/lfile.h. I also created "utility" files like ag.h and libag.h. Over time I learned that it was best to put each module, each header file, in a directory of its own. Such a directory gives you a place to place tests, etc. There is a pattern of repeating the directory name and the include name #include "libag/test/test.h"

Above I have excerpted "header-only" libraries. I also have some C/C+ libraries that need to be compiled, but I have learned that "header only" lubraries, that only need to be #included, are a lot more convenient to use.

Some of my libraries have interdependencies. For example, libag/test/test.hh includes ../code_location/codelocation.hh.
First thing to note: the use of includer relative paths. If I simply copy (cp -R) libag/{test,code_location}, and #include "import/libag/test/test.hh", everything works.

Second, and most important thing to note: a typical user of some (but not all) of my libraries might want a pruned subtree:

import/libag
" test
" code_location

Importing all of libag is just clutter.

I.e. they do not want to import just complete subtrees.

They want to import a pruned subtree - stuff that is in the parent directory, libag, as well as subdirectories such as libag/test and libag/code_location.

I no longer put actual library functions at such parent-root directories. (Alright, I still have some files there, libag/stralloc.h, mainly dating back before I decided to use the "directory per module" pattern.) But I still have metadata there - libag/README.libag, explaining library organization. I also have tools like SConstruct files and files that guide test jig runners, so that I can simply say "make test" or "scons test" in libag, and all the tests run. (My test runner does NOT require a list of all the subdirectories.)
I would like to keep some of that metadata in libag when it is checked out for use by other projects.
I.e. I want all of the file contents of libag, but only a subset of the subdirectories.
I say again: I want a PRUNED SUBTREE of the source.

---

Really, what I want is a version control that makes it easy to share small modules. Not heavyweight subprojects, a la git. Not projects that I have to define in advance, like git or CVSROOT/modules. I want really lightweight modules. Directory subtrees seem to be a very natural way of specifying submodules.
I.e. at the very least I want to be able to do "vcs co libag/test libag/code_location".
Unfortunately, this least thing that I want to do is barely supported by any of the modern version control tools (git, hg, bzr). cvs, oronically, supports it fairly well.

But I want to do better than this least.

Ultimately, I want automatic dependency tracking. I want to be able to say "vcs co libag/test", and have something automatically recognize that I need to checdk out libag/code-location as well. Perl CPAN does it - I want it everywhere.

But I also want to be able to check out libag, with local files, and a pruned set of subdirectories.

---

OK, say I have gotten that far: I can check out just the modules I want.

Next, I want to be able to work in a single workspace - and check things into multiple version control repositories.
E.g. I want to be able to use CVS to check changes made to my libraries back into my personal epositories.
But the other projects that are importing my stuff also want to check things into their repositories. E.g. keiko/imprt/libag/test/test.hh gets BitKeepered, as well as CVS'ed.

Years ago, I gave the CVS community patches to allow this: I allowed there to be multiple CVS metadata directories, e.g. CVS1 and CVS2, and I allowed the user to specify which to use, CVS1 to check into repository 1, CVS2 for repository 2.

I've done similar kluges with BitKeeper and Subversion. E.g. I have checked CVS subdirectories, containg CVS/Root, CVS/Repository, and CVS/Entries files into BitKeeper - so that a bk clone or bk pull can always be kept in synch with CVS.
It is hard to go the other way: distributed version control systems such as git and BitKeeper, that clone an entire repository, *can* be checked into other VC systems, but don't behave nicely, wrt disk space and other issues. The problem: they do not clearly separate the concept of repository and workspace and links between the two.
AMD's "buildlist" methodology - basically a list of all files, and their RCS/CVS versions - lent itself well to this.


---

Reading through some of the interminable "Bzr versus Git versus Hg" comparisons, I see people asking "Who cares about history? You only need the last few years of changes."
Well, I care about history. I have been accumulating code snippets, library functions, and tools for more than 20 years. Some may date back to 1980. I probably have SCCS (!) files dating back to 1985-1987, copied and/or checked into RCS, and then CVS. There are some big gaps in the record, corresponding to periods where changes I made to my libraries were owned by companies, not me --- but I have a long history. Not very dense - some of these tools may sit unaffected for years, e.g. I am just now brushing off PerlSQL - but long lived.
But why care about this history? Well, I *have* on several occasions had to back up to 10 year old versions of some of my library functions, when the flavors of UNIX/Linux changed under me.

Git, Renaming, etc

Git does not track file renames.

Linus's email, http://permalink.gmane.org/gmane.comp.version-control.git/217, is essentially correct, but shortsighted. Linus argues that file renames are just a special case of moving content around. E.g. how does file rename tracking help you if you take a source file foo.h, move all of its content to bar.h, and then put #include "bar.h" inside foo.h? Linus argues that a content based tool that can detect this sort of movement, is more useful than tracking renames in Git.

Linus is right. But, Linus is shortsighted. Linus is considering only one usage model: that of a programmer studying code history. There is a human in the loop.

I want to use a version control system such as Git to perform such actions when a human is not in the loop.

E.g. I want to use Git, instead of RCS, as the version control system in twiki. Then, if a user requests http://mytwikisite.net/OldTopic, I can tell him or her that OldTopic has moved to NewTopic. To do this, the content tracking system must be able to make a single suggestion.

Of course, a content tracking system can make a single suggestion. But, it may get confused - e.g. two different wiki pages may start off from a common answer. Some human may have to decide who is the most logical primary choice. If that choice has been made, why not record it? Which amounts to recording the "primary" renaming.

Similarly, even a wiki may want to have a content tracking system that has a human in the loop. But it is nice to have a fully automated system with no human in the loop, that takes advantage of recorded rename tracking.

And, I hazard, even an SCM will need the fully automated version.

I.e.:

Rename tracking is a convenience.

Content tracking, with or without a human in the loop, is of additional value.

Content based filesystems and VC

It's time that I switched to Git for version control of my home directory - which has CVS'ed for the last, what, 10 years, maybe longer - and which has also been RCS'ed, SCCS'ed, and, briefly, BK'ed.

A few months ago Linus told me that Git was ready for folks like me to use it. At the same time he also discussed the following issue:

Git is, essentially, a content based filesystem or object store. It uses the SHA-1 cryptographic hash of a file as that file's name.

When last Linus and I talked (which was also the first and only time we have ever talked in person, at a restaurant - we've only briefly talked via email and newsgroups otherwise) Linus assured me that Git could handle the case where two objects had the same hash. I haven't seen how it is handled in the code. The Git discussion groups seem to be populated by people who cannot imagine that a collision would ever occur. I'm willing to believe that Linus has handled it properly. I'm going to use this blog to discuss what properly is.

First off, the basics: I'm with Val Henson, http://infohost.nmt.edu/~val/review/hash.pdf: using compare-by-hash without being prepared to handle collisions is bad, Bad, BAD. Given a large enough collection of files, a hash collision will occur. Worse if one can be constructed by a malicious user seeking to corrupt a repository.

But I really like the convenience and efficiency of compare-by-hash --- I call it "content based" addressing. So I want a content based scheme that handles collisions.

I can't understand why everyone doesn't do it: it's pretty simple.

E.g. in the object store, you create an index that maps hashes to object names. The object names could still be the cryptographic hash, perhaps with an instance number appended: i.e. the first object in the repository that has hash F00 would be named F00-0, the next F00-1, etc.
If you are so confident that there will never be collisions, you will only see F00-0 names, right? What does it harm you to append the instance number?

Or, you could use some other scheme for creating a unique name for the repository, such as a sequece number. In fact, I would probably suggest using both such designation schemes: sequence numbers inside the repository are more likely to need to be changed when two different repositories are merged. Hashes are more likely to be unique - although, if you merge two repositories that both have F00-0 objects, which are different, one is going to be named F00-1 after the merge. But, again, for those who are confident that collisions will never occur, you will never see this _slight_ renaming.

The only way in which this deviates from compare-by-hash content based systems such as Monotone is that, when you are adding an object to the repository, you don't just stop when you have computed the hash, and have seen that the hash is already in the repository. You have to compare the new object to the object that is already in the database that has the same hash. I.e. you use the hash to determine who to compare to, but you still do a full comparison.

Note: to compute the hash of the new object, you have to scan all of its bytes. That's O(n) work. To do the full comparison is still O(n) work - albeit with a bigger constant multiplier, circa 3X (one scan for the hash, then a scan of both the new and old object for the compare).

This suggests that you may not want to use a cryptographic hash of the entire file's n bytes. You may want a sampled hash. E.g. a hash of the first kilobyte, or a random selection of bytes. The purpose of the hash is now just to reduce the probability of collision, not eliminate it.
(Of course, the real issue is that no hash ever eliminates the possibility of collision:
people just fool themselves that it does.)

Another trivial optimization is to use the object size as well as its hash. If two objects that have the same hash differ in size, you can avoid the full comparison. If you are one of those people who believe that SHA-1 hash collisions can never occur, then certainly they will never occur for objects of the same size. So, by your own standard of belief, the full file comparison will never be done.

So, let's compare what I propose - using the hash as a hint, but handling collisions - to what Monotone did, using hash as a name, not providing for collisions. Let's call them collision-handling-content-based, and collision-neglecting-content-based:

If you believe that hash collisions will never occur:

• when naming objects in the repository, my collision-handling and Monotine's collision ignoing approach will work the same.
  
• when adding objects to the repository, my approach *might* require a full comparison - but the simple expediet of including the object size in the hash comparison avoids this -- in all of the cases where no hash collision occurs.
  

I.e. my collision handling approach and Monotone's collision ignoring approach are equivalent, so long as no collisions occur. And, of course, if collisions occur, Monotone breaks, but my approach still works.

The only reason that I can possibly imagine for not using my approach is code complexity. Why add code that will never be exercised? How do you test it? When I started writing rcs-file-merge -- until I learned that Linus was writing Git - I planned to use the content-based approach. But, I deliberately used a really weak hash - UNIX checksum - to deliberately create collisions, so that I could test that I could handle them. Found collisions in my home directory. Of course, a stronger hash would be used in actual production.

I really, really, hope that Git handles hash collisions. As I describe above, it is very straightforward, and costs nothing in performance.