| Message ID | 20231109185439.1535962-1-visitorckw@gmail.com (mailing list archive) |
|---|---|
| Headers | show |
| Series | platform/chrome: Implement quickselect for median calculation | expand |
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.
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(-)