From nobody Fri Feb 13 11:47:40 2026 Received: from mail-pf1-f173.google.com (mail-pf1-f173.google.com [209.85.210.173]) (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 0011B161301 for ; Mon, 27 May 2024 20:30:19 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.173 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716841821; cv=none; b=MkpACqHqS+kG9Q3iWcS6208CZhYQ8cAYES+4kNwIJLwvucYHipoRF7uE0CFubhBLRz01c0eWCWUrdr/y6gDKcTbfPv543P5s+KfBJscJfdQ1NStSyuoxEmuBQdMCuwxaKt08isDYw7V+bA1TD3vByKJQ+VQNxUJ74eh1B8qjyM4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716841821; c=relaxed/simple; bh=6AvePvddep+UiANmWmMBWS7SEkWIUQ1bJKkudQIKeT0=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=KjsIOS1rfLUgUSUgNh/juG+ZkiB4TNNzpVZ83aY3TM1WWKZ52/KF6f3HyIO4/cRHqaRvzFNAw8y8POg9AR+ucaIdtQDDjsZTEUP8uupSnKMwFRUyqQ8sJLcN5BQKDAfqIoY2nR24/gFIPP2uOYZ9GDih4hzamfQsN7neVUZ5Xu8= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=du4/i/TF; arc=none smtp.client-ip=209.85.210.173 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="du4/i/TF" Received: by mail-pf1-f173.google.com with SMTP id d2e1a72fcca58-6f8ec1a4fb3so2109b3a.3 for ; Mon, 27 May 2024 13:30:19 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1716841819; x=1717446619; 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=RSyU+GhS3C1q4ZjPz7YWQnRjryhy+q7kVdtg3o+JGS0=; b=du4/i/TFrmELLnxUnRH79orgbLyRl7hBq8viJkHpqlpW2j3HfoJRUA7MtFpw8EHSYW WrBQaeMOYI9Ewfej1G8YfYaQp9v/cW8fRZfQTyNyfhxsH9JdU1AmHtym6Z/QshzCW/xd 7jqUgfBAQ2RO9T4Xh0CKforUEcgsWkXS4uXWvpioJqbe640aezC2KaygLxWO8I4dbDHk QGg7HofFQOpqsHNqNpTgLKlZgsyzBtqhQR5GP3mZvg/m4Wxrd+XdeXTJH5Fmr5nEGJt7 e36+AGXvDIst7w9A7YuMbgyk9whKT4z+0MKXN9qpVBKXUHanrDJm9taokprtB2V2/Pnz EcKA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1716841819; x=1717446619; 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=RSyU+GhS3C1q4ZjPz7YWQnRjryhy+q7kVdtg3o+JGS0=; b=WaKeNSr3IuwN7+trANUXuvoF8EQCSMKB3EI4VyLSCp+x1DgUFzF5mSj+yiYl+0CJsU 7enHpuloyU7QHjXjeEGqy7r+huG793hVib/6tlX4xm8fPmAjG93dc4dCgnNqTE0d5P5z 2trdPcp7LtYYlcJMxxO8xh6pYtZjrYp7gCbZVCoZkCoEna0/MUXrYoAnVWWYJCgKl8R9 /thsi+o+0jh20bcJTMrEenC5kiNkjsvv4RtoeYxb1a+y/w5jBYLALwR4M8HOhtjmKKEX z3WaTdC9iy0Lz4oPskrstgSNUEHfcbBE9wJij592LqiI+53r6L/tiRBlBN2UAMKkkHRd 4Uiw== X-Forwarded-Encrypted: i=1; AJvYcCXFNMtnX+TccmMNfOSVYNny9lecq/AAO5tJ28FhID6TjDvUn3HyXDHGIhdQqhLVYcb0tIpGwUCPTjC/QRzlxdkLueutml2saXpfTG6y X-Gm-Message-State: AOJu0Yymgm+5vA6STFy0Pawo+stTDGCoLNF1J73UYzdJLjEVb2bmsHXL A3yEItnBkjW8+ueSnPlt7nm6jd2/3X+uPUp9mb93YiUm11qXmlDC X-Google-Smtp-Source: AGHT+IFAvP1jE8ZmjP699QD1DAnNNLCklYHn4LKspc4oObBHAAA8qbTvDoqBCEfPEGeXn1RSJbj2zg== X-Received: by 2002:a05:6a20:1054:b0:1af:cf0c:95aa with SMTP id adf61e73a8af0-1b212ce3f7fmr10155297637.2.1716841819017; Mon, 27 May 2024 13:30:19 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 41be03b00d2f7-6822092a678sm5324279a12.11.2024.05.27.13.30.17 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 27 May 2024 13:30:18 -0700 (PDT) From: Kuan-Wei Chiu To: akpm@linux-foundation.org Cc: jserv@ccns.ncku.edu.tw, linux-kernel@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH 1/4] lib/sort: Remove unused pr_fmt macro Date: Tue, 28 May 2024 04:30:08 +0800 Message-Id: <20240527203011.1644280-2-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240527203011.1644280-1-visitorckw@gmail.com> References: <20240527203011.1644280-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" The pr_fmt macro is defined but not used in lib/sort.c. Since there are no pr_* functions printing any messages, the pr_fmt macro is redundant and can be safely removed. Signed-off-by: Kuan-Wei Chiu --- lib/sort.c | 2 -- 1 file changed, 2 deletions(-) diff --git a/lib/sort.c b/lib/sort.c index a0509088f82a..651b73205f6d 100644 --- a/lib/sort.c +++ b/lib/sort.c @@ -10,8 +10,6 @@ * quicksort's O(n^2) worst case. */ =20 -#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt - #include #include #include --=20 2.34.1 From nobody Fri Feb 13 11:47:40 2026 Received: from mail-il1-f173.google.com (mail-il1-f173.google.com [209.85.166.173]) (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 AEAA216133E for ; Mon, 27 May 2024 20:30:22 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.166.173 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716841824; cv=none; b=ndiy7L1mhK99HCKy8lqomfHQ2aRTcRTl1oc/OCG5wQh1qEqXMQDIzqD2ka/c+6igP3cQndsYJoWkQxWLtIWTy4GAHMaptR/sb8f0RGzEHW8kFEWqSN0zIrlkZtqABIsHZ5KH/7IUTSznyzVTRYYNOQPSmHWuSrg6xPFzyL4oG4Y= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716841824; c=relaxed/simple; bh=miz7CyMIADUVHaJwVFLRC9ZGG4NWk6IFWm7j6D/ics0=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=apTqPl9crRu4tLXXGBTjJMgBUWlA572EUfs21RXnm+cb7BW0XcOZ8+6j75Oslc5G/i7GENmAJ/LjGvsASGGsGpb1QKLISvEvIzilbnC8HVPUXrexzuLHMcm+7DekMti4Gv5I7LTSyHh48gOKjSP3GyHLO02zig2iryKViSCFzQQ= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=lZv07vSk; arc=none smtp.client-ip=209.85.166.173 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="lZv07vSk" Received: by mail-il1-f173.google.com with SMTP id e9e14a558f8ab-36daacdbf21so59635ab.2 for ; Mon, 27 May 2024 13:30:22 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1716841822; x=1717446622; 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=i004hZB22bqjMNJFc+n67bTnhzWYs+D5uA7aOWn+Ye4=; b=lZv07vSkEuMmlhG6U3SwC0gTcyLGFXh1sFrkRvrjxV6h0H7asYyGV69xG1za02kEKX swmt5GDnji64tmYFUvgQDXN97qLUee2xAczOd+6iI9F7QpVHjV6JQNUUj9p4uHLhQHaH Hmnk6fpwO/EbNBaCy/Ch1LFib1K3WAWvpUb9McPSDs6W89KhOd+bGfdI5AZ2jWT24af3 fbBQHjXBo0vD9jN4nLQK7J3S3DVMGDyfqlG+Tut8nnGlWnVz3ccjhlhdC51rlm/YPK4+ yR7wlMtJiqhYVYttma412PkaGupI9TWmPIdlLK0pexn2xMMkakxH3DtQZ7WucO50tOWM 3sZg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1716841822; x=1717446622; 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=i004hZB22bqjMNJFc+n67bTnhzWYs+D5uA7aOWn+Ye4=; b=N/LSW2XZjpjhu7Bqr1rszC23XOyFxkFIksfIV2LggO8zmWGd1X6fDxb2NU1nFtuLlB VbdyNeXkKbQLbTpxjf40A/MPvgpvMfguarh6lfPI/zZvQTlknPWx3EMxxpY/2gPwvM1U U1esNByjSKLpG33f9dN1JWvGLl2gVYyPg1q9H5cTCy8ya1cADCCOp8CT578IazF9THWw aDRiBlgGjQmO8vQXyxAIYubFFd2E+Om6U8qYp+C8mHvzCe5e9GX/YbiKpAScHwLuhO2l 8ehEPfWbRde0XiQYMGk5V+aEvvPp6Lqzrr9aHTZ6Q1yOZo85/8CtYroKfG470vVpBsk4 ZkiA== X-Forwarded-Encrypted: i=1; AJvYcCVDB/NrrMdFIHLsRDk3k0XiOCDdNnMadMeIkiPt88mVzP0WH90tcsU1BjAjxt4A5flpGQpT0Sv9yCd8TncLhX53xNEnqsddUg/IF0Hk X-Gm-Message-State: AOJu0Yx8/Rq530mUF+1urA/bY0SL0SlXFzNNuxiqS1JjmhWaZmd5BwmD BhuihUXs3RgQeiW22AFdy3OnM3zd4N280tf77rWJdYlOZ7NbcicB X-Google-Smtp-Source: AGHT+IEeDtdDFbyG/VbCJB+hOYKSqRLvSuvYTT9GOjcWHVn/us0YWPRGyIqHjDl2WGfON48XahWsFw== X-Received: by 2002:a05:6e02:1d83:b0:36d:96ab:f4a with SMTP id e9e14a558f8ab-3737b2e3524mr110040075ab.1.1716841821738; Mon, 27 May 2024 13:30:21 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 41be03b00d2f7-6822092a678sm5324279a12.11.2024.05.27.13.30.20 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 27 May 2024 13:30:21 -0700 (PDT) From: Kuan-Wei Chiu To: akpm@linux-foundation.org Cc: jserv@ccns.ncku.edu.tw, linux-kernel@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH 2/4] lib/sort: Fix outdated comment regarding glibc qsort() Date: Tue, 28 May 2024 04:30:09 +0800 Message-Id: <20240527203011.1644280-3-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240527203011.1644280-1-visitorckw@gmail.com> References: <20240527203011.1644280-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" The existing comment in lib/sort refers to glibc qsort() using quicksort. However, glibc qsort() no longer uses quicksort; it now uses mergesort and falls back to heapsort if memory allocation for mergesort fails. This makes the comment outdated and incorrect. Update the comment to refer to quicksort in general rather than glibc's implementation to provide accurate information about the comparisons and trade-offs without implying an outdated implementation. Signed-off-by: Kuan-Wei Chiu --- lib/sort.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/lib/sort.c b/lib/sort.c index 651b73205f6d..b918ae15302d 100644 --- a/lib/sort.c +++ b/lib/sort.c @@ -5,7 +5,7 @@ * This performs n*log2(n) + 0.37*n + o(n) comparisons on average, * and 1.5*n*log2(n) + O(n) in the (very contrived) worst case. * - * Glibc qsort() manages n*log2(n) - 1.26*n for random inputs (1.63*n + * Quicksort manages n*log2(n) - 1.26*n for random inputs (1.63*n * better) at the expense of stack usage and much larger code to avoid * quicksort's O(n^2) worst case. */ --=20 2.34.1 From nobody Fri Feb 13 11:47:40 2026 Received: from mail-pg1-f177.google.com (mail-pg1-f177.google.com [209.85.215.177]) (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 B5A091667C3 for ; Mon, 27 May 2024 20:30:24 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.215.177 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716841826; cv=none; b=fzVHkCxSC8hTqB4U7a0wz83zWKqvaHpJK4JSYHvr5xp5jSKVVtjpsYMCkPAP5l3Qf3C7IdKxUGMORYI01ijuOisVgaW/K4q67E+0cJAHqxZHDK3p6N6ay05IY92AVkacjPmVmn7QVOVI4XA9KSYSjOnQMS9HJiZ+l3vx80n+eHs= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716841826; c=relaxed/simple; bh=1LD7c5LViI7urQvc+sfSQLQyNFLgn5A2MV6jvln6c2s=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=qZTcsNEO2aAGmO05lRrIo5u/jyfd+sghZthcqPKuWq3+geuNlSjSXGCy8gFi4A95Dmb5YhSDnaY8z/FN9CpEIoaDg55yBgjCY0LLzGyVKk9V2xPTTeD9ePRLbfoN32Jm+66aW3+TCs9EjdqLzKksWp7Af1fR/Q4kQpLStYCfHfw= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=OYv2ITGJ; arc=none smtp.client-ip=209.85.215.177 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="OYv2ITGJ" Received: by mail-pg1-f177.google.com with SMTP id 41be03b00d2f7-698ef41ed78so15000a12.1 for ; Mon, 27 May 2024 13:30:24 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1716841824; x=1717446624; 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=9u1J2zaM6wMEMZtGfmaKCd9HEjdRd9oqVcYxMgAgPQg=; b=OYv2ITGJjitO9pPbRF1dauiNbJ3wlxMr/+0oviLu3guYNVtqRpqygsNOitYif+rpji Tb9zODnok6h2laJC5SKPIu7YaM8Rs38waMuYjHvYHjQhWZMT07Q9oVvXNl/GttPq3PXT dyk/c2ZuTIV9WAMoCWigfeEdOaTuj58JPt7/qWGpbhNAPX98exrMDpSPU4yRAOi6oEyS TYB04WBEtiiE/hUKw+Bkmb6erbb2LTlWKSPb4ZQ2Yss8tkU6QLHAcii+CoseLzrObciq FI1Ox41QV6DkcSfh7GY87bz5d1sbBjWAlW9YG6dCarP+M0nBSwruoT/Ttmt6Y2L0Monh i3yA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1716841824; x=1717446624; 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=9u1J2zaM6wMEMZtGfmaKCd9HEjdRd9oqVcYxMgAgPQg=; b=AEKpbpvQKAgIfE3e/179MzN7ObIvBHJ/1YXqouv7UssH2HTgwypyf1oFq6XSlN+w8K 2+4HywgEncWLUqHHd8RTQRG1Jb6i00gJbiESBcDyDsAmMcCMrX+pMGt5GiaIVNrp38Y/ O6lLMos2fnLO4EJzSrE0TdtsoZ8Id4hZmBcsNswzQ8EjIHXk1EMd4Qkg3V65JzbQoms1 59lbMfYfnS0OZXbpHgvMV/17YkIrUoMnM833/XW1PiUSH6gLyP6zQdqp8l3RqEYYMMMA 4afM0aGeSD2dYYQQUzDrIhfXjda0l3JV3095CTKt8bm1xYXVNpjp4deCQuSPCts3E9s/ SlqQ== X-Forwarded-Encrypted: i=1; AJvYcCV6mvPmXKqj34uQ/kvrIGj1UVQyk3RlqaRduqwqajfODIQKEcG7ez3HSarTOmbND1FJF6bUXuliyR8371gEcf5VL+hA9r+k4bnV9Vi3 X-Gm-Message-State: AOJu0YwkDCfdQC+1tjXKd7sAkNVtCR47fOYIP9QwlVJF29hSC6M950gl wLETyrSb3FM6ANxDEdYPt19dWPzfPQe7iYMTzfjPTK7jmPTfazfcWc39gA== X-Google-Smtp-Source: AGHT+IEqo3X1+g+xb8gq3a69aw38LlEIjE24l4riHOcwFr919xGm+e7v0AexfS3qQRnsRZA0dz3Cnw== X-Received: by 2002:a05:6a00:2e85:b0:6fd:1705:9cb8 with SMTP id d2e1a72fcca58-6fd17059fdemr7479260b3a.1.1716841823980; Mon, 27 May 2024 13:30:23 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 41be03b00d2f7-6822092a678sm5324279a12.11.2024.05.27.13.30.22 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 27 May 2024 13:30:23 -0700 (PDT) From: Kuan-Wei Chiu To: akpm@linux-foundation.org Cc: jserv@ccns.ncku.edu.tw, linux-kernel@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH 3/4] lib/sort: Optimize heapsort for handling final 2 or 3 elements Date: Tue, 28 May 2024 04:30:10 +0800 Message-Id: <20240527203011.1644280-4-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240527203011.1644280-1-visitorckw@gmail.com> References: <20240527203011.1644280-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" After building the heap, the code continuously pops two elements from the heap until only 2 or 3 elements remain, at which point it switches back to a regular heapsort with one element popped at a time. However, to handle the final 2 or 3 elements, an additional else-if statement in the while loop was introduced, potentially increasing branch misses. Moreover, when there are only 2 or 3 elements left, continuing with regular heapify operations is unnecessary as these cases are simple enough to be handled with a single comparison and 1 or 2 swaps outside the while loop. Eliminating the additional else-if statement and directly managing cases involving 2 or 3 elements outside the loop reduces unnecessary conditional branches resulting from the numerous loops and conditionals in heapify. This optimization maintains consistent numbers of comparisons and swaps for arrays with even lengths while reducing swaps and comparisons for arrays with odd lengths from 2.5 swaps and 1 comparison to 1.5 swaps and 1 comparison. Signed-off-by: Kuan-Wei Chiu --- lib/sort.c | 10 ++++++---- 1 file changed, 6 insertions(+), 4 deletions(-) diff --git a/lib/sort.c b/lib/sort.c index b918ae15302d..048b7a6ef967 100644 --- a/lib/sort.c +++ b/lib/sort.c @@ -250,10 +250,7 @@ void sort_r(void *base, size_t num, size_t size, a =3D size << shift; n -=3D size; do_swap(base + a, base + n, size, swap_func, priv); - } else if (n > size) { /* Sorting: Extract root */ - n -=3D size; - do_swap(base, base + n, size, swap_func, priv); - } else { /* Sort complete */ + } else { /* Sort complete */ break; } =20 @@ -283,6 +280,11 @@ void sort_r(void *base, size_t num, size_t size, do_swap(base + b, base + c, size, swap_func, priv); } } + + n -=3D size; + do_swap(base, base + n, size, swap_func, priv); + if (n =3D=3D size * 2 && do_cmp(base, base + size, cmp_func, priv) > 0) + do_swap(base, base + size, size, swap_func, priv); } EXPORT_SYMBOL(sort_r); =20 --=20 2.34.1 From nobody Fri Feb 13 11:47:40 2026 Received: from mail-pg1-f178.google.com (mail-pg1-f178.google.com [209.85.215.178]) (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 2EDBA1667FC for ; Mon, 27 May 2024 20:30:27 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.215.178 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716841828; cv=none; b=FaF4cbKqnRVo/E4CsdrC5Fq8smFJVweoCqXKuk9J3x5ZDfvOQSZDvkO7VzL7b1AL3Vbv12rRgE2GLgnsbThVu3N4++Ktp4dcFvZY8xN7dERqsqaUfoDVg3cllBMgEeCZbfwNuyHNkG3F7Rw+KIJdtK8acVwY5VtnBWr7JvOTHEk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716841828; c=relaxed/simple; bh=RKjvan0E7Im/7BRlGrzyeoNxj37ylBgB9GBoKbO6QUk=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=HwDxP3kM1xrJot68o/Bo+C7SpyT0J8ixvHfs+LEZLbpfEYSFAgkd3IsKWukT3Q0WjOnO0Mh/FQfPLyAjWH7Rv3FChuIU2NPjgbXhaJLx+OveUprd9J3YurvXNsfqItrWA9RFSHBF+yp4KyazlcxzcAkl7QljhKZ4Ic0kpTsONGE= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=CCWzREyg; arc=none smtp.client-ip=209.85.215.178 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="CCWzREyg" Received: by mail-pg1-f178.google.com with SMTP id 41be03b00d2f7-667fbbbf36dso9917a12.1 for ; Mon, 27 May 2024 13:30:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1716841826; x=1717446626; 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=iVBlz0vl7yDyH9ZJUwo7OCKU71+Ygf2UNq0ZwoLT7g0=; b=CCWzREygNaU3QvnCMwO2kuJDGDFpPrXlDCvIrIThcnAoUL6CJmzUsz23ogv8sVPSR+ wRA5cFuDLQwO6XV4BkSU2KoFT31oueW+PbkiuXTzLj0DkbIUGoEg+VilA0pQbNnRlB5y m6AZx3hDttSkHeyzoN5fVD9kmclsikFlYyILvb7aab4xThEfUx6w/qUBGcg4Ff9OgMaW OKuW7uTm2Y3uEEnwqM5YkvrdphtR/iHmEuTIt83+E20fCdUdhrBFuoyTl0uH7nwrnFN0 YQl8fXwsUwRzlVEsPxpglhGShKcOqDl03qebrvUdrvCEncBKBJa7SOoXo2xE8fuJtjU/ 05Vg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1716841826; x=1717446626; 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=iVBlz0vl7yDyH9ZJUwo7OCKU71+Ygf2UNq0ZwoLT7g0=; b=cj483LK5q5SFpI/yO5+fAJVamVRTEMKpTiep/4KKtSXXgmCkOvxcX0qfHxzqpMosyb MJj4A9JbsW2+l0YhWUtKdxSUSkP8aqWC2ntAQIHVXgMoVGjKkIz+UJZ4CAlx98YsQAgS Rqjo90xuJjQzoqRo7CEg/oce6YhcMmKKMoSc0i65dRP1ZRWijY3kqHll7n5s1hZotAQw Q5R5Mivfdajk0Eu4yT8M5EHPfjEMozDV4xlegBBCEjqUGbHBIjEK3sIUfAXQfaVR2JEk iK4u+I85cfhn5MSrAx6m8Y1rdgRaWp+pVzaGxecE6XE5Ju3Y+V8FjLtdpJZhFmHUfJoc iEtw== X-Forwarded-Encrypted: i=1; AJvYcCUxs8uD3m2RwCO0YohMs6JbmaiYMQltTvlvtkB+XLG8qATSFZ6rJgAFlAkSzrrgoOQ7/AMvn8u4GVDn883SWF46CPoRkJHOqs6SKnpE X-Gm-Message-State: AOJu0Yy7ApLisYcgSAKaOoUAiwNlfsFGvgqre2zu4jHqMjLWJRJIp/5G vDvAsLeSIQrxt7wjIsrFTqZRCbvvG+FCAHI29tYtNlV4N+lmGV40 X-Google-Smtp-Source: AGHT+IGOWeM2xnSztaV/irrmiqlYuhiEx8We1Pn8+7m5wsLcukICOnjli3kKbMCoetXsgFNmc4z4Vg== X-Received: by 2002:a05:6a20:9489:b0:1af:a4a5:a26a with SMTP id adf61e73a8af0-1b212cc65e8mr9715951637.1.1716841826471; Mon, 27 May 2024 13:30:26 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 41be03b00d2f7-6822092a678sm5324279a12.11.2024.05.27.13.30.25 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 27 May 2024 13:30:25 -0700 (PDT) From: Kuan-Wei Chiu To: akpm@linux-foundation.org Cc: jserv@ccns.ncku.edu.tw, linux-kernel@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH 4/4] lib/test_sort: Add a testcase to ensure code coverage Date: Tue, 28 May 2024 04:30:11 +0800 Message-Id: <20240527203011.1644280-5-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240527203011.1644280-1-visitorckw@gmail.com> References: <20240527203011.1644280-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" The addition of an if statement in lib/sort to handle the final unsorted 2 or 3 elements is not covered by existing test cases, leading to incomplete test coverage. To ensure comprehensive testing and maintain 100% code coverage, add a new testcase for scenarios where the if statement is triggered. Since the if statement is only triggered when the array length is odd and the first element is greater than the second element, a testcase is created using an array length of TEST_LEN - 1 and a suitable random seed to maintain full code coverage. Signed-off-by: Kuan-Wei Chiu --- lib/test_sort.c | 14 +++++++++++++- 1 file changed, 13 insertions(+), 1 deletion(-) diff --git a/lib/test_sort.c b/lib/test_sort.c index be02e3a098cf..da4495125097 100644 --- a/lib/test_sort.c +++ b/lib/test_sort.c @@ -29,7 +29,19 @@ static void test_sort(struct kunit *test) =20 sort(a, TEST_LEN, sizeof(*a), cmpint, NULL); =20 - for (i =3D 0; i < TEST_LEN-1; i++) + for (i =3D 0; i < TEST_LEN - 1; i++) + KUNIT_ASSERT_LE(test, a[i], a[i + 1]); + + r =3D 48; + + for (i =3D 0; i < TEST_LEN - 1; i++) { + r =3D (r * 725861) % 6599; + a[i] =3D r; + } + + sort(a, TEST_LEN - 1, sizeof(*a), cmpint, NULL); + + for (i =3D 0; i < TEST_LEN - 2; i++) KUNIT_ASSERT_LE(test, a[i], a[i + 1]); } =20 --=20 2.34.1