From patchwork Sun Sep 1 01:54:56 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kuan-Wei Chiu X-Patchwork-Id: 1979365 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; unprotected) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20230601 header.b=TjFzYKRV; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=sourceware.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=libc-alpha-bounces~incoming=patchwork.ozlabs.org@sourceware.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (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 4WxFPB5ppLz1yZ9 for ; Sun, 1 Sep 2024 11:56:46 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 279973858C52 for ; Sun, 1 Sep 2024 01:56:41 +0000 (GMT) X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-oo1-xc33.google.com (mail-oo1-xc33.google.com [IPv6:2607:f8b0:4864:20::c33]) by sourceware.org (Postfix) with ESMTPS id B20743858D34 for ; Sun, 1 Sep 2024 01:55:20 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org B20743858D34 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 B20743858D34 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::c33 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1725155728; cv=none; b=uXAY7hiVEC4fMJl7LtBwAUSOwvhmQyGsupTOal8EKjBSAnDK5nzES6jbNap5YLQbBoCJN4YoSE0PT2jhMMfHD96i+ipuhWg2mepj2fOcmLspCnmLQuBSPziJ7etRk37f9dGHFxn9PSbTItX9F1jD1u7d83hv1ljambR6SjwIN2Y= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1725155728; c=relaxed/simple; bh=W6gp5SrHKw5YjJXuRlxNyIEogjGGR7XiwwDV5abndHc=; h=DKIM-Signature:From:To:Subject:Date:Message-Id:MIME-Version; b=NH0cNe9eU2mY280st1xyTaPWm2IvlaZW/fXBk39No0BPeb2gsbaNBsfcFyAm8qxXpsFTIFjg1chgmeqw1H5BIA1FUZXKVkw1hxJoz3j6YKp5ZX/y5bPhkBMDDTZz5BMP53lOXm9kxZqsDQGANxM/e+7LYR9mmujNo2fw1Dqy9rs= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-oo1-xc33.google.com with SMTP id 006d021491bc7-5daa93677e1so1922763eaf.3 for ; Sat, 31 Aug 2024 18:55:20 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1725155719; x=1725760519; darn=sourceware.org; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=T/HLuu7k7hihvC/ZqTcbUNuD4Xvtd02F8ZY1hZ/joik=; b=TjFzYKRV8x5ZLTv7u0SyZSLB3FwIUGAVu4VjGB3dmaoE3YGE8Ujv4cDiV5+lvCC4SR BEbGsn4tCXzHzz/RzHo2wdVX04r8QJhK/i88La48zL8haKwPWj4Xm+p+Jkq5mIYOCDRL TqBI2EN16pMEujS17tXhy6Ri9rYQvPWzUyXnQrUEWE7d7MRkmEg2YJzJqySGiTDiOvep KIC0pWzy5wjxfLDxMvgKeM2cQoo+KAlyz7gWGOFu0cFHnkem7IvQ9DD9ObMWXui5XFHa Xkas4ec7DINKCHYFyH7fc5ADfanmWUuctGh/F+ZfsVDpiTOfqeBB6GHt3Svr3RUA/cd6 eiWg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1725155719; x=1725760519; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=T/HLuu7k7hihvC/ZqTcbUNuD4Xvtd02F8ZY1hZ/joik=; b=XiOgtFU8TMJdXBbVK1QjXI0XRcAxe9PSSYBvfsJ1fL2Mngq/OAxd3jbuYu+SvGJfZw /T9ob2JhhHYqoBpYHgeKj9w1Ib9jzbc+mvVha4Q66OpiFI18od9iWCThvyuuuwzoGlXC Oh9VnBJ0sH0EjEH2xo1qCpA3XVOXOhWOWTy3wErP/RS8i4DEqOY6WffLiVtw7A31u34z QxU++zFvXvuAqwU+ZsMNSsI8XITTOQfK0AH245aYrjSvhWmM7x5VpZ1+R/7uPEVLWCYL q5rIqSgbEzjwZ5ogvpBIG3Rg6lleQB27fWhSs3Ddnauv31gDQhacT4TgClgUGooo+Ai1 whIw== X-Gm-Message-State: AOJu0YzXdt7K9g+ORjOF+QYXR0OJForenAotNZuvCNihcDH+/Kkb3W8/ wNPTdYUpkBuCsAAuxIQSRfCET/ZWGjSHLiTQZnWfdiGtFY4TeVSKDLI1Yw== X-Google-Smtp-Source: AGHT+IF1Jh0Q8hkLF9mwGVTthT8e9g4RlhGV+LjfWDXAPyQ3k6W2KqIUJuC7nXEJGoHRCCO3vvUjcQ== X-Received: by 2002:a05:6870:8455:b0:268:9e7a:a493 with SMTP id 586e51a60fabf-2779031a52fmr11929979fac.42.1725155719159; Sat, 31 Aug 2024 18:55:19 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-715e56e3e46sm4722751b3a.150.2024.08.31.18.55.17 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 31 Aug 2024 18:55:18 -0700 (PDT) From: Kuan-Wei Chiu To: libc-alpha@sourceware.org Cc: jserv@ccns.ncku.edu.tw, Kuan-Wei Chiu Subject: [RFC PATCH] Optimize bsearch() implementation for performance Date: Sun, 1 Sep 2024 09:54:56 +0800 Message-Id: <20240901015456.1782446-1-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 MIME-Version: 1.0 X-Spam-Status: No, score=-10.4 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE 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~incoming=patchwork.ozlabs.org@sourceware.org Optimize the bsearch() function to improve binary search performance. This modification reduces the execution time by approximately 8% on an x86 machine with a 100,000-element array under 1e8 searches. The optimization slightly increases the code size by 8 bytes. code size: * old: text data bss dec hex filename 250 0 0 250 fa ./stdlib/bsearch.o * new: text data bss dec hex filename 258 0 0 258 102 ./stdlib/bsearch.o benchmark: Old bsearch elapsed time: 4536833 New bsearch elapsed time: 4137556 Improve efficiency by 8 % Signed-off-by: Kuan-Wei Chiu --- Since I only have x86 machines available for testing, I am not entirely certain whether this patch will bring performance improvements across different architectures. Therefore, I am sending this as an RFC patch first. bits/stdlib-bsearch.h | 20 +++++++++----------- 1 file changed, 9 insertions(+), 11 deletions(-) diff --git a/bits/stdlib-bsearch.h b/bits/stdlib-bsearch.h index 540d718952..57f060b504 100644 --- a/bits/stdlib-bsearch.h +++ b/bits/stdlib-bsearch.h @@ -20,22 +20,14 @@ __extern_inline void * bsearch (const void *__key, const void *__base, size_t __nmemb, size_t __size, __compar_fn_t __compar) { - size_t __l, __u, __idx; const void *__p; int __comparison; - __l = 0; - __u = __nmemb; - while (__l < __u) + while (__nmemb) { - __idx = (__l + __u) / 2; - __p = (const void *) (((const char *) __base) + (__idx * __size)); + __p = (const void *) (((const char *) __base) + ((__nmemb >> 1) * __size)); __comparison = (*__compar) (__key, __p); - if (__comparison < 0) - __u = __idx; - else if (__comparison > 0) - __l = __idx + 1; - else + if (__comparison == 0) { #if __GNUC_PREREQ(4, 6) # pragma GCC diagnostic push @@ -46,6 +38,12 @@ bsearch (const void *__key, const void *__base, size_t __nmemb, size_t __size, # pragma GCC diagnostic pop #endif } + if (__comparison > 0) + { + __base = ((const char *) __p) + __size; + --__nmemb; + } + __nmemb >>= 1; } return NULL;