.../platform/chrome/cros_ec_sensorhub_ring.c | 83 ++++++++++++++----- 1 file changed, 60 insertions(+), 23 deletions(-)
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
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
I apologize for all the foolish mistakes I've made. I'll separate this patch series into two patches and submit v2 later.
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.1Hello:
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
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
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.1Hello:
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
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
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.
© 2016 - 2025 Red Hat, Inc.