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

Re: [BAD PATCH 0/9] v4-aware tree walker API

From
Duy Nguyen <pclouds@gmail.com>
Date
Oct 12, 2013, 15:59 UTC
Message-ID
<CACsJy8DZvdWyKSvLzPhS7OqKUU-OKG40M7M1HxN4eADsx0od6Q@mail.gmail.com>
In-Reply-To
<alpine.LFD.2.03.1310121001000.3023@syhkavp.arg>
On Sat, Oct 12, 2013 at 9:42 PM, Nicolas Pitre <nico@fluxnic.net> wrote:
Show 19 quoted lines
> On Fri, 11 Oct 2013, Duy Nguyen wrote:
>
>> On Fri, Oct 11, 2013 at 07:22:59PM +0700, Duy Nguyen wrote:
>> > > > Maybe we could make an exception and allow the tree walker to pass
>> > > > pv4_tree_cache* directly to decode_entries so it does not need to do
>> > > > the first lookup every time..
>> > > >
>> > > > Suggestions?
>>
>> Looking at decode_entries() traces I think the "one decode_entries()
>> for one tree_entry()" just amplifies the delta chain effect. If you
>> hide 3 entries behind 5 layers of copy sequences
>> (i.e. tree1->tree2->..->tree5->real-tree-entry), then every
>> decode_entries(count=1) will have to go through 5 layers.
>
> Calling decode_entries() for every tree entry is a bad approach.  We
> should really implement this as a state machine preserving the entire
> state between entries so that moving to the next entry is just a matter
> of advancing a pointer in most cases.

Yeah. Maybe first step is avoid recursion in decode_entries(). We need to do that eventually to avoid stack overlow due to long depths.

-- 
Duy
Previous: Nicolas Pitre
Message 15 of 15 in “v4-aware tree walker API”
  1. 0/9 v4-aware tree walker APINguyễn Thái Ngọc Duy, Oct 9, 2013
  2. 1/9 sha1_file: provide real packed type in object_info_extendedNguyễn Thái Ngọc Duy, Oct 9, 2013
  3. 2/9 pack v4: move v2 tree entry generation code out of decode_entriesNguyễn Thái Ngọc Duy, Oct 9, 2013
  4. 3/9 pv4_tree_desc: introduce new struct for pack v4 tree walkerNguyễn Thái Ngọc Duy, Oct 9, 2013
  5. 4/9 pv4_tree_desc: use struct tree_desc from pv4_tree_descNguyễn Thái Ngọc Duy, Oct 9, 2013
  6. 5/9 pv4_tree_desc: allow decode_entries to return v4 trees, one at a timeNguyễn Thái Ngọc Duy, Oct 9, 2013
  7. 6/9 pv4_tree_desc: complete interfaceNguyễn Thái Ngọc Duy, Oct 9, 2013
  8. 7/9 pv4_tree_desc: don't bother looking for v4 trees if no v4 packs are presentNguyễn Thái Ngọc Duy, Oct 9, 2013
  9. 8/9 pv4_tree_desc: avoid lookup_object() when possibleNguyễn Thái Ngọc Duy, Oct 9, 2013
  10. 9/9 list-object.c: take "advantage" of new pv4_tree_desc interfaceNguyễn Thái Ngọc Duy, Oct 9, 2013
  11. Nicolas PitreOct 9, 2013
  12. Duy NguyenOct 11, 2013
  13. Duy NguyenOct 11, 2013
  14. Nicolas PitreOct 12, 2013
  15. Duy NguyenOct 12, 2013

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.