diff options
| author | Kuan-Wei Chiu <visitorckw@gmail.com> | 2024-01-10 16:12:12 +0800 |
|---|---|---|
| committer | Andrew Morton <akpm@linux-foundation.org> | 2024-02-22 15:38:51 -0800 |
| commit | c499c717ee7cc07f47d7ee38a1791a58dcf1d4eb (patch) | |
| tree | 2b58964167d3fd4d0ee2c40949b4ad884827281c /include/linux/min_heap.h | |
| parent | b73aa539a7789d2366aa7ffa627cede77d6f1c4e (diff) | |
lib min_heap: optimize number of calls to min_heapify()
Patch series "lib min_heap: Min heap optimizations".
The purpose of this patch series is to enhance the existing min heap
implementation. The optimization focuses on both the heap construction
process and the number of comparisons made during the heapify operation.
This patch (of 2):
Improve the heap construction process by reducing unnecessary heapify
operations. Specifically, adjust the starting condition from n / 2 to n /
2 - 1 in the loop that iterates over all non-leaf elements.
Link: https://lkml.kernel.org/r/20240110081213.2289636-1-visitorckw@gmail.com
Link: https://lkml.kernel.org/r/20240110081213.2289636-2-visitorckw@gmail.com
Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
Acked-by: Ian Rogers <irogers@google.com>
Cc: Adrian Hunter <adrian.hunter@intel.com>
Cc: Alexander Shishkin <alexander.shishkin@linux.intel.com>
Cc: Arnaldo Carvalho de Melo <acme@kernel.org>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: Jiri Olsa <jolsa@kernel.org>
Cc: Mark Rutland <mark.rutland@arm.com>
Cc: Namhyung Kim <namhyung@kernel.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Diffstat (limited to 'include/linux/min_heap.h')
| -rw-r--r-- | include/linux/min_heap.h | 2 |
1 files changed, 1 insertions, 1 deletions
diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index 44077837385f..18a581310eb3 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -70,7 +70,7 @@ void min_heapify_all(struct min_heap *heap, { int i; - for (i = heap->nr / 2; i >= 0; i--) + for (i = heap->nr / 2 - 1; i >= 0; i--) min_heapify(heap, i, func); } |