[prev in list] [next in list] [prev in thread] [next in thread] 

List:       rsync
Subject:    Re: bugfix: indeterministic file choice from multiple sources
From:       Dirk Pape <pape () inf ! fu-berlin ! de>
Date:       2004-08-26 7:18:52
Message-ID: 0BB9824D900C1331675B6314 () eremix
[Download RAW message or body]

Hello Paul,

--Am Mittwoch, 25. August 2004 16:59 Uhr +0200 schrieb Paul Slootman 
<paul@debian.org>:

> In the meantime I'm curious about the relative memory usage of qsort
> vs. mergesort.  I'd hate rsync's memory usage to go up again.

as far as I am informed (I am not a profi in complexity)

mergesort has better worst case time complexity and equal average time 
complexity than/as quicksort

space complexity is also the same (both are linear :-) but mergesort uses 
double space of quicksort in worst case.

On Linux with gnulibc libc chooses mergesort instead of qsort for you if 
"space is enough" (I hate *this* hidden "optimisation"!). So if you are 
experiencing too high memory consumption with long file lists on Linux you 
might actual see mergesort at work.

Dirk.
-- 
To unsubscribe or change options: http://lists.samba.org/mailman/listinfo/rsync
Before posting, read: http://www.catb.org/~esr/faqs/smart-questions.html
[prev in list] [next in list] [prev in thread] [next in thread]