From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR02-DB5-obe.outbound.protection.outlook.com (mail-db5eur02on2067.outbound.protection.outlook.com [40.107.249.67]) by sourceware.org (Postfix) with ESMTPS id DA9133858404 for ; Thu, 18 Apr 2024 13:03:36 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org DA9133858404 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=arm.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=arm.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org DA9133858404 Authentication-Results: server2.sourceware.org; arc=pass smtp.remote-ip=40.107.249.67 ARC-Seal: i=3; a=rsa-sha256; d=sourceware.org; s=key; t=1713445427; cv=pass; b=vYTYKKawgzU+ZX9jcMpY4zj/xoNhCfYHQRbhisR/p2ypVlkVijlx+ylcAIYU6JMSvNzExhGWR28DzH7NKDCYNferfNIVhANk+2rmVIhv4KRIdLPmXqkshYlbCqVUWpv9+bwu9VUV0RehwEK2KpWiqHUcOTTRIdhx2QJHXHOJEPU= ARC-Message-Signature: i=3; a=rsa-sha256; d=sourceware.org; s=key; t=1713445427; c=relaxed/simple; bh=Uj+9ArfIkRPxjDv3+/TNvMSDMb5B8Xymg+a8V+kv+N8=; h=DKIM-Signature:DKIM-Signature:From:To:Subject:Date:Message-ID: MIME-Version; b=o/l9Tg5EUoLEXjFlvbH7K25l8Q6slMbGZBFx9Ngg85U8Xc7+rdy8Y+Loj7YI1xyPMae0ThdyRvLjVvG3YmA4TeyeMxSmhtAf1UMXfIQlGS+Yu0eV3TjEbcz9/SQIX6d4vfTAERaccC/reSmBfEG6Y3uZmxJ7hgqxouvP64s8A1E= ARC-Authentication-Results: i=3; server2.sourceware.org ARC-Seal: i=2; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=pass; b=ibSqQ0jgaFIbbRVDNvfY4bcjlU6i9cD5JL0HIEicX1tn742BNBXJgfQe7X/crDpT+NlvCeWZRWbChNYuE8PhC5IqdV0Jwr0XoME65i98Kt1im6EeIKRGzYNARVG/MQeKAcJpPvshk80ZK/yRj0KJ2aZOVCpK4Mceb7c0YfjsVH9TG69PIaSvVx5rKAJPEdxOuvxAXreMYRgv4vmfL16UbYyV6XGlrJZgRHZjaXrcTwKE+WB0akl/vamFCeDExxFcepLdyvps58ZikOa9YGtWDCDTxSkyhEdOD5Es9rXlOxecrO7JwxkxMlCGvL9OcIBCRmHTAkEKFFVgXECyWqUJGQ== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=ZOx3ep0o6uCow+qpsAnZkWiwOZ+KUDegB9B0OKnNahg=; b=Ednzk1IaTeeRnI+gzH0FtjYnmpJXHRTqkR3UFJ9cCexd3fJqyQd0f+7fM+hLWpe1lEhcGL4OGQGwSfpMgTqlEquhXuQxq9sWiVBqweHf/+F7sCeNRtLmiXONd+uGbXc5ZrEDx8xkz2XEPnVsnMwha04kkUfT2esxrPW8saI4ZJ6iN4l4Oub1Db6S235SOq9j0xyaEKQxlUFXbASZ02X5uvpxHoZqtNcwvJrxt5PoRBWV3HOJ1ig0L2qCIn4MwOTQlUrQzoaawh+o7cYsXS0l3dVLXWk6PCqrTFJVs4t0iouBIImpOJkkwNEBccLP+8tpuICZxOj8daLPMWtG/u9JGg== ARC-Authentication-Results: i=2; mx.microsoft.com 1; spf=pass (sender ip is 63.35.35.123) smtp.rcpttodomain=sourceware.org smtp.mailfrom=arm.com; dmarc=pass (p=none sp=none pct=100) action=none header.from=arm.com; dkim=pass (signature was verified) header.d=armh.onmicrosoft.com; arc=pass (0 oda=1 ltdi=1 spf=[1,1,smtp.mailfrom=arm.com] dkim=[1,1,header.d=arm.com] dmarc=[1,1,header.from=arm.com]) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector2-armh-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=ZOx3ep0o6uCow+qpsAnZkWiwOZ+KUDegB9B0OKnNahg=; b=u5vB4KAYprc2TY8iFAe5zFr/v/lzsOFI8AUs7qHBsscPbRdeJamk7CwIxG925vDezgYxGqw+1pQK2QwIVv95kSmpDUD9CNMS+fnwxiY9Cg4xOWtZ7DhuE/2pnJPbqXoBHhu5eR/E7MS869kHdewzKPC7skL9fw4i4BRv7sh9Jx8= Received: from AS9PR05CA0318.eurprd05.prod.outlook.com (2603:10a6:20b:491::25) by VE1PR08MB5758.eurprd08.prod.outlook.com (2603:10a6:800:1a0::11) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7472.37; Thu, 18 Apr 2024 13:03:33 +0000 Received: from AMS0EPF00000198.eurprd05.prod.outlook.com (2603:10a6:20b:491:cafe::21) by AS9PR05CA0318.outlook.office365.com (2603:10a6:20b:491::25) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7495.23 via Frontend Transport; Thu, 18 Apr 2024 13:03:33 +0000 X-MS-Exchange-Authentication-Results: spf=pass (sender IP is 63.35.35.123) smtp.mailfrom=arm.com; dkim=pass (signature was verified) header.d=armh.onmicrosoft.com;dmarc=pass action=none header.from=arm.com; Received-SPF: Pass (protection.outlook.com: domain of arm.com designates 63.35.35.123 as permitted sender) receiver=protection.outlook.com; client-ip=63.35.35.123; helo=64aa7808-outbound-1.mta.getcheckrecipient.com; pr=C Received: from 64aa7808-outbound-1.mta.getcheckrecipient.com (63.35.35.123) by AMS0EPF00000198.mail.protection.outlook.com (10.167.16.244) with Microsoft SMTP Server (version=TLS1_3, cipher=TLS_AES_256_GCM_SHA384) id 15.20.7452.22 via Frontend Transport; Thu, 18 Apr 2024 13:03:33 +0000 Received: ("Tessian outbound f1e9a43166b5:v313"); Thu, 18 Apr 2024 13:03:33 +0000 X-CheckRecipientChecked: true X-CR-MTA-CID: 3e34d716dd646a41 X-CR-MTA-TID: 64aa7808 Received: from 496296c7a6ea.1 by 64aa7808-outbound-1.mta.getcheckrecipient.com id B7A01FBB-DF9B-4585-9D80-101A26C335CB.1; Thu, 18 Apr 2024 13:03:27 +0000 Received: from EUR05-DB8-obe.outbound.protection.outlook.com by 64aa7808-outbound-1.mta.getcheckrecipient.com with ESMTPS id 496296c7a6ea.1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384); Thu, 18 Apr 2024 13:03:27 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=MH0X+08OvhBH3FqRr2Lk2F15jk/lSdluJhBJUKF+YyEeH/zq6u1tqcem9lBpPMBGKqCl6UzKsGcNXeN5ddeExDK5kBFQ48FGEJuKCwaVI2SJ8Bp5PJrVcKGKr7a0I0BvmZ1O/Y2/ODMtQuBmOr7l4rRmuqELCVLb1WR0yt5Ex5nChAGSgvaNAgqUyqKZvgJeEqLEYdyqRPhCjt9bgI5nmtUX8fjhFLMRAwe2vgWxyuEPLPaVt/WQ69saP0DYsslbtajc/GdRSZl2Q0bXHP3ud4GdxRiKg8NoUe/PtrLDMhXi70odgzg42osJPUPqg4ICpRfWNlTzvdcAUs8IwlRn/Q== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=ZOx3ep0o6uCow+qpsAnZkWiwOZ+KUDegB9B0OKnNahg=; b=i9wZq0TFmrGW9VZpaSM4EpLEdvcWQDzgNNeYiXsxvQgxGiikFEFO8cHYbN0Fdm6REvLWRxwkSeka13qms57wldnlHw3xuMXHjAkZ/lHkjjtbQBJBXwm30ySKZHZL79oD1YTVvECeNCG9nHWQTaYwz570YlxIcSzin4nplmQREw0T9Cx3jNaIgBSWzKhK+OnsQ10XFpmayPGZZvI9N7VJWdrsu5Z3ZFBeMND0TYwINZTxyJ71qZbRT6wPR6QX+TAmgBaIkusDNhmBopf4H1fVwmSbmdsaFvkaeMe6V1Se67Pcb5fZvvNsTjsFmvTmZpLqo25aAW8qJOYnu+C54kFWaw== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=arm.com; dmarc=pass action=none header.from=arm.com; dkim=pass header.d=arm.com; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector2-armh-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=ZOx3ep0o6uCow+qpsAnZkWiwOZ+KUDegB9B0OKnNahg=; b=u5vB4KAYprc2TY8iFAe5zFr/v/lzsOFI8AUs7qHBsscPbRdeJamk7CwIxG925vDezgYxGqw+1pQK2QwIVv95kSmpDUD9CNMS+fnwxiY9Cg4xOWtZ7DhuE/2pnJPbqXoBHhu5eR/E7MS869kHdewzKPC7skL9fw4i4BRv7sh9Jx8= Received: from PAWPR08MB8982.eurprd08.prod.outlook.com (2603:10a6:102:33f::20) by DB4PR08MB9864.eurprd08.prod.outlook.com (2603:10a6:10:3cf::14) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7452.50; Thu, 18 Apr 2024 13:03:24 +0000 Received: from PAWPR08MB8982.eurprd08.prod.outlook.com ([fe80::8b1b:5f28:5006:ac18]) by PAWPR08MB8982.eurprd08.prod.outlook.com ([fe80::8b1b:5f28:5006:ac18%4]) with mapi id 15.20.7472.037; Thu, 18 Apr 2024 13:03:23 +0000 From: Wilco Dijkstra To: 'GNU C Library' Subject: [PATCH] benchtests: Add difficult strstr needle for bruteforce algorithms Thread-Topic: [PATCH] benchtests: Add difficult strstr needle for bruteforce algorithms Thread-Index: AQHakZCNQC/3+YUpT0qWSIBgjs2Jpg== Date: Thu, 18 Apr 2024 13:03:22 +0000 Message-ID: Accept-Language: en-GB, en-US Content-Language: en-GB X-MS-Has-Attach: X-MS-TNEF-Correlator: msip_labels: Authentication-Results-Original: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=arm.com; x-ms-traffictypediagnostic: PAWPR08MB8982:EE_|DB4PR08MB9864:EE_|AMS0EPF00000198:EE_|VE1PR08MB5758:EE_ X-MS-Office365-Filtering-Correlation-Id: 8827642a-9bb8-4b54-a288-08dc5fa7f3d4 x-checkrecipientrouted: true nodisclaimer: true X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam-Untrusted: BCL:0; X-Microsoft-Antispam-Message-Info-Original: jdqrJS7ZLiz7UN3EHm7oiT8xBE1w1/azfAVRnvsu/BV4f4gZG9RhVnSWYUajsBq+3N3x4/c7m2lBxc/MfvM/g9TThn84IpBaHBG8g4ptd6kp+V1Epq6//I+Fh6Cl0sQdTBlocqVQw9VUjRmRcghRgj3XFqe/vY9aqMeCayUjT1YKYXFTecAc6siJq2Seuy1XPRYdNiMuriv3Eu3bRMzhgu4Pu3ChVNA8ok6DoqNUsuoFTQLAc3pQSHi1c8iYZVNYbXSIxkchBl48ZabcuhD5POzuf8CccVvGUpmCec8dxlFoclNS/2EMproXVaeuVe/5GYRhpORIYhZQTE164LbgAmsF3XoK/QpdHIJpZ/V1/xw5kdeYEkFQfFj5XWNi9b4npM1h6bHE7332xlQTJQH2MO9JSlMrntih4gr4CjML1/hWrTDnVgP78wjO+lRTKRKdFJyKNokq4GLRvrI+jQLP4quLxJVimfkzoEj3A2ZX3DMCJS92pvBK80tp58sONNmTCbu4mop0IBzOi/daGNCWGk/ZR7rjfcazqXya/ZAEeNX5Jxp/v3PsS57m4aKr4VJ3nv/nOPb+UvuS7v1VDufkHwIRph6OtPQ5/DIelULdGFjgBxXAqZfQG7dTWzSkjgSunuAf+dFmlV+lnOS4AgFhqvQ3UOYtfbGoVy1aZZJCOFBVeCF/Iw74tsH+dsK/steBJuyI6Yr+gXVH/eAPkFSLAACAYg1u7EBCdpRHMftFxxw= X-Forefront-Antispam-Report-Untrusted: CIP:255.255.255.255;CTRY:;LANG:en;SCL:1;SRV:;IPV:NLI;SFV:NSPM;H:PAWPR08MB8982.eurprd08.prod.outlook.com;PTR:;CAT:NONE;SFS:(13230031)(366007)(1800799015)(376005)(38070700009);DIR:OUT;SFP:1101; Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-MS-Exchange-Transport-CrossTenantHeadersStamped: DB4PR08MB9864 Original-Authentication-Results: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=arm.com; X-EOPAttributedMessage: 0 X-MS-Exchange-Transport-CrossTenantHeadersStripped: AMS0EPF00000198.eurprd05.prod.outlook.com X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id-Prvs: 22770f12-42e6-4750-e214-08dc5fa7ed99 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: ss7pGCm/6FU7ZjI3YaSR/haQdmZwR2jqoLpMzkp21tW8ExT6auW7ljpPXCjibzhuaEJoUJ+aEKNkqKwrjqlxbxNI+h/i4xn22fZR0BvekoPntD/YEXmbCxppD+FueKRt/OfqCWeJ53Imc8BwprpDLX25G3SylLlkiu4oyGGvu/Ul8QIRkE15cepXyyol2yGZXWUQW3KHsPPOq8JTZ5PIvUrs6ZZ2JoH/h4JF2NU3NQ9qUCCC3hX7PEK9MrfFkf/kSW6iP+NZnmqi7r4Fku8HBSUdYv3TS6/5CkbzfaGOxM9miiplYOj5/zR+Zi7tENOiPdsFEidek3UBCTQFERbdGX2ZdXRPK68C9w58LhvUYr3P7yo0QT2gM8MsQxY5ELgf0LGdtVGBzGWqw7jgR/BSO+ddXOqU1OsCY1J/WNHw7JDzdz97w99iA0OP1qGvnOcO+3mJtS2fiebZjc3fOre2ZRHKsNxnX/eNXXHbqGHxZqsNHwrfnhbBIC8hHfcBwEDlmYwNwEjMFlLbc5q6HWK3E90f2VVdNMsUsHAOSnB7gNRQinMAxC3Ndj/mNA8lBzupyXNx7hAl4XsB659IUNYbp8rHgCLgxrcgrL6pgel6zRwVT1j9atSW0Iea3VuLamkj9bG+bGPeGpdi4g5tz61xILVn49DNY4lBU1ce3HBRdOx2mcifyiIZMGCyVdMSJ3h5V1kGe5ygt5w1ySt8URPJxtQpf7Nt7Ox7CikalCKzeCe+nvabIIFSuTrRIKmOhaln X-Forefront-Antispam-Report: CIP:63.35.35.123;CTRY:IE;LANG:en;SCL:1;SRV:;IPV:CAL;SFV:NSPM;H:64aa7808-outbound-1.mta.getcheckrecipient.com;PTR:ec2-63-35-35-123.eu-west-1.compute.amazonaws.com;CAT:NONE;SFS:(13230031)(82310400014)(376005)(36860700004)(1800799015);DIR:OUT;SFP:1101; X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 18 Apr 2024 13:03:33.4118 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 8827642a-9bb8-4b54-a288-08dc5fa7f3d4 X-MS-Exchange-CrossTenant-Id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=f34e5979-57d9-4aaa-ad4d-b122a662184d;Ip=[63.35.35.123];Helo=[64aa7808-outbound-1.mta.getcheckrecipient.com] X-MS-Exchange-CrossTenant-AuthSource: AMS0EPF00000198.eurprd05.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: VE1PR08MB5758 X-Spam-Status: No, score=-10.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,FORGED_SPF_HELO,GIT_PATCH_0,KAM_DMARC_NONE,RCVD_IN_MSPIKE_H2,SPF_HELO_PASS,SPF_NONE,TXREP,UNPARSEABLE_RELAY autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: =0A= Add another difficult needle to strstr that clearly shows the quadratic=0A= complexity of bruteforce algorithms.=0A= =0A= OK for commit?=0A= =0A= ---=0A= =0A= diff --git a/benchtests/bench-strstr.c b/benchtests/bench-strstr.c=0A= index 9288ad16e963d5397419aa11263520d259d2d6b9..4b07d39a50b0e5e1f29743a258b= 05466099c1959 100644=0A= --- a/benchtests/bench-strstr.c=0A= +++ b/benchtests/bench-strstr.c=0A= @@ -352,6 +352,33 @@ test_hard_needle (json_ctx_t *json_ctx, size_t ne_len,= size_t hs_len)=0A= json_array_end (json_ctx);=0A= json_element_object_end (json_ctx);=0A= }=0A= +=0A= + /* Hard needle for bruteforce algorithms that match first few chars. */= =0A= + {=0A= + memset (hs, 'a', hs_len);=0A= + for (int i =3D ne_len-1; i < hs_len; i +=3D ne_len)=0A= + hs[i] =3D 'b';=0A= + hs[hs_len] =3D 0;=0A= +=0A= + memset (ne, 'a', ne_len);=0A= + ne[ne_len] =3D 0;=0A= +=0A= + json_element_object_begin (json_ctx);=0A= + json_attr_uint (json_ctx, "len_haystack", hs_len);=0A= + json_attr_uint (json_ctx, "len_needle", ne_len);=0A= + json_attr_uint (json_ctx, "align_haystack", 0);=0A= + json_attr_uint (json_ctx, "align_needle", 0);=0A= + json_attr_uint (json_ctx, "fail", 1);=0A= + json_attr_string (json_ctx, "desc", "Difficult bruteforce needle");=0A= +=0A= + json_array_begin (json_ctx, "timings");=0A= +=0A= + FOR_EACH_IMPL (impl, 0)=0A= + do_one_test (json_ctx, impl, hs, ne, NULL);=0A= +=0A= + json_array_end (json_ctx);=0A= + json_element_object_end (json_ctx);=0A= + }=0A= }=0A= =0A= static int=0A= =0A=