From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by sourceware.org (Postfix) with ESMTPS id 85FC13858D1E for ; Sun, 31 Dec 2023 06:20:05 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 85FC13858D1E Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=systematicsw.ab.ca Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=systematicsw.ab.ca ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 85FC13858D1E Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=216.40.44.11 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1704003607; cv=none; b=L3wltmvSDUtUcY/+m2S9S6CGG3FtioKO3A66qIi25Z5QtRpq4EaXUqcsRBCQH2GicO32FDB+efUTkMyeQVJBHUdyU6PtX9oSjmiAFqP5Nqj/sAqbTRP42DsD91zmwA1ekENslSDAeztfDAmaflFsmbuDRsa13KMNa/SabMVlMbI= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1704003607; c=relaxed/simple; bh=vTOa9nt9tdcm/og1poesLWUlwwKu75W8Pv6z9itC/TU=; h=Message-ID:Date:MIME-Version:From:Subject:To; b=PG/f5S4o7kcu2w0e6NR8DQA6y0KAaTR0pi1DaynHgccE5zd8oxut87oF9OG4l6W4P6LyxooKlC87cRgKtzvEVAtzWby0oLw2ulvHlLIA1Ak/eQWqgWrwZvqrGhdmJmanE4K5rGCUCptFv+c/3b+gigHE729Qj80JR5Jkl0wBdqI= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from omf01.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id 866C61A0319 for ; Sun, 31 Dec 2023 06:20:04 +0000 (UTC) Received: from [HIDDEN] (Authenticated sender: Brian.Inglis@SystematicSW.ab.ca) by omf01.hostedemail.com (Postfix) with ESMTPA id 0219C60009 for ; Sun, 31 Dec 2023 06:20:01 +0000 (UTC) Message-ID: Date: Sat, 30 Dec 2023 23:20:01 -0700 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird From: brian.inglis@systematicsw.ab.ca Reply-To: "newlib@sourceware.org" Subject: Re: [PATCH] Implement introsort for qsort Content-Language: en-CA To: newlib@sourceware.org References: <20231230195940.1989559-1-visitorckw@gmail.com> Autocrypt: addr=brian.inglis@systematicsw.ab.ca; keydata= xjMEXopx8xYJKwYBBAHaRw8BAQdAnCK0qv/xwUCCZQoA9BHRYpstERrspfT0NkUWQVuoePbN LkJyaWFuIEluZ2xpcyA8QnJpYW4uSW5nbGlzQFN5c3RlbWF0aWNTdy5hYi5jYT7ClgQTFggA PhYhBMM5/lbU970GBS2bZB62lxu92I8YBQJeinHzAhsDBQkJZgGABQsJCAcCBhUKCQgLAgQW AgMBAh4BAheAAAoJEB62lxu92I8Y0ioBAI8xrggNxziAVmr+Xm6nnyjoujMqWcq3oEhlYGAO WacZAQDFtdDx2koSVSoOmfaOyRTbIWSf9/Cjai29060fsmdsDM44BF6KcfMSCisGAQQBl1UB BQEBB0Awv8kHI2PaEgViDqzbnoe8B9KMHoBZLS92HdC7ZPh8HQMBCAfCfgQYFggAJhYhBMM5 /lbU970GBS2bZB62lxu92I8YBQJeinHzAhsMBQkJZgGAAAoJEB62lxu92I8YZwUBAJw/74rF IyaSsGI7ewCdCy88Lce/kdwX7zGwid+f8NZ3AQC/ezTFFi5obXnyMxZJN464nPXiggtT9gN5 RSyTY8X+AQ== Organization: Systematic Software In-Reply-To: <20231230195940.1989559-1-visitorckw@gmail.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Stat-Signature: 6geweba917dfdeoyjrdz6936dbmnd6bq X-Rspamd-Server: rspamout07 X-Spam-Status: No, score=-2.2 required=5.0 tests=BAYES_00,KAM_DMARC_STATUS,KAM_SHORT,RCVD_IN_DNSWL_NONE,RCVD_IN_MSPIKE_H3,RCVD_IN_MSPIKE_WL,SPF_HELO_PASS,SPF_PASS,TXREP,T_SCC_BODY_TEXT_LINE,UNPARSEABLE_RELAY autolearn=ham autolearn_force=no version=3.4.6 X-Rspamd-Queue-Id: 0219C60009 X-Session-Marker: 427269616E2E496E676C69734053797374656D6174696353572E61622E6361 X-Session-ID: U2FsdGVkX183or2BUcqnNOuZhqDG/w2Wn/NpAv+1OIk= X-HE-Tag: 1704003601-125788 X-HE-Meta: U2FsdGVkX1+9MrvhN4VUlPg2AEwdTv2gCjQR5uumCkJCL99cEcw7T31/Wj7RlyDFdrTdNVZmc/Gz/3tIBXRrJeH+VSdmNz01rGFbH36+AYNuXhYV6V56sjrKov7CY6qpRewAnAXpIHRrABHoPrEl7aYKZgdcNvQBlBVf+4FZnswRW3emiblQASEHs9lCw0xD+t66R6YasrQlp5g9qK/q4om+ZjlmEW4a0qwHyadnif08Ce9GYSu5VXVtwiEt8euqigE/U8tiziFaZ1rrMH8n4CH5WVSLl8ZAaq1D9aDzODHEPnBWkxkO4yA2eW54/47rEidktG1BpoHtXucnhWiWKUEztQFnxdD3io0SUNxoWpLRefVPerA+L46XI/3PdKV+qzVhlFsGxGoiHGDzoOIIVGX4rwIzN4GrL/sVr+KjvcnEcrFql86F10LNv53w9ytYLoSN1c3ZEoCMgI+R/pKKoI0m0p2+EexOSH23YC3PwU9Wd+bRIyLjfUV3feA2xVQyh+euuY4fjHOMRVvd1Qjk9w== X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: On 2023-12-30 12:59, Kuan-Wei Chiu wrote: > Enhances the qsort implementation by introducing introsort to address > the worst-case time complexity of O(n^2) associated with quicksort. > Introsort is utilized to switch to heapsort when quicksort recursion > depth becomes excessive, ensuring a worst-case time complexity of > O(n log n). > > The heapsort implementation adopts a bottom-up approach, significantly > reducing the number of required comparisons and enhancing overall > efficiency. > > Refs: > Introspective Sorting and Selection Algorithms > David R. Musser > Software—Practice & Experience, 27(8); Pages 983–993, Aug 1997 > https://dl.acm.org/doi/10.5555/261387.261395 > > A killer adversary for quicksort > M. D. McIlroy > Software—Practice & Experience, 29(4); Pages 341–344, 10 April 1999 > https://dl.acm.org/doi/10.5555/311868.311871 > > BOTTOM-UP-HEAPSORT, a new variant of HEAPSORT beating, on an average, > QUICKSORT (if n is not very small) > Ingo Wegener > Theoretical Computer Science, 118(1); Pages 81-98, 13 September 1993 > https://dl.acm.org/doi/10.5555/162625.162643 > > Signed-off-by: Kuan-Wei Chiu > --- > To assess the performance of the new introsort and the old quicksort in > worst-case scenarios, we examined the number of comparisons required > for sorting based on the paper "A killer adversary for quicksort." > > Before the patch: > n = 1000, cmp_count = 100853 > n = 2000, cmp_count = 395991 > n = 3000, cmp_count = 885617 > n = 4000, cmp_count = 1569692 > n = 5000, cmp_count = 2448183 > n = 6000, cmp_count = 3521140 > n = 7000, cmp_count = 4788493 > n = 8000, cmp_count = 6250342 > n = 9000, cmp_count = 7906610 > n = 10000, cmp_count = 9757353 > > After the patch: > n = 1000, cmp_count = 27094 > n = 2000, cmp_count = 61500 > n = 3000, cmp_count = 100529 > n = 4000, cmp_count = 136538 > n = 5000, cmp_count = 182698 > n = 6000, cmp_count = 221120 > n = 7000, cmp_count = 259933 > n = 8000, cmp_count = 299058 > n = 9000, cmp_count = 356405 > n = 10000, cmp_count = 397723 See an earlier post on the same issue: https://inbox.sourceware.org/newlib/1361223558.67926.YahooMailNeo@web141001.mail.bf1.yahoo.com/ which addresses points your patch addresses, with more analysis, but no data or tests, and was not reworked or resubmitted as a valid patch. You may also wish to look at the BSD implementations for comparison to see how they may have addressed these issues, and replace current newlib with an update from another distro, that has already received live testing. Evaluating sort implementations requires you to also look at number of moves as well as comparisons - reducing comparisons is only useful if that results in fewer data moves - in general doing (not too many) more comparisons to make fewer moves gives better performance, so you have to check that, and also measure stack and memory used, as newlib may be built for some low memory targets, which may need some light sorting done, but not at the expense of (much) more memory or time used. So you also have to compare behaviour of different test data, including all rows identical, already in forward and in reverse order, two values out of order repeated to fill the array, in alternating rows and alternate halves, and other documented antagonistic sequences, with pre- and post-change counts and times, to check there are no data-dependent regressions in time taken or space used. You may want to make your improved sort implementation available in a way that allows easily switching it in and out, using definitions or config options, so that you, or other newlib users, can easily do their own comparisons. -- Take care. Thanks, Brian Inglis Calgary, Alberta, Canada La perfection est atteinte Perfection is achieved non pas lorsqu'il n'y a plus rien à ajouter not when there is no more to add mais lorsqu'il n'y a plus rien à retirer but when there is no more to cut -- Antoine de Saint-Exupéry