linux-kernel - [PATCH 0/7] platform/chrome: Implement quickselect for median calculation

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Date:   Fri, 10 Nov 2023 02:54:32 +0800
From:   Kuan-Wei Chiu <visitorckw@...il.com>
To:     bleung@...omium.org, tzungbi@...nel.org
Cc:     groeck@...omium.org, chrome-platform@...ts.linux.dev,
        linux-kernel@...r.kernel.org, Kuan-Wei Chiu <visitorckw@...il.com>
Subject: [PATCH 0/7] platform/chrome: Implement quickselect for median calculation

This patch series improves the performance of the
cros_ec_sensor_ring_median function. Currently, an inefficient sorting
algorithm (> O(n)) is used to find the median of an array. This series
replaces the sorting approach with the quickselect algorithm, achieving
an average time complexity of O(n).

The correctness and performance improvement have been verified through
a simple unit testing, including a micro-benchmark [1].

In addition to the algorithmic improvement, this series includes
several typo fixes to enhance the overall code quality and maintain
consistency.

--
[1]:
static void init_array(s64 *arr, size_t length, s64 seed)
{
	for (int i = 0; i < length; i++) {
		seed = (seed * 725861) % 6599;
		arr[i] = seed;
	}
}

static int quickselect_test(void)
{
	s64 *arr;
	s64 median_old, median_new;
	ktime_t start, end;
	s64 delta;
	const size_t array_length = 1000;
	const s64 seed = 1;

	arr = kmalloc(array_length * sizeof(s64), GFP_KERNEL);
	if (!arr)
		return -ENOMEM;

	init_array(arr, array_length, seed);
	start = ktime_get();
	median_old = cros_ec_sensor_ring_median(arr, array_length);
	end = ktime_get();
	delta = ktime_us_delta(end, start);
	printk(KERN_ALERT "time of original function: %lld\n", delta);

	init_array(arr, array_length, seed);
	start = ktime_get();
	median_new = cros_ec_sensor_ring_median_new(arr, array_length);
	end = ktime_get();
	delta = ktime_us_delta(end, start);
	printk(KERN_ALERT "time of new function: %lld\n", delta);

	kfree(arr);

	/* return 0 on success */
	return median_old != median_new;
}

/* Result:
 * time of original function: 897
 * time of new function: 16
 */

Signed-off-by: Kuan-Wei Chiu <visitorckw@...il.com>

--

Kuan-Wei Chiu (7):
  platform/chrome: Fix typo 'preceeds' in comment
  platform/chrome: Fix typo 'perod' in comment
  platform/chrome: Fix typo 'noone' in comment
  platform/chrome: Fix typo 'lantency' in comment
  platform/chrome: Fix typo 'kifo' in commet
  platform/chrome: Fix typo 'change' in comment
  platform/chrome: Implement quickselect for median calculation

 .../platform/chrome/cros_ec_sensorhub_ring.c  | 83 ++++++++++++++-----
 1 file changed, 60 insertions(+), 23 deletions(-)

-- 
2.25.1