From: Minchan Kim <minchan@kernel.org>
To: Taejoon Song <taejoon.song@lge.com>,
Andrew Morton <akpm@linux-foundation.org>
Cc: ngupta@vflare.org, sergey.senozhatsky.work@gmail.com,
axboe@kernel.dk, linux-kernel@vger.kernel.org,
linux-block@vger.kernel.org, yjay.kim@lge.com
Subject: Re: [PATCH] zram: try to avoid worst-case scenario on same element pages
Date: Wed, 4 Dec 2019 14:54:51 -0800 [thread overview]
Message-ID: <20191204225451.GA42672@google.com> (raw)
In-Reply-To: <1575424418-16119-1-git-send-email-taejoon.song@lge.com>
On Wed, Dec 04, 2019 at 10:53:38AM +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.
>
> Signed-off-by: Taejoon Song <taejoon.song@lge.com>
Acked-by: Minchan Kim <minchan@kernel.org>
I think it's very reasonable optimization with small cost.
next prev parent reply other threads:[~2019-12-04 22:54 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-12-04 1:53 [PATCH] zram: try to avoid worst-case scenario on same element pages Taejoon Song
2019-12-04 22:54 ` Minchan Kim [this message]
-- strict thread matches above, loose matches on Subject: below --
2020-01-10 7:40 Taejoon Song
2020-01-10 16:45 ` Minchan Kim
2019-12-03 10:43 Taejoon Song
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20191204225451.GA42672@google.com \
--to=minchan@kernel.org \
--cc=akpm@linux-foundation.org \
--cc=axboe@kernel.dk \
--cc=linux-block@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=ngupta@vflare.org \
--cc=sergey.senozhatsky.work@gmail.com \
--cc=taejoon.song@lge.com \
--cc=yjay.kim@lge.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).