+ all v1 reviewers. Does this look ok? -Yogesh.
>-----Original Message----- >From: mesa-dev [mailto:[email protected]] On Behalf Of >[email protected] >Sent: Thursday, September 14, 2017 12:13 PM >To: [email protected] >Cc: Muthukumar, Aravindan <[email protected]>; J Karanje, >Kedar <[email protected]> >Subject: [Mesa-dev] [PATCH v2] i965 : optimized bucket index calculation > >From: Aravindan Muthukumar <[email protected]> > >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 <[email protected]> >Signed-off-by: Kedar Karanje <[email protected]> >Reviewed-by: Yogesh Marathe <[email protected]> >--- > 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 >[email protected] >https://lists.freedesktop.org/mailman/listinfo/mesa-dev _______________________________________________ mesa-dev mailing list [email protected] https://lists.freedesktop.org/mailman/listinfo/mesa-dev
