{"thread":{"id":"43189","subject":"Re: If I were redoing git from scratch...","startedAt":"2006-11-04T11:34:42Z","lastAt":"2006-11-04T23:15:26Z","messageCount":7,"participants":["Linus Torvalds","Robin Rosenberg","Junio C Hamano","Jakub Narebski","Shawn Pearce"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"296760","messageId":"7vpsc3xx65.fsf@assigned-by-dhcp.cox.net","threadId":"43189","inReplyTo":null,"subject":"If I were redoing git from scratch...","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-11-04T11:34:42Z","receivedAt":"2006-11-04T11:34:42Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"I've been thinking about these for a while on the back of my\nhead, and thought it might be better to start writing it down.\n\nA lot of issues involve UI which means it will not materialize\nwithout breaking existing uses, but if we know in advance what\nwe will be aiming for, maybe we will find a smoother path to\nreach there.\n\n* Core data structure\n\nI consider on-disk data structures and on-wire protocol we\ncurrently use are sane and there is not much to fix.  There are\ncertainly things to be enhanced (64-bit .idx offset, for\nexample), but I do not think there is anything fundamentally\nbroken and needs to be reworked.\n\nI have the same feeling for in-core data structures in general,\nexcept a few issues.\n\nThe biggest one is that we use too many static (worse, function\nscope static) variables that live for the life of the process,\nwhich makes many things very nice and easy (\"run-once and let\nexit clean up the mess\" mentality), but because of this it\nbecomes awkward to do certain things.  Examples are:\n\n - Multiple invocations of merge-bases (needs clearing the\n   marks left on commit objects by earlier traversal),\n\n - Creating a new pack and immediately start using it inside the\n   process itself (prepare_packed_git() is call-once, and we\n   have hacks to cause it re-read the packs in many places).\n\n - Visiting more than one repositories within one process\n   (many per-repository variables in sha1_file.c are static\n   variables and there is no \"struct repository\" that we can\n   re-initialize in one go),\n\n - The object layer holds onto all parsed objects\n   indefinitely.  Because the object store at the philosophy\n   level represents the global commit ancestry DAG, there is\n   no inherent reason to have more than one instance of\n   object.c::obj_hash even if we visit more than one\n   repositories in a process, but if the two repositories are\n   unrelated, objects from the repository we were looking at\n   only waste memory after switching to a different\n   repostiory.\n\n - The diffcore is not run-once but it is run-one-at-a-time.\n   This is easy to fix if needed, though.\n\nThere are some other minor details but they are not as\nfundamental.  Examples are:\n\n - The revision traversal is nicely done but one gripe I have is\n   that it is focused on painting commits into two (and only\n   two) classes: interesting and uninteresting.  If we allowed\n   more than one (especially, arbitrary number of) kinds of\n   interesting, answering questions like \"which branches does\n   this commit belong to?  which tagged versions is this commit\n   already included in?\"  would become more easy and efficient.\n   show-branch has machinery to do that for a handful but it\n   could be unified with the revision.c traversal machinery. \n\n - We have at least three independent implementations of\n   pathspec match logic and two different semantics (one is\n   component-prefix match, the other is shell glob), and they\n   should be unified.  You can say \"git grep foo -- 't/t5*'\" but\n   not \"git diff otherbranch -- 't/t5*'\".\n\n\n* Fetch/Push/Pull/Merge confusion\n\nEverybody hates the fact that inverse of push is fetch not pull,\nand merge is not a usual Porcelain (while it _is_ usable as a\nregular UI command, it was originally done as a lower layer\nhelper to \"pull\" Porcelain and has a strange parameter order\nwith seemingly useless HEAD parameter in the middle).\n\nIf I were doing git from scratch, I would probably avoid any of\nthe above words that have loaded meanings from other SCMs.\nPerhaps...\n\n - \"git download\" would download changes made in the other end\n   since we contacted them the last time and would not touch our\n   branches nor working tree (associate the word with getting\n   tarballs -- people would not expect the act of downloading a\n   tarball would touch their working tree nor local history.\n   untarring it does).  It is a different story if the end-user\n   should be required to explicitly say \"download\"; I am leaning\n   towards making it more or less transparent.\n\n - \"git upload\" to upload our changes to the other end -- that\n   is what \"git push\" currently does.\n\n - \"git join\" to merge another branch into the current branch,\n   with the \"per branch configuration\" frills to decide what the\n   default for \"another branch\" is based on what the current\n   branch is, etc.\n\n* Less visible \"remoteness\" of remote branches\n\nIf I were doing git from scratch, I would probably have done\nseparate remotes _the_ only layout, except I might have opted to\nmake \"remotes\" even less visible and treating it as merely a\ncache of \"the branch tips and tags we saw when we connected over\nthe network to look at them the last time\".\n\nSo \"git branch --list $remote\" might contact the remote over the\nnetwork or use cached version.  When you think about, it it is\nnot all that different from always contacting the remote end --\nthe remote end may have mirror propagation delays, and your\nlocal instance of git caching and not contacting the remote all\nthe time introduces a similar delay on your end which is (1) not\na big deal, and (2) unlike the remote mirror delay, controllable\non your end.  For example, you could force it to update the\ncache by \"git download $remote; git branch --list $remote\".\n\n* Unified \"fetch\" and \"push\" across backends.\n\nI was rediscovering git-cvsimport today and wished if I could\njust have said (syntax aside):\n\n\tURL: cvs;/my.re.po/.cvsroot\n        Pull: HEAD:remotes/cvs/master\n        Pull: experiment:remotes/cvs/experiment\n\nto cause \"git fetch\" to run git-cvsimport to update the remotes/cvs/\nbranches (and \"git pull\" to merge CVS changes to my branches).\nThe same thing should be possible for SVN and other foreign SCM\nbackends.\n\nAlso it should be possible to use git-cvsexportcommit as a\nbackend for \"git push\" into the cvs repository.\n\nThat's it for tonight...\n"},{"id":"297025","messageId":"eii0kg$1co$1@sea.gmane.org","threadId":"43189","inReplyTo":"7vpsc3xx65.fsf@assigned-by-dhcp.cox.net","subject":"Re: If I were redoing git from scratch...","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-11-04T12:21:57Z","receivedAt":"2006-11-04T12:21:57Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Junio C Hamano wrote:\n\n> * Core data structure\n[...]\n> The biggest one is that we use too many static (worse, function\n> scope static) variables that live for the life of the process,\n> which makes many things very nice and easy (\"run-once and let\n> exit clean up the mess\" mentality), but because of this it\n> becomes awkward to do certain things.  Examples are:\n\nOne of examples that have been only rarely fixed was for_each_ref\nforcing callers to using static variable to store gathered data\ninstead of passing the data as one of arguments.\n\n> * Fetch/Push/Pull/Merge confusion\n> \n> Everybody hates the fact that inverse of push is fetch not pull,\n> and merge is not a usual Porcelain (while it _is_ usable as a\n> regular UI command, it was originally done as a lower layer\n> helper to \"pull\" Porcelain and has a strange parameter order\n> with seemingly useless HEAD parameter in the middle).\n> \n> If I were doing git from scratch, I would probably avoid any of\n> the above words that have loaded meanings from other SCMs.\n\nI'm a bit used to \"push\", \"fetch\" and \"pull\". I consider \"pull\"\na bit of artifact from times of one branch per repository layout.\nThe fact that \"pull\" fetches _all_ the branches but merges one\n[usually] with the _current_ branch (unless you configure it other\nway)...\n\nI'll leave \"push\" as is, leave \"fetch\" as is, and make \"pull\" to be\n\"fetch\" by default unless you use \"--merge[=<branch>]\" option.\nI'd rename \"merge\" to \"merge-driver\" and make new \"merge\" thanks\nto new users wouldn't have to learn to use \"git pull . branchA\"\nto merge current branch with branchA. \n\nPerhaps would make it possible to specify remote branch a la cogito,\n<URL>#<branch>, to pull remote branch without tracking branch, and\nfor symmetry have \"--pull[=<repo>]\" or \"--fetch[=<repo>]\" option.\n\n> * Unified \"fetch\" and \"push\" across backends.\n>\n\nVery nice idea, but one must remember the limitations of import/export tools\nand of course limitations of other SCM... well, and also limitations of\nGit, if there are any compared to other SCM ;-)\n\n-- \nJakub Narebski\nWarsaw, Poland\nShadeHawk on #git\n\n"},{"id":"297086","messageId":"Pine.LNX.4.64.0611040829040.25218@g5.osdl.org","threadId":"43189","inReplyTo":"7vpsc3xx65.fsf@assigned-by-dhcp.cox.net","subject":"Re: If I were redoing git from scratch...","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-11-04T16:44:02Z","receivedAt":"2006-11-04T16:44:02Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 4 Nov 2006, Junio C Hamano wrote:\n> \n> The biggest one is that we use too many static (worse, function\n> scope static) variables that live for the life of the process,\n> which makes many things very nice and easy (\"run-once and let\n> exit clean up the mess\" mentality), but because of this it\n> becomes awkward to do certain things.  Examples are:\n> \n>  - Multiple invocations of merge-bases (needs clearing the\n>    marks left on commit objects by earlier traversal),\n\nWell, quite frankly, I dare anybody to do it differently, yet have good \nperformance with millions of objects.\n\nThe fact is, I don't think it _can_ be done. I would seriously suggest \nre-visiting this in five years, just because CPU's and memory will by then \nhopefully have gotten an order of magnitude faster/bigger.\n\nThe thing is, the object database when we read it in really needs to be \npretty compact-sized, and we need to remember objects we've seen earlier \n(exactly _because_ we depend on the flags). So there's exactly two \nalternatives:\n - global life-time allocations of objects like we do now\n - magic memory management with unknown lifetimes and keeping track of all \n   pointers.\n\nAnd I'd like to point out that the memory management right now is simply \nnot realistic:\n\n - it's too damn hard. A simple garbage collector based on the approach we \n   have now would simply not be able to do anything, since all objects are \n   _by_definition_ reachable from the hash chains, so there's nothing to \n   collect. The lifetime of an object fundamentally _is_ the whole process \n   lifetime, exactly because we expect the objects (and the object flags \n   in particular) to be meaningful.\n\n - pretty much all garbage collection schemes tend to have a memory \n   footprint that is about twice what a static footprint is under any \n   normal load. Think about what we already do with \"git pack-objects\" for \n   something like the mozilla repository: I worked quite a lot on getting \n   the memory footprint down, and it's _still_ several hundred MB. \n\nIn other words, I can pretty much guarantee that some kind of \"smarter\" \nmemory management would be a huge step backwards. Yes, we now have to do \nsome things explicitly, but exactly because we do them explicitly we can \n_afford_ to have the stupid and simple and VERY EFFICIENT memory \nmanagement (\"lack of memory management\") that we have now.\n\nThe memory use of git had an very real correlation with performance when I \nwas doing the memory shrinking a few months back (back in June). I realize \nthat it's perhaps awkward, but I would really want people to realize that \nit's a huge performance issue. It was a clear performance issue for me \n(and I use machines with 2GB of RAM, so I was never swapping), it would be \nan even bigger one for anybody where the size meant that you needed to \nstart doing paging.\n\nSo I would seriously ask you not to even consider changing the object \nmodel. Maybe add a few more helper routines to clear all object flags or \nsomething, but the \"every object is global and will never be de-allocated\" \nis really a major deal.\n\nFive years from now, or for somebody who re-implements git in Java (where \nperformance isn't going to be the major issue anyway, and you probably do \n\"small\" things like \"commit\" and \"diff\", and never do full-database things \nlike \"git repack\"), _then_ you can happily look at having something \nfancier. Right now, it's too easy to just look at cumbersome interfaces, \nand forget about the fact that those interfaces is sometimes what allows \nus to practically do some things in the first place.\n\n"},{"id":"298186","messageId":"20061104191651.GC2517@spearce.org","threadId":"43189","inReplyTo":"Pine.LNX.4.64.0611040829040.25218@g5.osdl.org","subject":"Re: If I were redoing git from scratch...","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-11-04T19:16:51Z","receivedAt":"2006-11-04T19:16:51Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> wrote:\n> or for somebody who re-implements git in Java (where \n> performance isn't going to be the major issue anyway, and you probably do \n> \"small\" things like \"commit\" and \"diff\", and never do full-database things \n> like \"git repack\"), _then_ you can happily look at having something \n> fancier. Right now, it's too easy to just look at cumbersome interfaces, \n> and forget about the fact that those interfaces is sometimes what allows \n> us to practically do some things in the first place.\n\nYes and no.  :-)\n\nAs the only person here who has hacked on some of Git and also\nreimplemented the core on disk data structures in Java I can say\nI mostly agree with Linus.\n\nAbstractions like the repository (to allow different GIT_DIRs to\nbe used in the same process) isn't really a big deal and is not\na large impact on performance.  They could be implemented in the\ncurrent C core.\n\nBut trying to abstractly represent an object in Java the same\nway that it is represented in Git costs a huge amount of memory.\nJava is at least 16 bytes of overhead per object, before you get to\nstore anything in it.  Translation: Linus is right, doing a real\nimplementation of \"git repack\" in Java is nuts.  It would barely\nbe able to handle git.git, let alone linux.git or mozilla.git.\n\n-- \n"},{"id":"296283","messageId":"200611042329.46556.robin.rosenberg.lists@dewire.com","threadId":"43189","inReplyTo":"20061104191651.GC2517@spearce.org","subject":"Re: If I were redoing git from scratch...","fromName":"Robin Rosenberg","fromEmail":"robin.rosenberg.lists@dewire.com","sentAt":"2006-11-04T22:29:45Z","receivedAt":"2006-11-04T22:29:45Z","isPatch":false,"sender":{"key":"robin.rosenberg@dewire.com","avatar":"https://avatars.githubusercontent.com/u/46357?v=4"},"body":"lördag 04 november 2006 20:16 skrev Shawn Pearce:\n> But trying to abstractly represent an object in Java the same\n> way that it is represented in Git costs a huge amount of memory.\n> Java is at least 16 bytes of overhead per object, before you get to\n> store anything in it.  \n\nThe overhead is eigth bytes per object on a 32-bit platform and 16 on a 64-bit \nplatform for Sun's JDK. The granularity is eight bytes in both cases. \n\n"},{"id":"294003","messageId":"Pine.LNX.4.64.0611041436050.25218@g5.osdl.org","threadId":"43189","inReplyTo":"200611042329.46556.robin.rosenberg.lists@dewire.com","subject":"Re: If I were redoing git from scratch...","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-11-04T22:44:25Z","receivedAt":"2006-11-04T22:44:25Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 4 Nov 2006, Robin Rosenberg wrote:\n> \n> The overhead is eigth bytes per object on a 32-bit platform and 16 on a 64-bit \n> platform for Sun's JDK. The granularity is eight bytes in both cases. \n\nNote that the object structure itself is just 24 bytes (regardless of \nwhether we're on a 32-bit or 64-bit architecture).\n\nIn addition to that, we need one pointer per hash entry, and in order to \nkeep the hash list size down we need that hash array to be about 25% free, \nso say 1.5 pointers per object: ~6 bytes or ~12 bytes depending on whether \nit's a 32- or 64-bit architecture.\n\nSo 8 or 16 bytes overhead per object is roughly a 25% or 50% pure \noverhead. In contrast, right now we have pretty much _zero_ overhead (we \ndo end up having some malloc cost, but since we batch them, it's on the \norder of a few bytes per _thousand_ objects, so we're talking fractions of \na percent).\n\nOf course, the memory footprint isn't _just_ the objects, but it's a big \npart of it, for some important apps (not just repack, but git-send-pack \nobviously also has this). So on a git server, keeping the memory use down \nis likely the #1 concern - even if the server might have gigabytes of RAM.\n\n"},{"id":"298760","messageId":"Pine.LNX.4.64.0611041509370.25218@g5.osdl.org","threadId":"43189","inReplyTo":"Pine.LNX.4.64.0611041436050.25218@g5.osdl.org","subject":"Re: If I were redoing git from scratch...","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-11-04T23:15:26Z","receivedAt":"2006-11-04T23:15:26Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 4 Nov 2006, Linus Torvalds wrote:\n> \n> In addition to that, we need one pointer per hash entry, and in order to \n> keep the hash list size down we need that hash array to be about 25% free, \n> so say 1.5 pointers per object: ~6 bytes or ~12 bytes depending on whether \n> it's a 32- or 64-bit architecture.\n\nBtw, one of the things I considered (but rejected as being _too_ far out \nfor now) during the memory shrinking thing was to make both 32-bit and \n64-bit entities use a 32-bit hash table entry.\n\nThe way to do that would be to instead of using a pointer, use a 32-bit \ninteger where the low ~10 bits are an index into the allocation buffer \n(since we batch allocations), and the rest of the bits would be an index \ninto which batch-buffer it is.\n\nExactly because 8 bytes per hash entry is actually right now a big part of \nthe object memory allocation overhead on 64-bit architectures, and cutting \nit down to just 4 bytes would help save memory.\n\nI never got around to it, if only because I actually just compile my \nuser-land git stuff as 32-bit, even on my ppc64 system. And partly because \nI had shrunk the object allocations enough that I just felt pretty happy \nwith it anyway, and the change would have been pretty painful. But on \n64-bit architectures, the hash table right now is about a third of the \nwhole memory overhead of the object database, and cutting it down by half \nwould actually be noticeable.\n\n"}]}