Re: [PATCH 7/7] platform/chrome: Implement quickselect for median calculation

[Tzung-Bi Shih <tzungbi@kernel.org>]

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.