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

[Kuan-Wei Chiu]

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@xxxxxxxxx>

--

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