From patchwork Mon May 20 11:07:07 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Viktor Reznov X-Patchwork-Id: 90478 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 29BE53858C32 for ; Mon, 20 May 2024 11:07:41 +0000 (GMT) X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-pj1-x1031.google.com (mail-pj1-x1031.google.com [IPv6:2607:f8b0:4864:20::1031]) by sourceware.org (Postfix) with ESMTPS id 0BC313858D20 for ; Mon, 20 May 2024 11:07:20 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 0BC313858D20 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 0BC313858D20 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::1031 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1716203242; cv=none; b=BlUSv8C8nVe3+Fn/MvGRaRo5SitU2u+kTmcHRQjviKBaier1137E2JUvSe6D4lnPZmsVjJr0eIvHc5QZBL5fp+vxSxO2p95Mg/9eUyO0YeIDo+vuK7PgglKidwmBzH0AY2o/2IZcQNcZY7MgF9l2uWfEbwrJsAameneKFnwTfgc= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1716203242; c=relaxed/simple; bh=d6S2tEaYtgg0v8Rnr8rq2YSKJolhx2Kosq8MAbnYXoY=; h=DKIM-Signature:MIME-Version:From:Date:Message-ID:Subject:To; b=jz3zlSlZZx8yZoYC48v/2u43yo74lC+BWuLkAPHxXlwYjHbcLHAhGSM/chY5pTejrJewftDUeGXhVYLilvL4SVvx2tDUTSu/Ew6bw8vd25xO5xxuMW6ykI9V9xcRCROdP4RJWoCdSFiKqEmX4FVTgbUjo4XTnoKI75rYz6Tdcug= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-pj1-x1031.google.com with SMTP id 98e67ed59e1d1-2b27eec1eb1so124568a91.0 for ; Mon, 20 May 2024 04:07:20 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1716203238; x=1716808038; darn=sourceware.org; h=to:subject:message-id:date:from:mime-version:from:to:cc:subject :date:message-id:reply-to; bh=i5yhAO8jVqMdruzu91amzYTffLi/LXc10IxjSEyDFUY=; b=AqJDT/f4/LaGMI2ioxT/gWlYqlQ40Qgr1w52xSnFgaJZmtiowgvNU3SiYAXswYjdyi 6hHnpyfJIBW9X5wavGzolVvAh5fqEFb4tgg4A5OJe3lmdUtz0zdHmOqFMv/z30EPNAmv uHDJotdjwihTlMMEbgOicWb6wKI5pwoYcp7TierlghgZIKnGdsDcr3MUH6Rn36afvLOS XKns4v0Z7vn5QeSCNmCDFENRJK3wQog3JvxyIpRJHg5gl+woeWJn9s6WenzJVADhqXDY 8Ks8wf0QEbLuXgcFmdKxvR0pOUiqlTmyQNoOfB06pvROOXbPzoSK5J67U6HH5oSQs2AT poeA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1716203238; x=1716808038; h=to:subject:message-id:date:from:mime-version:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=i5yhAO8jVqMdruzu91amzYTffLi/LXc10IxjSEyDFUY=; b=j9oLHL5dU74i9+J1SyRJEiH/oxZe8szzdUo4XOb7Fx1AKhyz35xH7Zj6ktF3kwzs0V RrJ9g/02kbDYqnjRmCBzobu/2s5qrv0JtOhoFkpdiTw9bf+uRQtIwyYp6Z0TfCfnR51C 6PzzcC07OtuMNhgJ6ZMNZExMxp58I3kswKO0xpr9jX0QPb/crWGRny+9QOcKN+L5Gevk UoKKRgFcRyj9o0tVNsFzm1wJy5CrNDu0QvDDyHpzedgsQJxSECDu+z1okVSGdHmUxLZA RhUJh8dn6gkVP5IwqMkDD0DsEIrZo6zcWme/4yMKIRJ2H3eZkEMsiQvPjxSGK4aWQOC8 0Z7w== X-Gm-Message-State: AOJu0YxkLC7Y4v/lrRwaGHLO7nXGlo7ajUrModDNvMT0tcJSlBYPb2+1 XwVqs4LqlmuuYPO7b8pTIvCH2RM/jUEt+ym5HlceujZFyOiV6Qmw8rFL93A/9Z8DZ+xquEBzEw9 pwaHkcCTK7ugzi+uundgNJXT0CYx65tIk X-Google-Smtp-Source: AGHT+IHpInEgJK13Z8WPnHcTVu5tMXgOnYc1gCb2jA+8dRUIYZMv0z3fq5jX96QeWZi95rJ24PPZ0lCjlwLkE0EyjoM= X-Received: by 2002:a17:90a:8d81:b0:2ac:f010:b1c0 with SMTP id 98e67ed59e1d1-2b6cc97c7bdmr24483181a91.22.1716203238541; Mon, 20 May 2024 04:07:18 -0700 (PDT) MIME-Version: 1.0 From: Viktor Reznov Date: Mon, 20 May 2024 14:07:07 +0300 Message-ID: Subject: [PATCH] avoid unnecessary copying of a left_subarray's tail To: libc-alpha@sourceware.org X-Spam-Status: No, score=-8.3 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, HTML_MESSAGE, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: libc-alpha-bounces+patchwork=sourceware.org@sourceware.org Let's imagine a test case in which all elements of the right subarray must be placed to the left of any element of the left subarray. Before merge loop: tmp => _ _ _ _ _ _ b => 4 5 6 1 2 3 After merge loop: tmp => 1 2 3 _ _ _ b => 4 5 6 _ _ _ Next begins the section of code modified by the patch: The old code (current master) first copies 3 elements from `b` to the end of `tmp`, then 6 elements from `tmp` to `b`. The changed code immediately copies 3 elements from the left subarray to the end of `b` and then copies 3 elements from `tmp` to the beginning of `b`. Signed-off-by: Viktor Reznov --- stdlib/qsort.c | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) static void diff --git a/stdlib/qsort.c b/stdlib/qsort.c index be47aebbe0..51ecf1e5c0 100644 --- a/stdlib/qsort.c +++ b/stdlib/qsort.c @@ -288,9 +288,10 @@ msort_with_tmp (const struct msort_param *p, void *b, size_t n) break; } + const size_t d = tmp - p->t; if (n1 > 0) - memcpy (tmp, b1, n1 * s); - memcpy (b, p->t, (n - n2) * s); + memcpy ((char *) b + d, b1, n1 * s); + memcpy (b, p->t, d); }