linux-kernel - [PATCH 7/8] Documentation/core-api: min_heap: Document

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

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

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