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

hashmap vs khash? Re: [PATCH] packfile.c: speed up loading lots of packfiles.

From
EWEric Wong <e@80x24.org>
Date
Nov 28, 2019, 00:42 UTC
Message-ID
<20191128004202.GA25910@dcvr>
In-Reply-To
<20191127222453.GA3765@owl.colinstolley.com>
Colin Stolley <cstolley@runbox.com> wrote:
Show 5 quoted lines
> When loading packfiles on start-up, we traverse the internal packfile
> list once per file to avoid reloading packfiles that have already
> been loaded. This check runs in quadratic time, so for poorly
> maintained repos with a large number of packfiles, it can be pretty
> slow.

Cool! Thanks for looking into this, and I've been having trouble in that department with big alternates files.

> Add a hashmap containing the packfile names as we load them so that
> the average runtime cost of checking for already-loaded packs becomes
> constant.
Btw, would you have time to do a comparison against khash?

AFAIK hashmap predates khash in git; and hashmap was optimized for removal. Removals don't seem to be a problem for pack loading.

I'm interested in exploring the removing of hashmap entirely in favor of khash to keep our codebase smaller and easier-to-learn. khash shows up more in other projects, and ought to have better cache-locality.

Thanks again.
Previous: Colin StolleyNext: Junio C Hamano
Message 2 of 15 in “packfile.c: speed up loading lots of packfiles.”
  1. packfile.c: speed up loading lots of packfiles.Colin Stolley, Nov 27, 2019
  2. hashmap vs khash? Re: [PATCH] packfile.c: speed up loading lots of packfiles.Eric Wong, Nov 28, 2019
  3. Junio C HamanoNov 30, 2019
  4. Jeff KingDec 2, 2019
  5. SZEDER GáborDec 2, 2019
  6. Jeff KingDec 2, 2019
  7. Taylor BlauDec 3, 2019
  8. Jeff KingDec 3, 2019
  9. Junio C HamanoDec 3, 2019
  10. Colin StolleyDec 3, 2019
  11. Jeff KingDec 3, 2019
  12. Junio C HamanoDec 4, 2019
  13. Jeff KingDec 3, 2019
  14. Jonathan NiederDec 4, 2019
  15. Taylor BlauDec 3, 2019

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.