From unknown Sun Jun 22 00:56:21 2025 X-Loop: help-debbugs@gnu.org Subject: bug#13354: sort: File Merge Order is Suboptimal with Many Passes Resent-From: Jason Bucata Original-Sender: debbugs-submit-bounces@debbugs.gnu.org Resent-CC: bug-coreutils@gnu.org Resent-Date: Fri, 04 Jan 2013 07:46:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 13354 X-GNU-PR-Package: coreutils X-GNU-PR-Keywords: To: 13354@debbugs.gnu.org X-Debbugs-Original-To: bug-coreutils@gnu.org Received: via spool by submit@debbugs.gnu.org id=B.135728553613542 (code B ref -1); Fri, 04 Jan 2013 07:46:01 +0000 Received: (at submit) by debbugs.gnu.org; 4 Jan 2013 07:45:36 +0000 Received: from localhost ([127.0.0.1]:42556 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1Tr1yA-0003WL-QP for submit@debbugs.gnu.org; Fri, 04 Jan 2013 02:45:35 -0500 Received: from eggs.gnu.org ([208.118.235.92]:43529) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1TqysM-000717-VC for submit@debbugs.gnu.org; Thu, 03 Jan 2013 23:27:24 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1TqysE-0003Og-7k for submit@debbugs.gnu.org; Thu, 03 Jan 2013 23:27:18 -0500 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=0.6 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_NONE, RECEIVED_FROM_WINDOWS_HOST, T_RP_MATCHES_RCVD autolearn=no version=3.3.2 Received: from lists.gnu.org ([208.118.235.17]:36512) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TqysE-0003OZ-55 for submit@debbugs.gnu.org; Thu, 03 Jan 2013 23:27:14 -0500 Received: from eggs.gnu.org ([208.118.235.92]:54854) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Tqys9-0004Pt-LH for bug-coreutils@gnu.org; Thu, 03 Jan 2013 23:27:14 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Tqys6-0003LT-GZ for bug-coreutils@gnu.org; Thu, 03 Jan 2013 23:27:09 -0500 Received: from pacmmta51-sus.windstream.net ([162.39.147.129]:51927) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Tqys6-0003JK-BZ for bug-coreutils@gnu.org; Thu, 03 Jan 2013 23:27:06 -0500 X-WS-COS: WSOB803 X-Cloudmark-Category: Undefined:Undefined X-Cloudmark-Analysis: v=1.1 cv=lfjML3bQkTsh5H+cJ65BAulV5zVM2pgB13D795OEGio= c=1 sm=0 a=wom5GMh1gUkA:10 a=sOQeOs8UIY8A:10 a=UT_QgiwtmQIA:10 a=kj9zAlcOel0A:10 a=pGK8OwJzR2P7zcECln4A:9 a=CjuIK1q_8ugA:10 a=dz2mxp1oIKHW0rOC:21 a=odtLUDsTzLGe6CCZ:21 a=8DVXnpw8tet3daRLJoVClA==:117 X-Cloudmark-Score: 0 Received: from [75.91.245.220] ([75.91.245.220:60418] helo=localhost) by pacmmta51 (envelope-from ) (ecelerity 2.2.3.47 r(39824M)) with ESMTP id A1/32-24841-46556E05; Thu, 03 Jan 2013 23:07:01 -0500 Date: Thu, 3 Jan 2013 22:07:00 -0600 From: Jason Bucata Message-ID: <20130104040700.GA30079@windstream.net> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.5.21 (2010-09-15) X-detected-operating-system: by eggs.gnu.org: Windows NT kernel [generic] [fuzzy] X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-Received-From: 208.118.235.17 X-Spam-Score: -3.4 (---) X-Mailman-Approved-At: Fri, 04 Jan 2013 02:45:33 -0500 X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -6.1 (------) Over a year ago, I was working with sort on some large input files. I noticed a performance problem that related to the number of temp files being used for sort runs. As I recall, I'd also seen the problem prior to that, but this was the first time I took an opportunity to diagnose the problem in detail. (As for why I waited so long to finally report it, more below.) >From what I recall, it tended to want to do 8-way merges on my system. If the input file was just big enough, it would wind up with 9 files left over toward the end. It would merge the largest 8 files in another pass, and then do one final merge to combine the now-huge temp file with the one, likely very tiny temp file still remaining. I found that the extra pass added a lot of extra time to the sort. If I bumped up the memory buffer to increase the initial run sizes so that I got rid of one temp file, I could shave at least a few minutes off the total run time: The little extra memory made a disproportionate difference, and I could attribute it directly to the extra merge pass at the end that was avoided. At the time I reasoned that it would make the most sense to merge temp files at the very beginning to reduce the number just enough to have a bunch of --batch-size merge passes after that until the end. In this case, if the extra temp file at the end was 10 MB, then each merge pass would have to process 10 MB more. Over 4 merge passes, say, that's 40 MB extra to read. But the benefit is saving the final merge pass with 10 MB plus something a WHOLE log bigger than 40 MB, if it's big enough to require 4 merge passes to combine it all in the first place! I held off on reporting the bug because I wanted to see what Knuth had to say on the subject. Well, tonight I finally went to the library and looked through volume 3 to see his advice. :) In section 5.4.9 he basically echoes my thinking. In the simple case where all runs were the same length, he recommends a queue to track the files to process, with N files pulled from the front of the queue and the merged output added to the back. But, he says to add a number of "dummy" empty files to the front queue. The net effect is that fewer than N files are merged the first time. Looking at the merge function in sort.c, it appears that it can merge both temp files and input files all at the same time. With that, we probably want an enhancement to that algorithm, which Knuth called "Huffman's method" (referencing something in chapter 2). For files or sort runs of varying sizes, Knuth says to use a priority queue, to merge the smallest N files at each pass. He also says to add a number of 0-length dummy files at the front of the priority queue so that the first merge pass grabs fewer than N files. If I understand his formula correctly, he suggests to add (1-F) % (N-1) dummy runs, where N is --batch-size and F is the starting number of files. To get it ideal, we'd need a priority queue implementation here, maybe a heap or something. (Irony of having to maintain a sorted list of files in a sort program is duly noted...) It would be an improvement, though, to handle merging a smaller batch of files at the beginning, the equivalent of adding 0-byte dummy files at the front. That might be quicker to implement, unless there's a GPL'd heap library lying around somewhere... Jason B. -- Half the harm that is done in this world is due to people who want to feel important. -- T. S. Eliot From unknown Sun Jun 22 00:56:21 2025 X-Loop: help-debbugs@gnu.org Subject: bug#13354: sort: File Merge Order is Suboptimal with Many Passes Resent-From: =?UTF-8?Q?P=C3=A1draig?= Brady Original-Sender: debbugs-submit-bounces@debbugs.gnu.org Resent-CC: bug-coreutils@gnu.org Resent-Date: Fri, 04 Jan 2013 11:03:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 13354 X-GNU-PR-Package: coreutils X-GNU-PR-Keywords: To: Jason Bucata Cc: 13354@debbugs.gnu.org Received: via spool by 13354-submit@debbugs.gnu.org id=B13354.135729733211359 (code B ref 13354); Fri, 04 Jan 2013 11:03:01 +0000 Received: (at 13354) by debbugs.gnu.org; 4 Jan 2013 11:02:12 +0000 Received: from localhost ([127.0.0.1]:42699 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1Tr52O-0002x2-Cd for submit@debbugs.gnu.org; Fri, 04 Jan 2013 06:02:12 -0500 Received: from mx1.redhat.com ([209.132.183.28]:1261) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1Tr52H-0002wW-Q1 for 13354@debbugs.gnu.org; Fri, 04 Jan 2013 06:02:06 -0500 Received: from int-mx12.intmail.prod.int.phx2.redhat.com (int-mx12.intmail.prod.int.phx2.redhat.com [10.5.11.25]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id r04B1sDo028614 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Fri, 4 Jan 2013 06:01:54 -0500 Received: from [10.36.116.81] (ovpn-116-81.ams2.redhat.com [10.36.116.81]) by int-mx12.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id r04B1paa021364 (version=TLSv1/SSLv3 cipher=DHE-RSA-CAMELLIA256-SHA bits=256 verify=NO); Fri, 4 Jan 2013 06:01:52 -0500 Message-ID: <50E6B69E.4030307@draigBrady.com> Date: Fri, 04 Jan 2013 11:01:50 +0000 From: =?UTF-8?Q?P=C3=A1draig?= Brady User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:13.0) Gecko/20120615 Thunderbird/13.0.1 MIME-Version: 1.0 References: <20130104040700.GA30079@windstream.net> In-Reply-To: <20130104040700.GA30079@windstream.net> Content-Type: text/plain; charset=ISO-8859-1; format=flowed X-Scanned-By: MIMEDefang 2.68 on 10.5.11.25 Content-Transfer-Encoding: quoted-printable X-MIME-Autoconverted: from 8bit to quoted-printable by mx1.redhat.com id r04B1sDo028614 X-Spam-Score: -6.9 (------) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -6.9 (------) On 01/04/2013 04:07 AM, Jason Bucata wrote: > Over a year ago, I was working with sort on some large input files. I > noticed a performance problem that related to the number of temp files = being > used for sort runs. As I recall, I'd also seen the problem prior to th= at, > but this was the first time I took an opportunity to diagnose the probl= em > in detail. > > (As for why I waited so long to finally report it, more below.) > >>>From what I recall, it tended to want to do 8-way merges on my system. = If > the input file was just big enough, it would wind up with 9 files left = over > toward the end. It would merge the largest 8 files in another pass, an= d > then do one final merge to combine the now-huge temp file with the one, > likely very tiny temp file still remaining. > > I found that the extra pass added a lot of extra time to the sort. If = I > bumped up the memory buffer to increase the initial run sizes so that I= got > rid of one temp file, I could shave at least a few minutes off the tota= l run > time: The little extra memory made a disproportionate difference, and I > could attribute it directly to the extra merge pass at the end that was > avoided. > > At the time I reasoned that it would make the most sense to merge temp = files > at the very beginning to reduce the number just enough to have a bunch = of > --batch-size merge passes after that until the end. In this case, if t= he > extra temp file at the end was 10 MB, then each merge pass would have t= o > process 10 MB more. Over 4 merge passes, say, that's 40 MB extra to re= ad. > But the benefit is saving the final merge pass with 10 MB plus somethin= g a > WHOLE log bigger than 40 MB, if it's big enough to require 4 merge pass= es to > combine it all in the first place! > > I held off on reporting the bug because I wanted to see what Knuth had = to > say on the subject. Well, tonight I finally went to the library and lo= oked > through volume 3 to see his advice. :) > > In section 5.4.9 he basically echoes my thinking. > > In the simple case where all runs were the same length, he recommends a > queue to track the files to process, with N files pulled from the front= of > the queue and the merged output added to the back. But, he says to add= a > number of "dummy" empty files to the front queue. The net effect is th= at > fewer than N files are merged the first time. > > Looking at the merge function in sort.c, it appears that it can merge b= oth > temp files and input files all at the same time. With that, we probabl= y > want an enhancement to that algorithm, which Knuth called "Huffman's me= thod" > (referencing something in chapter 2). For files or sort runs of varyin= g > sizes, Knuth says to use a priority queue, to merge the smallest N file= s at > each pass. He also says to add a number of 0-length dummy files at the > front of the priority queue so that the first merge pass grabs fewer th= an N > files. > > If I understand his formula correctly, he suggests to add (1-F) % (N-1) > dummy runs, where N is --batch-size and F is the starting number of fil= es. > > To get it ideal, we'd need a priority queue implementation here, maybe = a > heap or something. (Irony of having to maintain a sorted list of files= in a > sort program is duly noted...) It would be an improvement, though, to > handle merging a smaller batch of files at the beginning, the equivalen= t of > adding 0-byte dummy files at the front. That might be quicker to imple= ment, > unless there's a GPL'd heap library lying around somewhere... There is a little heap lib already used by sort: http://git.sv.gnu.org/gitweb/?p=3Dcoreutils.git;a=3Dblob;f=3Dgl/lib/heap.= c;hb=3DHEAD Would that suffice? thanks, P=E1draig. From unknown Sun Jun 22 00:56:21 2025 X-Loop: help-debbugs@gnu.org Subject: bug#13354: sort: File Merge Order is Suboptimal with Many Passes Resent-From: Jason Bucata Original-Sender: debbugs-submit-bounces@debbugs.gnu.org Resent-CC: bug-coreutils@gnu.org Resent-Date: Fri, 04 Jan 2013 15:52:34 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 13354 X-GNU-PR-Package: coreutils X-GNU-PR-Keywords: To: =?UTF-8?Q?P=EF=BF=BDdraig?= Brady Cc: 13354@debbugs.gnu.org Received: via spool by 13354-submit@debbugs.gnu.org id=B13354.135731466815179 (code B ref 13354); Fri, 04 Jan 2013 15:52:34 +0000 Received: (at 13354) by debbugs.gnu.org; 4 Jan 2013 15:51:08 +0000 Received: from localhost ([127.0.0.1]:43714 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1Tr9X7-0003vD-2l for submit@debbugs.gnu.org; Fri, 04 Jan 2013 10:51:02 -0500 Received: from pacmmta52-sus.windstream.net ([162.39.147.131]:59302) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1Tr9Vf-0003si-TZ for 13354@debbugs.gnu.org; Fri, 04 Jan 2013 10:49:31 -0500 X-WS-COS: WSOB803 X-Cloudmark-Category: Undefined:Undefined X-Cloudmark-Analysis: v=1.1 cv=Jx9570vtCJLmtsOyCYU8diIJ7rMkbYjjtWgWPSCZpp4= c=1 sm=0 a=wom5GMh1gUkA:10 a=WK78Ywk0ZsgA:10 a=UT_QgiwtmQIA:10 a=IkcTkHD0fZMA:10 a=mDV3o1hIAAAA:8 a=b1lljSwoqm4JOpkQShIA:9 a=QEXdDO2ut3YA:10 a=8DVXnpw8tet3daRLJoVClA==:117 X-Cloudmark-Score: 0 Received: from [75.91.245.220] ([75.91.245.220:61150] helo=localhost) by pacmmta52 (envelope-from ) (ecelerity 2.2.3.47 r(39824M)) with ESMTP id 16/54-19678-BC9F6E05; Fri, 04 Jan 2013 10:48:27 -0500 Date: Fri, 4 Jan 2013 09:48:27 -0600 From: Jason Bucata Message-ID: <20130104154827.GA31670@windstream.net> References: <20130104040700.GA30079@windstream.net> <50E6B69E.4030307@draigBrady.com> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: <50E6B69E.4030307@draigBrady.com> User-Agent: Mutt/1.5.21 (2010-09-15) X-Spam-Score: 0.8 (/) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: 0.8 (/) On Fri, Jan 04, 2013 at 11:01:50AM +0000, P�draig Brady wrote: > On 01/04/2013 04:07 AM, Jason Bucata wrote: > > To get it ideal, we'd need a priority queue implementation here, maybe a > > heap or something. (Irony of having to maintain a sorted list of files in a > > sort program is duly noted...) It would be an improvement, though, to > > handle merging a smaller batch of files at the beginning, the equivalent of > > adding 0-byte dummy files at the front. That might be quicker to implement, > > unless there's a GPL'd heap library lying around somewhere... > > There is a little heap lib already used by sort: > http://git.sv.gnu.org/gitweb/?p=coreutils.git;a=blob;f=gl/lib/heap.c;hb=HEAD > Would that suffice? > > thanks, > Pádraig. Oh, good to know. If you're asking me, I'm sure it's fine, though I guess it's up to whoever will write the fix. I don't know what it would take for me to be able to get a copyright disclaimer from my employer, so I'm probably not in a position to develop a patch for this myself. I'm hoping some established developer will see this and be able to step in. Jason B. -- Half the harm that is done in this world is due to people who want to feel important. -- T. S. Eliot From unknown Sun Jun 22 00:56:21 2025 X-Loop: help-debbugs@gnu.org Subject: bug#13354: sort: File Merge Order is Suboptimal with Many Passes Resent-From: Assaf Gordon Original-Sender: "Debbugs-submit" Resent-CC: bug-coreutils@gnu.org Resent-Date: Thu, 18 Oct 2018 23:14:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 13354 X-GNU-PR-Package: coreutils X-GNU-PR-Keywords: To: Jason Bucata Cc: 13354@debbugs.gnu.org Received: via spool by 13354-submit@debbugs.gnu.org id=B13354.153990440015640 (code B ref 13354); Thu, 18 Oct 2018 23:14:02 +0000 Received: (at 13354) by debbugs.gnu.org; 18 Oct 2018 23:13:20 +0000 Received: from localhost ([127.0.0.1]:57539 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1gDHTk-000447-1t for submit@debbugs.gnu.org; Thu, 18 Oct 2018 19:13:20 -0400 Received: from mail-io1-f49.google.com ([209.85.166.49]:39368) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1gDHTg-00043l-NJ; Thu, 18 Oct 2018 19:13:18 -0400 Received: by mail-io1-f49.google.com with SMTP id z16-v6so22030237iol.6; Thu, 18 Oct 2018 16:13:16 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=subject:to:cc:references:from:message-id:date:user-agent :mime-version:in-reply-to:content-language:content-transfer-encoding; bh=Gus5ZzxIQUk7gCF4xgTW4f5wkIXYa478kOnIHI7/y30=; b=CvyTz1NFDg1JBNR7CidJkZEKh36kukC7oNMax6nkicNHhBIVMKBJrfecsNC3ePg52M UKK16G+xFUZgrjgVKFs54W0pzoDfSnVNM6lkssMiTX2TTywPOj7PrkfGXo2y8CjxFl6u 6IkdiVnSVBkitn7cVu0oUQEmP3mPuHvyK5iHutGvnjSiHHJlWiNYDBUVAWAzJFPuO2uX b27l8BCCAcP49o+fyHzTcYLo+vgw+L8Pg4ALR3pxDw3MncmC7gq7qw3oXKO2eLAT/Uji NO6y+RvciWuLZ7gHZrlJ+u+MtfMkTxRrU0i2V5OSNbBJaHCa0SS7OASrp05KlG9zBFTT P0KQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:cc:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=Gus5ZzxIQUk7gCF4xgTW4f5wkIXYa478kOnIHI7/y30=; b=fnsbVH98pZwq09h8idPlxw7G1/jhXyCSOpZg4FU/egyHD3xxaXpvUGggtX436Dyznt j8tVj9LKnp9/QVGDWKk2KgaJqbElv2+JG+n7jptUV+JYet/GKIsDUcZR+nraNyiuDOTw lMQ6sGklWThC7nVPHBUvQ8nB/vxF4BqRHCngFRmSGpU3OXNX9JE9slpIwJWgdEZTRroG jvS8fNShVjxVxPzNCHVOyPieMk0+Qsy7ptvfl2oVRkGbdwC0hgx17YmXgZ76sD4RVm0C 3inKroQbHBpXlIMI06F7qMzwSdlojEhPfn+sLJIz6hmAiDlWhCca/BKxv5zVpDrtDMHg b6jA== X-Gm-Message-State: AGRZ1gKeKxVqqSmY+mlabpabpLQTeeeLjq0astq0dBOOsXy6YjhYYDxQ h03DT9go3TYIG+WlZk43M6Qnn7bT X-Google-Smtp-Source: AJdET5e6YTq1+fkeW57qwc6ks9J10BgvqCKTXIM8OY5vJa5SGFvnByyt1EyRbeF1JpCfJmOEviLA9Q== X-Received: by 2002:a6b:3b8d:: with SMTP id i135-v6mr1635724ioa.215.1539904390713; Thu, 18 Oct 2018 16:13:10 -0700 (PDT) Received: from tomato.housegordon.com (moose.housegordon.com. [184.68.105.38]) by smtp.googlemail.com with ESMTPSA id z4-v6sm6786959iob.65.2018.10.18.16.13.09 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 18 Oct 2018 16:13:09 -0700 (PDT) References: <20130104040700.GA30079@windstream.net> <50E6B69E.4030307@draigBrady.com> <20130104154827.GA31670@windstream.net> From: Assaf Gordon Message-ID: Date: Thu, 18 Oct 2018 17:13:08 -0600 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.9.1 MIME-Version: 1.0 In-Reply-To: <20130104154827.GA31670@windstream.net> Content-Type: text/plain; charset=utf-8; format=flowed Content-Language: en-US Content-Transfer-Encoding: 8bit X-Spam-Score: -0.0 (/) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) tags 13354 moreinfo close 13354 stop (triaging old bugs) Hello, On 04/01/13 08:48 AM, Jason Bucata wrote: > On Fri, Jan 04, 2013 at 11:01:50AM +0000, P�draig Brady wrote: >> On 01/04/2013 04:07 AM, Jason Bucata wrote: >>> To get it ideal, we'd need a priority queue implementation here, maybe a >>> heap or something. >> >> There is a little heap lib already used by sort: >> http://git.sv.gnu.org/gitweb/?p=coreutils.git;a=blob;f=gl/lib/heap.c;hb=HEAD >> Would that suffice? > > Oh, good to know. If you're asking me, I'm sure it's fine, though I guess > it's up to whoever will write the fix. With no further follow-ups in 5 years, I'm closing this item. Discussion can continue by replying to this thread. regards, - assaf