From patchwork Mon Nov 4 16:11:07 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: =?utf-8?q?Marc_Poulhi=C3=A8s?= X-Patchwork-Id: 2006319 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (2048-bit key; secure) header.d=adacore.com header.i=@adacore.com header.a=rsa-sha256 header.s=google header.b=Lh4Md+ya; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4XhxV03TfDz1xxW for ; Tue, 5 Nov 2024 03:18:32 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 607893857001 for ; Mon, 4 Nov 2024 16:18:30 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-wm1-x32d.google.com (mail-wm1-x32d.google.com [IPv6:2a00:1450:4864:20::32d]) by sourceware.org (Postfix) with ESMTPS id 2BD913857374 for ; Mon, 4 Nov 2024 16:11:53 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 2BD913857374 Authentication-Results: sourceware.org; dmarc=pass (p=quarantine dis=none) header.from=adacore.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=adacore.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 2BD913857374 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a00:1450:4864:20::32d ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1730736749; cv=none; b=DNRutIgh8vH1iUy8kI/wNBFrqKZ1PbRrnlmHUeZP4LOfIlIUfQ0nBGPnjKPTAlaRR3eeKsmBIJ+Q4G+XjW2y47KByXZxTSpjhTM09F/aJ/qcZZQvUukTusY+8x6R1Wipb/2AdYesOt6/FTrqNOMLFG2HB5lykwotV3S1M9rh7uA= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1730736749; c=relaxed/simple; bh=8Pfe/u9GfkRGVM4PvTLu7TlSxUfEA8Fz+WRQZS//lKQ=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=EQiTvYisluCnCqtsDTK0KTz36igL8qGhqpqB5by+g2YkaUWE7llaqDhyzGHkOO8u6UiHhAg/84s9jAfoXlSDNfoS9qSJf5MrnZIbKyi09fa+T66rdyQYJi8JcHZpWQav58FsPj0ShogOVO66XmI+woc+zZVlOQEkGT68d/35XbA= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-wm1-x32d.google.com with SMTP id 5b1f17b1804b1-43155afca99so32436955e9.1 for ; Mon, 04 Nov 2024 08:11:53 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=adacore.com; s=google; t=1730736712; x=1731341512; darn=gcc.gnu.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=CanoitEuan7nZ7zXtvGLz59fFXX3oXIfY7Jtkfkywbs=; b=Lh4Md+yaZyq9cjRKGzsdx/sSv80i3BU0ULMQPy9MJqlVxqkqiUdZEzsKWpo7znQHzU gqJU3vwDbJet3wUCZUaVmwgTd7cH/vxkSEQzuPvOEvbiN3g0EyK3z6QZhrDDGAU7iqrv Yqbfl32lsxtIRUqGXmfLCFcL4aWWhOn/izKNZEq75BEBm8ilbD4B+1k82LRzVWjAhmOS lF7JW2nEpwYaTLOS0WwBU3Ca9uTMCcz8fsAYXHbER2stwslC9AJK7gKpuISSW0WuSoIU gcsjRiGNPROTP96reMFytJjAtC1cK0/mo6NVNwAq/7jeawVe7eoKOZHY9NL+TqieFiD9 hRCw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1730736712; x=1731341512; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=CanoitEuan7nZ7zXtvGLz59fFXX3oXIfY7Jtkfkywbs=; b=W8akbq2joH+Wr3dvWmpgA28kWsYotYN0NCbpBbEGFNwRaEcNTXDJ9z/073mbypuGFy n3xBriHGKKPRECPoqGqR7IorbuyUvQrC4Lp0VVLJSRG7Qz4PVKGYVTSRRwMQPC6YV7E8 /904R++LWtWgK2cwMpw8U4N8BD1Wcp5QGg3jLkymbYrxYgU8t5OGk/ttk0i3X3HTR7fO jKyEb8m3wTC7KRzISj2VjyW94PqVMveiwdZHVr7J6KLjd0e2UM1POcEPHbkwWW0pg4U0 B+viU3ijg/iJwoYEw4EKbS8v8QL0I1CIB7IsO/wm9QJJsW7ETFtpgGCBVLd1dhX/AgmB Lqhw== X-Gm-Message-State: AOJu0YxBRO3wT1ODoASgb0hGf62fcBhp+yVj/gjztUNMP1JQpXPG9ADk XAWG2kGtqs6gzrpvweVY1E4GgleMv0UKdwr6aR3ErLxcxlSexB+9YKeGeDduViWpJE+K8DdvYYo = X-Google-Smtp-Source: AGHT+IFgrL7FEL2VOL3WvEsDUeddbsoCCYEyAQzlBGmWRiqmswNZVBX1k4sSsDy6V8hHiZTDYhRGjg== X-Received: by 2002:a5d:5f93:0:b0:371:6fc7:d45d with SMTP id ffacd0b85a97d-381c13069b6mr14556027f8f.2.1730736711772; Mon, 04 Nov 2024 08:11:51 -0800 (PST) Received: from poulhies-Precision-5550.telnowedge.local (lmontsouris-659-1-24-67.w81-250.abo.wanadoo.fr. [81.250.175.67]) by smtp.gmail.com with ESMTPSA id ffacd0b85a97d-381c10e747csm13574463f8f.64.2024.11.04.08.11.51 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 04 Nov 2024 08:11:51 -0800 (PST) From: =?utf-8?q?Marc_Poulhi=C3=A8s?= To: gcc-patches@gcc.gnu.org Cc: Nicolas Roche Subject: [COMMITTED 32/38] ada: Improve Unbounded_String performance Date: Mon, 4 Nov 2024 17:11:07 +0100 Message-ID: <20241104161116.1431659-32-poulhies@adacore.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20241104161116.1431659-1-poulhies@adacore.com> References: <20241104161116.1431659-1-poulhies@adacore.com> MIME-Version: 1.0 X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org From: Nicolas Roche Improve performance of iteration using Element function. Improve performance of Append. gcc/ada/ChangeLog: * libgnat/a-strunb__shared.adb: Restructure code to inline only the most common cases. Remove whenever possible runtime checks. * libgnat/a-strunb__shared.ads: Add Inline => True to Append variants and Element. Tested on x86_64-pc-linux-gnu, committed on master. --- gcc/ada/libgnat/a-strunb__shared.adb | 165 ++++++++++++++++++++------- gcc/ada/libgnat/a-strunb__shared.ads | 18 ++- 2 files changed, 134 insertions(+), 49 deletions(-) diff --git a/gcc/ada/libgnat/a-strunb__shared.adb b/gcc/ada/libgnat/a-strunb__shared.adb index ef4f8c93bdb..2f0ae3a1c92 100644 --- a/gcc/ada/libgnat/a-strunb__shared.adb +++ b/gcc/ada/libgnat/a-strunb__shared.adb @@ -35,6 +35,23 @@ package body Ada.Strings.Unbounded is use Ada.Strings.Maps; + procedure Non_Inlined_Append + (Source : in out Unbounded_String; + New_Item : Unbounded_String); + + procedure Non_Inlined_Append + (Source : in out Unbounded_String; + New_Item : String); + + procedure Non_Inlined_Append + (Source : in out Unbounded_String; + New_Item : Character); + -- Non_Inlined_Append are part of the respective Append method that + -- should not be inlined. The idea is that the code of Append is inlined. + -- In order to make inlining efficient it is better to have the inlined + -- code as small as possible. Thus most common cases are inlined and less + -- common cases are deferred in these functions. + Growth_Factor : constant := 2; -- The growth factor controls how much extra space is allocated when -- we have to increase the size of an allocated unbounded string. By @@ -542,10 +559,12 @@ package body Ada.Strings.Unbounded is (Source : in out Unbounded_String; New_Item : Unbounded_String) is + pragma Suppress (All_Checks); + -- Suppress checks as they are redundant with the checks done in that + -- function. + SR : constant Shared_String_Access := Source.Reference; NR : constant Shared_String_Access := New_Item.Reference; - DL : constant Natural := Sum (SR.Last, NR.Last); - DR : Shared_String_Access; begin -- Source is an empty string, reuse New_Item data @@ -562,19 +581,17 @@ package body Ada.Strings.Unbounded is -- Try to reuse existing shared string - elsif Can_Be_Reused (SR, DL) then - SR.Data (SR.Last + 1 .. DL) := NR.Data (1 .. NR.Last); - SR.Last := DL; + elsif System.Atomic_Counters.Is_One (SR.Counter) + and then NR.Last <= SR.Max_Length + and then SR.Max_Length - NR.Last >= SR.Last + then + SR.Data (SR.Last + 1 .. SR.Last + NR.Last) := NR.Data (1 .. NR.Last); + SR.Last := SR.Last + NR.Last; -- Otherwise, allocate new one and fill it else - DR := Allocate (DL, DL / Growth_Factor); - DR.Data (1 .. SR.Last) := SR.Data (1 .. SR.Last); - DR.Data (SR.Last + 1 .. DL) := NR.Data (1 .. NR.Last); - DR.Last := DL; - Source.Reference := DR; - Unreference (SR); + Non_Inlined_Append (Source, New_Item); end if; end Append; @@ -582,31 +599,34 @@ package body Ada.Strings.Unbounded is (Source : in out Unbounded_String; New_Item : String) is - SR : constant Shared_String_Access := Source.Reference; - DL : constant Natural := Sum (SR.Last, New_Item'Length); - DR : Shared_String_Access; + pragma Suppress (All_Checks); + -- Suppress checks as they are redundant with the checks done in that + -- function. + New_Item_Length : constant Natural := New_Item'Length; + SR : constant Shared_String_Access := Source.Reference; begin - -- New_Item is an empty string, nothing to do if New_Item'Length = 0 then + -- New_Item is an empty string, nothing to do null; - -- Try to reuse existing shared string - - elsif Can_Be_Reused (SR, DL) then - SR.Data (SR.Last + 1 .. DL) := New_Item; - SR.Last := DL; - - -- Otherwise, allocate new one and fill it + elsif System.Atomic_Counters.Is_One (SR.Counter) + -- The following test checks in fact that + -- SR.Max_Length >= SR.Last + New_Item_Length without causing + -- overflow. + and then New_Item_Length <= SR.Max_Length + and then SR.Max_Length - New_Item_Length >= SR.Last + then + -- Try to reuse existing shared string + SR.Data (SR.Last + 1 .. SR.Last + New_Item_Length) := New_Item; + SR.Last := SR.Last + New_Item_Length; else - DR := Allocate (DL, DL / Growth_Factor); - DR.Data (1 .. SR.Last) := SR.Data (1 .. SR.Last); - DR.Data (SR.Last + 1 .. DL) := New_Item; - DR.Last := DL; - Source.Reference := DR; - Unreference (SR); + -- Otherwise, allocate new one and fill it. Deferring the worst case + -- into a separate non-inlined function ensure that inlined Append + -- code size remains short and thus efficient. + Non_Inlined_Append (Source, New_Item); end if; end Append; @@ -614,26 +634,24 @@ package body Ada.Strings.Unbounded is (Source : in out Unbounded_String; New_Item : Character) is - SR : constant Shared_String_Access := Source.Reference; - DL : constant Natural := Sum (SR.Last, 1); - DR : Shared_String_Access; + pragma Suppress (All_Checks); + -- Suppress checks as they are redundant with the checks done in that + -- function. + SR : constant Shared_String_Access := Source.Reference; begin - -- Try to reuse existing shared string - - if Can_Be_Reused (SR, DL) then + if System.Atomic_Counters.Is_One (SR.Counter) + and then SR.Max_Length > SR.Last + then + -- Try to reuse existing shared string SR.Data (SR.Last + 1) := New_Item; SR.Last := SR.Last + 1; - -- Otherwise, allocate new one and fill it - else - DR := Allocate (DL, DL / Growth_Factor); - DR.Data (1 .. SR.Last) := SR.Data (1 .. SR.Last); - DR.Data (DL) := New_Item; - DR.Last := DL; - Source.Reference := DR; - Unreference (SR); + -- Otherwise, allocate new one and fill it. Deferring the worst case + -- into a separate non-inlined function ensure that inlined Append + -- code size remains short and thus efficient. + Non_Inlined_Append (Source, New_Item); end if; end Append; @@ -801,9 +819,10 @@ package body Ada.Strings.Unbounded is (Source : Unbounded_String; Index : Positive) return Character is + pragma Suppress (All_Checks); SR : constant Shared_String_Access := Source.Reference; begin - if Index <= SR.Last then + if Index <= SR.Last and then Index > 0 then return SR.Data (Index); else raise Index_Error; @@ -1215,6 +1234,66 @@ package body Ada.Strings.Unbounded is return Left * Right; end Mul; + ------------------------ + -- Non_Inlined_Append -- + ------------------------ + + procedure Non_Inlined_Append + (Source : in out Unbounded_String; + New_Item : Unbounded_String) + is + SR : constant Shared_String_Access := Source.Reference; + NR : constant Shared_String_Access := New_Item.Reference; + DL : constant Natural := Sum (SR.Last, NR.Last); + DR : Shared_String_Access; + begin + DR := Allocate (DL, DL / Growth_Factor); + DR.Data (1 .. SR.Last) := SR.Data (1 .. SR.Last); + DR.Data (SR.Last + 1 .. DL) := NR.Data (1 .. NR.Last); + DR.Last := DL; + Source.Reference := DR; + Unreference (SR); + end Non_Inlined_Append; + + procedure Non_Inlined_Append + (Source : in out Unbounded_String; + New_Item : String) + is + SR : constant Shared_String_Access := Source.Reference; + DL : constant Natural := Sum (SR.Last, New_Item'Length); + DR : Shared_String_Access; + begin + DR := Allocate (DL, DL / Growth_Factor); + DR.Data (1 .. SR.Last) := SR.Data (1 .. SR.Last); + DR.Data (SR.Last + 1 .. DL) := New_Item; + DR.Last := DL; + Source.Reference := DR; + Unreference (SR); + end Non_Inlined_Append; + + procedure Non_Inlined_Append + (Source : in out Unbounded_String; + New_Item : Character) + is + SR : constant Shared_String_Access := Source.Reference; + begin + if SR.Last = Natural'Last then + raise Constraint_Error; + else + declare + DL : constant Natural := SR.Last + 1; + DR : Shared_String_Access; + begin + DR := Allocate (DL, DL / Growth_Factor); + DR.Data (1 .. SR.Last) := SR.Data (1 .. SR.Last); + DR.Data (DL) := New_Item; + DR.Last := DL; + Source.Reference := DR; + Unreference (SR); + end; + end if; + end Non_Inlined_Append; + --------------- -- Overwrite -- --------------- diff --git a/gcc/ada/libgnat/a-strunb__shared.ads b/gcc/ada/libgnat/a-strunb__shared.ads index fa97680a7fa..d81c66b9f0a 100644 --- a/gcc/ada/libgnat/a-strunb__shared.ads +++ b/gcc/ada/libgnat/a-strunb__shared.ads @@ -153,7 +153,8 @@ is Pre => Length (New_Item) <= Natural'Last - Length (Source), Post => To_String (Source) = To_String (Source)'Old & To_String (New_Item), - Global => null; + Global => null, + Inline => True; procedure Append (Source : in out Unbounded_String; @@ -161,7 +162,8 @@ is with Pre => New_Item'Length <= Natural'Last - Length (Source), Post => To_String (Source) = To_String (Source)'Old & New_Item, - Global => null; + Global => null, + Inline => True; procedure Append (Source : in out Unbounded_String; @@ -169,7 +171,8 @@ is with Pre => Length (Source) < Natural'Last, Post => To_String (Source) = To_String (Source)'Old & New_Item, - Global => null; + Global => null, + Inline => True; function "&" (Left : Unbounded_String; @@ -217,7 +220,8 @@ is with Pre => Index <= Length (Source), Post => Element'Result = To_String (Source) (Index), - Global => null; + Global => null, + Inline => True; procedure Replace_Element (Source : in out Unbounded_String; @@ -1578,11 +1582,13 @@ private type Shared_String_Access is access all Shared_String; - procedure Reference (Item : not null Shared_String_Access); + procedure Reference (Item : not null Shared_String_Access) + with Inline => True; -- Increment reference counter. -- Do nothing if Item points to Empty_Shared_String. - procedure Unreference (Item : not null Shared_String_Access); + procedure Unreference (Item : not null Shared_String_Access) + with Inline => True; -- Decrement reference counter, deallocate Item when counter goes to zero. -- Do nothing if Item points to Empty_Shared_String.