From nobody Fri Dec 26 05:27:31 2025 Received: from mail-pl1-f179.google.com (mail-pl1-f179.google.com [209.85.214.179]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 6E2F73EA82; Wed, 10 Jan 2024 08:12:25 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="ESMH/sf+" Received: by mail-pl1-f179.google.com with SMTP id d9443c01a7336-1d54c7ef801so5020485ad.0; Wed, 10 Jan 2024 00:12:25 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1704874345; x=1705479145; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=fdLU/U7TSYkmEg20IDPG1xvAMQzbpbdvIaAXCBEqQ4o=; b=ESMH/sf+RRHlA+5aajuRYZ+nuZJWG0bq1S+YEuOMK63urN75ziuzteS+3elYqhCW1C +wUG1K5Wn4zjw3HoMGueYDM6sKsrmCtYKFWkuWyMtRvi0gec3BLQ053QiZGw9vHzlLbN 0b+drW9S59v1RkF9JgnLn1E2kaBPYj2udNtAq7Ikl0Ifjwn0kkLhRCYvojfv6IEduSmZ qgC4eT3hMLQfiK51Tr1kUnrX+xuuTwsQfaH3nHn0ofxzd/Q0i+rrEqC06dQFxQM5qugX 5o6y0eO3u9Q+znoiP2qS7Vp+WTXABRCD0gugmR1DuplF9Rs+J66w7/XPL06KZmZY69lU KoiA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1704874345; x=1705479145; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=fdLU/U7TSYkmEg20IDPG1xvAMQzbpbdvIaAXCBEqQ4o=; b=OIRT+0iNnJfgHX5tm+Xb49WoFB3zdyGsEaaTwucQs2AZu2SznpbA6Wrx3GxPo+yW0t XF+lR1z8uaFrLigqfJ+SjzjIiko5sGbomImnGkX/2SL5JGzYOxcx2KPSyLsJhupnkdkq KgDd0wqN4IHqk/ZVxfiX0Ncz9P9+18wVYkbxMs5ugQfCPOpWWrxSOm0P3bCwRcVLdfFQ 5OtPjNZ09oxUwuKpFq6R5pPtbMtTh3xkyr4cRqW60WxSNV9ugTnCvf1sFYoSxTOrjZXV rADHpEcXsvwapL7jrRguvXnEKg9dno7w/tLu8ALMCnZGWzgewKqjWoHhNrPxdm5xtmlr iXTQ== X-Gm-Message-State: AOJu0YzwNMAKYi8HXgnu2tyacUDiBCxqZN9gc7bl00Jt/D7Ac5v+Lgod Fp8hesCTu46jJwTqOF2jhgE= X-Google-Smtp-Source: AGHT+IGhot4iwi3m1yLqxzOhmtU6B0eeF2Q4Mt3OnQKrQybwteCJEtqqeNLgCiiTVHFo9tCuL/z6mA== X-Received: by 2002:a17:902:d50e:b0:1d4:e665:c54f with SMTP id b14-20020a170902d50e00b001d4e665c54fmr1172366plg.6.1704874344734; Wed, 10 Jan 2024 00:12:24 -0800 (PST) Received: from localhost.localdomain ([140.116.154.65]) by smtp.gmail.com with ESMTPSA id c12-20020a170902b68c00b001cf51972586sm3044243pls.292.2024.01.10.00.12.20 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 10 Jan 2024 00:12:24 -0800 (PST) From: Kuan-Wei Chiu To: akpm@linux-foundation.org Cc: peterz@infradead.org, mingo@redhat.com, acme@kernel.org, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, namhyung@kernel.org, irogers@google.com, adrian.hunter@intel.com, linux-perf-users@vger.kernel.org, linux-kernel@vger.kernel.org, Kuan-Wei Chiu Subject: [RESEND PATCH v2 1/2] lib min_heap: Optimize number of calls to min_heapify() Date: Wed, 10 Jan 2024 16:12:12 +0800 Message-Id: <20240110081213.2289636-2-visitorckw@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20240110081213.2289636-1-visitorckw@gmail.com> References: <20240110081213.2289636-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" 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. Signed-off-by: Kuan-Wei Chiu --- include/linux/min_heap.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) 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; =20 - for (i =3D heap->nr / 2; i >=3D 0; i--) + for (i =3D heap->nr / 2 - 1; i >=3D 0; i--) min_heapify(heap, i, func); } =20 --=20 2.25.1 From nobody Fri Dec 26 05:27:31 2025 Received: from mail-pl1-f170.google.com (mail-pl1-f170.google.com [209.85.214.170]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 69E863EA82; Wed, 10 Jan 2024 08:12:30 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="bVeMmdAa" Received: by mail-pl1-f170.google.com with SMTP id d9443c01a7336-1d3b84173feso7686205ad.1; Wed, 10 Jan 2024 00:12:30 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1704874349; x=1705479149; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=iYaz82mYYzCwX1xxNWNg9eztYs/P62dbK5BPPUgSW7A=; b=bVeMmdAa/ZnF9uxmuvX0BQN6P9WSbE46OShI8wg4e4R5wFZBJUyXohtUnHb5iks8/o YbW8wxO9xnA5N+A6FhJK4OTtj6YQtX9VvfstnIJY+kli1XVUUCONHtPSrou7nqK3AyVO xKotmeXzgWAvpX7rUO8E7exlnwAe5OIQLBzFUgifq5Cq6DSxd9Mw0gUv2u1fibB2ygw0 uLlUuHifuf+/anVaG4TrmGGdW/bQoawdVwi3ME+I+nKya+IWKjJgoJ6AJRHP3W6IGwzS sIzbrU10XwkuOcLpa/Zv6EJIOeY2lQsQ9yXdDlYKkVwkcSzZwFUm/qKP5JD9ENCr2yN/ QOWQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1704874349; x=1705479149; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=iYaz82mYYzCwX1xxNWNg9eztYs/P62dbK5BPPUgSW7A=; b=RmShWWfO9gAz9ylv6DUkNVFS3SB9wSfyN11ZT/0Sx4Nqko6dWW64UJisU2eFSltSZe KTjX4CMw0nOeEu4qRKrvXyr109AqcHVSaUANYpyqK7BdXKhmEKeMdALtCwAm2x84sPE0 x2TPmpmvaY0QHQmAauT7VAjvT1cZPBms73WC9Ccb3P1YzfE/+5srmHZEJHRdwN765avQ bNdr8zSAjOJfMm+1PukPmiSWoZf+8hsg4N5gvR7dQsoMHyLMQTG63wJnCcnsJSdnMwvz 5dX4OQG2IfkXpFLC/HLPfQAESYvE+8hT3HN89QxQfJOYNghHbCAEJ6dCOeqWs6LUpMZl ixAg== X-Gm-Message-State: AOJu0YzmIGf1nGOV0doTdS7PBh7L0u3idgat8J1FjGDFuOFlj6dBNZqM nLF4N4YRheFfIylYWB91B20= X-Google-Smtp-Source: AGHT+IHpdXji4t0wxJVbSPH8Z2/slBHqUAFGgIFZITd1/McXsQZu63Yz4Pa307KIahaW3bvcuHPVrw== X-Received: by 2002:a17:902:9a90:b0:1d4:e308:d6fb with SMTP id w16-20020a1709029a9000b001d4e308d6fbmr1207351plp.5.1704874349630; Wed, 10 Jan 2024 00:12:29 -0800 (PST) Received: from localhost.localdomain ([140.116.154.65]) by smtp.gmail.com with ESMTPSA id c12-20020a170902b68c00b001cf51972586sm3044243pls.292.2024.01.10.00.12.26 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 10 Jan 2024 00:12:29 -0800 (PST) From: Kuan-Wei Chiu To: akpm@linux-foundation.org Cc: peterz@infradead.org, mingo@redhat.com, acme@kernel.org, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, namhyung@kernel.org, irogers@google.com, adrian.hunter@intel.com, linux-perf-users@vger.kernel.org, linux-kernel@vger.kernel.org, Kuan-Wei Chiu Subject: [RESEND PATCH v2 2/2] lib min_heap: Optimize number of comparisons in min_heapify() Date: Wed, 10 Jan 2024 16:12:13 +0800 Message-Id: <20240110081213.2289636-3-visitorckw@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20240110081213.2289636-1-visitorckw@gmail.com> References: <20240110081213.2289636-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Optimize the min_heapify() function, resulting in a significant reduction of approximately 50% in the number of comparisons for large random inputs, while maintaining identical results. The current implementation performs two comparisons per level to identify the minimum among three elements. In contrast, the proposed bottom-up variation uses only one comparison per level to assess two children until reaching the leaves. Then, it sifts up until the correct position is determined. Typically, the process of sifting down proceeds to the leaf level, resulting in O(1) secondary comparisons instead of log2(n). This optimization significantly reduces the number of costly indirect function calls and improves overall performance. Signed-off-by: Kuan-Wei Chiu --- include/linux/min_heap.h | 42 +++++++++++++++++++++------------------- 1 file changed, 22 insertions(+), 20 deletions(-) diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index 18a581310eb3..d52daf45861b 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -35,31 +35,33 @@ static __always_inline void min_heapify(struct min_heap *heap, int pos, const struct min_heap_callbacks *func) { - void *left, *right, *parent, *smallest; + void *left, *right; void *data =3D heap->data; + void *root =3D data + pos * func->elem_size; + int i =3D pos, j; =20 + /* Find the sift-down path all the way to the leaves. */ for (;;) { - if (pos * 2 + 1 >=3D heap->nr) + if (i * 2 + 2 >=3D heap->nr) break; + left =3D data + (i * 2 + 1) * func->elem_size; + right =3D data + (i * 2 + 2) * func->elem_size; + i =3D func->less(left, right) ? i * 2 + 1 : i * 2 + 2; + } =20 - left =3D data + ((pos * 2 + 1) * func->elem_size); - parent =3D data + (pos * func->elem_size); - smallest =3D parent; - if (func->less(left, smallest)) - smallest =3D left; - - if (pos * 2 + 2 < heap->nr) { - right =3D data + ((pos * 2 + 2) * func->elem_size); - if (func->less(right, smallest)) - smallest =3D right; - } - if (smallest =3D=3D parent) - break; - func->swp(smallest, parent); - if (smallest =3D=3D left) - pos =3D (pos * 2) + 1; - else - pos =3D (pos * 2) + 2; + /* Special case for the last leaf with no sibling. */ + if (i * 2 + 2 =3D=3D heap->nr) + i =3D i * 2 + 1; + + /* Backtrack to the correct location. */ + while (i !=3D pos && func->less(root, data + i * func->elem_size)) + i =3D (i - 1) / 2; + + /* Shift the element into its correct place. */ + j =3D i; + while (i !=3D pos) { + i =3D (i - 1) / 2; + func->swp(data + i * func->elem_size, data + j * func->elem_size); } } =20 --=20 2.25.1