Re: [PATCH] Avoid a useless prefix lookup in strbuf_expand()

From: René Scharfe <rene.scharfe@lsrfire.ath.cx>
Date: Jan 2, 2008, 18:11 UTC
Message-ID: <477BD3B4.2070708@lsrfire.ath.cx>
In-Reply-To: <e5bfff550712300546o167c460bl4628d87f8a4e14db@mail.gmail.com>

Marco Costalba schrieb:

Show 24 quoted lines

> Currently the --prett=format prefix is looked up in a
> tight loop in strbuf_expand(), if found is passed as parameter
> to format_commit_item() that does another search using a
> switch statement to select the proper operation according to
> the kind of prefix.
> 
> Because the switch statement is already able to discard unknown
> matches we don't need the prefix lookup before to call format_commit_item()
> 
> This patch removes an useless loop in a very fasth path,
> used by, as example, by 'git log' with --pretty=format option
> 
> Signed-off-by: Marco Costalba <mcostalba@gmail.com>
> ---
> 
> This patch is somewhat experimental and is not intended to be merged as is.
> 
> That's what is missing:
> 
> - Matching of multi char prefixes is not 100% reliable, as example to match
>   prefix "Cgreen" only the first 'C' and the third char 'e' is
> checked, this could
>   lead to aliases in case of malformed prefixes, as example something like
>   "Cxxexxxx" will match the same.

Well, you need to undo this optimization if you remove the loop that makes sure that only valid placeholders are passed to the callback function -- the result would be that you only move the prefixcmp() from strbuf_expand() into the callbacks.

A better way to speed up strbuf_expand() may be to require the list of placeholders to be sorted, their count to be passed on and then to replace the sequential lookup with a binary search. --pretty=format currently recognizes 29 placeholders, which might be a high enough number for a more complicated search method to pay off.

> marco@localhost linux-2.6]$ time git log --topo-order --no-color
> --parents -z --log-size --boundary
> --pretty=format:"%m%HX%PX%n%an<%ae>%n%at%n%s%n%b" HEAD > /dev/null

In your special case it would be even faster to simply reorder the list with decreasing number of occurrence. Of course it's hard to guess how often a particular placeholder is used in the wild, but moving %n from next to last to first place should be a safe bet.

René