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 BBE7FC433F5 for ; Tue, 31 May 2022 22:10:42 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 0E1B26B0072; Tue, 31 May 2022 18:10:42 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 093EB6B0073; Tue, 31 May 2022 18:10:42 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id E98616B0074; Tue, 31 May 2022 18:10:41 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id D8DC96B0072 for ; Tue, 31 May 2022 18:10:41 -0400 (EDT) Received: from smtpin02.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id B6CE9205E3 for ; Tue, 31 May 2022 22:10:41 +0000 (UTC) X-FDA: 79527433482.02.3C489F6 Received: from mail.cybernetics.com (mail.cybernetics.com [173.71.130.66]) by imf31.hostedemail.com (Postfix) with ESMTP id A0D2020072 for ; Tue, 31 May 2022 22:10:00 +0000 (UTC) X-ASG-Debug-ID: 1654035038-1cf43917f334d340001-v9ZeMO Received: from cybernetics.com ([10.10.4.126]) by mail.cybernetics.com with ESMTP id pi5n3chlKhW5dG70; Tue, 31 May 2022 18:10:38 -0400 (EDT) X-Barracuda-Envelope-From: tonyb@cybernetics.com X-ASG-Whitelist: Client DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=cybernetics.com; s=mail; bh=Pscrfy4zfmI9B2/f3RlaAfD71lZsuhWSoCA2Yk9IIwI=; h=Content-Transfer-Encoding:Content-Type:In-Reply-To:From:References:Cc:To: Content-Language:Subject:MIME-Version:Date:Message-ID; b=q5PB8adp564e7QMu+Y67 rqxW9A2//yQphTVtYoOJzENI1mQv1RQmgvsm7Lip7aY8a7rF+htFUguM3OldCVKcojJicdxPHrfCe RfT8TUxLI1Q2o5QHc1BeFYM3K6ctZm0dHzpcsepgcE3x6eZwrBlQGNCsc3NwiuaJ4K8luj2hLA= Received: from [10.157.2.224] (HELO [192.168.200.1]) by cybernetics.com (CommuniGate Pro SMTP 7.1.1) with ESMTPS id 11830524; Tue, 31 May 2022 18:10:38 -0400 Message-ID: <803feeab-b27b-983d-45da-02a0daf0179a@cybernetics.com> Date: Tue, 31 May 2022 18:10:38 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.9.1 Subject: Re: [PATCH 10/10] dmapool: improve scalability of dma_pool_free Content-Language: en-US X-ASG-Orig-Subj: Re: [PATCH 10/10] dmapool: improve scalability of dma_pool_free To: 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 , Robin Murphy , Tony Lindgren References: <9b08ab7c-b80b-527d-9adf-7716b0868fbc@cybernetics.com> <801335ba-00f3-12ae-59e0-119d7d8fd8cd@cybernetics.com> From: Tony Battersby In-Reply-To: Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-Barracuda-Connect: UNKNOWN[10.10.4.126] X-Barracuda-Start-Time: 1654035038 X-Barracuda-URL: https://10.10.4.122:443/cgi-mod/mark.cgi X-Virus-Scanned: by bsmtpd at cybernetics.com X-Barracuda-Scan-Msg-Size: 989 X-Barracuda-BRTS-Status: 1 Authentication-Results: imf31.hostedemail.com; dkim=pass header.d=cybernetics.com header.s=mail header.b=q5PB8adp; dmarc=pass (policy=none) header.from=cybernetics.com; spf=pass (imf31.hostedemail.com: domain of "btv1==1503f279fc1==tonyb@cybernetics.com" designates 173.71.130.66 as permitted sender) smtp.mailfrom="btv1==1503f279fc1==tonyb@cybernetics.com" X-Stat-Signature: s1ond9a941wciqbxxjji19psxg9t1dff X-Rspam-User: X-Rspamd-Server: rspam05 X-Rspamd-Queue-Id: A0D2020072 X-HE-Tag: 1654035000-558381 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 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. Tony