Re: [RFC v2 PATCH] ksm: add offset arg to memcmp_pages() to speedup comparing

[Timofey Titovets]

Gentle ping.

P.S.
If someone can tests that on "big" machine, that will be cool (i just
have not one).
I think may be, that need more tuning, as example set max_offset_error
to 128, instead of 8, to trade off precision with performance.
I'm also wander that possible of more profit on machines with "big pages (64k)".

Thanks!

2017-10-02 15:58 GMT+03:00 Timofey Titovets <nefelim4ag@xxxxxxxxx>:
> Currently while search/inserting in RB tree,
> memcmp used for comparing out of tree pages with in tree pages.
>
> But on each compare step memcmp for pages start at
> zero offset, i.e. that just ignore forward progress.
>
> That make some overhead for search in deep RB tree and/or with
> bit pages (4KiB+), so store last start offset where no diff in page content.
>
> Added: memcmpe()
> iter 1024 -  that a some type of magic value
> max_offset_error - 8 - acceptable error level for offset.
>
> With that patch i get ~ same performance in bad case (where offset useless)
> on tiny tree and default 4KiB pages.
>
> So that just RFC, i.e. does that type of optimization make a sense?
>
> Thanks.
>
> Changes:
>         v1 -> v2:
>                 Add: configurable max_offset_error
>                 Move logic to memcmpe()
>
> Signed-off-by: Timofey Titovets <nefelim4ag@xxxxxxxxx>
> ---
>  mm/ksm.c | 61 +++++++++++++++++++++++++++++++++++++++++++++++++++++++------
>  1 file changed, 55 insertions(+), 6 deletions(-)
>
> diff --git a/mm/ksm.c b/mm/ksm.c
> index 15dd7415f7b3..780630498de8 100644
> --- a/mm/ksm.c
> +++ b/mm/ksm.c
> @@ -991,14 +991,58 @@ static u32 calc_checksum(struct page *page)
>         return checksum;
>  }
>
> -static int memcmp_pages(struct page *page1, struct page *page2)
> +
> +/*
> + * memcmp used to compare pages in RB-tree
> + * but on every step down the tree forward progress
> + * just has been ignored, that make performance pitfall
> + * on deep tree and/or big pages (ex. 4KiB+)
> + *
> + * Fix that by add memcmp wrapper that will try to guess
> + * where difference happens, to only scan from that offset against
> + * next pages
> + */
> +
> +static int memcmpe(const void *p, const void *q, const u32 len,
> +                  u32 *offset)
> +{
> +       const u32 max_offset_error = 8;
> +       u32 iter = 1024, i = 0;
> +       int ret;
> +
> +       if (offset == NULL)
> +               return memcmp(p, q, len);
> +
> +       if (*offset < len)
> +               i = *offset;
> +
> +       while (i < len) {
> +               iter = min_t(u32, iter, len - i);
> +               ret = memcmp(p, q, iter);
> +
> +               if (ret) {
> +                       iter = iter >> 1;
> +                       if (iter < max_offset_error)
> +                               break;
> +                       continue;
> +               }
> +
> +               i += iter;
> +       }
> +
> +       *offset = i;
> +
> +       return ret;
> +}
> +
> +static int memcmp_pages(struct page *page1, struct page *page2, u32 *offset)
>  {
>         char *addr1, *addr2;
>         int ret;
>
>         addr1 = kmap_atomic(page1);
>         addr2 = kmap_atomic(page2);
> -       ret = memcmp(addr1, addr2, PAGE_SIZE);
> +       ret = memcmpe(addr1, addr2, PAGE_SIZE, offset);
>         kunmap_atomic(addr2);
>         kunmap_atomic(addr1);
>         return ret;
> @@ -1006,7 +1050,7 @@ static int memcmp_pages(struct page *page1, struct page *page2)
>
>  static inline int pages_identical(struct page *page1, struct page *page2)
>  {
> -       return !memcmp_pages(page1, page2);
> +       return !memcmp_pages(page1, page2, NULL);
>  }
>
>  static int write_protect_page(struct vm_area_struct *vma, struct page *page,
> @@ -1514,6 +1558,7 @@ static __always_inline struct page *chain(struct stable_node **s_n_d,
>  static struct page *stable_tree_search(struct page *page)
>  {
>         int nid;
> +       u32 diff_offset;
>         struct rb_root *root;
>         struct rb_node **new;
>         struct rb_node *parent;
> @@ -1532,6 +1577,7 @@ static struct page *stable_tree_search(struct page *page)
>  again:
>         new = &root->rb_node;
>         parent = NULL;
> +       diff_offset = 0;
>
>         while (*new) {
>                 struct page *tree_page;
> @@ -1590,7 +1636,7 @@ static struct page *stable_tree_search(struct page *page)
>                         goto again;
>                 }
>
> -               ret = memcmp_pages(page, tree_page);
> +               ret = memcmp_pages(page, tree_page, &diff_offset);
>                 put_page(tree_page);
>
>                 parent = *new;
> @@ -1760,6 +1806,7 @@ static struct page *stable_tree_search(struct page *page)
>  static struct stable_node *stable_tree_insert(struct page *kpage)
>  {
>         int nid;
> +       u32 diff_offset;
>         unsigned long kpfn;
>         struct rb_root *root;
>         struct rb_node **new;
> @@ -1773,6 +1820,7 @@ static struct stable_node *stable_tree_insert(struct page *kpage)
>  again:
>         parent = NULL;
>         new = &root->rb_node;
> +       diff_offset = 0;
>
>         while (*new) {
>                 struct page *tree_page;
> @@ -1819,7 +1867,7 @@ static struct stable_node *stable_tree_insert(struct page *kpage)
>                         goto again;
>                 }
>
> -               ret = memcmp_pages(kpage, tree_page);
> +               ret = memcmp_pages(kpage, tree_page, &diff_offset);
>                 put_page(tree_page);
>
>                 parent = *new;
> @@ -1884,6 +1932,7 @@ struct rmap_item *unstable_tree_search_insert(struct rmap_item *rmap_item,
>         struct rb_root *root;
>         struct rb_node *parent = NULL;
>         int nid;
> +       u32 diff_offset = 0;
>
>         nid = get_kpfn_nid(page_to_pfn(page));
>         root = root_unstable_tree + nid;
> @@ -1908,7 +1957,7 @@ struct rmap_item *unstable_tree_search_insert(struct rmap_item *rmap_item,
>                         return NULL;
>                 }
>
> -               ret = memcmp_pages(page, tree_page);
> +               ret = memcmp_pages(page, tree_page, &diff_offset);
>
>                 parent = *new;
>                 if (ret < 0) {
> --
> 2.14.2
>



-- 
Have a nice day,
Timofey.