{"thread":{"id":"41887","subject":"RFC: New reference iteration paradigm","startedAt":"2016-03-31T16:13:33Z","lastAt":"2018-05-29T16:52:26Z","messageCount":7,"participants":["Michael Haggerty","Junio C Hamano","Jeff King","David Turner","Jakub Narebski"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"282332","messageId":"56FD4CAD.3070100@alum.mit.edu","threadId":"41887","inReplyTo":null,"subject":"RFC: New reference iteration paradigm","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2016-03-31T16:13:33Z","receivedAt":"2016-03-31T16:13:33Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"Currently the way to iterate over references is via a family of\nfor_each_ref()-style functions. You pass some arguments plus a callback\nfunction and cb_data to the function, and your callback is called for\neach reference that is selected.\n\nThis works, but it has two big disadvantages:\n\n1. It is cumbersome for callers. The caller's logic has to be split\n   into two functions, the one that calls for_each_ref() and the\n   callback function. Any data that have to be passed between the\n   functions has to be stuck in a separate data structure.\n\n2. This interface is not composable. For example, you can't write a\n   single function that iterates over references from two sources,\n   as is interesting for combining packed plus loose references,\n   shared plus worktree-specific references, symbolic plus normal\n   references, etc. The current code for combining packed and loose\n   references needs to walk the two reference trees in lockstep,\n   using intimate knowledge about how references are stored [1,2,3].\n\nI'm currently working on a patch series to transition the reference code\nfrom using for_each_ref()-style iteration to using proper iterators.\n\nThe main point of this change is to change the base iteration paradigm\nthat has to be supported by reference backends. So instead of\n\n> int do_for_each_ref_fn(const char *submodule, const char *base,\n>                        each_ref_fn fn, int trim, int flags,\n>                        void *cb_data);\n\nthe backend now has to implement\n\n> struct ref_iterator *ref_iterator_begin_fn(const char *submodule,\n>                                            const char *prefix,\n>                                            unsigned int flags);\n\nThe ref_iterator itself has to implement two main methods:\n\n> int iterator_advance_fn(struct ref_iterator *ref_iterator);\n> void iterator_free_fn(struct ref_iterator *ref_iterator);\n\nA loop over references now looks something like\n\n> struct ref_iterator *iter = each_ref_in_iterator(\"refs/tags/\");\n> while (ref_iterator_advance(iter)) {\n>         /* code using iter->refname, iter->oid, iter->flags */\n> }\n\nI built quite a bit of ref_iterator infrastructure to make it easy to\nplug things together quite flexibly. For example, there is an\noverlay_ref_iterator which takes two other iterators (e.g., one for\npacked and one for loose refs) and overlays them, presenting the result\nvia the same iterator interface. But the same overlay_ref_iterator can\nbe used to overlay any two other iterators on top of each other.\n\nIf you are interested, check out my branch wip/ref-iterators on my\nGitHub repo [4]. That branch is based off of a version of David Turner's\npatch series (i.e., it will have to be rebased at some point). But it\nall works and the early part of the patch series is pretty well polished\nI think. In fact, the later patches are optional; there is no special\nreason to rewrite client code wholesale to use the new reference\niteration API, because the old API continues to be supported (but is now\nbuilt on the new API).\n\nFeedback is welcome!\n\nMichael\n\n[1]\nhttps://github.com/git/git/blob/90f7b16b3adc78d4bbabbd426fb69aa78c714f71/refs/files-backend.c#L1665-L1719\n[2]\nhttps://github.com/git/git/blob/90f7b16b3adc78d4bbabbd426fb69aa78c714f71/refs/files-backend.c#L582-L608\n[3]\nhttps://github.com/git/git/blob/90f7b16b3adc78d4bbabbd426fb69aa78c714f71/refs/files-backend.c#L610-L680\n[4] https://github.com/mhagger/git\n"},{"id":"282356","messageId":"xmqqlh4yo7av.fsf@gitster.mtv.corp.google.com","threadId":"41887","inReplyTo":"56FD4CAD.3070100@alum.mit.edu","subject":"Re: RFC: New reference iteration paradigm","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-03-31T18:01:44Z","receivedAt":"2016-03-31T18:01:44Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty <mhagger@alum.mit.edu> writes:\n\n> the backend now has to implement\n>\n>> struct ref_iterator *ref_iterator_begin_fn(const char *submodule,\n>>                                            const char *prefix,\n>>                                            unsigned int flags);\n>\n> The ref_iterator itself has to implement two main methods:\n>\n>> int iterator_advance_fn(struct ref_iterator *ref_iterator);\n>> void iterator_free_fn(struct ref_iterator *ref_iterator);\n>\n> A loop over references now looks something like\n>\n>> struct ref_iterator *iter = each_ref_in_iterator(\"refs/tags/\");\n>> while (ref_iterator_advance(iter)) {\n>>         /* code using iter->refname, iter->oid, iter->flags */\n>> }\n\nWe'd want to take advantage of the tree-like organization of the\nrefs (i.e. refs/tags/a and refs/tags/b sit next to each other and\nthey are closer to each other than they are to refs/heads/a) so that\na request \"I want to iterate only over tags, even though I may have\nmillions of other kinds of refs\" can be done with cost that is\nproportional to how many tags you have.\n\nThe current implementation of for_each_tag_ref() that goes down to\ndo_for_each_entry() in files-backend.c has that propertly, and the\nnew iteration mechanism with the above design seems to keep it,\nwhich is very nice.\n"},{"id":"282378","messageId":"20160331193150.GC5013@sigill.intra.peff.net","threadId":"41887","inReplyTo":"xmqqlh4yo7av.fsf@gitster.mtv.corp.google.com","subject":"Re: RFC: New reference iteration paradigm","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-03-31T19:31:51Z","receivedAt":"2016-03-31T19:31:51Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Mar 31, 2016 at 11:01:44AM -0700, Junio C Hamano wrote:\n\n> Michael Haggerty <mhagger@alum.mit.edu> writes:\n> \n> > the backend now has to implement\n> >\n> >> struct ref_iterator *ref_iterator_begin_fn(const char *submodule,\n> >>                                            const char *prefix,\n> >>                                            unsigned int flags);\n> >\n> > The ref_iterator itself has to implement two main methods:\n> >\n> >> int iterator_advance_fn(struct ref_iterator *ref_iterator);\n> >> void iterator_free_fn(struct ref_iterator *ref_iterator);\n> >\n> > A loop over references now looks something like\n> >\n> >> struct ref_iterator *iter = each_ref_in_iterator(\"refs/tags/\");\n> >> while (ref_iterator_advance(iter)) {\n> >>         /* code using iter->refname, iter->oid, iter->flags */\n> >> }\n> \n> We'd want to take advantage of the tree-like organization of the\n> refs (i.e. refs/tags/a and refs/tags/b sit next to each other and\n> they are closer to each other than they are to refs/heads/a) so that\n> a request \"I want to iterate only over tags, even though I may have\n> millions of other kinds of refs\" can be done with cost that is\n> proportional to how many tags you have.\n> \n> The current implementation of for_each_tag_ref() that goes down to\n> do_for_each_entry() in files-backend.c has that propertly, and the\n> new iteration mechanism with the above design seems to keep it,\n> which is very nice.\n\nActually, that is a slight fiction. :)\n\nWe traverse only the loose ref directories we need, but we populate the\nentire packed-refs tree in one go. That's fine if you have a reasonable\nnumber of refs and care about the cold-cache case (where you care a lot\nabout hitting directories you don't need to, but reading the entire\npacked-refs file isn't a big deal). But it's really bad if you have an\n800MB packed-refs file, as looking up one tiny subset of the entries\nwastes a lot of RAM and CPU pulling that into our internal\nrepresentation[1].\n\nAt one point I wrote a patch to binary search the packed-refs file, find\nthe first \"refs/tags/\" entry, and then walk linearly through there. What\nstopped me is that the current refs.c code (I guess file-backend.c these\ndays) was not happy with me partially filling in the ref_dir structs in\nthis \"inside out\" way.\n\nThat is, they assume we may have iterated \"refs/\", but not yet dove into\n\"refs/tags/\" (because that's what makes sense for traversing loose\nrefs). But they are not happy if you already dove into \"refs/tags/\", but\ndon't know what else might be present in \"refs/\".\n\nI wonder if, while Michael is fiddling with the iterator code, it might\nbe possible to fix that (it's not a fundamental problem, just one with\nthe way the ref-caching works right now).\n\n-Peff\n\n[1] As you probably guessed, I run into these giant packed-refs files as\n    part of our \"alternates\" storage for multiple forks of the same\n    repository. So all of the refs match the pattern\n    \"refs/remotes/$fork_id/*\", and I really would like to be able to\n    iterate the refs for just one fork at a time.\n"},{"id":"282382","messageId":"xmqqa8lemmui.fsf@gitster.mtv.corp.google.com","threadId":"41887","inReplyTo":"20160331193150.GC5013@sigill.intra.peff.net","subject":"Re: RFC: New reference iteration paradigm","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-03-31T20:08:53Z","receivedAt":"2016-03-31T20:08:53Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> On Thu, Mar 31, 2016 at 11:01:44AM -0700, Junio C Hamano wrote:\n>\n>> Michael Haggerty <mhagger@alum.mit.edu> writes:\n>> \n>> > the backend now has to implement\n>> >\n>> >> struct ref_iterator *ref_iterator_begin_fn(const char *submodule,\n>> >>                                            const char *prefix,\n>> >>                                            unsigned int flags);\n>> >\n>> > The ref_iterator itself has to implement two main methods:\n>> >\n>> >> int iterator_advance_fn(struct ref_iterator *ref_iterator);\n>> >> void iterator_free_fn(struct ref_iterator *ref_iterator);\n>> >\n>> > A loop over references now looks something like\n>> >\n>> >> struct ref_iterator *iter = each_ref_in_iterator(\"refs/tags/\");\n>> >> while (ref_iterator_advance(iter)) {\n>> >>         /* code using iter->refname, iter->oid, iter->flags */\n>> >> }\n>> \n>> We'd want to take advantage of the tree-like organization of the\n>> refs (i.e. refs/tags/a and refs/tags/b sit next to each other and\n>> they are closer to each other than they are to refs/heads/a) so that\n>> a request \"I want to iterate only over tags, even though I may have\n>> millions of other kinds of refs\" can be done with cost that is\n>> proportional to how many tags you have.\n>> \n>> The current implementation of for_each_tag_ref() that goes down to\n>> do_for_each_entry() in files-backend.c has that propertly, and the\n>> new iteration mechanism with the above design seems to keep it,\n>> which is very nice.\n>\n> Actually, that is a slight fiction. :)\n\nI know.  My first draft had \"(at least for the loose ref side)\"\nthere, but I omitted it for brevity.\n\n> We traverse only the loose ref directories we need, but we populate the\n> entire packed-refs tree in one go.\n> ...\n> 800MB packed-refs file, as looking up one tiny subset of the entries\n> wastes a lot of RAM and CPU pulling that into our internal\n> representation[1].\n\nYes, that is an important use case that needs to be kept in mind for\nany restructure of this machinery.\n"},{"id":"282384","messageId":"1459455337.2976.36.camel@twopensource.com","threadId":"41887","inReplyTo":"56FD4CAD.3070100@alum.mit.edu","subject":"Re: RFC: New reference iteration paradigm","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2016-03-31T20:15:37Z","receivedAt":"2016-03-31T20:15:37Z","isPatch":false,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Thu, 2016-03-31 at 18:13 +0200, Michael Haggerty wrote:\n> Currently the way to iterate over references is via a family of\n> for_each_ref()-style functions. You pass some arguments plus a\n> callback\n> function and cb_data to the function, and your callback is called for\n> each reference that is selected.\n> \n> This works, but it has two big disadvantages:\n> \n> 1. It is cumbersome for callers. The caller's logic has to be split\n>    into two functions, the one that calls for_each_ref() and the\n>    callback function. Any data that have to be passed between the\n>    functions has to be stuck in a separate data structure.\n> \n> 2. This interface is not composable. For example, you can't write a\n>    single function that iterates over references from two sources,\n>    as is interesting for combining packed plus loose references,\n>    shared plus worktree-specific references, symbolic plus normal\n>    references, etc. The current code for combining packed and loose\n>    references needs to walk the two reference trees in lockstep,\n>    using intimate knowledge about how references are stored [1,2,3].\n> \n> I'm currently working on a patch series to transition the reference\n> code\n> from using for_each_ref()-style iteration to using proper iterators.\n> \n> The main point of this change is to change the base iteration\n> paradigm\n> that has to be supported by reference backends. So instead of\n> \n> > int do_for_each_ref_fn(const char *submodule, const char *base,\n> >                        each_ref_fn fn, int trim, int flags,\n> >                        void *cb_data);\n> \n> the backend now has to implement\n> \n> > struct ref_iterator *ref_iterator_begin_fn(const char *submodule,\n> >                                            const char *prefix,\n> >                                            unsigned int flags);\n> \n> The ref_iterator itself has to implement two main methods:\n> \n> > int iterator_advance_fn(struct ref_iterator *ref_iterator);\n> > void iterator_free_fn(struct ref_iterator *ref_iterator);\n> \n> A loop over references now looks something like\n> \n> > struct ref_iterator *iter = each_ref_in_iterator(\"refs/tags/\");\n> > while (ref_iterator_advance(iter)) {\n> >         /* code using iter->refname, iter->oid, iter->flags */\n> > }\n> \n> I built quite a bit of ref_iterator infrastructure to make it easy to\n> plug things together quite flexibly. For example, there is an\n> overlay_ref_iterator which takes two other iterators (e.g., one for\n> packed and one for loose refs) and overlays them, presenting the\n> result\n> via the same iterator interface. But the same overlay_ref_iterator\n> can\n> be used to overlay any two other iterators on top of each other.\n\nI haven't looked at the code yet, but this makes sense to me.  In\ngeneral, the major reason to supply a callback style of API is when\niteration is more complicated than whatever will be consuming the data\n(I can't remember where I heard this argument, but I found it pretty\nconvincing).  It seems like this is increasingly not the case, so we\nshould move towards the iterator style.\n"},{"id":"348603","messageId":"86h8mu1g8j.fsf@gmail.com","threadId":"41887","inReplyTo":"20160331193150.GC5013@sigill.intra.peff.net","subject":"Re: RFC: New reference iteration paradigm","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2018-05-26T17:25:32Z","receivedAt":"2018-05-26T17:30:13Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Jeff King <peff@peff.net> writes:\n> On Thu, Mar 31, 2016 at 11:01:44AM -0700, Junio C Hamano wrote:\n>> Michael Haggerty <mhagger@alum.mit.edu> writes:\n>> \n>>> the backend now has to implement\n>>>\n>>>> struct ref_iterator *ref_iterator_begin_fn(const char *submodule,\n>>>>                                            const char *prefix,\n>>>>                                            unsigned int flags);\n\nThe problem with callbacks, including their lack of composability, is\noften solved in high-level languages by using Promises / Futures (or\nChannels / Supplies).\n\nBut I think in this case implementing a straightforward Iterator pattern\nwould be a better and simpler solution, especially in C.\n\n>>> The ref_iterator itself has to implement two main methods:\n>>>\n>>>> int iterator_advance_fn(struct ref_iterator *ref_iterator);\n>>>> void iterator_free_fn(struct ref_iterator *ref_iterator);\n>>>\n>>> A loop over references now looks something like\n>>>\n>>>> struct ref_iterator *iter = each_ref_in_iterator(\"refs/tags/\");\n>>>> while (ref_iterator_advance(iter)) {\n>>>>         /* code using iter->refname, iter->oid, iter->flags */\n>>>> }\n>> \n>> We'd want to take advantage of the tree-like organization of the\n>> refs (i.e. refs/tags/a and refs/tags/b sit next to each other and\n>> they are closer to each other than they are to refs/heads/a) so that\n>> a request \"I want to iterate only over tags, even though I may have\n>> millions of other kinds of refs\" can be done with cost that is\n>> proportional to how many tags you have.\n>> \n>> The current implementation of for_each_tag_ref() that goes down to\n>> do_for_each_entry() in files-backend.c has that propertly, and the\n>> new iteration mechanism with the above design seems to keep it,\n>> which is very nice.\n>\n> Actually, that is a slight fiction. :)\n>\n> We traverse only the loose ref directories we need, but we populate the\n> entire packed-refs tree in one go. That's fine if you have a reasonable\n> number of refs and care about the cold-cache case (where you care a lot\n> about hitting directories you don't need to, but reading the entire\n> packed-refs file isn't a big deal). But it's really bad if you have an\n> 800MB packed-refs file, as looking up one tiny subset of the entries\n> wastes a lot of RAM and CPU pulling that into our internal\n> representation[1].\n>\n> At one point I wrote a patch to binary search the packed-refs file, find\n> the first \"refs/tags/\" entry, and then walk linearly through there. What\n> stopped me is that the current refs.c code (I guess file-backend.c these\n> days) was not happy with me partially filling in the ref_dir structs in\n> this \"inside out\" way.\n[...]\n\nIsn't this what reftable - an alternative way of storing refs in Git,\ntested by being used by JGit - would solve?  See Christian Couder post\n\"Implementing reftable in Git\"\n\n  https://public-inbox.org/git/CAP8UFD0PPZSjBnxCA7ez91vBuatcHKQ+JUWvTD1iHcXzPBjPBg@mail.gmail.com/t/#u\n\n'Efficient lookup of an entire namespace, such as refs/tags/' is\nallegedly one of the objectives of this format.\n\nRegards,\n-- \nJakub Narębski\n"},{"id":"348705","messageId":"20180529165221.GB13385@sigill.intra.peff.net","threadId":"41887","inReplyTo":"86h8mu1g8j.fsf@gmail.com","subject":"Re: RFC: New reference iteration paradigm","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-05-29T16:52:22Z","receivedAt":"2018-05-29T16:52:26Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, May 26, 2018 at 07:25:32PM +0200, Jakub Narebski wrote:\n\n> > At one point I wrote a patch to binary search the packed-refs file, find\n> > the first \"refs/tags/\" entry, and then walk linearly through there. What\n> > stopped me is that the current refs.c code (I guess file-backend.c these\n> > days) was not happy with me partially filling in the ref_dir structs in\n> > this \"inside out\" way.\n> [...]\n> \n> Isn't this what reftable - an alternative way of storing refs in Git,\n> tested by being used by JGit - would solve?  See Christian Couder post\n> \"Implementing reftable in Git\"\n> \n>   https://public-inbox.org/git/CAP8UFD0PPZSjBnxCA7ez91vBuatcHKQ+JUWvTD1iHcXzPBjPBg@mail.gmail.com/t/#u\n> \n> 'Efficient lookup of an entire namespace, such as refs/tags/' is\n> allegedly one of the objectives of this format.\n\nThe thread you are responding to is over 2 years old. ;)\n\nSince then, Michael rewrote the packed-refs code to handle this case,\nand we mmap and binary-search the file since v2.15.\n\nReftables would also have (amortized) log-n lookup, and also fix some\nother problems (like lack of atomic transactions). So yes, I hope we do\neventually move to reftable, too.\n\n-Peff\n"}]}