linux-kernel - Re: [PATCH 7/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-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <ZU3GWkKczNV-AQA4@google.com>
Date:   Fri, 10 Nov 2023 13:57:46 +0800
From:   Tzung-Bi Shih <tzungbi@...nel.org>
To:     Kuan-Wei Chiu <visitorckw@...il.com>
Cc:     bleung@...omium.org, groeck@...omium.org,
        chrome-platform@...ts.linux.dev, linux-kernel@...r.kernel.org
Subject: Re: [PATCH 7/7] platform/chrome: Implement quickselect for median
 calculation

On Fri, Nov 10, 2023 at 02:54:39AM +0800, Kuan-Wei Chiu wrote:
>  /*
>   * cros_ec_sensor_ring_median: Gets median of an array of numbers
>   *
> - * For now it's implemented using an inefficient > O(n) sort then return
> - * the middle element. A more optimal method would be something like
> - * quickselect, but given that n = 64 we can probably live with it in the
> - * name of clarity.
> + * It's implemented using the quickselect algorithm, which achieves an
> + * average time complexity of O(n) the middle element. In the worst case,
> + * the runtime of quickselect could regress to O(n^2). To mitigate this,
> + * algorithms like median-of-medians exist, which can guarantee O(n) even
> + * in the worst case. However, these algorithms come with a higher
> + * overhead and are more complex to implement, making quickselect a
> + * pragmatic choice for our use case.

I am wondering if the patch helps given that n = 64.

>  static s64 cros_ec_sensor_ring_median(s64 *array, size_t length)
>  {
> -	sort(array, length, sizeof(s64), cros_ec_sensor_ring_median_cmp, NULL);
> -	return array[length / 2];
> +	const int k = length / 2;

`k` doesn't help readability.  Could you put `length / 2` to the code inline
or at least give it a better name.

> +	int lo = 0;
> +	int hi = length - 1;
> +
> +	while (lo <= hi) {
> +		int mid = lo + (hi - lo) / 2;
> +		int pivot, pivot_index;
> +		int i = lo - 1;

The be clear, I would prefer to initialize `i` when we really use it (i.e. at
the for-loop).

> +
> +		/* We employ the median-of-three rule to choose the pivot, mitigating

https://www.kernel.org/doc/html/latest/process/coding-style.html#commenting

> +		 * worst-case scenarios such as already sorted arrays and aiming to reduce
> +		 * the expected number of necessary comparisons. This strategy enhances the
> +		 * algorithm's performance and ensures a more balanced partitioning.
> +         */

$ ./scripts/checkpatch.pl --strict ...
ERROR: code indent should use tabs where possible
#284: FILE: drivers/platform/chrome/cros_ec_sensorhub_ring.c:171:
+         */$

> +		if (array[lo] > array[mid])
> +			cros_ec_sensor_ring_median_swap(&array[lo],
> +							&array[mid]);

It can fit into 100-column.

> +		if (array[lo] > array[hi])
> +			cros_ec_sensor_ring_median_swap(&array[lo], &array[hi]);
> +		if (array[mid] < array[hi])
> +			cros_ec_sensor_ring_median_swap(&array[mid],
> +							&array[hi]);

Ditto.

> +
> +		pivot = array[hi];
> +
> +		for (int j = lo; j < hi; j++)
> +			if (array[j] < pivot)
> +				cros_ec_sensor_ring_median_swap(&array[++i],
> +								&array[j]);

Ditto.

> +		cros_ec_sensor_ring_median_swap(&array[i + 1], &array[hi]);
> +		pivot_index = i + 1;
> +		if (pivot_index == k)
> +			return array[pivot_index];
> +		if (pivot_index > k)
> +			hi = pivot_index - 1;
> +		else
> +			lo = pivot_index + 1;

Add a comment and thus `pivot_index` can be eliminated.