Re: [PATCH] branch as a builtin (again)

From: Johannes Schindelin <johannes.schindelin@gmx.de>
Date: Aug 21, 2006, 21:25 UTC
Message-ID: <Pine.LNX.4.63.0608212323420.28360@wbgn013.biozentrum.uni-wuerzburg.de>
In-Reply-To: <59ad55d30608211337jabd515bra3566fbd0f7ba5a0@mail.gmail.com>

Hi,

On Mon, 21 Aug 2006, Kristian Høgsberg wrote:

Show 15 quoted lines

> On 8/21/06, Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:
> > Hi,
> > 
> > On Mon, 21 Aug 2006, Kristian Høgsberg wrote:
> > 
> > > Thanks to all who reviewed the patch, here's an updated version which
> > > should address all issues.
> > 
> > I would have preferred the use of path_list instead of rolling your own
> > thing with qsort(), but oh well.
> 
> Yeah, I saw that, but since I got flack for computing
> lookup_commit_reference(head_sha1) inside the delete_branches loop, I
> couldn't possibly risk the performance bottle neck of listing the
> branches using a O(n^2) insertion sort.

Insertion sort, as implemented in path_list, has an average O(n log(n)) runtime, and a worst-case O(n^2) runtime. Same as qsort...

Besides, it is not like we are dealing with millions of branches here. And using path_list _would_ make the code shorter.

Ciao, Dscho