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

Re: [PATCH 2/2] index-pack: a naive attempt to flatten find_unresolved_deltas

From
Shawn Pearce <spearce@spearce.org>
Date
Dec 8, 2011, 16:42 UTC
Message-ID
<CAJo=hJu35cYkWfBXAoL6OoCLVT4fE-mKjgqyGBN5xRLmiBeRdw@mail.gmail.com>
In-Reply-To
<4ee0be70.44f2320a.3fe8.632b@mx.google.com>
2011/12/8  <pclouds@gmail.com>:
Show 8 quoted lines
> From: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
>
> This seems to work for me. But I think this approach uses (much?) more
> memory because it turns a tree of calls into a flat list of calls and
> keep the list until the end, while the recursive version only has to
> keep one call chain at a time.
>
> Any ideas how to improve it?

Well, fortunately JGit is under a very liberal BSD license and has a pretty efficient version of a heap based algorithm for delta resolution. You could look at [1] for ideas. I am told the BSD license is very compatible with the GPLv2. (Unlike the reverse.)

[1] http://egit.eclipse.org/w/?p=jgit.git;a=blob;f=org.eclipse.jgit/src/org/eclipse/jgit/transport/PackParser.java;hb=HEAD#l556
Previous: pclouds@gmail.com
Message 19 of 19 in “Set hard limit on delta chain depth”
  1. Set hard limit on delta chain depthNguyễn Thái Ngọc Duy, Dec 5, 2011
  2. Erik Faye-LundDec 6, 2011
  3. Nguyen Thai Ngoc DuyDec 6, 2011
  4. Erik Faye-LundDec 6, 2011
  5. Nguyen Thai Ngoc DuyDec 6, 2011
  6. Michael HaggertyDec 6, 2011
  7. Nguyen Thai Ngoc DuyDec 6, 2011
  8. Shawn PearceDec 6, 2011
  9. Jeff KingDec 6, 2011
  10. Junio C HamanoDec 6, 2011
  11. Nguyen Thai Ngoc DuyDec 6, 2011
  12. Junio C HamanoDec 10, 2011
  13. index-pack: eliminate unlimited recursion in get_delta_base()Nguyễn Thái Ngọc Duy, Dec 7, 2011
  14. Shawn PearceDec 8, 2011
  15. Nguyen Thai Ngoc DuyDec 8, 2011
  16. 1/2 index_pack: indent find_unresolved_detals one levelpclouds@gmail.com, Dec 8, 2011
  17. Junio C HamanoDec 9, 2011
  18. 2/2 index-pack: a naive attempt to flatten find_unresolved_deltaspclouds@gmail.com, Dec 8, 2011
  19. Shawn PearceDec 8, 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.