220 9677 article Path: news.gmane.org!not-for-mail From: "Billy O'Neal" Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: New implementation for __inplace_stable_sort Date: Fri, 7 Mar 2014 16:04:52 -0800 Lines: 142 Approved: news@gmane.org Message-ID: References: Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=001a1134850003377104f40d216a X-Trace: ger.gmane.org 1394237124 32381 80.91.229.3 (8 Mar 2014 00:05:24 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sat, 8 Mar 2014 00:05:24 +0000 (UTC) To: std-proposals Original-X-From: std-proposals+bncBDKLBLVE6ADBBTN55GMAKGQECIKWVQQ@isocpp.org Sat Mar 08 01:05:35 2014 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-qc0-f198.google.com ([209.85.216.198]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1WM4li-0002YP-Ct for gclcip-std-proposals@m.gmane.org; Sat, 08 Mar 2014 01:05:34 +0100 Original-Received: by mail-qc0-f198.google.com with SMTP id r5sf11560907qcx.5 for ; Fri, 07 Mar 2014 16:05:33 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:x-original-sender :x-original-authentication-results:reply-to:precedence:mailing-list :list-id:list-post:list-help:list-archive:list-subscribe :list-unsubscribe:content-type; bh=ruBxFGwfbRFkrL6qAQ9s3jfRgyRRb6x2Ef9pyEMth/I=; b=CTcVtYMaVz03Oc2ANoXGbe5p6zIauFy8c+yvThipRX6bnWhMTqUhGTl5jJKHA0Nurc ObGgwMeQXDaV4EgekcmbjjOqIpzIai4eby+JvMmmwKYds1XiBklWZZjNi5W2ljXgCRde +JJSH5R1sbWk1MrGm0TCCg8tbsQWN7/b7gQmWP8br9eBeWwL6D6oPFifcfJyQfrjVUfO aOQPIAaAY3B9FizZE6uZckLV0Bfd6gQX1HlcIUUV6bCMsxHA2o+UzjssPuPNPeAzG6Ov cWmWauHGWiUEu3EC2it+1tgI7CAPBkS2FFGSUOSej9B8/NnEC5q4WoleTr7t2h8AmO6U oILg== X-Gm-Message-State: ALoCoQnkfFZ+NhHu8o/G11CvOCZ1pKeLnvFQrp1ErtIDHVMdpqck3AN09BdJ/HFpHGdt7A64oBDf X-Received: by 10.236.29.45 with SMTP id h33mr8223076yha.45.1394237133628; Fri, 07 Mar 2014 16:05:33 -0800 (PST) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.182.5.196 with SMTP id u4ls500872obu.83.gmail; Fri, 07 Mar 2014 16:05:32 -0800 (PST) X-Received: by 10.60.80.137 with SMTP id r9mr13600344oex.30.1394237132756; Fri, 07 Mar 2014 16:05:32 -0800 (PST) Original-Received: from mail-oa0-x230.google.com (mail-oa0-x230.google.com [2607:f8b0:4003:c02::230]) by mx.google.com with ESMTPS id i2si8396849oeu.116.2014.03.07.16.05.32 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Fri, 07 Mar 2014 16:05:32 -0800 (PST) Received-SPF: pass (google.com: domain of billy.oneal@gmail.com designates 2607:f8b0:4003:c02::230 as permitted sender) client-ip=2607:f8b0:4003:c02::230; Original-Received: by mail-oa0-f48.google.com with SMTP id m1so4871985oag.7 for ; Fri, 07 Mar 2014 16:05:32 -0800 (PST) X-Received: by 10.182.149.168 with SMTP id ub8mr3033716obb.74.1394237132449; Fri, 07 Mar 2014 16:05:32 -0800 (PST) Original-Received: by 10.182.87.37 with HTTP; Fri, 7 Mar 2014 16:04:52 -0800 (PST) In-Reply-To: X-Original-Sender: billy.oneal@gmail.com X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of billy.oneal@gmail.com designates 2607:f8b0:4003:c02::230 as permitted sender) smtp.mail=billy.oneal@gmail.com; dkim=pass header.i=@gmail.com; dmarc=pass (p=NONE dis=NONE) header.from=gmail.com Precedence: list Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org List-ID: X-Google-Group-Id: 399137483710 List-Post: , List-Help: , List-Archive: List-Subscribe: , List-Unsubscribe: , Xref: news.gmane.org gmane.comp.lang.c++.isocpp.proposals:9677 Archived-At: --001a1134850003377104f40d216a Content-Type: text/plain; charset=UTF-8 That implementation is not correct because it copies around Ts using memcpy. You too can have faster results if you give up correctness. :) Billy O'Neal https://github.com/BillyONeal/ http://stackoverflow.com/users/82320/billy-oneal On Fri, Mar 7, 2014 at 4:00 PM, BonzaiThePenguin wrote: > stable_sort is nice and speedy when there's enough memory available, but > when it fails to allocate the required buffer it calls > __inplace_stable_sort instead. This part seems to be based on a rather old > in-place merge algorithm. There's been a lot of recent progress in this > area, to the point where it can be 3x faster while also reducing the stack > requirements from O(log n) to O(1). > > I have a self-contained implementation up and running here: > https://github.com/BonzaiThePenguin/WikiSort > > In order to adapt it to the STL, I'd recommend removing the cache and the > floating-point multiplication hack. The hack was profiled and found to be > 10% faster than a standard bottom-up merge sort, but it's also not > mathematically "pure" and is guaranteed to fail well before reaching the > 2^64 limit. I only tested it for up to 17 billion items. > > Anyway, it seems like a no-brainer to me, although it could certainly use > a little vetting. If there's interest I can make a version that's a bit > closer to what an STL version might look like. > > -- > > --- > You received this message because you are subscribed to the Google Groups > "ISO C++ Standard - Future Proposals" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to std-proposals+unsubscribe@isocpp.org. > To post to this group, send email to std-proposals@isocpp.org. > Visit this group at > http://groups.google.com/a/isocpp.org/group/std-proposals/. > -- --- You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group. To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org. To post to this group, send email to std-proposals@isocpp.org. Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/. --001a1134850003377104f40d216a Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
That implementation is not correct because it copies aroun= d Ts using memcpy. You too can have faster results if you give up correctne= ss. :)



On Fri, Mar 7, 2014 at 4:00 PM, BonzaiTh= ePenguin <mike@bonzaiapps.com> wrote:
stable_sort is nice and speedy when there's = enough memory available, but when it fails to allocate the required buffer = it calls __inplace_stable_sort instead. This part seems to be based on a ra= ther old in-place merge algorithm. There's been a lot of recent progres= s in this area, to the point where it can be 3x faster while also reducing = the stack requirements from O(log n) to O(1).

I have a self-contained implementation up and running h= ere:

In order to adapt it to the STL, I'd recommend removing the = cache and the floating-point multiplication hack. The hack was profiled and= found to be 10% faster than a standard bottom-up merge sort, but it's = also not mathematically "pure" and is guaranteed to fail well bef= ore reaching the 2^64 limit. I only tested it for up to 17 billion items.

Anyway, it seems like a no-brainer to me, althoug= h it could certainly use a little vetting. If there's interest I can ma= ke a version that's a bit closer to what an STL version might look like= ..

--

---
You received this message because you are subscribed to the Google Groups &= quot;ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/gro= up/std-proposals/.

--

---
You received this message because you are subscribed to the Google Groups &= quot;ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposa= ls+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/<= /a>.
--001a1134850003377104f40d216a-- .