From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 60307 invoked by alias); 3 Jul 2018 04:16:39 -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 58947 invoked by uid 89); 3 Jul 2018 04:16:13 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-1.4 required=5.0 tests=AWL,BAYES_00,RCVD_IN_DNSWL_NONE,SPF_PASS autolearn=ham version=3.3.2 spammy=HTo:U*libc-help, Hx-languages-length:774, H*r:sk:libc-he, HContent-Transfer-Encoding:8bit X-HELO: mail-it0-f49.google.com Received: from mail-it0-f49.google.com (HELO mail-it0-f49.google.com) (209.85.214.49) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 03 Jul 2018 04:16:12 +0000 Received: by mail-it0-f49.google.com with SMTP id a195-v6so1267401itd.3 for ; Mon, 02 Jul 2018 21:16:12 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=mtu-edu.20150623.gappssmtp.com; s=20150623; h=to:from:subject:message-id:date:user-agent:mime-version :content-transfer-encoding:content-language; bh=WDXB/r2G+Me/GtA5RbWFc75obV/Ov/nnMNnal8n9xm4=; b=rOceWVzURYRFFseimPVPob44utMX6e+EgOj4nnVkvFI5/kRte1fPY2Q+uHAOMxmEpd HZJkB6mNiujAAEmZnDXJuMojD8//a6SObg+RiJf/Iftuu8lhSxIomnS9pCgwDXbxpoBN auI10ojxw9AAOLy9n5YtsgfQvU1Mmc90Zll1IIWKwWeHxmN64PBCCCDhOwLWZLo2SCvO qaqx2AYFmET8uSsj2Ecbv/tnSFh3/XZv9YbXaQuN7v+8MCESwAYjsJyf1pu30kH4e7bc 1eJK2w4de3lVH+A/4EomfVSyMIGcpp/tzT38Yl2qfH7XqAQlJR7R7uu+uSRAchbhdKdU OoKQ== Return-Path: Received: from [192.168.1.171] (97-83-155-19.dhcp.eucl.wi.charter.com. [97.83.155.19]) by smtp.gmail.com with ESMTPSA id i193-v6sm82571ioi.38.2018.07.02.21.16.09 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 02 Jul 2018 21:16:09 -0700 (PDT) To: libc-help@sourceware.org From: jrmarsha Subject: Considering merge optimizations from Timsort in __move_merge_adaptive, __move_merge_adaptive_backward Message-ID: <3c1e0790-9e50-f27b-b78d-b9149517b3e6@mtu.edu> Date: Tue, 03 Jul 2018 04:16:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.8.0 MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit X-SW-Source: 2018-07/txt/msg00001.txt.bz2 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?