From patchwork Fri Jan 31 06:15:22 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andrew Morton X-Patchwork-Id: 11359283 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id DF61192A for ; Fri, 31 Jan 2020 06:15:29 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id AB5E820663 for ; Fri, 31 Jan 2020 06:15:29 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (1024-bit key) header.d=kernel.org header.i=@kernel.org header.b="ENjjoQQE" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org AB5E820663 Authentication-Results: mail.kernel.org; dmarc=none (p=none dis=none) header.from=linux-foundation.org Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=owner-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix) id 98E766B0559; Fri, 31 Jan 2020 01:15:24 -0500 (EST) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id 9205E6B055B; Fri, 31 Jan 2020 01:15:24 -0500 (EST) X-Original-To: int-list-linux-mm@kvack.org X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 7DF8A6B055C; Fri, 31 Jan 2020 01:15:24 -0500 (EST) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0130.hostedemail.com [216.40.44.130]) by kanga.kvack.org (Postfix) with ESMTP id 651F86B0559 for ; Fri, 31 Jan 2020 01:15:24 -0500 (EST) Received: from smtpin08.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay03.hostedemail.com (Postfix) with ESMTP id 1649B8248D7C for ; Fri, 31 Jan 2020 06:15:24 +0000 (UTC) X-FDA: 76436917368.08.bikes37_2f1da31512123 X-Spam-Summary: 2,0,0,f48adb0c72a75e07,d41d8cd98f00b204,akpm@linux-foundation.org,:akpm@linux-foundation.org:axboe@kernel.dk::minchan@kernel.org:mm-commits@vger.kernel.org:sergey.senozhatsky.work@gmail.com:taejoon.song@lge.com:torvalds@linux-foundation.org,RULES_HIT:41:355:379:800:960:967:973:982:988:989:1260:1263:1345:1359:1381:1431:1437:1534:1542:1711:1730:1747:1777:1792:1801:2198:2199:2393:2525:2559:2564:2682:2685:2859:2902:2933:2937:2939:2942:2945:2947:2951:2954:3022:3138:3139:3140:3141:3142:3354:3865:3866:3867:3868:3871:3874:3934:3936:3938:3941:3944:3947:3950:3953:3956:3959:4250:4321:4471:4605:5007:6119:6120:6261:6653:7514:7576:7901:7903:9025:9121:9391:9545:10004:10913:11026:11658:11914:12043:12048:12295:12296:12297:12517:12519:12555:12679:12783:12986:13053:13146:13161:13229:13230:13846:14181:14721:14849:21080:21324:21433:21451:21627:21740:21819:21939:21990:30034:30054:30070,0,RBL:error,CacheIP:none,Bayesian:0.5,0.5,0.5,Netcheck:none,DomainCache:0,MSF:not bulk,SPF:fp,MSB L:0,DNSB X-HE-Tag: bikes37_2f1da31512123 X-Filterd-Recvd-Size: 4144 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by imf06.hostedemail.com (Postfix) with ESMTP for ; Fri, 31 Jan 2020 06:15:23 +0000 (UTC) Received: from localhost.localdomain (c-73-231-172-41.hsd1.ca.comcast.net [73.231.172.41]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPSA id C2EB820663; Fri, 31 Jan 2020 06:15:22 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=default; t=1580451323; bh=R3oZzR/NDGSFq+nwnMTuT2Xar1cx/JDCvr+NW3dtA4c=; h=Date:From:To:Subject:In-Reply-To:From; b=ENjjoQQEiMeraAzD0ncrJ4LM1R0gKCfwYi1wqHpDTkWDO8msZuZI3sQjVO8LJjUNL VC41wpWigIXtLkOnjV1u/vYcFDnIoSE4pP3RosnAORHwMLlwh2Ffi7nKdkiVI+bf3o 1cAwvcpaBOJpjdt+NHrry6h/iV18zq7sjbRxOKpg= Date: Thu, 30 Jan 2020 22:15:22 -0800 From: Andrew Morton To: akpm@linux-foundation.org, axboe@kernel.dk, linux-mm@kvack.org, minchan@kernel.org, mm-commits@vger.kernel.org, sergey.senozhatsky.work@gmail.com, taejoon.song@lge.com, torvalds@linux-foundation.org Subject: [patch 079/118] zram: try to avoid worst-case scenario on same element pages Message-ID: <20200131061522.LPWx062nX%akpm@linux-foundation.org> In-Reply-To: <20200130221021.5f0211c56346d5485af07923@linux-foundation.org> User-Agent: s-nail v14.8.16 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: From: Taejoon Song Subject: zram: try to avoid worst-case scenario on same element pages 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. [taejoon.song@lge.com: fix off-by-one] Link: http://lkml.kernel.org/r/1578642001-11765-1-git-send-email-taejoon.song@lge.com Link: http://lkml.kernel.org/r/1575424418-16119-1-git-send-email-taejoon.song@lge.com Signed-off-by: Taejoon Song Acked-by: Minchan Kim Cc: Sergey Senozhatsky Cc: Jens Axboe Signed-off-by: Andrew Morton --- drivers/block/zram/zram_drv.c | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-) --- a/drivers/block/zram/zram_drv.c~zram-try-to-avoid-worst-case-scenario-on-same-element-pages +++ a/drivers/block/zram/zram_drv.c @@ -207,14 +207,17 @@ static inline void zram_fill_page(void * static bool page_same_filled(void *ptr, unsigned long *element) { - unsigned int pos; unsigned long *page; unsigned long val; + unsigned int pos, last_pos = PAGE_SIZE / sizeof(*page) - 1; page = (unsigned long *)ptr; val = page[0]; - for (pos = 1; pos < PAGE_SIZE / sizeof(*page); pos++) { + if (val != page[last_pos]) + return false; + + for (pos = 1; pos < last_pos; pos++) { if (val != page[pos]) return false; }