From: "René Scharfe" <rene.scharfe@lsrfire.ath.cx>
To: Junio C Hamano <gitster@pobox.com>
Cc: mhagger@alum.mit.edu, Jeff King <peff@peff.net>, git@vger.kernel.org
Subject: Re: [PATCH 3/3] refs: use strings directly in find_containing_dir()
Date: Wed, 23 May 2012 00:11:30 +0200 [thread overview]
Message-ID: <4FBC0F12.2000001@lsrfire.ath.cx> (raw)
In-Reply-To: <7vlikj3nzc.fsf@alter.siamese.dyndns.org>
Am 22.05.2012 23:27, schrieb Junio C Hamano:
> René Scharfe<rene.scharfe@lsrfire.ath.cx> writes:
>
>> Why allocate a NUL-terminated copy at all when we can teach the code to
>> stop after a given number of characters just as easily? Alas, this
>> will still trigger an allocation in search_ref_dir() (see first patch).
>
> Yeah, but it is only because search_ref_dir() tries to use ref_entry_cmp(),
> whose signature is geared more towards being used as a qsort(3) callback,
> as the comparison function for bsearch(3).
>
> A bsearch() callback takes two pointers, one is for the key and the other
> for an array element, and there is no reason to require the two types be
> the same.
>
> In other words, something like this patch and we won't need an allocation
> of the ref_entry that did not have to be a full ref_entry in the first
> place (it only had to be something that supplies the "key" into a sorted
> array).
Right, and this order (key-first) is documented for Linux, *BSD and by
Microsoft, so we can probably rely on it. The proposed asymmetry
between sorting and lookup is a bit ... untidy, nevertheless. But it's
certainly worth it to avoid that ugly allocation.
Here's a random observation that led me to write the three patches: When
running the following command under valgrind, it reports a few
interesting numbers for total heap usage:
$ git grep guess xdiff/xutils.c
v1.7.8 591 allocs, 96 frees, 383,565 bytes allocated
v1.7.9 2,940 allocs, 121 frees, 361,001 bytes allocated
v1.7.10 3,002 allocs, 129 frees, 366,487 bytes allocated
master 4,555 allocs, 1,586 frees, 2,380,265 bytes allocated
3 patches 4,079 allocs, 1,110 frees, 430,093 bytes allocated
4 patches 3,093 allocs, 124 frees, 377,749 bytes allocated
With your last patch, I think we're doing fine again, as the total
allocated size is within a few KB of the smallest one in this
arbitrary list of versions.
What has git grep to do with refs? It checks if the path in the command
above is a ref, which makes it iterate over all of them..
René
next prev parent reply other threads:[~2012-05-22 22:11 UTC|newest]
Thread overview: 12+ messages / expand[flat|nested] mbox.gz Atom feed top
2012-05-22 13:16 [PATCH] find_containing_dir(): allocate strbuf less extravagantly mhagger
2012-05-22 17:34 ` Jeff King
2012-05-22 18:50 ` [PATCH 1/3] refs: convert parameter of search_ref_dir() to length-limited string René Scharfe
2012-05-22 18:50 ` [PATCH 2/3] refs: convert parameter of create_dir_entry() " René Scharfe
2012-05-22 18:50 ` [PATCH 3/3] refs: use strings directly in find_containing_dir() René Scharfe
2012-05-22 21:27 ` Junio C Hamano
2012-05-22 22:11 ` René Scharfe [this message]
2012-05-22 22:18 ` Junio C Hamano
2012-05-23 16:20 ` René Scharfe
2012-05-23 16:56 ` Junio C Hamano
2012-05-23 17:15 ` René Scharfe
2012-05-24 4:34 ` Michael Haggerty
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=4FBC0F12.2000001@lsrfire.ath.cx \
--to=rene.scharfe@lsrfire.ath.cx \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
--cc=mhagger@alum.mit.edu \
--cc=peff@peff.net \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).