platform/chrome: Implement quickselect for median calculation
Subsystems (2)
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
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
@@ -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
PATCH 2/7 platform/chrome: Fix typo 'perod' in comment
In reply to Kuan-Wei ChiuReplace '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
@@ -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
PATCH 3/7 platform/chrome: Fix typo 'noone' in comment
In reply to Kuan-Wei ChiuReplace '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
@@ -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
PATCH 4/7 platform/chrome: Fix typo 'lantency' in comment
In reply to Kuan-Wei ChiuReplace '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
@@ -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
PATCH 5/7 platform/chrome: Fix typo 'kifo' in commet
In reply to Kuan-Wei ChiuReplace '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
@@ -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
PATCH 6/7 platform/chrome: Fix typo 'change' in comment
In reply to Kuan-Wei ChiuReplace '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
@@ -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
PATCH 7/7 platform/chrome: Implement quickselect for median calculation
In reply to Kuan-Wei ChiuThe 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
@@ -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
Tzung-Bi Shih
maintainerQuoted 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.
Tzung-Bi Shih
maintainerQuoted 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
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 1/1 platform/chrome: sensorhub: Fix typos
In reply to Tzung-Bi ShihReplace '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
@@ -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
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
Signed-off-by Kuan-Wei Chiu <[email protected]>---
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.
Re: [PATCH v2] platform/chrome: sensorhub: Fix typos
In reply to Kuan-Wei ChiuThis 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
Re: [PATCH v2] platform/chrome: sensorhub: Fix typos
In reply to Kuan-Wei ChiuThis 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
PATCH v2 1/1 platform/chrome: sensorhub: Implement quickselect for median calculation
In reply to Tzung-Bi ShihThe 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
@@ -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
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_medianfunction 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
Re: [PATCH v2] platform/chrome: sensorhub: Implement quickselect for median calculation
In reply to Kuan-Wei ChiuThis 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_medianfunction 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