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

[Muthukumar, Aravindan]

Hi Reviewers,
	Please review and provide the comments on the second version of the patch.

Thanks,
Aravindan

> -----Original Message-----
> From: Marathe, Yogesh
> Sent: Friday, September 22, 2017 8:41 AM
> To: Ekstrand, Jason <jason.ekstrand at intel.com>; Palli, Tapani
> <tapani.palli at intel.com>; Ian Romanick <idr at freedesktop.org>; Emil Velikov
> <emil.l.velikov at gmail.com>
> Cc: Muthukumar, Aravindan <aravindan.muthukumar at intel.com>; J Karanje,
> Kedar <kedar.j.karanje at intel.com>; mesa-dev at lists.freedesktop.org
> Subject: RE: [Mesa-dev] [PATCH v2] i965 : optimized bucket index calculation
> 
> + all v1 reviewers. Does this look ok?
> 
> -Yogesh.
> 
> >-----Original Message-----
> >From: mesa-dev [mailto:mesa-dev-bounces at lists.freedesktop.org] On
> >Behalf Of aravindan.muthukumar at intel.com
> >Sent: Thursday, September 14, 2017 12:13 PM
> >To: mesa-dev at lists.freedesktop.org
> >Cc: Muthukumar, Aravindan <aravindan.muthukumar at intel.com>; J Karanje,
> >Kedar <kedar.j.karanje at intel.com>
> >Subject: [Mesa-dev] [PATCH v2] i965 : optimized bucket index
> >calculation
> >
> >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)
> >
> >Algorithm calculates the index using matrix method.
> >Matrix arrangement is as below:
> >Assuming PAGE_SIZE is 4096.
> >
> >         1*4096   2*4096    3*4096    4*4096
> >         5*4096   6*4096    7*4096    8*4096
> >          ...      ...       ...       ...
> >          ...      ...       ...       ...
> >          ...      ...       ...   max_cache_size
> >
> >From this matrix its cleary seen that every row follows the below way:
> >         ...       ...       ...        n
> >       n+(1/4)n  n+(1/2)n  n+(3/4)n    2n
> >
> >Row is calulated as log2(size/PAGE_SIZE) Column is calculated as
> >converting the difference between the elements to fit into power size of two
> and indexing it.
> >
> >Final Index is (row*4)+(col-1)
> >
> >Tested with Intel Mesa CI.
> >
> >Improves performance of 3d Mark on Broxton.
> >Analyzed using Compare Perf Analyser:
> >Average : 201.2 +/- 65.4836 (n=20)
> >Percentage : 0.705966% +/- 0.229767% (n=20)
> >
> >v2: Review comments regarding cosmetics and asserts implemented
> >
> >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 | 46
> >++++++++++++++++++++++++++++------
> > 1 file changed, 39 insertions(+), 7 deletions(-)
> >
> >diff --git a/src/mesa/drivers/dri/i965/brw_bufmgr.c
> >b/src/mesa/drivers/dri/i965/brw_bufmgr.c
> >index 8017219..8013ccb 100644
> >--- a/src/mesa/drivers/dri/i965/brw_bufmgr.c
> >+++ b/src/mesa/drivers/dri/i965/brw_bufmgr.c
> >@@ -87,6 +87,8 @@
> >
> > #define memclear(s) memset(&s, 0, sizeof(s))
> >
> >+#define PAGE_SIZE 4096
> >+
> > #define FILE_DEBUG_FLAG DEBUG_BUFMGR
> >
> > static inline int
> >@@ -181,19 +183,45 @@ bo_tile_pitch(struct brw_bufmgr *bufmgr, uint32_t
> >pitch, uint32_t tiling)
> >    return ALIGN(pitch, tile_width);
> > }
> >
> >+static inline int
> >+ilog2_round_up(int value)
> >+{
> >+   assert(value != 0);
> >+   return 32 - __builtin_clz(value - 1); }
> >+
> >+/*
> >+ * This function finds the correct bucket fit for the input size.
> >+ * The 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;
> >+   int index = -1;
> >+   int row, col = 0;
> >+   int pages, pages_log2;
> >
> >-   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 (16KB) page size */
> >+   if(size <= 4 * PAGE_SIZE) {
> >+      index = DIV_ROUND_UP(size, PAGE_SIZE) - 1;;
> >+   } else {
> >+      /* Number of pages of page size */
> >+      pages = DIV_ROUND_UP(size, PAGE_SIZE);
> >+      pages_log2 = ilog2_round_up(pages) - 1;
> >+
> >+      /* Finding the row and column of the matrix */
> >+      row = pages_log2 - 1;
> >+      col = DIV_ROUND_UP((pages - (1 << pages_log2)),
> >+            (1 << (pages_log2 - 2)));
> >+
> >+      /* Using the calculated row and column to index into the matrix */
> >+      index = (row << 2) + (col - 1);
> >    }
> >
> >-   return NULL;
> >+   /* Checking the error condition */
> >+   return (index >= 0 && index < bufmgr->num_buckets) ?
> >+          (&bufmgr->cache_bucket[index]) : NULL;
> > }
> >
> > int
> >@@ -1239,6 +1267,10 @@ add_bucket(struct brw_bufmgr *bufmgr, int size)
> >    list_inithead(&bufmgr->cache_bucket[i].head);
> >    bufmgr->cache_bucket[i].size = size;
> >    bufmgr->num_buckets++;
> >+
> >+   assert(bucket_for_size(bufmgr, size) == &bufmgr->cache_bucket[i]);
> >+   assert(bucket_for_size(bufmgr, size - 2048) == &bufmgr->cache_bucket[i]);
> >+   assert(bucket_for_size(bufmgr, size + 1) !=
> >+ &bufmgr->cache_bucket[i]);
> > }
> >
> > static void
> >--
> >2.7.4
> >
> >_______________________________________________
> >mesa-dev mailing list
> >mesa-dev at lists.freedesktop.org
> >https://lists.freedesktop.org/mailman/listinfo/mesa-dev