From: bdowning@lavos•net (Brian Downing)
To: Johannes Schindelin <Johannes.Schindelin@gmx•de>
Cc: Mike Ralphson <mike.ralphson@gmail•com>,
Steffen Prohaska <prohaska@zib•de>,
Junio C Hamano <gitster@pobox•com>, Nicolas Pitre <nico@cam•org>,
Linus Torvalds <torvalds@linux-foundation•org>,
Jakub Narebski <jnareb@gmail•com>,
Git Mailing List <git@vger•kernel.org>
Subject: Re: Some git performance measurements..
Date: Sat, 8 Dec 2007 17:04:03 -0600 [thread overview]
Message-ID: <20071208230402.GK6212@lavos.net> (raw)
In-Reply-To: <Pine.LNX.4.64.0712081103430.27959@racer.site>
On Sat, Dec 08, 2007 at 11:05:35AM +0000, Johannes Schindelin wrote:
> On Fri, 7 Dec 2007, Mike Ralphson wrote:
> > I've just tried the mergesort implementation as used in msysgit and that
> > performs faster for me. It's simpler, and compatibly licensed. It looks
> > good.
>
> Now I'm confused. You said you tested qsortG, NetBSD qsort and qlibc,
> with glibc performing the slowest. Now, 4msysgit's implementation is
> based on glibc (Thanks Brian!), so I wonder if you could redo the
> performance tests and say if qsortG still is substantially faster than
> 4msysgit's qsort?
This is just me guessing, but when he said:
> I benchmarked 3 alternative qsorts, qsortG [2] was the fastest on my
> system but has funky licensing, the NetBSD qsort was middle-range and
> the glibc one the slowest of the three (but that could be due to it
> being tuned for a "Sun 4/260"). All of them show over 100x speed
> improvements on a git-status of my main repo (104s -> ~0.7s)
It's possible he tried glibc's actual quicksort implementation, rather
than their "qsort." Their qsort basically has the following behavior:
if size < 1024
mergesort with temporary array on stack
if allocating size bytes would likely cause swapping
quicksort in place
else
mergesort with temporary array in heap
I removed the "quicksort in place" possibility, as it would have added
another sort algorithm and I had no way to easily determine whether
"allocating size bytes would likely cause swapping."
-bcd
next prev parent reply other threads:[~2007-12-08 23:04 UTC|newest]
Thread overview: 28+ messages / expand[flat|nested] mbox.gz Atom feed top
2007-11-29 2:49 Some git performance measurements Linus Torvalds
2007-11-29 3:14 ` Linus Torvalds
2007-11-29 3:59 ` Nicolas Pitre
2007-11-29 4:32 ` Linus Torvalds
2007-11-29 17:25 ` Nicolas Pitre
2007-11-29 17:48 ` Linus Torvalds
2007-11-29 18:52 ` Nicolas Pitre
2007-11-30 5:00 ` Junio C Hamano
2007-11-30 6:03 ` Linus Torvalds
2007-11-30 0:54 ` Jakub Narebski
2007-11-30 2:21 ` Linus Torvalds
2007-11-30 2:39 ` Jakub Narebski
2007-11-30 2:40 ` Nicolas Pitre
2007-11-30 6:11 ` Steffen Prohaska
2007-12-07 13:35 ` Mike Ralphson
2007-12-07 13:49 ` Johannes Schindelin
2007-12-07 16:07 ` Linus Torvalds
2007-12-07 16:09 ` Mike Ralphson
2007-12-07 18:37 ` Johannes Schindelin
2007-12-07 19:15 ` Mike Ralphson
2007-12-08 11:05 ` Johannes Schindelin
2007-12-08 23:04 ` Brian Downing [this message]
2007-11-30 2:54 ` Linus Torvalds
2007-12-05 1:04 ` Federico Mena Quintero
2007-12-01 11:36 ` Joachim B Haga
2007-12-01 17:19 ` Linus Torvalds
2007-11-29 5:17 ` Junio C Hamano
2007-11-29 10:17 ` [PATCH] per-directory-exclude: lazily read .gitignore files Junio C Hamano
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
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20071208230402.GK6212@lavos.net \
--to=bdowning@lavos$(echo .)net \
--cc=Johannes.Schindelin@gmx$(echo .)de \
--cc=git@vger$(echo .)kernel.org \
--cc=gitster@pobox$(echo .)com \
--cc=jnareb@gmail$(echo .)com \
--cc=mike.ralphson@gmail$(echo .)com \
--cc=nico@cam$(echo .)org \
--cc=prohaska@zib$(echo .)de \
--cc=torvalds@linux-foundation$(echo .)org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox