[Mesa-dev] [PATCH v2] i965 : optimized bucket index calculation
Muthukumar, Aravindan
aravindan.muthukumar at intel.com
Tue Oct 17 03:15:42 UTC 2017
Hi Jason,
Please review and let us know if any other changes need to be done for this patch.
We have incorporated all the review comments in the second version of the patch.
Thanks,
Aravindan
> -----Original Message-----
> From: Muthukumar, Aravindan
> Sent: Tuesday, October 3, 2017 10:04 AM
> To: Marathe, Yogesh <yogesh.marathe at intel.com>; 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: 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
>
> 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
More information about the mesa-dev
mailing list