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

[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@gmail.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

[PATCH 1/7] platform/chrome: Fix typo 'preceeds' in comment

[Kuan-Wei Chiu]

Replace 'preceeds' with 'precedes' in the comment.

Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
 drivers/platform/chrome/cros_ec_sensorhub_ring.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/drivers/platform/chrome/cros_ec_sensorhub_ring.c b/drivers/platform/chrome/cros_ec_sensorhub_ring.c
index 71948dade0e2..568bbb64a389 100644
--- a/drivers/platform/chrome/cros_ec_sensorhub_ring.c
+++ b/drivers/platform/chrome/cros_ec_sensorhub_ring.c
@@ -511,7 +511,7 @@ cros_ec_sensor_ring_process_event(struct cros_ec_sensorhub *sensorhub,
  *                                 ringbuffer.
  *
  * This is the new spreading code, assumes every sample's timestamp
- * preceeds the sample. Run if tight_timestamps == true.
+ * precedes the sample. Run if tight_timestamps == true.
  *
  * Sometimes the EC receives only one interrupt (hence timestamp) for
  * a batch of samples. Only the first sample will have the correct
-- 
2.25.1

[PATCH 2/7] platform/chrome: Fix typo 'perod' in comment

[Kuan-Wei Chiu]

Replace 'porod' with 'period' in the comment.

Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
 drivers/platform/chrome/cros_ec_sensorhub_ring.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/drivers/platform/chrome/cros_ec_sensorhub_ring.c b/drivers/platform/chrome/cros_ec_sensorhub_ring.c
index 568bbb64a389..ee1c3124d31a 100644
--- a/drivers/platform/chrome/cros_ec_sensorhub_ring.c
+++ b/drivers/platform/chrome/cros_ec_sensorhub_ring.c
@@ -701,7 +701,7 @@ cros_ec_sensor_ring_spread_add(struct cros_ec_sensorhub *sensorhub,
  *           last_out -->
  *
  *
- * We spread time for the samples using perod p = (current - TS1)/4.
+ * We spread time for the samples using period p = (current - TS1)/4.
  * between TS1 and TS2: [TS1+p/4, TS1+2p/4, TS1+3p/4, current_timestamp].
  *
  */
-- 
2.25.1

[PATCH 3/7] platform/chrome: Fix typo 'noone' in comment

[Kuan-Wei Chiu]

Replace 'noone' with 'no one' in the comment.

Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
 drivers/platform/chrome/cros_ec_sensorhub_ring.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/drivers/platform/chrome/cros_ec_sensorhub_ring.c b/drivers/platform/chrome/cros_ec_sensorhub_ring.c
index ee1c3124d31a..85764e62cbe4 100644
--- a/drivers/platform/chrome/cros_ec_sensorhub_ring.c
+++ b/drivers/platform/chrome/cros_ec_sensorhub_ring.c
@@ -103,7 +103,7 @@ EXPORT_SYMBOL_GPL(cros_ec_sensorhub_unregister_push_data);
  * @sensorhub: Sensor Hub object
  * @on: true when events are requested.
  *
- * To be called before sleeping or when noone is listening.
+ * To be called before sleeping or when no one is listening.
  * Return: 0 on success, or an error when we can not communicate with the EC.
  *
  */
-- 
2.25.1

[PATCH 4/7] platform/chrome: Fix typo 'lantency' in comment

[Kuan-Wei Chiu]

Replace 'lantency' with 'latency' in the comment.

Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
 drivers/platform/chrome/cros_ec_sensorhub_ring.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/drivers/platform/chrome/cros_ec_sensorhub_ring.c b/drivers/platform/chrome/cros_ec_sensorhub_ring.c
index 85764e62cbe4..92faf701b8f0 100644
--- a/drivers/platform/chrome/cros_ec_sensorhub_ring.c
+++ b/drivers/platform/chrome/cros_ec_sensorhub_ring.c
@@ -176,7 +176,7 @@ static s64 cros_ec_sensor_ring_median(s64 *array, size_t length)
  * While a and b are recorded at accurate times (due to the EC real time
  * nature); c is pretty untrustworthy, even though it's recorded the
  * first thing in ec_irq_handler(). There is a very good change we'll get
- * added lantency due to:
+ * added latency due to:
  *   other irqs
  *   ddrfreq
  *   cpuidle
-- 
2.25.1

[PATCH 5/7] platform/chrome: Fix typo 'kifo' in commet

[Kuan-Wei Chiu]

Replace 'kifo' with 'kfifo' in the comment.

Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
 drivers/platform/chrome/cros_ec_sensorhub_ring.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/drivers/platform/chrome/cros_ec_sensorhub_ring.c b/drivers/platform/chrome/cros_ec_sensorhub_ring.c
index 92faf701b8f0..6c2aa2651e5f 100644
--- a/drivers/platform/chrome/cros_ec_sensorhub_ring.c
+++ b/drivers/platform/chrome/cros_ec_sensorhub_ring.c
@@ -595,7 +595,7 @@ cros_ec_sensor_ring_spread_add(struct cros_ec_sensorhub *sensorhub,
 			} else {
 				/*
 				 * Push first sample in the batch to the,
-				 * kifo, it's guaranteed to be correct, the
+				 * kfifo, it's guaranteed to be correct, the
 				 * rest will follow later on.
 				 */
 				sample_idx = 1;
-- 
2.25.1

[PATCH 6/7] platform/chrome: Fix typo 'change' in comment

[Kuan-Wei Chiu]

Replace 'change' with 'chance' in the comment.

Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
 drivers/platform/chrome/cros_ec_sensorhub_ring.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/drivers/platform/chrome/cros_ec_sensorhub_ring.c b/drivers/platform/chrome/cros_ec_sensorhub_ring.c
index 6c2aa2651e5f..9e17f7483ca0 100644
--- a/drivers/platform/chrome/cros_ec_sensorhub_ring.c
+++ b/drivers/platform/chrome/cros_ec_sensorhub_ring.c
@@ -175,7 +175,7 @@ static s64 cros_ec_sensor_ring_median(s64 *array, size_t length)
  *
  * While a and b are recorded at accurate times (due to the EC real time
  * nature); c is pretty untrustworthy, even though it's recorded the
- * first thing in ec_irq_handler(). There is a very good change we'll get
+ * first thing in ec_irq_handler(). There is a very good chance we'll get
  * added latency due to:
  *   other irqs
  *   ddrfreq
-- 
2.25.1

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

[Kuan-Wei Chiu]

The cros_ec_sensor_ring_median function currently uses an inefficient
sorting algorithm (> O(n)) to find the median of an array. This patch
replaces the sorting approach with the quickselect algorithm, which
achieves an average time complexity of O(n).

The algorithm employs the median-of-three rule to select the pivot,
mitigating worst-case scenarios and reducing the expected number of
necessary comparisons. This strategy enhances the algorithm's
efficiency and ensures a more balanced partitioning.

In the worst case, the runtime of quickselect could regress to O(n^2).
To address this, alternative algorithms like median-of-medians that
can guarantee O(n) even in the worst case. However, due to higher
overhead and increased complexity, quickselect remains a pragmatic
choice for our use case.

Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
 .../platform/chrome/cros_ec_sensorhub_ring.c  | 71 ++++++++++++++-----
 1 file changed, 54 insertions(+), 17 deletions(-)

diff --git a/drivers/platform/chrome/cros_ec_sensorhub_ring.c b/drivers/platform/chrome/cros_ec_sensorhub_ring.c
index 9e17f7483ca0..4ac718be38b0 100644
--- a/drivers/platform/chrome/cros_ec_sensorhub_ring.c
+++ b/drivers/platform/chrome/cros_ec_sensorhub_ring.c
@@ -133,33 +133,70 @@ int cros_ec_sensorhub_ring_fifo_enable(struct cros_ec_sensorhub *sensorhub,
 	return ret;
 }
 
-static int cros_ec_sensor_ring_median_cmp(const void *pv1, const void *pv2)
+static void cros_ec_sensor_ring_median_swap(s64 *a, s64 *b)
 {
-	s64 v1 = *(s64 *)pv1;
-	s64 v2 = *(s64 *)pv2;
-
-	if (v1 > v2)
-		return 1;
-	else if (v1 < v2)
-		return -1;
-	else
-		return 0;
+	s64 tmp = *a;
+	*a = *b;
+	*b = tmp;
 }
 
 /*
  * 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.
  *
- * Warning: the input array gets modified (sorted)!
+ * Warning: the input array gets modified!
  */
 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;
+	int lo = 0;
+	int hi = length - 1;
+
+	while (lo <= hi) {
+		int mid = lo + (hi - lo) / 2;
+		int pivot, pivot_index;
+		int i = lo - 1;
+
+		/* We employ the median-of-three rule to choose the pivot, mitigating
+		 * 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.
+         */
+		if (array[lo] > array[mid])
+			cros_ec_sensor_ring_median_swap(&array[lo],
+							&array[mid]);
+		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]);
+
+		pivot = array[hi];
+
+		for (int j = lo; j < hi; j++)
+			if (array[j] < pivot)
+				cros_ec_sensor_ring_median_swap(&array[++i],
+								&array[j]);
+
+		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;
+	}
+
+	/* Should never reach here. */
+	return -1;
 }
 
 /*
-- 
2.25.1

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

[Tzung-Bi Shih]

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.

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

[Tzung-Bi Shih]

On Fri, Nov 10, 2023 at 02:54:32AM +0800, Kuan-Wei Chiu wrote:
> In addition to the algorithmic improvement, this series includes
> several typo fixes to enhance the overall code quality and maintain
> consistency.

The typo fixes are not necessary to be in the same series.  I would suggest
you separate the typo fixes to "an" (squash them) independent patch.

Please also use more specific prefix (e.g. "platform/chrome: sensorhub: ") to
make the title more clear.

> 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
>  */

Could you also run the micro-benchmark for n = 64[2][3]?

[2] https://elixir.bootlin.com/linux/v6.6/source/include/linux/platform_data/cros_ec_sensorhub.h#L64
[3] https://elixir.bootlin.com/linux/v6.6/source/drivers/platform/chrome/cros_ec_sensorhub_ring.c#L154

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

[Kuan-Wei Chiu]

I apologize for all the foolish mistakes I've made.
I'll separate this patch series into two patches and submit v2 later.

[PATCH v2] platform/chrome: sensorhub: Fix typos

[Kuan-Wei Chiu]

Replace 'preceeds' with 'precedes' in the comment.
Replace 'porod' with 'period' in the comment.
Replace 'noone' with 'no one' in the comment.
Replace 'lantency' with 'latency' in the comment.
Replace 'kifo' with 'kfifo' in the comment.
Replace 'change' with 'chance' in the comment.

Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
v1 -> v2:
 * Separate patch series into two patches.

 drivers/platform/chrome/cros_ec_sensorhub_ring.c | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)

diff --git a/drivers/platform/chrome/cros_ec_sensorhub_ring.c b/drivers/platform/chrome/cros_ec_sensorhub_ring.c
index 71948dade0e2..9e17f7483ca0 100644
--- a/drivers/platform/chrome/cros_ec_sensorhub_ring.c
+++ b/drivers/platform/chrome/cros_ec_sensorhub_ring.c
@@ -103,7 +103,7 @@ EXPORT_SYMBOL_GPL(cros_ec_sensorhub_unregister_push_data);
  * @sensorhub: Sensor Hub object
  * @on: true when events are requested.
  *
- * To be called before sleeping or when noone is listening.
+ * To be called before sleeping or when no one is listening.
  * Return: 0 on success, or an error when we can not communicate with the EC.
  *
  */
@@ -175,8 +175,8 @@ static s64 cros_ec_sensor_ring_median(s64 *array, size_t length)
  *
  * While a and b are recorded at accurate times (due to the EC real time
  * nature); c is pretty untrustworthy, even though it's recorded the
- * first thing in ec_irq_handler(). There is a very good change we'll get
- * added lantency due to:
+ * first thing in ec_irq_handler(). There is a very good chance we'll get
+ * added latency due to:
  *   other irqs
  *   ddrfreq
  *   cpuidle
@@ -511,7 +511,7 @@ cros_ec_sensor_ring_process_event(struct cros_ec_sensorhub *sensorhub,
  *                                 ringbuffer.
  *
  * This is the new spreading code, assumes every sample's timestamp
- * preceeds the sample. Run if tight_timestamps == true.
+ * precedes the sample. Run if tight_timestamps == true.
  *
  * Sometimes the EC receives only one interrupt (hence timestamp) for
  * a batch of samples. Only the first sample will have the correct
@@ -595,7 +595,7 @@ cros_ec_sensor_ring_spread_add(struct cros_ec_sensorhub *sensorhub,
 			} else {
 				/*
 				 * Push first sample in the batch to the,
-				 * kifo, it's guaranteed to be correct, the
+				 * kfifo, it's guaranteed to be correct, the
 				 * rest will follow later on.
 				 */
 				sample_idx = 1;
@@ -701,7 +701,7 @@ cros_ec_sensor_ring_spread_add(struct cros_ec_sensorhub *sensorhub,
  *           last_out -->
  *
  *
- * We spread time for the samples using perod p = (current - TS1)/4.
+ * We spread time for the samples using period p = (current - TS1)/4.
  * between TS1 and TS2: [TS1+p/4, TS1+2p/4, TS1+3p/4, current_timestamp].
  *
  */
-- 
2.25.1

Re: [PATCH v2] platform/chrome: sensorhub: Fix typos

[Randy Dunlap]

On 11/10/23 08:52, Kuan-Wei Chiu wrote:
> Replace 'preceeds' with 'precedes' in the comment.
> Replace 'porod' with 'period' in the comment.
> Replace 'noone' with 'no one' in the comment.
> Replace 'lantency' with 'latency' in the comment.
> Replace 'kifo' with 'kfifo' in the comment.
> Replace 'change' with 'chance' in the comment.
> 
> Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
> ---
> v1 -> v2:
>  * Separate patch series into two patches.
> 
>  drivers/platform/chrome/cros_ec_sensorhub_ring.c | 12 ++++++------
>  1 file changed, 6 insertions(+), 6 deletions(-)
> 

Reviewed-by: Randy Dunlap <rdunlap@infradead.org>

Thanks.

Re: [PATCH v2] platform/chrome: sensorhub: Fix typos

[patchwork-bot+chrome-platform]

Hello:

This patch was applied to chrome-platform/linux.git (for-kernelci)
by Tzung-Bi Shih <tzungbi@kernel.org>:

On Sat, 11 Nov 2023 00:52:39 +0800 you wrote:
> Replace 'preceeds' with 'precedes' in the comment.
> Replace 'porod' with 'period' in the comment.
> Replace 'noone' with 'no one' in the comment.
> Replace 'lantency' with 'latency' in the comment.
> Replace 'kifo' with 'kfifo' in the comment.
> Replace 'change' with 'chance' in the comment.
> 
> [...]

Here is the summary with links:
  - [v2] platform/chrome: sensorhub: Fix typos
    https://git.kernel.org/chrome-platform/c/49e380795414

You are awesome, thank you!
-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html

Re: [PATCH v2] platform/chrome: sensorhub: Fix typos

[patchwork-bot+chrome-platform]

Hello:

This patch was applied to chrome-platform/linux.git (for-next)
by Tzung-Bi Shih <tzungbi@kernel.org>:

On Sat, 11 Nov 2023 00:52:39 +0800 you wrote:
> Replace 'preceeds' with 'precedes' in the comment.
> Replace 'porod' with 'period' in the comment.
> Replace 'noone' with 'no one' in the comment.
> Replace 'lantency' with 'latency' in the comment.
> Replace 'kifo' with 'kfifo' in the comment.
> Replace 'change' with 'chance' in the comment.
> 
> [...]

Here is the summary with links:
  - [v2] platform/chrome: sensorhub: Fix typos
    https://git.kernel.org/chrome-platform/c/49e380795414

You are awesome, thank you!
-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html

[PATCH v2] platform/chrome: sensorhub: Implement quickselect for median calculation

[Kuan-Wei Chiu]

The cros_ec_sensor_ring_median function currently uses an inefficient
sorting algorithm (> O(n)) to find the median of an array. This patch
replaces the sorting approach with the quickselect algorithm, which
achieves an average time complexity of O(n).

The algorithm employs the median-of-three rule to select the pivot,
mitigating worst-case scenarios and reducing the expected number of
necessary comparisons. This strategy enhances the algorithm's
efficiency and ensures a more balanced partitioning.

In the worst case, the runtime of quickselect could regress to O(n^2).
To address this, alternative algorithms like median-of-medians that
can guarantee O(n) even in the worst case. However, due to higher
overhead and increased complexity of implementation, quickselect
remains a pragmatic choice for our use case.

Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
v1 -> v2:
 * Separate patch series into two patches.
 * Modify the microbenchmark[1] to set n=64 and run 10000 repeated times.
 * Enhance coding style and comments.

[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, time_old = 0, time_new = 0;
	const size_t array_length = 64;
	const size_t round = 10000;

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

	for(size_t i = 0; i < round; i++) {
		init_array(arr, array_length, i + 1);
		start = ktime_get();
		median_old = cros_ec_sensor_ring_median(arr, array_length);
		end = ktime_get();
		delta = ktime_us_delta(end, start);
		time_old += delta;

		init_array(arr, array_length, i + 1);
		start = ktime_get();
		median_new = cros_ec_sensor_ring_median_new(arr, array_length);
		end = ktime_get();
		delta = ktime_us_delta(end, start);
		time_new += delta;

		if(median_old != median_new)
			return 1;
	}

	printk(KERN_ALERT "Total time of original function: %lld\n", time_old);
	printk(KERN_ALERT "Total time of new function: %lld\n", time_new);

	kfree(arr);

	/* return 0 on success */
	return 0;
}

/* Result:
 * Total time of original function: 157561
 * Total time of new function: 1480
 */

 .../platform/chrome/cros_ec_sensorhub_ring.c  | 62 ++++++++++++++-----
 1 file changed, 45 insertions(+), 17 deletions(-)

diff --git a/drivers/platform/chrome/cros_ec_sensorhub_ring.c b/drivers/platform/chrome/cros_ec_sensorhub_ring.c
index 9e17f7483ca0..1205219515d6 100644
--- a/drivers/platform/chrome/cros_ec_sensorhub_ring.c
+++ b/drivers/platform/chrome/cros_ec_sensorhub_ring.c
@@ -133,33 +133,61 @@ int cros_ec_sensorhub_ring_fifo_enable(struct cros_ec_sensorhub *sensorhub,
 	return ret;
 }
 
-static int cros_ec_sensor_ring_median_cmp(const void *pv1, const void *pv2)
+static void cros_ec_sensor_ring_median_swap(s64 *a, s64 *b)
 {
-	s64 v1 = *(s64 *)pv1;
-	s64 v2 = *(s64 *)pv2;
-
-	if (v1 > v2)
-		return 1;
-	else if (v1 < v2)
-		return -1;
-	else
-		return 0;
+	s64 tmp = *a;
+	*a = *b;
+	*b = tmp;
 }
 
 /*
  * 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.
  *
- * Warning: the input array gets modified (sorted)!
+ * Warning: the input array gets modified!
  */
 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];
+	int lo = 0;
+	int hi = length - 1;
+
+	while (lo <= hi) {
+		int mid = lo + (hi - lo) / 2;
+		int pivot, i;
+
+		if (array[lo] > array[mid])
+			cros_ec_sensor_ring_median_swap(&array[lo], &array[mid]);
+		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]);
+
+		pivot = array[hi];
+		i = lo - 1;
+
+		for (int j = lo; j < hi; j++)
+			if (array[j] < pivot)
+				cros_ec_sensor_ring_median_swap(&array[++i], &array[j]);
+
+		/* The pivot's index corresponds to i+1. */
+		cros_ec_sensor_ring_median_swap(&array[i + 1], &array[hi]);
+		if (i + 1 == length / 2)
+			return array[i + 1];
+		if (i + 1 > length / 2)
+			hi = i;
+		else
+			lo = i + 2;
+	}
+
+	/* Should never reach here. */
+	return -1;
 }
 
 /*
-- 
2.25.1

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

[patchwork-bot+chrome-platform]

Hello:

This patch was applied to chrome-platform/linux.git (for-kernelci)
by Tzung-Bi Shih <tzungbi@kernel.org>:

On Sat, 11 Nov 2023 00:53:14 +0800 you wrote:
> The cros_ec_sensor_ring_median function currently uses an inefficient
> sorting algorithm (> O(n)) to find the median of an array. This patch
> replaces the sorting approach with the quickselect algorithm, which
> achieves an average time complexity of O(n).
> 
> The algorithm employs the median-of-three rule to select the pivot,
> mitigating worst-case scenarios and reducing the expected number of
> necessary comparisons. This strategy enhances the algorithm's
> efficiency and ensures a more balanced partitioning.
> 
> [...]

Here is the summary with links:
  - [v2] platform/chrome: sensorhub: Implement quickselect for median calculation
    https://git.kernel.org/chrome-platform/c/d131f1f3b459

You are awesome, thank you!
-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html

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

[patchwork-bot+chrome-platform]

Hello:

This patch was applied to chrome-platform/linux.git (for-next)
by Tzung-Bi Shih <tzungbi@kernel.org>:

On Sat, 11 Nov 2023 00:53:14 +0800 you wrote:
> The cros_ec_sensor_ring_median function currently uses an inefficient
> sorting algorithm (> O(n)) to find the median of an array. This patch
> replaces the sorting approach with the quickselect algorithm, which
> achieves an average time complexity of O(n).
> 
> The algorithm employs the median-of-three rule to select the pivot,
> mitigating worst-case scenarios and reducing the expected number of
> necessary comparisons. This strategy enhances the algorithm's
> efficiency and ensures a more balanced partitioning.
> 
> [...]

Here is the summary with links:
  - [v2] platform/chrome: sensorhub: Implement quickselect for median calculation
    https://git.kernel.org/chrome-platform/c/d131f1f3b459

You are awesome, thank you!
-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html