[Maple Tree v6] Report of inefficient code at the lib/maple_tree.c

[Liam Howlett]

* JaeJoon Jung <rgbi3307 at gmail.com> [220218 20:46]:
> Hello,
> I am testing your Maple Tree of PATCH v6 dated 2022-02-16.
> I found some inefficient code at the lib/maple_tree.c as below:
> 
> $ git diff
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index a1f6e2025399..70710113283d 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> 
> 
> 1. likely/unlikely/offset at the mtree_range_walk()
>    I think it's better to change it like below.
>    Most of all, offset is always greater than zero because of running
> after offset++.
> 
> @@ -2808,13 +2809,12 @@ static inline void *mtree_range_walk(struct
> ma_state *mas)
> 
>                 prev_min = min;
>                 prev_max = max;
> -               if (offset < mt_pivots[type] && pivots[offset])
> +               if (likely(offset < mt_pivots[type] && pivots[offset]))
>                         max = pivots[offset];
> 
> -               if (offset)
> -                       min = pivots[offset - 1] + 1;
> +               min = pivots[offset - 1] + 1;
> 
> -               if (likely(offset > end) && pivots[offset])
> +               if (unlikely(offset > end && pivots[offset]))
>                         max = pivots[offset];

Thank you for pointing this out.  How you have written it is still
not as efficient as it could be.  I will revisit this function.

> 
> 
> 2. return is unnecessary at the mas_walk()
>    Don't need it here because it returns at the end of this if block.
> 
> @@ -5019,7 +5019,6 @@ void *mas_walk(struct ma_state *mas)
>                         mas->index = 1;
>                         mas->last = ULONG_MAX;
>                 }
> -               return entry;
>         } else if (mas_is_none(mas)) {
>                 mas->index = 1;
>                 mas->last = ULONG_MAX;
> 

Thanks.  I'd rather return entry there and make the else if statement
its own thing.

> 
> 3. Below is a more readable one.
> 
> @@ -751,10 +752,10 @@ static inline void mte_set_pivot(struct
> maple_enode *mn, unsigned char piv,
>         default:
>         case maple_range_64:
>         case maple_leaf_64:
> -               (&node->mr64)->pivot[piv] = val;
> +               node->mr64.pivot[piv] = val;
>                 break;
>         case maple_arange_64:
> -               (&node->ma64)->pivot[piv] = val;
> +               node->ma64.pivot[piv] = val;
>         case maple_dense:
>                 break;
>         }
> 

Thanks, I will make this change.


> 
> 4. I think it is good to rename from mas_is_ptr to mas_is_root
> according to meaning as below:
> 
> @@ -226,6 +226,7 @@ static inline void mas_set_err(struct ma_state
> *mas, long err)
>         mas->node = MA_ERROR(err);
>  }
> 
> static inline bool mas_is_ptr(struct ma_state *mas)
> {
>         return mas->node == MAS_ROOT;
> }
> 
> static inline bool mas_is_start(struct ma_state *mas)
> {
>         return mas->node == MAS_START;
> }
> 
> static inline bool mas_is_err(struct ma_state *mas)
> {
>         return xa_is_err(mas->node);
> }

mas_is_root() is likely to be confused with mas_root().

mas_is_root() is also not as clear as it may mean that the maple state
is at the root and not that the maple tree is a single pointer.  Using
MAS_POINTER (or something) instead of MAS_ROOT would indicate that the
maple tree is a pointer but wouldn't explicitly say the maple state is
at the root.


> 
> I hope checking.
> From JaeJoon Jung.