From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 126300 invoked by alias); 3 Jul 2018 20:04:47 -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 126288 invoked by uid 89); 3 Jul 2018 20:04:47 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-2.4 required=5.0 tests=AWL,BAYES_00,RCVD_IN_DNSWL_NONE,SPF_PASS autolearn=ham version=3.3.2 spammy=H*Ad:U*libc-help, Considering, H*r:a9d, jrmarsha X-HELO: mail-oi0-f43.google.com Received: from mail-oi0-f43.google.com (HELO mail-oi0-f43.google.com) (209.85.218.43) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 03 Jul 2018 20:04:45 +0000 Received: by mail-oi0-f43.google.com with SMTP id m2-v6so6277727oim.12 for ; Tue, 03 Jul 2018 13:04:43 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=systemhalted.org; s=google; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=zxahKyR5S3jqkXfP8CBonZO7QXOxR+4wtKZWwxkD984=; b=EopS6QQlxM1ltIqy8Z/GpJ5tNhtohWNLnMC/gmYSc+7lQ0yzj0H/S9SrVRvj1KmEhA sAi+ZtAfa7XYl1D5CxNQnIRYhTdDiFOrNizs5vd1Hnidc8PPV8XDQeBzAj8JPtyKgIRA ewQi0NhehyJwSJOblH5qKLJo5WXdOB1Xs9w2M= MIME-Version: 1.0 Received: by 2002:a9d:268c:0:0:0:0:0 with HTTP; Tue, 3 Jul 2018 13:04:41 -0700 (PDT) In-Reply-To: <3c1e0790-9e50-f27b-b78d-b9149517b3e6@mtu.edu> References: <3c1e0790-9e50-f27b-b78d-b9149517b3e6@mtu.edu> From: "Carlos O'Donell" Date: Tue, 03 Jul 2018 20:04:00 -0000 Message-ID: Subject: Re: Considering merge optimizations from Timsort in __move_merge_adaptive, __move_merge_adaptive_backward To: jrmarsha Cc: libc-help@sourceware.org Content-Type: text/plain; charset="UTF-8" X-IsSubscribed: yes X-SW-Source: 2018-07/txt/msg00002.txt.bz2 On Tue, Jul 3, 2018 at 12:16 AM, 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.