From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 50DE6C433F5 for ; Wed, 1 Jun 2022 09:44:38 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id DE8206B00A7; Wed, 1 Jun 2022 05:44:37 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id D943F8D0003; Wed, 1 Jun 2022 05:44:37 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id C81466B00A9; Wed, 1 Jun 2022 05:44:37 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id BA0F36B00A7 for ; Wed, 1 Jun 2022 05:44:37 -0400 (EDT) Received: from smtpin05.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id 8A4412033A for ; Wed, 1 Jun 2022 09:44:37 +0000 (UTC) X-FDA: 79529182194.05.F64F117 Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by imf02.hostedemail.com (Postfix) with ESMTP id E2ABE8006B for ; Wed, 1 Jun 2022 09:44:31 +0000 (UTC) Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 4F56FED1; Wed, 1 Jun 2022 02:44:36 -0700 (PDT) Received: from [10.57.81.38] (unknown [10.57.81.38]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id DBB503F66F; Wed, 1 Jun 2022 02:44:34 -0700 (PDT) Message-ID: <408315d1-9820-65d0-c0a7-cc038bfa9eb1@arm.com> Date: Wed, 1 Jun 2022 10:44:29 +0100 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Windows NT 10.0; rv:91.0) Gecko/20100101 Thunderbird/91.9.1 Subject: Re: [PATCH 10/10] dmapool: improve scalability of dma_pool_free Content-Language: en-GB To: Tony Battersby , Keith Busch Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, iommu@lists.linux-foundation.org, kernel-team@fb.com, Matthew Wilcox , Andy Shevchenko , Tony Lindgren References: <9b08ab7c-b80b-527d-9adf-7716b0868fbc@cybernetics.com> <801335ba-00f3-12ae-59e0-119d7d8fd8cd@cybernetics.com> <803feeab-b27b-983d-45da-02a0daf0179a@cybernetics.com> From: Robin Murphy In-Reply-To: <803feeab-b27b-983d-45da-02a0daf0179a@cybernetics.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Rspam-User: Authentication-Results: imf02.hostedemail.com; dkim=none; dmarc=pass (policy=none) header.from=arm.com; spf=pass (imf02.hostedemail.com: domain of robin.murphy@arm.com designates 217.140.110.172 as permitted sender) smtp.mailfrom=robin.murphy@arm.com X-Rspamd-Server: rspam10 X-Rspamd-Queue-Id: E2ABE8006B X-Stat-Signature: aggsdmzyotgwxwgek56ashj4oweydgr5 X-HE-Tag: 1654076671-882450 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: On 2022-05-31 23:10, Tony Battersby wrote: > On 5/31/22 17:54, Keith Busch wrote: >> On Tue, May 31, 2022 at 02:23:44PM -0400, Tony Battersby wrote: >>> dma_pool_free() scales poorly when the pool contains many pages because >>> pool_find_page() does a linear scan of all allocated pages. Improve its >>> scalability by replacing the linear scan with a red-black tree lookup. >>> In big O notation, this improves the algorithm from O(n^2) to O(n * log n). >> The improvement should say O(n) to O(log n), right? > > That would be the improvement for a single call to dma_pool_alloc or > dma_pool_free, but I was going with the improvement for "n" calls > instead, which is consistent with the improvement for the example in the > cover letter for mpt3sas.  I would have to look up the convention to be > sure of the proper notation in a situation like this, but I usually > think "inserting N items takes N^2 time"; to me it makes less sense to > say "inserting 1 item takes N time", because the N seems to come out of > nowhere. No, n represents the size of the set that the algorithm is inserting into (or removing from, searching within, etc.). Hence why constant time is represented by O(1), i.e. not involving the variable at all. Robin.