From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 119111 invoked by alias); 20 Jul 2018 03:48:51 -0000 Mailing-List: contact libc-help-help@sourceware.org; run by ezmlm Precedence: bulk List-Subscribe: List-Post: List-Help: , Sender: libc-help-owner@sourceware.org Received: (qmail 118927 invoked by uid 89); 20 Jul 2018 03:48:23 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-1.9 required=5.0 tests=BAYES_00,HTML_MESSAGE,KAM_SHORT,SPF_PASS autolearn=ham version=3.3.2 spammy=H*Ad:U*libc-help, Considering, focusing, outperform X-HELO: mail-lf1-f43.google.com Received: from mail-lf1-f43.google.com (HELO mail-lf1-f43.google.com) (209.85.167.43) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 20 Jul 2018 03:48:21 +0000 Received: by mail-lf1-f43.google.com with SMTP id u14-v6so816852lfu.0 for ; Thu, 19 Jul 2018 20:48:20 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=mtu-edu.20150623.gappssmtp.com; s=20150623; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=bMivhTAlTBFjBUk3sS4WV2pqCXt5G8q8Y1yb855iz7U=; b=wxc7OLy50+EH9yS9l7FWAzlAkUAUD6/2JihnZ1z1GfUIWvxrbFFD257xq5t73HcCV6 Fp8mrNmpATf0t+NiK1ZitScKIJ2NJ5gXXul5vsupEF8e5hbE+XCLoH54WJ2TnHNRFiJA 4742XQGD+XcawEdaAaKRprTbZhwoMLBo2Sl1C8phu/VBwksee8KRayURDLqVzHH2LZOd MGdyo6MITuSrRu8ERfkDssGyD6+gMREKGb/X8YAH/OE14GvDeo2c2eL92Xb7B/abJ2NG WhwLw4We7NljMj7jPneqGq/yjXKEh3GTVBIxhcIPW/NB0JAbGUTt84g2Ov1zAo+SwfSF QRGA== MIME-Version: 1.0 Received: by 2002:a19:ee15:0:0:0:0:0 with HTTP; Thu, 19 Jul 2018 20:48:18 -0700 (PDT) In-Reply-To: References: <3c1e0790-9e50-f27b-b78d-b9149517b3e6@mtu.edu> From: Joshua Marshall Date: Fri, 20 Jul 2018 03:48:00 -0000 Message-ID: Subject: Re: Considering merge optimizations from Timsort in __move_merge_adaptive, __move_merge_adaptive_backward To: "Carlos O'Donell" , adhemerval.zanella@linaro.org Cc: libc-help@sourceware.org Content-Type: text/plain; charset="UTF-8" X-SW-Source: 2018-07/txt/msg00010.txt.bz2 Humor me here, it looks like I was somehow dropped from the chain and I'm not sure how to get it back on track. It looks like you're focusing on the preferred sort implementation while I was more focusing on if Timsort had a better general case approach to merging runs of numbers. It does a kind of exponential probing thing which _should_ be about as fast for switching between merging sides often and provide substantial benefits to long chains to be merged. As for the actual implementations of std::sort, and std::stable_sort, isn't introspective sort used and not quick sort + merge sort? In any case, I'm more interested in the std::stable_sort side of things and am nearly finished with a Timsort implementation with is parallelizable but doesn't outperform the current std::stable_sort I think in large part because of the inplace merging. For that matter, I can't seem to track down what the actual sort type used for std::stable_sort is. On Tue, Jul 3, 2018 at 7:30 PM, Carlos O'Donell wrote: > On Tue, Jul 3, 2018 at 4:10 PM, jrmarsha wrote: > > > >>> Hello all, > >>> > >>> I've been implementing a new version of Timsort in C++ using more > >>> standard > >>> facilities. One thing I've come across which adds a divide between a > >>> larger > >>> codebase and faster code is the implementation of std::inplace_merge > with > >>> sufficient memory. This goes to the specific functions > >>> __move_merge_adaptive, and __move_merge_adaptive_backward. In > >>> particular, > >>> there is an optimization where each insertion searches for the maximum > >>> number of elements it can move. A brief in context explanation is > here: > >>> https://en.wikipedia.org/wiki/Timsort#Individual_merges . Would such > a > >>> trick have a place in glibc or is the overhead likely too great in the > >>> general case? > >> > >> It's possible. We have a tunable framework for changing runtime > >> parameters like this based on application needs. The interface only > >> allows you to make the choice once at startup. So it may not be > >> sufficient to meet the needs of all users. However some choice in this > >> area may be better than no choice. > >> > >> Cheers, > >> Carlos. > > > > How would I get new code incorporated into this and make that decision > > intelligently at compile time? What would be a good way to add this > > inplace_merge variant in? > > If you are looking specifically at std::inplace_merge, then you need to > talk > to the GCC developers, since libstdc++ is part of GCC. > Please see: https://gcc.gnu.org/ > > If you are interested in similar strategies for the C library, then you > can look > at the qsort() API, which can be implemented in any way really as long as > it meets the API requirements (and is written in C). In glibc you might > use a > tunable to switch between one algorithm and another. You can see this > implementation in stdlib/qsort.c in glibc, which does implement quicksort. > > Cheers, > Carlos. >