Skip to contentSkip to conversation

platform/chrome: Implement quickselect for median calculation

PATCH Superseded Kuan-Wei Chiu 4 participants 18 messages Nov 9, 2023 – Nov 14, 2023

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

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

--

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(-)
Signature · 1 line
2.25.1
#1 lore raw

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

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

---
 drivers/platform/chrome/cros_ec_sensorhub_ring.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
drivers/platform/chrome/cros_ec_sensorhub_ring.c +1 -1
index 71948dade0e2..568bbb64a389 100644
@@ -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
Signature · 1 line
2.25.1
#2 lore raw

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

In reply to Kuan-Wei Chiu

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

---
 drivers/platform/chrome/cros_ec_sensorhub_ring.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
drivers/platform/chrome/cros_ec_sensorhub_ring.c +1 -1
index 568bbb64a389..ee1c3124d31a 100644
@@ -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].
  *
  */
Signature · 1 line
2.25.1
#3 lore raw

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

In reply to Kuan-Wei Chiu

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

---
 drivers/platform/chrome/cros_ec_sensorhub_ring.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
drivers/platform/chrome/cros_ec_sensorhub_ring.c +1 -1
index ee1c3124d31a..85764e62cbe4 100644
@@ -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.
  *
  */
Signature · 1 line
2.25.1
#4 lore raw

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

In reply to Kuan-Wei Chiu

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

---
 drivers/platform/chrome/cros_ec_sensorhub_ring.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
drivers/platform/chrome/cros_ec_sensorhub_ring.c +1 -1
index 85764e62cbe4..92faf701b8f0 100644
@@ -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
Signature · 1 line
2.25.1
#5 lore raw

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

In reply to Kuan-Wei Chiu

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

---
 drivers/platform/chrome/cros_ec_sensorhub_ring.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
drivers/platform/chrome/cros_ec_sensorhub_ring.c +1 -1
index 92faf701b8f0..6c2aa2651e5f 100644
@@ -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;
Signature · 1 line
2.25.1
#6 lore raw

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

In reply to Kuan-Wei Chiu

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

---
 drivers/platform/chrome/cros_ec_sensorhub_ring.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
drivers/platform/chrome/cros_ec_sensorhub_ring.c +1 -1
index 6c2aa2651e5f..9e17f7483ca0 100644
@@ -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
Signature · 1 line
2.25.1
#7 lore raw

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

In reply to 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.

---
 .../platform/chrome/cros_ec_sensorhub_ring.c  | 71 ++++++++++++++-----
 1 file changed, 54 insertions(+), 17 deletions(-)
drivers/platform/chrome/cros_ec_sensorhub_ring.c +54 -17
index 9e17f7483ca0..4ac718be38b0 100644
@@ -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;
 }
 
 /*
Signature · 1 line
2.25.1
maintainer
#8 lore raw
Quoted 6 lines · Kuan-Wei Chiu

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

Quoted 8 lines

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

drivers/platform/chrome/cros_ec_sensorhub_ring.c int cros_ec_sensorhub_ring_fifo_enable(struct cros_ec_sensorhub *sensorhub, · line 158

Quoted 5 lines

static s64 cros_ec_sensor_ring_median(s64 *array, size_t length) {

drivers/platform/chrome/cros_ec_sensorhub_ring.c +1 -2
-	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.

drivers/platform/chrome/cros_ec_sensorhub_ring.c int cros_ec_sensorhub_ring_fifo_enable(struct cros_ec_sensorhub *sensorhub, · line 165

Quoted 7 lines
drivers/platform/chrome/cros_ec_sensorhub_ring.c +7 -0
+	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).

Review

Quoted 2 lines
(quoted diff) +2 -0
+
+		/* We employ the median-of-three rule to choose the pivot, mitigating

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

drivers/platform/chrome/cros_ec_sensorhub_ring.c int cros_ec_sensorhub_ring_fifo_enable(struct cros_ec_sensorhub *sensorhub, · line 171

Quoted 4 lines
drivers/platform/chrome/cros_ec_sensorhub_ring.c +4 -0
+		 * 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:
+         */$

drivers/platform/chrome/cros_ec_sensorhub_ring.c int cros_ec_sensorhub_ring_fifo_enable(struct cros_ec_sensorhub *sensorhub, · line 174

Quoted 3 lines
drivers/platform/chrome/cros_ec_sensorhub_ring.c +3 -0
+		if (array[lo] > array[mid])
+			cros_ec_sensor_ring_median_swap(&array[lo],
+							&array[mid]);

It can fit into 100-column.

drivers/platform/chrome/cros_ec_sensorhub_ring.c int cros_ec_sensorhub_ring_fifo_enable(struct cros_ec_sensorhub *sensorhub, · line 179

Quoted 5 lines
drivers/platform/chrome/cros_ec_sensorhub_ring.c +5 -0
+		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.

drivers/platform/chrome/cros_ec_sensorhub_ring.c int cros_ec_sensorhub_ring_fifo_enable(struct cros_ec_sensorhub *sensorhub, · line 186

Quoted 7 lines
drivers/platform/chrome/cros_ec_sensorhub_ring.c +7 -0
+
+		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.

drivers/platform/chrome/cros_ec_sensorhub_ring.c int cros_ec_sensorhub_ring_fifo_enable(struct cros_ec_sensorhub *sensorhub, · line 195

Quoted 8 lines
drivers/platform/chrome/cros_ec_sensorhub_ring.c +8 -0
+		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.

maintainer
#9 lore raw
In reply to Kuan-Wei Chiu
Quoted 3 lines · Kuan-Wei Chiu

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.

Quoted 33 lines

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;
}
Quoted 4 lines

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

#10 lore raw

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

#11 lore raw

PATCH v2 1/1 platform/chrome: sensorhub: Fix typos

In reply to Tzung-Bi Shih

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.

---
v1 -> v2:
* Separate patch series into two patches.

 drivers/platform/chrome/cros_ec_sensorhub_ring.c | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)
drivers/platform/chrome/cros_ec_sensorhub_ring.c +6 -6
index 71948dade0e2..9e17f7483ca0 100644
@@ -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].
  *
  */
Signature · 1 line
2.25.1
Reviewed-by on v2 1/1
#12 lore raw

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

Quoted 7 lines · 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.

Quoted 8 lines

---
v1 -> v2:
* Separate patch series into two patches.

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

Thanks.

#13 lore raw

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

In reply to Kuan-Wei Chiu
This patch was applied to chrome-platform/linux.git (for-kernelci) by Tzung-Bi Shih <[email protected]>:

Hello:

This patch was applied to chrome-platform/linux.git (for-kernelci) by Tzung-Bi Shih <[email protected]>:

Quoted 8 lines · 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!

Signature · 2 lines
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html
#14 lore raw

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

In reply to Kuan-Wei Chiu
This patch was applied to chrome-platform/linux.git (for-next) by Tzung-Bi Shih <[email protected]>:

Hello:

This patch was applied to chrome-platform/linux.git (for-next) by Tzung-Bi Shih <[email protected]>:

Quoted 8 lines · 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!

Signature · 2 lines
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html
#15 lore raw

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

In reply to Tzung-Bi Shih

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.

---
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(-)
drivers/platform/chrome/cros_ec_sensorhub_ring.c +45 -17
index 9e17f7483ca0..1205219515d6 100644
@@ -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;
 }
 
 /*
Signature · 1 line
2.25.1
#16 lore raw

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

This patch was applied to chrome-platform/linux.git (for-kernelci) by Tzung-Bi Shih <[email protected]>:

Hello:

This patch was applied to chrome-platform/linux.git (for-kernelci) by Tzung-Bi Shih <[email protected]>:

Quoted 11 lines · 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!

Signature · 2 lines
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html
#17 lore raw

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

In reply to Kuan-Wei Chiu
This patch was applied to chrome-platform/linux.git (for-next) by Tzung-Bi Shih <[email protected]>:

Hello:

This patch was applied to chrome-platform/linux.git (for-next) by Tzung-Bi Shih <[email protected]>:

Quoted 11 lines · 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!

Signature · 2 lines
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html