lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
Open Source and information security mailing list archives
| ||
|
Message-Id: <20250610215516.1513296-8-visitorckw@gmail.com> Date: Wed, 11 Jun 2025 05:55:15 +0800 From: Kuan-Wei Chiu <visitorckw@...il.com> To: corbet@....net, colyli@...nel.org, kent.overstreet@...ux.dev, akpm@...ux-foundation.org, robertpang@...gle.com Cc: linux-kernel@...r.kernel.org, linux-doc@...r.kernel.org, linux-bcache@...r.kernel.org, jserv@...s.ncku.edu.tw, Kuan-Wei Chiu <visitorckw@...il.com>, stable@...r.kernel.org Subject: [PATCH 7/8] Documentation/core-api: min_heap: Document _eqaware variants of min-heap APIs Add documentation for equality-aware variants of min-heap maintenance functions, which use a top-down sift_down strategy. These variants, suffixed with _eqaware, reduce the number of comparisons to O(1) in workloads with many elements of equal priority and can be used as drop-in replacements for their standard counterparts. Cc: stable@...r.kernel.org # 6.11+ Signed-off-by: Kuan-Wei Chiu <visitorckw@...il.com> --- Documentation/core-api/min_heap.rst | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) diff --git a/Documentation/core-api/min_heap.rst b/Documentation/core-api/min_heap.rst index 9f57766581df..012c82038b46 100644 --- a/Documentation/core-api/min_heap.rst +++ b/Documentation/core-api/min_heap.rst @@ -30,6 +30,26 @@ more expensive. As with the non-inline versions, it is important to use the macro wrappers for inline functions instead of directly calling the functions themselves. +Equality-Aware Heap Maintenance +------------------------------- + +In some workloads, a large number of elements in the heap may be equal under +the user-defined comparison function. For such cases, the standard +``min_heap_sift_down()`` implementation, which uses the bottom-up heapify +strategy, can be inefficient. While bottom-up heapify reduces the number of +comparisons by approximately 50% for randomly ordered data, it may perform up +to :math:`2 \times \log_2(n)` comparisons in the presence of many equal +elements. + +To address this, equality-aware versions of heap maintenance APIs are provided. +These versions use the traditional top-down heapify strategy, which performs +better - sometimes requiring only :math:`\mathcal{O}(1)` comparisons - when +many elements are equal. + +The equality-aware APIs are suffixed with ``_eqaware``, and serve as drop-in +replacements for their standard counterparts when equal elements are expected. + + Data Structures =============== -- 2.34.1
Powered by blists - more mailing lists