From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/11933 Path: news.gmane.org!.POSTED!not-for-mail From: Markus Wichmann Newsgroups: gmane.linux.lib.musl.general Subject: Re: Wrong info in libc comparison Date: Fri, 15 Sep 2017 21:18:46 +0200 Message-ID: <20170915191846.wvjp2x4u4nobhi52@voyager> References: <20170913135154.pfwpg7f32nv4dhja@voyager> <20170913181010.GS1627@brightrain.aerifal.cx> <20170913185106.ddbgztckagdojcdd@voyager> <20170913192528.GA15263@port70.net> <20170913195306.GU1627@brightrain.aerifal.cx> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: blaine.gmane.org 1505503140 24742 195.159.176.226 (15 Sep 2017 19:19:00 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Fri, 15 Sep 2017 19:19:00 +0000 (UTC) User-Agent: NeoMutt/20170113 (1.7.2) To: musl@lists.openwall.com Original-X-From: musl-return-11946-gllmg-musl=m.gmane.org@lists.openwall.com Fri Sep 15 21:18:56 2017 Return-path: Envelope-to: gllmg-musl@m.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by blaine.gmane.org with smtp (Exim 4.84_2) (envelope-from ) id 1dsw8e-0006IF-4I for gllmg-musl@m.gmane.org; Fri, 15 Sep 2017 21:18:56 +0200 Original-Received: (qmail 3675 invoked by uid 550); 15 Sep 2017 19:19:00 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Original-Received: (qmail 3655 invoked from network); 15 Sep 2017 19:18:59 -0000 Content-Disposition: inline In-Reply-To: <20170913195306.GU1627@brightrain.aerifal.cx> X-Provags-ID: V03:K0:FIuvlcemqDvc2Yl2NyBBoCtnYCy6Ab2m5lKsX5DB18OO7sMgUlj M4/ZTN6BRhNKtEVVVOlcNL4/YEEGrT6PHUNvEy0812X3kPyyODUokREAAvxP/Iej3VWqCyY s9ygLxJu8Zgr6T01EBDSigXzu/T2AS47hlEZc1j72kOEILkVwA8tnaUGCHM+PaDymSW2mzk ABjjqXKUQbr70KSRWDJbQ== X-UI-Out-Filterresults: notjunk:1;V01:K0:RC9Vd431pI0=:TM0rcH/Hx/dM3+S8U4k8uO pwLxFSl6hHqe5okFRnRsZYbAbGG/vU/KrW62Fx2rFMxxZQiXuc6EGeNDamtN3pkZow9caP8z3 XPEaH3gTLqZu3nQlL8UxdnuiIoHC93fo+5I4wJ6PLtNoN0+U/B6js7ZF2dsJxSXfdEIbKxBkx 50sFUMFkcoIIvMlQb98iqdixGt91jY/Lp/zgGtJXamR8NUYcgnxpgc1isP1DkdZ9UsBV+GEvQ OABj+TvNKrrKlhQz7oktuTGHxe0gJ9Z/yyOuFZjncCB78vbls4YoVQvi3xCy4jmffQAgpYeFk tMoMBV++8EWM2HdLKz3rRtPcwD0YD/VJ6sfjpJZ6MHFkkafwduojvgtvj89leIXkbhzcQxz5C uRefUa5Eb6Q1Jyzw/EUP3akxghHhCiuZxGQj8yB9MbFht4IQ43LYRNMbU2DjN7v+WCYyBzI7L yWfJbfSL4d5oyzjhtJTBF6GWPUzQf+tsUrK88jXH7lQ5elHUamS88QUSWoZwLn+c3wkC2nnIT YbZ3Tl3URzAeEE2wyqoDSpRr0+WIFsoKRKOhlCKcbhFegAXu4Iswz+fmZhZXYyxsMIsWTgjjn S98YWqpaJR2efZvX7sZzJc6F2Wq5HM+m/84+cH3kgSYFV7AuHS97dtVJZMLv3j1Nk9qBJtzA6 sYJmgwnxzZ31n7aXRHIu5wkEsi99SWJ+Xy+abVVQC/juagucnwcL/RMSDfnN1YPcXej7/W8rR v0/PGuFf/wGJoRMISk3gNHiytBV4BhSC9dF/K88xzYb2aroH3KAuFvFJ+6hh4l2CUEQZ+IEv Xref: news.gmane.org gmane.linux.lib.musl.general:11933 Archived-At: On Wed, Sep 13, 2017 at 03:53:06PM -0400, Rich Felker wrote: > If you're considering big-O, where n->infinity (or at least to the > largest value that can fit in memory), malloc most certainly has > failed (because the array to be sorted already filled memory) and > you're looking at the "fallback" case. > I think we're getting sidetracked here. Every libc worth its salt uses a loglinear sorting algorithm. Thus they are all equal in that regard. Only exception to this I've ever seen is uclibc, which uses Shell sort with Pratt's sequence, which is O(sqrt(n^3)) instead (is there a snappy term for this complexity?) Besides, big-O is also about the behavior of time on change of space (what happens if the problem doubles in size?). > Maybe the comparison of sort algorithm used is interesting for reasons > other than just big-O though, in which case mentioning the "merge > (when it fits in memory)" would probably be helpful. > > Rich Algorithms can be compared on a number of metrics, and just the name doesn't tell us much (e.g. quicksort with naive "first element" pivot selection has a pathological case on sorted input, while quicksort with med3 pivot selection handles that very well). If you really want to know something specific, you'll have to look it up in source, anyway. But, if you do give a name, make sure it's the right one. Ciao, Markus