On Mon, 6 Feb 2023 04:00:36 +0900 Taejoon Song <taejoon.song@xxxxxxx> 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; > }
