From patchwork Mon Sep 9 02:19:15 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: 57434 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 84B98385E830 for ; Mon, 9 Sep 2024 02:20:28 +0000 (GMT) X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-pf1-x42a.google.com (mail-pf1-x42a.google.com [IPv6:2607:f8b0:4864:20::42a]) by sourceware.org (Postfix) with ESMTPS id 02639385840C for ; Mon, 9 Sep 2024 02:19:37 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 02639385840C 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 02639385840C Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::42a ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1725848379; cv=none; b=iB2JQO21Am90N/kbHROLLhUjeHZPqsdcWQLDtQvA2XXC1PZ0if765rMRLSWqOa5aJlObMnLq4AK/t/cfjtcOHCJmlXUh47OFtMBC6D3HAhIB80hKQrjcoVVmxANxVvoBviFaTcM2urJv5zDq4LD7QQiq6LVYsstZ8Vq6Vd769zI= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1725848379; c=relaxed/simple; bh=T9hKCYAUn2sybVQMWFZJxySUNFAZHe+DNQb9L7WHWv0=; h=DKIM-Signature:From:To:Subject:Date:Message-Id:MIME-Version; b=NdZVGTurYnfYAGATJ8+7FifLqzkrtEDZ3OfRdGTtTf6B58F6cMfIrmKvsGoNQ22k06vR4uapidQrOrZQhmKFiuivwNQuVkhflHTsFA9GQvhS8E1HfZwJwikSTkm+bVpTSyYQI2rPvnWcYRfhgRkaE0Go4BxI7N+7UtnivsxjPgY= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-pf1-x42a.google.com with SMTP id d2e1a72fcca58-717849c0dcaso3417160b3a.3 for ; Sun, 08 Sep 2024 19:19:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1725848375; x=1726453175; 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=qWngtEUsfrFXDPc1FjBfnWTycvNXAQFHlYrxv2VK70w=; b=HnFk5qGA56XYllYOcTGqBRRhIinWsh8B4H6hhXWzJc6mCMy+jnZ18THyag+cQprE7p fzIWbggLLMSjAClEufTi88elNPpRWh5fSQGIvCxs4r3xQOoOW7V6V4nabDSbOPV1RbT+ nKIcpzjwuKGk3g3JzuSkkjGb5eC0XVMunfPchWJSRYFHUhkLTwgCarFjITFt6YsOjLPq /nimlJZkYM5x/vPMB0QQ848u/bByRBZmLpQAMQ4m/go87sQfbwaOUeIqcOBDoCoJlqqB h+UpgB59iXfhPhi7jbBoAO79QuKmp7DlfkwFCTkinaQizVzt/Z5w1rk0b13hus3WEIxV Umfw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1725848375; x=1726453175; 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=qWngtEUsfrFXDPc1FjBfnWTycvNXAQFHlYrxv2VK70w=; b=YMdD/Ov4Pym9WomupqSDNXaHpus/8iIyIp1jK+i3fG7H6YHGIjz7ax5KKlgw9iaCTg gIcGqr+NfB7Va3CQTCXqjbuiIH33XTsr5Uj/8G+DF5hnBEQdM8GYfuAGdOZPM8dKW+dQ 1o1qJrJU93fSgwzCctcUbDyuVH78FYuB+O/tiuSOc+15Qy9flw4cA2umCyCHp5Rgnww1 2qk7drS6+g7I3T/q0RW2+ltO2Zh2/ddVj2Yh6OYyZOkJ/iwYr2OCv+RQyR3xn/oNkblq qAEITitltFKW3FjkMzwWTOivplKEeaLubeA6A6KD2TyPrZxYQcQKMR5/T9Fbjd42UTnB ANtg== X-Gm-Message-State: AOJu0YxcH1J1OL723L+sUet59LV9cuh49rmujw8SpnuqTky6VrKCpkYt PPlnB9/vmsXrH+7+AWMBUH0kdXxjc+eRi+vXETTnbqCxHexdLA0zHe2T+w== X-Google-Smtp-Source: AGHT+IFh0QXBOTlAnINiNcJ0Ht1+kO84O5FkqSQoaAWLFqRF6t9Vp20AdmK9ik5MklzW6aZdejt/qw== X-Received: by 2002:a05:6a21:1706:b0:1c6:ed5e:241 with SMTP id adf61e73a8af0-1cf1d0acadcmr9644626637.15.1725848374570; Sun, 08 Sep 2024 19:19:34 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2dadc1104a3sm5398524a91.45.2024.09.08.19.19.32 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 08 Sep 2024 19:19:33 -0700 (PDT) From: Kuan-Wei Chiu To: libc-alpha@sourceware.org Cc: goldstein.w.n@gmail.com, jserv@ccns.ncku.edu.tw, Kuan-Wei Chiu Subject: [PATCH v6 0/2] Optimization and benchmarking of bsearch() Date: Mon, 9 Sep 2024 10:19:15 +0800 Message-Id: <20240909021917.3159077-1-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 MIME-Version: 1.0 X-Spam-Status: No, score=-4.5 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, 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 Hello, I have added a benchmark test for the bsearch() function and optimized its implementation to enhance its efficiency. Benchmark results on my x86 machine demonstrate that the new implementation reduces execution time by 15% compared to the previous version. Changes in v6: - Add 'nmemb' field to the 'results' array. Changes in v5: - Move 'array-size', 'key-pattern', and 'contained' fields into the 'results' array. - Add 'simple' field to the 'results' array. - Add tests for 'key-pattern' = 'descending' and 'contained' = 'no'. - Drop the full benchmark log from the commit message as it is becoming too verbose. Changes in v4: - Add three fields: "array-size," "key-pattern," and "contained" to benchmark json output. - Update the benchmark result format in commit messages. Changes in v3: - Sort the stdlib-benchset entries in Makefile to resolve CI failures. Changes in v2: - Add benchmark tests for the bsearch() function. - Update the commit message to reflect the new benchmark results. Regards, Kuan-Wei Kuan-Wei Chiu (2): benchtests: Add benchmark test for bsearch Optimize bsearch() implementation for performance benchtests/Makefile | 1 + benchtests/bench-bsearch.c | 137 +++++++++++++++++++++++++++++++++++++ bits/stdlib-bsearch.h | 20 +++--- 3 files changed, 147 insertions(+), 11 deletions(-) create mode 100644 benchtests/bench-bsearch.c