Hi Andrew,
Previous version has a off-by-one error to check every unsigned long bytes
so it misses a unsigned long bytes in PAGE_SIZE. It could make zram
believe it's same page but not true.
This is a new patch Tejun fixed so could you replace [1] with this
version?
Thanks.
[1] mmotm: zram-try-to-avoid-worst-case-scenario-on-same-element-pages.patch with
On Fri, Jan 10, 2020 at 04:40:01PM +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@xxxxxxx>
Acked-by: Minchan Kim <minchan@xxxxxxxxxx>
> ---
> drivers/block/zram/zram_drv.c | 7 +++++--
> 1 file changed, 5 insertions(+), 2 deletions(-)
>
> diff --git a/drivers/block/zram/zram_drv.c b/drivers/block/zram/zram_drv.c
> index 4285e75..71d5946 100644
> --- a/drivers/block/zram/zram_drv.c
> +++ b/drivers/block/zram/zram_drv.c
> @@ -207,14 +207,17 @@ static inline void zram_fill_page(void *ptr, unsigned long len,
>
> 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++) {
FYI, this is fixed part from previous one.
> if (val != page[pos])
> return false;
> }
> --
> 2.7.4
>
