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

Re: [RFC] Use a 16-tree instead of a 256-tree for storing notes

From
Johan Herland <johan@herland.net>
Date
Aug 26, 2009, 14:43 UTC
Message-ID
<200908261643.45097.johan@herland.net>
In-Reply-To
<4A95383A.4080104@op5.se>
On Wednesday 26 August 2009, Andreas Ericsson wrote:
> Alex Riesen wrote:
> > On Wed, Aug 26, 2009 at 14:56, Johan Herland<johan@herland.net> 
wrote:
> >> On Wednesday 26 August 2009, Alex Riesen wrote:
> >>> On Wed, Aug 26, 2009 at 12:31, Johan Herland<johan@herland.net> 
wrote:
Show 24 quoted lines
> >>>> The 256-tree structure is considerably faster than storing all
> >>>> entries in a
> >>>
> >>> This part is confusing. Was 256-tree better (as in "faster")
> >>> then?
> >>
> >> 256-tree is faster than the everything-in-hash_map draft.
> >> 16-tree is slightly faster than 256-tree
> >>
> >> 256-tree uses more memory (in the worst case) that the
> >> everything-in-hash-map draft.
> >> 16-tree uses less memory than both.
> >>
> >> Makes sense?
> >
> > Oh, it does, it is just confusingly presented. How about:
> >
> > The 16-tree is both faster and has lower footprint then 256-tree
> > code, which in its turn is noticably faster and smaller then
> > existing hash_map implementation. ...
>
> If it's to be squashed in, why mention the 256-tree at all (except
> for possibly as something to compare with at the end)?
> If it goes on top, why mention the hash_map at all?

Ah. Sorry for the confusion. These patches are not meant to standalone patches in the jh/notes series. They just compare various solutions to the problem of parsing a notes tree structure with fanout in an efficient manner.

The next iteration of the jh/notes series will include the preferred solution (16-tree unless something better shows up), _without_ talking about the differences between alternative solutions. As such the hash_map and 256-tree will not be mentioned at all.

...Johan
-- 
Johan Herland, <johan@herland.net>
www.herland.net
Previous: Andreas EricssonNext: Johannes Schindelin
Message 24 of 30 in “[PATCHv3 0/8] RESEND: git notes”
  1. Johan HerlandJul 29, 2009
  2. 1/8 Introduce commit notesJohan Herland, Jul 29, 2009
  3. Alex RiesenJul 29, 2009
  4. Johannes SchindelinJul 29, 2009
  5. Johan HerlandJul 30, 2009
  6. Johannes SchindelinJul 30, 2009
  7. Johan HerlandJul 30, 2009
  8. 2/8 Add a script to edit/inspect notesJohan Herland, Jul 29, 2009
  9. 3/8 Speed up git notes lookupJohan Herland, Jul 29, 2009
  10. 4/8 Add an expensive test for git-notesJohan Herland, Jul 29, 2009
  11. 5/8 Teach "-m <msg>" and "-F <file>" to "git notes edit"Johan Herland, Jul 29, 2009
  12. Thomas RastJul 29, 2009
  13. Johan HerlandJul 30, 2009
  14. 6/8 First draft of notes tree parser with support for fanout subtreesJohan Herland, Jul 29, 2009
  15. Johannes SchindelinJul 29, 2009
  16. Testing performance of the notes lookup code (Was: [PATCHv3 6/8] First draft of notes tree parser with support for fanout subtrees)Johan Herland, Jul 30, 2009
  17. [RFC] First draft of 256-tree structure for storing notesJohan Herland, Aug 1, 2009
  18. [RFC] Store subtree entries in the same hash map as the note entriesJohan Herland, Aug 13, 2009
  19. [RFC] Use a 16-tree instead of a 256-tree for storing notesJohan Herland, Aug 26, 2009
  20. Alex RiesenAug 26, 2009
  21. Johan HerlandAug 26, 2009
  22. Alex RiesenAug 26, 2009
  23. Andreas EricssonAug 26, 2009
  24. Johan HerlandAug 26, 2009
  25. Johannes SchindelinAug 27, 2009
  26. 7/8 fast-import: Add support for importing commit notesJohan Herland, Jul 29, 2009
  27. Shawn O. PearceJul 29, 2009
  28. Johan HerlandJul 30, 2009
  29. 8/8 t3302-notes-index-expensive: Speed up create_repo()Johan Herland, Jul 29, 2009
  30. Johannes SchindelinJul 29, 2009

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.