From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Eli Zaretskii Newsgroups: gmane.emacs.devel Subject: Re: sorting in C Date: Wed, 23 Feb 2022 15:14:48 +0200 Message-ID: <83zgmhsp13.fsf@gnu.org> References: <87ilt7bokp.fsf@ust.hk> <83tucrt75y.fsf@gnu.org> <8735kakymb.fsf@ust.hk> <835yp5u5h7.fsf@gnu.org> <87ee3thhh3.fsf@ust.hk> Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="37258"; mail-complaints-to="usenet@ciao.gmane.io" Cc: emacs-devel@gnu.org To: Andrew Cohen Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Wed Feb 23 14:19:52 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 1nMrYe-0009Wb-0L for ged-emacs-devel@m.gmane-mx.org; Wed, 23 Feb 2022 14:19:52 +0100 Original-Received: from localhost ([::1]:50976 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1nMrYc-0001QW-Ai for ged-emacs-devel@m.gmane-mx.org; Wed, 23 Feb 2022 08:19:50 -0500 Original-Received: from eggs.gnu.org ([209.51.188.92]:52900) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nMrTb-0006Zz-4B for emacs-devel@gnu.org; Wed, 23 Feb 2022 08:14:39 -0500 Original-Received: from [2001:470:142:3::e] (port=50896 helo=fencepost.gnu.org) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nMrTa-00054H-95; Wed, 23 Feb 2022 08:14:38 -0500 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=References:Subject:In-Reply-To:To:From:Date: mime-version; bh=tk6EUCLLtBiY09lJj/iZowV98hvatGWrFcrNZ1irk54=; b=mifY5PMjCQ75 0K9BO6VYFn0bcWzFZn4pgsJnnSYnyHx5BRAcLnEDkICSl9gpkr4xMprqnUp29abOSp2/5KA1Or3mT gTE8zVTo4gzYS4vNu6ubOamZT1DPt4h1+dQM1w5sN7o7J382Ruq0mSHekju93Kz0doN7JRHYBkRiW 6LZzy6EtG8vNHlFVPd4i6j8IoBSmEJo5Ag7BcLAinOmf6qFjfItZ7QsSAp6v1q8xihb3VGKo31ArA fTw/x1tppGNH7RN1luqz29vGExs/PFQREjOT8es2L83W07yj4oY1IX1cC6ewgPJ0Uaeu6Ppshclhz cZIojwtMJ+OyOkY5OyYpfQ==; Original-Received: from [87.69.77.57] (port=1278 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nMrTZ-0004zk-L9; Wed, 23 Feb 2022 08:14:37 -0500 In-Reply-To: <87ee3thhh3.fsf@ust.hk> (message from Andrew Cohen on Wed, 23 Feb 2022 20:53:28 +0800) 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:286622 Archived-At: > From: Andrew Cohen > Date: Wed, 23 Feb 2022 20:53:28 +0800 > > >>>>> "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. OK, thanks. Let's see the improved numbers, and can you also show absolute times? If they are short enough, the slowdown might not be significant, since if the data structure is larger, the slow method will not be used, right? Or did I misunderstand? > >> And implementing TIMSORT will be even better---similar or better > >> speedup for the best cases, and only marginal degradation of the > >> worst. But I think even this small change here is a win. > > EZ> Can we see the numbers? This sounds like a net win to me. > > Err, no? I have it all working but I'm using a C version of TIMSORT from > the web. I don't think the license is acceptable so it probably needs to > be written from scratch. But for showing the performance, the license is not important, is it? > Shouldn't be that difficult (the algorithm itself is > well-documented) but I'm not sure how much time I have to finish it. >From my POV, take all the time you need. Emacs 29 is far from a release.