From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id ACD6E5D477 for ; Fri, 24 May 2024 21:51:21 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=198.137.202.133 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716587483; cv=none; b=rIz73wcFy40wmPnG3zW3Cx6dbkCz6IHCBULWhSsLMMl9+7Sqzd6ydfiPrG7zb4d4P7FAvbHSGXYqiv6+atzmBR9giqwhdGke4czm3v7hJxy8IU02fGv+xGeymJEuLm4suabIORhIu1M1LfqLZ1EUUXO+M4dN/P5648EnfjE0elM= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716587483; c=relaxed/simple; bh=WVFUtCe3lZWbkcTVb9/84OCv/f+3ZLrtdsiON1GvMy0=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=r2UqfJ8UGgB4q33RWYsuBodogwrSaTZgdT2Mfm68/8FX8oyGpsLIX3yQCM3NSZZ1tMU8nbXGhOxqOCmPbthVEmjcZ87oVRpF2cY87EZUW6cduV5UGfzIwM7L+SiYKPtbj7I38CKV3oC1fRbn1heABW48wSkpO97zQ1vUUEcpayI= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=fail (p=none dis=none) header.from=kernel.org; spf=none smtp.mailfrom=infradead.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b=K2rReX7w; arc=none smtp.client-ip=198.137.202.133 Authentication-Results: smtp.subspace.kernel.org; dmarc=fail (p=none dis=none) header.from=kernel.org Authentication-Results: smtp.subspace.kernel.org; spf=none smtp.mailfrom=infradead.org Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b="K2rReX7w" DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20210309; h=Sender:Content-Transfer-Encoding: MIME-Version:References:In-Reply-To:Message-ID:Date:Subject:Cc:To:From: Reply-To:Content-Type:Content-ID:Content-Description; bh=qGOeoV79yVTrL5mdmx/uR9vy1E82DMauUscQQ+zkTYU=; b=K2rReX7wSJ2mMxWFsW5h0r1ozT qyCzIDZ3MVuy4dK6tfm/tNkEfcpCuulNWNWdjan9OQhgbtDzXukQxkqIv6aZ2xwKoTWGy3LZG5JA3 xAiEWHo94U84wxYxrK0F9Y8pOX4n/4soVBdK9LGwUIJxI0lgbdg02fzRA31ZcSnfERfCX8/mU6f8r o62FBb0VmNsb+2S9IybeHPzmAjlnVhF4V4h+/vb8lnfT8+eC5GBMsOpY8meYxx49gP7xIeHUtxx4m ZBHGDTJxZ3giaspw1dWxyQBqrp55ZvIl2J5AY7UFs/PU+BxJKHTnOTDW24CjgTU3mbtkE8LzxUaqq Z4P41mVA==; Received: from mcgrof by bombadil.infradead.org with local (Exim 4.97.1 #2 (Red Hat Linux)) id 1sAcol-00000009xVG-0IvR; Fri, 24 May 2024 21:51:15 +0000 From: Luis Chamberlain To: mgorman@suse.de, jack@suse.cz, vbabka@suse.cz, dave@stgolabs.net, ziy@nvidia.com, yuzhao@google.com, jhubbard@nvidia.com, ryan.roberts@arm.com Cc: kdevops@lists.linux.dev, p.raghav@samsung.com, da.gomez@samsung.com, gost.dev@samsung.com, Luis Chamberlain Subject: [mmtests PATCH v3 2/2] MMTests::Stat: replace List::BinarySearch Date: Fri, 24 May 2024 14:51:12 -0700 Message-ID: <20240524215113.2373668-3-mcgrof@kernel.org> X-Mailer: git-send-email 2.44.0 In-Reply-To: <20240524215113.2373668-1-mcgrof@kernel.org> References: <20240524215113.2373668-1-mcgrof@kernel.org> Precedence: bulk X-Mailing-List: kdevops@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Sender: Luis Chamberlain List::BinarySearch is ancient and has a few issues: a) The project hasnt't received any updates since 2018 b) It's licensed under GPLv1 or Artistica v1 license which are not compatible with GPLv2 c) Some distributions don't carry a package for it Debian in particular doesn't have it anymore. I looked at the code and was bewildered with the amount of insane hacks to support ancient versions of perl and to also support running our custom comparison routine. All the above challenges seem silly to deal with on users if we can just implement what we need and call it a day. So let's do that. Instead of piling a set of unit tests on mmtests the approach taken to ensure a proper replacement for the library is to use a separate repository that proves a replacement for the library, which has its own unit tests [0]. The work we do here is then to not only show how we have simplified the old code, but also can use the same tests in the kill-List-BinarySearch against the exact old library without breaking things. That gives us two ways to test for correctness. While at it use SPDX license identifiers to simplify license clarity just as we have in the kernel. The same SPDX tag is already upstream on Linux. We can expand on this to keep things simpler later. [0] https://github.com/mcgrof/kill-List-BinarySearch Reviewed-by: Jan Kara Tested-by: Davidlohr Bueso [futex, hackbench, sysvs ipc] Signed-off-by: Luis Chamberlain --- README.md | 5 ++--- bin/install-depends | 1 - bin/lib/MMTests/Stat.pm | 48 +++++++++++++++++++++++++++++++++++++++-- compare-kernels.sh | 5 ----- 4 files changed, 48 insertions(+), 11 deletions(-) diff --git a/README.md b/README.md index ae9b119d150d..98c5975e4197 100644 --- a/README.md +++ b/README.md @@ -44,9 +44,8 @@ $ ../../compare-kernels.sh --format html --output-dir /tmp/html > /tmp/html/inde The first step is optional. Some configurations are auto-generated from a template, particularly the filesystem-specific ones. -Note that [`List::BinarySearch`](https://metacpan.org/pod/List::BinarySearch) -and maybe even [`Math::Gradient`](https://metacpan.org/pod/Math::Gradient) may -need to be installed from [CPAN](https://www.cpan.org/) for the reporting to +Note that perhaps [`Math::Gradient`](https://metacpan.org/pod/Math::Gradient) +may need to be installed from [CPAN](https://www.cpan.org/) for the reporting to work. Similarly, [`R`](https://www.r-project.org/) should be installed if attempting to highlight whether performance differences are statistically relevant. diff --git a/bin/install-depends b/bin/install-depends index a7cfaa49977b..0244816aa623 100755 --- a/bin/install-depends +++ b/bin/install-depends @@ -61,7 +61,6 @@ my %package_map = ( "debian::xz" => "xz-utils", "debian::zeromq-devel" => "libzmq3-dev", "debian::zlib-devel" => "zlib1g-dev", - "debian::perl-List-BinarySearch" => "liblist-binarysearch-perl", "debian::perl-GD" => "libgd-perl", "debian::sysvinit-tools" => "sysvinit-utils", "debian::gettext-runtime" => "gettext", diff --git a/bin/lib/MMTests/Stat.pm b/bin/lib/MMTests/Stat.pm index 41e6b79267c9..d14b51bb36c3 100644 --- a/bin/lib/MMTests/Stat.pm +++ b/bin/lib/MMTests/Stat.pm @@ -1,16 +1,23 @@ +# SPDX-License-Identifier: GPL-2.0-or-later OR copyleft-next-0.3.1 # # Stat.pm # # Basic stats module +# +# Copyright (c) 2002-2024 Mel Gorman +# Copyright (c) 2017-2019 Jan Kara +# Copyright (c) 2017-2023 Andreas Herrmann +# Copyright (c) 2024 Luis Chamberlain package MMTests::Stat; require Exporter; use vars qw (@ISA @EXPORT); use MMTests::Report; use strict; +use feature 'signatures'; +no warnings 'experimental::signatures'; use POSIX qw(floor); use FindBin qw($Bin); -use List::BinarySearch qw(binsearch_range); use Scalar::Util qw(looks_like_number); @ISA = qw(Exporter); @@ -479,6 +486,43 @@ sub calc_submean_ci { return ($parsedrow[1], $parsedrow[2]); } +sub binsearch_pos_num($target, $aref) { + die "Only numbers allowed" unless looks_like_number($target); + die "Expected an array reference!" unless ref $aref eq 'ARRAY'; + + my ($low, $high) = (0, scalar @$aref - 1); + + while ($low <= $high) { + my $mid = int(($low + $high) / 2); + if ($aref->[$mid] < $target) { + $low = $mid + 1; + } elsif ($aref->[$mid] > $target) { + $high = $mid - 1; + } else { + return $mid; + } + } + + return $low; +} + +# Returns an inclusive range for both, if you only use one return +# value, you consume the last value. +sub binsearch_range_num ($low_target, $high_target, $aref) { + die "Only numbers allowed" unless looks_like_number($low_target); + die "Only numbers allowed" unless looks_like_number($high_target); + die "Expected an array reference!" unless ref $aref eq 'ARRAY'; + + my $index_low = binsearch_pos_num($low_target, $aref); + my $index_high = binsearch_pos_num($high_target, $aref); + + if($index_high == scalar @$aref or $aref->[$index_high] > $high_target) { + $index_high--; + } + + return ($index_low, $index_high); +} + sub calc_samples { my ($dataref, $arg) = @_; my $elements = @{$dataref}; @@ -495,7 +539,7 @@ sub calc_samples { } elsif ($high eq "max") { $high = $dataref->[$elements - 1]; } - my ($lowidx, $highidx) = binsearch_range { $a <=> $b } $low, $high, @{$dataref}; + my ($lowidx, $highidx) = binsearch_range_num($low, $high, $dataref); return $highidx - $lowidx + 1; } diff --git a/compare-kernels.sh b/compare-kernels.sh index 7c49f2d95044..428de060c553 100755 --- a/compare-kernels.sh +++ b/compare-kernels.sh @@ -83,11 +83,6 @@ if [ ! -t 1 ]; then OUT=$(mktemp ~/.compare-kernel-XXXX.out) fi -perldoc -l List::BinarySearch &>/dev/null -if [ $? -ne 0 ]; then - install-depends perl-List-BinarySearch &> $OUT -fi - if [ "$FORMAT" = "html" ]; then install-depends gnuplot &>> $OUT install-depends perl-GD &>> $OUT -- 2.43.0