[Mesa-dev] [PATCH] i965 : optimized bucket index calculation

[Tapani Pälli]

Hi;

Won't comment on the algorithm itself but coding style should be fixed 
to follow style used in the rest of the file (some documentation on 
style available here: https://www.mesa3d.org/codingstyle.html).

On 09/08/2017 11:11 AM, aravindan.muthukumar at intel.com wrote:
> From: Aravindan Muthukumar <aravindan.muthukumar at intel.com>
> 
> Avoiding the loop which was running with O(n) complexity.
> Now the complexity has been reduced to O(1)
> 
> Tested with piglit.
> Slight performance improvement (~1%) in 3d mark.
> 
> Change-Id: Id099f1cd24ad5b691a69070eda79b8f4e9be39a6
> Signed-off-by: Aravindan Muthukumar <aravindan.muthukumar at intel.com>
> Signed-off-by: Kedar Karanje <kedar.j.karanje at intel.com>
> Reviewed-by: Yogesh Marathe <yogesh.marathe at intel.com>
> ---
>   src/mesa/drivers/dri/i965/brw_bufmgr.c | 48 +++++++++++++++++++++++++++++-----
>   1 file changed, 41 insertions(+), 7 deletions(-)
> 
> diff --git a/src/mesa/drivers/dri/i965/brw_bufmgr.c b/src/mesa/drivers/dri/i965/brw_bufmgr.c
> index 5b4e784..18cb166 100644
> --- a/src/mesa/drivers/dri/i965/brw_bufmgr.c
> +++ b/src/mesa/drivers/dri/i965/brw_bufmgr.c
> @@ -87,6 +87,11 @@
>   
>   #define memclear(s) memset(&s, 0, sizeof(s))
>   
> +/* Macros for BO cache size */
> +#define CACHE_PAGE_SIZE    4096
> +#define PAGE_SIZE_SHIFT    12
> +#define BO_CACHE_PAGE_SIZE (4 * CACHE_PAGE_SIZE)
> +
>   #define FILE_DEBUG_FLAG DEBUG_BUFMGR
>   
>   static inline int
> @@ -181,19 +186,48 @@ bo_tile_pitch(struct brw_bufmgr *bufmgr, uint32_t pitch, uint32_t tiling)
>      return ALIGN(pitch, tile_width);
>   }
>   
> +/*
> + * This functions is to find the correct bucket fit for the input size.
> + * This function works with O(1) complexity when the requested size
> + * was queried instead of iterating the size through all the buckets.
> + */
>   static struct bo_cache_bucket *
>   bucket_for_size(struct brw_bufmgr *bufmgr, uint64_t size)
>   {
> -   int i;
> +   struct bo_cache_bucket *bucket = NULL;

no need to initialize, I guess no harm though

> +   int x=0,index = -1;

space before and after operator 'x = 0', space after ',':

'int x = 0, index = -1;'

> +   int row, col=0;

space before and after operator

> -   for (i = 0; i < bufmgr->num_buckets; i++) {
> -      struct bo_cache_bucket *bucket = &bufmgr->cache_bucket[i];
> -      if (bucket->size >= size) {
> -         return bucket;
> -      }
> +   /* condition for size less  than 4*4096 (4KB) page size */
> +   if(size < BO_CACHE_PAGE_SIZE){

if (size ...) {

> +      index = (size>>PAGE_SIZE_SHIFT)+((size%(1<<PAGE_SIZE_SHIFT)?1:0))-1;

if size < BO_CACHE_PAGE_SIZE maybe just return the bucket here to get 
rid of else (?)

>      }
> +   else{

if else used it should be on line before like '} else {'

> +      /* When the size is more than 4*4096, the logic follows a matrix method
> +       * where the index will be searched using Arithmetico-Geometric progression.
> +       * So the given size will be divided by 4096 & the index will be traced out.
> +       */
> +      x = size>>PAGE_SIZE_SHIFT;

space before and after operator

>   
> -   return NULL;
> +      /* Find the row using Geometric Progression. The highest bit set will give
> +       * the row number. num = a * r^(n-1) where num = size a = 4 r = 2
> +       */
> +      row = 31 - __builtin_clz(x>>1);
> +
> +     /* Find the column using AP but using the row value
> +      * calculated using GP.
> +      */
> +      col =((x-(1<<(row+1)))/(1<<(row-1)))+1;

space before and after operators

> +      col += (size%(1<<PAGE_SIZE_SHIFT<<(row-1)))?1:0;

space before and after operators

> +
> +      /* Finding the index value using calculated row and col number */
> +      index = ((row-1)<<2) + col + 2;
> +   }
> +
> +   /* Checking the error condition */
> +   bucket = (index >= 0 && index < bufmgr->num_buckets)?(&bufmgr->cache_bucket[index]):NULL;

this won't fit to one line (exceeds ~80 char limit)

    bucket = (index >= 0 && index < bufmgr->num_buckets) ?
       (&bufmgr->cache_bucket[index]) : NULL;

> +   return bucket;
>   }
>   
>   int
>