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 E3C97C7EE2F for ; Sun, 26 Feb 2023 21:57:42 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id DCDAC6B0072; Sun, 26 Feb 2023 16:57:41 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id D7DDC6B0073; Sun, 26 Feb 2023 16:57:41 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id C6C9E6B0074; Sun, 26 Feb 2023 16:57:41 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0012.hostedemail.com [216.40.44.12]) by kanga.kvack.org (Postfix) with ESMTP id B63576B0072 for ; Sun, 26 Feb 2023 16:57:41 -0500 (EST) Received: from smtpin17.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id 709EC1A044F for ; Sun, 26 Feb 2023 21:57:41 +0000 (UTC) X-FDA: 80510805522.17.C9C8B5B Received: from ams.source.kernel.org (ams.source.kernel.org [145.40.68.75]) by imf29.hostedemail.com (Postfix) with ESMTP id 79E68120011 for ; Sun, 26 Feb 2023 21:57:38 +0000 (UTC) Authentication-Results: imf29.hostedemail.com; dkim=pass header.d=linux-foundation.org header.s=korg header.b=sTWY33hb; spf=pass (imf29.hostedemail.com: domain of akpm@linux-foundation.org designates 145.40.68.75 as permitted sender) smtp.mailfrom=akpm@linux-foundation.org; dmarc=none ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1677448658; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=+Dh75lqJSQFjYOUK4DTcpG47DH+29TE+JLK5Hz+0/Nc=; b=Fc1kY/dRkKFyFnnsHnx2y5KDtxBn8TNDspghMTtTstXLS/wM3saIE1L0IyaRotZblD18jI +iD+/Lwj4yD5wk7jDSu9s4Ud35dEWnS1InWxxeXRXPSi8FSDV28z3MhUVDoC4oOKQd2WTh 8FhsNbD43GzDZLdGmw9yav8gujpMUL8= ARC-Authentication-Results: i=1; imf29.hostedemail.com; dkim=pass header.d=linux-foundation.org header.s=korg header.b=sTWY33hb; spf=pass (imf29.hostedemail.com: domain of akpm@linux-foundation.org designates 145.40.68.75 as permitted sender) smtp.mailfrom=akpm@linux-foundation.org; dmarc=none ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1677448658; a=rsa-sha256; cv=none; b=5AoXw1pt/AjidNrrUG90ZKDBQ944U+uTH5wG7fLs4FYbCLKc2xXGzEPJe6jfi+bHC1lGoH ySwwVPtjvZotskmMTrNfpYyVjKJ73Ap5MeWEYChYP4gsYfOYrxaVdT7+nN2bgZ3WGD/Va2 ze3WZBijxqzWes5Cpc17XH6/TG34Tes= Received: from smtp.kernel.org (relay.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ams.source.kernel.org (Postfix) with ESMTPS id B95ADB80C92; Sun, 26 Feb 2023 21:57:36 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 14353C433EF; Sun, 26 Feb 2023 21:57:35 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=linux-foundation.org; s=korg; t=1677448655; bh=bq5sqXumtr7dE+wB1cCv2agmN87geA04zTmv9SMOTzI=; h=Date:From:To:Cc:Subject:In-Reply-To:References:From; b=sTWY33hbvW7D2ItwwBXT/lfpCkmq/JeiJL0r2nTNIOCcBIosuMAgKzXULvGCuLccL DyKYbaGxdkeUPSw6xYcZXQDN6o7hD5RLQII0SJPglEqspgQz+lTrNCA8qdh/JyZf3B GWWsFIRMmhkBIt5STP7Gf5bJhUkZtv1YXdLo6leE= Date: Sun, 26 Feb 2023 13:57:34 -0800 From: Andrew Morton To: Taejoon Song Cc: sjenning@redhat.com, ddstreet@ieee.org, vitaly.wool@konsulko.com, linux-mm@kvack.org, linux-kernel@vger.kernel.org, yjay.kim@lge.com, Sergey Senozhatsky , Minchan Kim Subject: Re: [PATCH] mm/zswap: try to avoid worst-case scenario on same element pages Message-Id: <20230226135734.6ba10ed872bc14802937c7ea@linux-foundation.org> In-Reply-To: <20230205190036.1730134-1-taejoon.song@lge.com> References: <20230205190036.1730134-1-taejoon.song@lge.com> X-Mailer: Sylpheed 3.7.0 (GTK+ 2.24.33; x86_64-pc-linux-gnu) Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit X-Rspamd-Server: rspam07 X-Rspamd-Queue-Id: 79E68120011 X-Rspam-User: X-Stat-Signature: htf3ngmxx3ed9w37by7h578whdqg8tr1 X-HE-Tag: 1677448658-447773 X-HE-Meta: U2FsdGVkX1+hXXlaFGuucf+BA/TdNcdPJznLe6MZZzurupXeF2T+9RTK+oRgi90+8zi65YrpQpj5suptDETSTtsOks9eNsCKa5xRFsdtM6bu8kZZ7vN6jQ8pPQUOx61qcBa4vY9RQJZ6oznZy1xHnlsBjzhGVwviCTwuOcx6Or/yYuoyI6kSaV+HL3kHyKSKB78vI3rifsnTdrJtN9vmI3V8VS0mdb1RMmWmO5ETGjqd6PYNAZkbs6yoNj2URN0VULL7edyiYstExdMOlsWb7G9vI7vgKtnsILl7s6uCtMrDWTLRynbauDs22ZIaKEiX2v2BFTjekFU92tSKHCmtHqb7WXz/JcGC5p7clo4EzIWjxhLg6k8TjBmUn3zUZr6jgXM/bQQlX2LDD3vxfBXH36j+TAtk45F4JixY9uhFHWCYtU7/6lz1ZXwJyWFTl2itOY7o+aYYdAQtVRvoC37XFWmyLynNSGzv581IgsnGZr1GU/ULy4LyEPK+UrD7aoBzLkxD3EdGqThV8sy5NnOjy+xSXJ29EzUFIxCXNa3astoMsjtEZzLVRzbN6WWUVjLyZ7JQTrrGDZk3fhATmIljWD58O6yF0HQDFpm+kSTLBt4rIU6TkXBbscptmd9P2nUBNYxf+OxgF4kRbG0VfOehWtPUjBQwl2kV8LdcckZgusS4DnpueWm/OeDAuPw+LAuKcNdlyr2lHFbY1Fvnsg16MZWWk7S2Be8JfPHm7aTl8bKKD3nmeOMMEi9RIOTU5rYNSWYtG3MrgYdLSFx77aDOO0Awcoa4oTp1f0v3842e2dSMtMUM3jGtrIbCjIn/p4SzcLJxCkd5ATScjgccPu6vueZhctV7ebRdDT5IDSAfQnA8tdh6/8VefXAvSslhPOOD8HWCtpwNidhJVW93A4GJVuvDDrmi8qUUtmGjnv/60BetLecfzW9OB3kXByKzUlIUsLAu7DFBJOnYFVIKwRu Wlms9MRh bYWp6hoLzacHpPC3zlJqV/KSFXjaP1TUDuOfPCNBXqTmCoREpw/LL9uA1rPKv2FOlTqcTziF6hpF6VdhVAGd3FEH3NHwFTC9UG1EaPsE8ZR7aLvG96f93N9QoO88uSMXnUKbSl1PCy7Vaa3zOx8BiDBhzxXtbSnlzXEv8va+dDG0aMcAaTWcw40X8FDnLGZL1O+Rw8EQ04rBjjKJVsevPUX4GjNfnUQLgbVXI1eoXF6JE4gKq2TKYTPfOc5vOHFhlVc4MbNbxLBCq8t42/AiiguCRfDdgsi/JKeP8H/RMHx/qROmS6mYQE6Hix4uC96i5Y1zmNS52emRS2coT2VERrBIUUFfd+b63/K0b6fpR00bVfQfKXA3JMVuDRF6KFhij94ZES1CEqS6NK8/OQMfaF56CTx4qJ/hNlFu30Rpd4nPvCpuSjWWk1EEb89I0p/YqZ/hM2Po8Okd1NTYCnoIRyRM7JA== 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 Mon, 6 Feb 2023 04:00:36 +0900 Taejoon Song wrote: > The worst-case scenario on finding same element pages is that almost all > elements are same at the first glance but only last few elements are > different. > > Since the same element tends to be grouped from the beginning of the > pages, if we check the first element with the last element before > looping through all elements, we might have some chances to quickly > detect non-same element pages. > > 1. Test is done under LG webOS TV (64-bit arch) > 2. Dump the swap-out pages (~819200 pages) > 3. Analyze the pages with simple test script which counts the iteration > number and measures the speed at off-line > > Under 64-bit arch, the worst iteration count is PAGE_SIZE / 8 bytes = > 512. The speed is based on the time to consume page_same_filled() > function only. The result, on average, is listed as below: > > Num of Iter Speed(MB/s) > Looping-Forward (Orig) 38 99265 > Looping-Backward 36 102725 > Last-element-check (This Patch) 33 125072 > > The result shows that the average iteration count decreases by 13% and > the speed increases by 25% with this patch. This patch does not > increase the overall time complexity, though. > > I also ran simpler version which uses backward loop. Just looping > backward also makes some improvement, but less than this patch. Seems a nice change. > This patch was already applied to zram on mainline v5.6-rc1: > https://lkml.org/lkml/2019/12/3/1422 I redid this a little: A similar change has already been made to zram in 90f82cbfe502 ("zram: try to avoid worst-case scenario on same element pages"). > ... > --- a/mm/zswap.c > +++ b/mm/zswap.c > @@ -1073,15 +1073,23 @@ static int zswap_writeback_entry(struct zpool *pool, unsigned long handle) > > static int zswap_is_page_same_filled(void *ptr, unsigned long *value) > { > - unsigned int pos; > unsigned long *page; > + unsigned long val; > + unsigned int pos, last_pos = PAGE_SIZE / sizeof(*page) - 1; > > page = (unsigned long *)ptr; > - for (pos = 1; pos < PAGE_SIZE / sizeof(*page); pos++) { > - if (page[pos] != page[0]) > + val = page[0]; > + > + if (val != page[last_pos]) > + return 0; > + > + for (pos = 1; pos < last_pos; pos++) { > + if (val != page[pos]) > return 0; > } > - *value = page[0]; > + > + *value = val; > + > return 1; > }