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

Re: [PATCH] Preallocate hash tables when the number of inserts are known in advance

From
Junio C Hamano <gitster@pobox.com>
Date
Mar 17, 2013, 05:34 UTC
Message-ID
<7vzjy2si7l.fsf@alter.siamese.dyndns.org>
In-Reply-To
<1363490886-29729-1-git-send-email-pclouds@gmail.com>
Nguyễn Thái Ngọc Duy <pclouds@gmail.com> writes:
Show 5 quoted lines
> This avoids unnecessary re-allocations and reinsertions. On webkit.git
> (i.e. about 182k inserts to the name hash table), this reduces about
> 100ms out of 3s user time.
>
> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>

I think this is a very good idea, but I would prefer the second parameter to the "preallocate" to be "expected number of entries" and have the preallocate, which is a part of the hash API, decide how to inflate that number to adjust to the desired load factor of the hash table. We shouldn't have to adjust the caller when the internal implementation of the hash table changes.

Show 5 quoted lines
> ---
>  nd/read-directory-recursive-optim reduces the number of input (from
>  182k to 11k on webkit) to exclude machinery that all patches in the
>  exclude optimization series I posted seem insignificant. So I won't
>  repost them for inclusion unless you think it has cleanup values.

Sorry, without a pointer, it is unclear what "exclude optimization series" you are referring to.

Previous: Nguyễn Thái Ngọc DuyNext: Duy Nguyen
Message 2 of 5 in “Preallocate hash tables when the number of inserts are known in advance”
  1. Preallocate hash tables when the number of inserts are known in advanceNguyễn Thái Ngọc Duy, Mar 17, 2013
  2. Junio C HamanoMar 17, 2013
  3. Duy NguyenMar 17, 2013
  4. Junio C HamanoMar 17, 2013
  5. Jeff KingMar 17, 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.