git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: Strange O(N^3) behavior in "git filter-branch"

From
Drew Northup <drew.northup@maine.edu>
Date
Jul 18, 2011, 16:01 UTC
Message-ID
<1311004870.18654.21.camel@drew-northup.unet.maine.edu>
In-Reply-To
<m3pql8yngt.fsf@localhost.localdomain>
On Mon, 2011-07-18 at 01:59 -0700, Jakub Narebski wrote:
Show 21 quoted lines
> Drew Northup <drew.northup@maine.edu> writes:
> 
> > On Sat, 2011-07-16 at 07:26 +0200, Michael Haggerty wrote:
> > 
> > > Currently, the loose ref cache is stored as a single linked list, so
> > > there is no easy way to populate part of it now and part of it later.
> > > So with the current data structure, the loose refs cache is
> > > all-or-nothing.  It would be possible to avoid filling it if there are
> > > not replace references, but if there is even one loose replace reference
> > > then the whole refs tree would have to be crawled.  Implementing this
> > > variation is alternative 4 from the early email.
> > > 
> > > More flexible would be to change the way the loose ref cache is stored
> > > from a linked list into a tree (probably mirroring the directory tree).
> > 
> > Given the potential for high performance inherent with trees, why mix
> > metaphors like this? What would the gain be?
> 
> Did you mean: "why linked list"?  I _guess_ that it is most probably
> because linked list is simpler and better known data structure than
> non-binary tree.

No, that I can compute. I was asking why mix tree metaphors (pure binary, R/B, and 234 being probably the most common kinds for the data structure; and filesystem "trees"). In my mind I was thinking of SHA1sums as the keys (for some reason that doesn't occur to me right now) and thought perhaps it was worth becoming enlightened (or something). Perhaps I should have looked harder in my mail queue for the patch referenced.

Show 5 quoted lines
> 
> What is needed I think is something like trie[1], but with path
> components and not letters stored in trie nodes.
> 
> [1]: http://en.wikipedia.org/wiki/Trie

Obviously, there are other "tree" structures. That's one I probably should have thought of earlier.

-- 
-Drew Northup
________________________________________________
"As opposed to vegetable or mineral error?"
-John Pescatore, SANS NewsBites Vol. 12 Num. 59
Previous: Jakub NarebskiNext: Michael Haggerty
Message 9 of 11 in “Strange O(N^3) behavior in "git filter-branch"”
  1. Michael HaggertyJul 14, 2011
  2. Michael HaggertyJul 14, 2011
  3. Michael HaggertyJul 15, 2011
  4. Junio C HamanoJul 15, 2011
  5. Jeff KingJul 15, 2011
  6. Michael HaggertyJul 16, 2011
  7. Drew NorthupJul 17, 2011
  8. Jakub NarebskiJul 18, 2011
  9. Drew NorthupJul 18, 2011
  10. Michael HaggertyAug 3, 2011
  11. Jeff KingAug 3, 2011

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.