On (23/02/26 13:57), Andrew Morton 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.
>
> A similar change has already been made to zram in 90f82cbfe502 ("zram: try
> to avoid worst-case scenario on same element pages").
>
> Link: https://lkml.kernel.org/r/20230205190036.1730134-1-taejoon.song@xxxxxxx
> Signed-off-by: Taejoon Song <taejoon.song@xxxxxxx>
> Cc: Dan Streetman <ddstreet@xxxxxxxx>
> Cc: Seth Jennings <sjenning@xxxxxxxxxx>
> Cc: Taejoon Song <taejoon.song@xxxxxxx>
> Cc: Vitaly Wool <vitaly.wool@xxxxxxxxxxxx>
> Cc: Minchan Kim <minchan@xxxxxxxxxx>
> Cc: Sergey Senozhatsky <senozhatsky@xxxxxxxxxxxx>
> Cc: <yjay.kim@xxxxxxx>
> Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
Reviewed-by: Sergey Senozhatsky <senozhatsky@xxxxxxxxxxxx>
