From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Andrew Cohen Newsgroups: gmane.emacs.devel Subject: Re: sorting in C Date: Wed, 23 Feb 2022 21:52:20 +0800 Message-ID: <878ru1heqz.fsf@ust.hk> References: <87ilt7bokp.fsf@ust.hk> <83tucrt75y.fsf@gnu.org> <8735kakymb.fsf@ust.hk> <835yp5u5h7.fsf@gnu.org> <87ee3thhh3.fsf@ust.hk> <83zgmhsp13.fsf@gnu.org> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="17341"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) Cc: emacs-devel@gnu.org To: Eli Zaretskii Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Wed Feb 23 15:02:32 2022 Return-path: Envelope-to: ged-emacs-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1nMsDu-0004J0-Ip for ged-emacs-devel@m.gmane-mx.org; Wed, 23 Feb 2022 15:02:32 +0100 Original-Received: from localhost ([::1]:39660 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1nMsDt-00021K-1B for ged-emacs-devel@m.gmane-mx.org; Wed, 23 Feb 2022 09:02:29 -0500 Original-Received: from eggs.gnu.org ([209.51.188.92]:42296) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nMs4H-0000IZ-0y for emacs-devel@gnu.org; Wed, 23 Feb 2022 08:52:33 -0500 Original-Received: from mail-tycjpn01on2100.outbound.protection.outlook.com ([40.107.114.100]:25083 helo=JPN01-TYC-obe.outbound.protection.outlook.com) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nMs4C-0005hl-UB; Wed, 23 Feb 2022 08:52:31 -0500 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=n3YTdwWfGDptamyBOIh+ybuX0K61l98q6rQhOf28YG6eAu4kcWitRda405TjfJXBs4fZe7lTuRJ8blIn7+KOXYeVy74B07zGDIK2X2RkD2yHuq44l8LeQu5MQbDJpOVYtJHRd9yp3p/d5h0GzBsov4iNUPboTHYeY7MCrnkfyYAL/zxW8DBL1F1tIFNBmIiyZJ2guFBUmklwjXCu4gBSOB5sHTOy6jrwN8YBo9gb+FEeYmzwYU8w+bCJm7PvqjRPHAgktSNicGmAOd+bcU8ct9yF1f7aBHyFS849MNUzGbvwu+xYSpFVsrFUZBDRVnWfyEaBMl+RsXUa3kNjqLAKGQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=bc15njuY8szC4YaJz0rbKb2GMp04TNHV71xx/V+DKjE=; b=CU2kTHj/WrcpSiu7bO9Xy58cVG0CtFlgh0AErLYnOmP8uFL6P5tIGJEx1Pm5z64kisZ6WtyMO7q/k4w78Ag43w6fsUbr+2euDyGNXPF4Oi2UotS3/RBavAqxUkDbUprW7R8zFb9vEkW0rwrhZSWBGxtPQrd2/eOqUP0ew1nT2xZ45sqfIuaBZfXmMxU2krXRR1Rzvd3EPmGZMKdfkc1rHZdUMf+maeCQQL5eKoR/zQIEcyYFIKwQLvXMyF2iDmD6JDUw2maP0GZZVbliBUy7SLZZD18tev6rQPcsFtNZSUO6T7Fl1nd4SiUZSERk8ZCyPkSrgdCU2MvVipgNi77bUw== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=ust.hk; dmarc=pass action=none header.from=ust.hk; dkim=pass header.d=ust.hk; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ust.hk; s=selector2; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=bc15njuY8szC4YaJz0rbKb2GMp04TNHV71xx/V+DKjE=; b=jmhLjWlaNWgTx0ZnjqulCtSZZ0qSV8F/nx+VmUVUV4emfXuJyVe4UyWukUX/rUcHKcYzzY1qKArdJTOmLLsXob/aEEg4wUtYyzREZ+KNs2sxww4etEo5MGuj/7t3Ft3XNSTOCQy41eTVfPnJRcV8Hwmd/8LVT+2lzNy8XuOrbD3vC9Hfi0VODpd4lHjxAuyJr0jPVxf36tnwnui6qC3e2oYBeYMvkTYLg0VMQHHam1fbNTJM6Y+UvMu6Vyaw81AmZjtPLfBr0X1sOu7rom1pkcgoS8efLqpubY7qToeMu3/IrDtQp7WjqOg3Hzakel17GC72HqO1V7bOAgmB2zFT6w== Authentication-Results: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=ust.hk; Original-Received: from OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM (2603:1096:604:1bf::11) by TYCP286MB1250.JPNP286.PROD.OUTLOOK.COM (2603:1096:400:b9::14) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5017.22; Wed, 23 Feb 2022 13:52:24 +0000 Original-Received: from OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM ([fe80::3dec:f964:3c31:30f]) by OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM ([fe80::3dec:f964:3c31:30f%7]) with mapi id 15.20.5017.022; Wed, 23 Feb 2022 13:52:23 +0000 In-Reply-To: <83zgmhsp13.fsf@gnu.org> (Eli Zaretskii's message of "Wed, 23 Feb 2022 08:14:39 -0500") X-ClientProxiedBy: HK2PR04CA0070.apcprd04.prod.outlook.com (2603:1096:202:15::14) To OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM (2603:1096:604:1bf::11) X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: 7a026bc9-70a9-4850-7702-08d9f6d3b7ff X-MS-TrafficTypeDiagnostic: TYCP286MB1250:EE_ X-Microsoft-Antispam-PRVS: X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: feV4w9trVd3aVJcmI+CAoU2WhowT5rY1MoqFVbKMxetoBENuITvajPiknyJp/BqYsNpTt5slGKY79GR8nt1RPt32lLB7lR1MAOKj4c/i163drbOSyE0Wom6GSOjgw8N/aQUdvfjd+NRTbKnCgh1uAJkPM2xLbtGC3j1/yahKHCXotEHonZFmGYShywq1hl9Sfb/P9MObSoUa8iuf8AS4PLL30I0817xYmMrDW3XZHwUnkUnbODkiEEub57RDXhA4evgZIiZMyT9IiOHvDUkP0qCsx3Eo5PJVe0cLfTOz2JUjhvCzEEpyAqzJF6uWAMW6iqVpGaWyret/64m4W3FfDdfZ6XMVe308NcQ2kx2JPOwcaKNkSkrKb3EtbHDlhwRlrhUDwcfOziWJ+ugmC6pxhAC/Rl2CoKcoLakx4W5cloAZvGCGUdRPeJhvRL9r7gs43GmsHR9t+BhgwE1yTueKNWwa/q43PSYWY3lT1ELKXtcWlT7XkqpLMP8yisyApQp2kYGRBUo1aSyCLEGvcch8HTXZPjcKW3E7f1v9O9a8y/dqox5wdVxHpPqqIeBfmeA3sFqnGfWw7Q90LpFiPsOUJDcTIYo4jRP0PeFKnOSjljAmxSsr2GM5tRVpVeaHxkbEiOqzhzs/KHiOL09BzIvEHw== X-Forefront-Antispam-Report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM; PTR:; CAT:NONE; SFS:(13230001)(4636009)(366004)(508600001)(6506007)(6512007)(6486002)(4326008)(7116003)(8676002)(450100002)(66476007)(66556008)(66946007)(5660300002)(8936002)(2906002)(38100700002)(786003)(6916009)(36756003)(316002)(186003)(26005)(2616005)(86362001)(3480700007); DIR:OUT; SFP:1102; X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?/QXbeYOyy36vKvEJROXVjj5se7n72U7tRncEA+2JLEjb0K/mV9R1TJuvPGdJ?= =?us-ascii?Q?xRiUWVGLkSt2K8pHbWOqttVOckJXltq76IcLFXOYDjis23D8Uwm5oph1yLlz?= =?us-ascii?Q?+BMypm338GA4R+CPd/4CcdBzum4+2zSYK3SNfwiegrPWT0Hj3DPBdOwfi9X9?= =?us-ascii?Q?4mvRP++ZENmFxN6cfM7e7885f7QPuzFZ2TqKkSnvXuzWdhv9KEiB/KXfhxny?= =?us-ascii?Q?SAxiu9pkUAhCnaYqwe/1NzmPkon/hitVa2YPkT9RQiPmr8oYVmYs1CUTLoPt?= =?us-ascii?Q?TYxh6gHQWcAlkygu2FRDP8ikDIdpye9iwXqr+Pf8NcD+swhwdTTAP5UhYhZL?= =?us-ascii?Q?WOkAk934n8iRip0H4MEE2j/vUK2/PFK9N2Mav9U6KQ+20NP4Lf4Vp2XO5iLK?= =?us-ascii?Q?5GDeApG4KzTEaUPN+8VYrvaqIi5JfL9bjsSAU1a9eberkyjsvXO5V/mcnnf+?= =?us-ascii?Q?u04eJMCK3sSjJ9aEOcXZGChmn0LYSLWXF7c4d9eF7vYlKAoh0wLOU5NGcG+W?= =?us-ascii?Q?yZRwU33wzHIbD0QUEAkfLiL6vIUyxuPSuy73Yze/SqFiT9+bhASu3fTdNMVQ?= =?us-ascii?Q?Rwmbn/dEK+iQy9aPVtsYQsqSOgrGXKfom509Ht+LHnoCttbU+vDOJTY3FmHN?= =?us-ascii?Q?tL X-OriginatorOrg: ust.hk X-MS-Exchange-CrossTenant-Network-Message-Id: 7a026bc9-70a9-4850-7702-08d9f6d3b7ff X-MS-Exchange-CrossTenant-AuthSource: OS3P286MB1877.JPNP286.PROD.OUTLOOK.COM X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-OriginalArrivalTime: 23 Feb 2022 13:52:23.7796 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: c917f3e2-9322-4926-9bb3-daca730413ca X-MS-Exchange-CrossTenant-MailboxType: HOSTED X-MS-Exchange-CrossTenant-UserPrincipalName: kkwQxMUGeEnwXY3SpkaNlU34TyUiv/cNAzLydd+7IHhF30GyHB8fqmObOapkEuEZ X-MS-Exchange-Transport-CrossTenantHeadersStamped: TYCP286MB1250 Received-SPF: pass client-ip=40.107.114.100; envelope-from=acohen@ust.hk; helo=JPN01-TYC-obe.outbound.protection.outlook.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.io gmane.emacs.devel:286624 Archived-At: >>>>> "EZ" == Eli Zaretskii writes: [...] EZ> The 5-fold slowdown is a pain, IMO. Can we do better in the EZ> worst case? >> >> Maybe, but probably not too much. That is the point of these >> hybrids---they improve on some cases and do worse on others. Its >> a win only if the real-world data favors the improved case. >> >> I played around a bit more and lowering the length threshold to >> 40 might be a better compromise. I am working on a more thorough >> set of tests first. EZ> OK, thanks. Let's see the improved numbers, and can you also EZ> show absolute times? If they are short enough, the slowdown EZ> might not be significant, since if the data structure is larger, EZ> the slow method will not be used, right? Or did I EZ> misunderstand? Yes, I will show absolute numbers in the future (for reference, it is microseconds). And you did not misunderstand---the "slow" method (which is much faster for sorted lists :)) isn't used for longer cases. [...] EZ> But for showing the performance, the license is not important, EZ> is it? Right, that was sort of a joke---just buying time until I can produce some nice looking data. I'm trying to automate their production a bit more. >> Shouldn't be that difficult (the algorithm itself is >> well-documented) but I'm not sure how much time I have to finish >> it. EZ> From my POV, take all the time you need. Emacs 29 is far from a EZ> release. Great, thanks. -- Andrew Cohen