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

From: René Scharfe <[email-masked]>
Date: Wed, 02 Jan 2008 19:11:00 +0100

Marco Costalba schrieb:
> 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 <[email-masked]>
> ---
> 
> 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é