<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"> <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> <meta name="Generator" content="Microsoft Word 15 (filtered medium)"> <style></style> </head> <body lang="EN-US" link="blue" vlink="purple"> <div class="WordSection1"> <p class="MsoNormal"><a name="_MailEndCompose"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Hi Jason,<o:p></o:p></span></a></p> <p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p> <p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">On the asserts you’ve mentioned below, I assume we need to add them after ‘bufmgr->num_buckets++’ in add_bucket() as num_buckets could be 0 initially. Another clarification on ~1%, we meant approx. 1% there, that’s an improvement we saw in 3Dmark total not a degradation, we’ll correct it in commit msg.<o:p></o:p></span></p> <p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p> <p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Rest all review comments from you, Tapani and Emil are noted & implemented, we are working on running it through mesa CI/CTS and we should see a v2 for review after that.<o:p></o:p></span></p> <p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p> <p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F4E79">Regards,<o:p></o:p></span></p> <p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F4E79">Yogesh.<o:p></o:p></span></p> <p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p> <div style="border:none;border-left:solid blue 1.5pt;padding:0in 0in 0in 4.0pt"> <div> <div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in"> <p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> mesa-dev [mailto:mesa-dev-bounces@lists.freedesktop.org] <b>On Behalf Of </b>Jason Ekstrand<br> <b>Sent:</b> Friday, September 8, 2017 9:09 PM<br> <b>To:</b> Muthukumar, Aravindan <aravindan.muthukumar@intel.com><br> <b>Cc:</b> mesa-dev@lists.freedesktop.org; J Karanje, Kedar <kedar.j.karanje@intel.com><br> <b>Subject:</b> Re: [Mesa-dev] [PATCH] i965 : optimized bucket index calculation<o:p></o:p></span></p> </div> </div> <p class="MsoNormal"><o:p> </o:p></p> <div> <div> <div> <p class="MsoNormal">In general, I'm very concerned about how this handles rounding behavior. Almost everywhere, you round down when what you want to do is round up. Also, as I said on IRC, I'd like to see some asserts in add_bucket so that we are sure this calculation is correct. In particular, I'd like to see<o:p></o:p></p> </div> <div> <p class="MsoNormal"><o:p> </o:p></p> </div> <div> <p class="MsoNormal">assert(bucket_for_size(size) == &bufmgr->cache_bucket[i]);<o:p></o:p></p> </div> <div> <p class="MsoNormal">assert(bucket_for_size(size - 2048) == &bufmgr->cache_bucket[i]);<o:p></o:p></p> </div> <div> <p class="MsoNormal">assert(bucket_for_size(size + 1) != &bufmgr->cache_bucket[i]);<o:p></o:p></p> </div> <div> <p class="MsoNormal"><o:p> </o:p></p> </div> <div> <p class="MsoNormal">We need to check on both sides of size to be 100% sure we're doing our rounding correctly.<o:p></o:p></p> </div> <div> <p class="MsoNormal"><o:p> </o:p></p> </div> <div> <p class="MsoNormal">On Fri, Sep 8, 2017 at 1:11 AM, <<a href="mailto:aravindan.muthukumar@intel.com" target="_blank">aravindan.muthukumar@intel.com</a>> wrote:<o:p></o:p></p> <blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in"> <p class="MsoNormal">From: Aravindan Muthukumar <<a href="mailto:aravindan.muthukumar@intel.com">aravindan.muthukumar@intel.com</a>><br> <br> Avoiding the loop which was running with O(n) complexity.<br> Now the complexity has been reduced to O(1)<br> <br> Tested with piglit.<br> Slight performance improvement (~1%) in 3d mark.<o:p></o:p></p> </blockquote> <div> <p class="MsoNormal"><o:p> </o:p></p> </div> <div> <p class="MsoNormal">Which 3dmark test? Also, what's the error in that 1%?<o:p></o:p></p> </div> <div> <p class="MsoNormal"> <o:p></o:p></p> </div> <blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in"> <p class="MsoNormal">Change-Id: Id099f1cd24ad5b691a69070eda79b8f4e9be39a6<br> Signed-off-by: Aravindan Muthukumar <<a href="mailto:aravindan.muthukumar@intel.com">aravindan.muthukumar@intel.com</a>><br> Signed-off-by: Kedar Karanje <<a href="mailto:kedar.j.karanje@intel.com">kedar.j.karanje@intel.com</a>><br> Reviewed-by: Yogesh Marathe <<a href="mailto:yogesh.marathe@intel.com">yogesh.marathe@intel.com</a>><br> ---<br> src/mesa/drivers/dri/i965/brw_bufmgr.c | 48 +++++++++++++++++++++++++++++-----<br> 1 file changed, 41 insertions(+), 7 deletions(-)<br> <br> diff --git a/src/mesa/drivers/dri/i965/brw_bufmgr.c b/src/mesa/drivers/dri/i965/brw_bufmgr.c<br> index 5b4e784..18cb166 100644<br> --- a/src/mesa/drivers/dri/i965/brw_bufmgr.c<br> +++ b/src/mesa/drivers/dri/i965/brw_bufmgr.c<br> @@ -87,6 +87,11 @@<br> <br> #define memclear(s) memset(&s, 0, sizeof(s))<br> <br> +/* Macros for BO cache size */<br> +#define CACHE_PAGE_SIZE 4096<o:p></o:p></p> </blockquote> <div> <p class="MsoNormal"><o:p> </o:p></p> </div> <div> <p class="MsoNormal">Just call this PAGE_SIZE<o:p></o:p></p> </div> <div> <p class="MsoNormal"> <o:p></o:p></p> </div> <blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in"> <p class="MsoNormal">+#define PAGE_SIZE_SHIFT 12<br> +#define BO_CACHE_PAGE_SIZE (4 * CACHE_PAGE_SIZE)<o:p></o:p></p> </blockquote> <div> <p class="MsoNormal"><o:p> </o:p></p> </div> <div> <p class="MsoNormal">I think I'd rather we just use 4 * PAGE_SIZE explicitly than have this extra #define. I think it's making things harder to read and not easier.<o:p></o:p></p> </div> <div> <p class="MsoNormal"> <o:p></o:p></p> </div> <blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in"> <p class="MsoNormal">+<br> #define FILE_DEBUG_FLAG DEBUG_BUFMGR<br> <br> static inline int<br> @@ -181,19 +186,48 @@ bo_tile_pitch(struct brw_bufmgr *bufmgr, uint32_t pitch, uint32_t tiling)<br> return ALIGN(pitch, tile_width);<br> }<br> <br> +/*<br> + * This functions is to find the correct bucket fit for the input size.<br> + * This function works with O(1) complexity when the requested size<br> + * was queried instead of iterating the size through all the buckets.<br> + */<br> static struct bo_cache_bucket *<br> bucket_for_size(struct brw_bufmgr *bufmgr, uint64_t size)<br> {<br> - int i;<br> + struct bo_cache_bucket *bucket = NULL;<br> + int x=0,index = -1;<br> + int row, col=0;<br> <br> - for (i = 0; i < bufmgr->num_buckets; i++) {<br> - struct bo_cache_bucket *bucket = &bufmgr->cache_bucket[i];<br> - if (bucket->size >= size) {<br> - return bucket;<br> - }<br> + /* condition for size less than 4*4096 (4KB) page size */<br> + if(size < BO_CACHE_PAGE_SIZE){<o:p></o:p></p> </blockquote> <div> <p class="MsoNormal"><o:p> </o:p></p> </div> <div> <p class="MsoNormal">This should be "<="<o:p></o:p></p> </div> <div> <p class="MsoNormal"> <o:p></o:p></p> </div> <blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in"> <p class="MsoNormal">+ index = (size>>PAGE_SIZE_SHIFT)+((size%(1<<PAGE_SIZE_SHIFT)?1:0))-1;<o:p></o:p></p> </blockquote> <div> <p class="MsoNormal"><o:p> </o:p></p> </div> <div> <p class="MsoNormal">I agree with tapani, that this can easily be an early return.<o:p></o:p></p> </div> <div> <p class="MsoNormal"><o:p> </o:p></p> </div> <div> <p class="MsoNormal">I think we can also make this calculation a lot more clear:<o:p></o:p></p> </div> <div> <p class="MsoNormal"><o:p> </o:p></p> </div> <div> <p class="MsoNormal">index = DIV_ROUND_UP(size, PAGE_SIZE) - 1;<o:p></o:p></p> </div> <div> <p class="MsoNormal"> <o:p></o:p></p> </div> <blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in"> <p class="MsoNormal"> }<br> + else{<br> + /* When the size is more than 4*4096, the logic follows a matrix method<br> + * where the index will be searched using Arithmetico-Geometric progression.<br> + * So the given size will be divided by 4096 & the index will be traced out.<br> + */<br> + x = size>>PAGE_SIZE_SHIFT;<o:p></o:p></p> </blockquote> <div> <p class="MsoNormal"><o:p> </o:p></p> </div> <div> <p class="MsoNormal">This rounds down not up like you want.<o:p></o:p></p> </div> <div> <p class="MsoNormal"> <o:p></o:p></p> </div> <blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in"> <p class="MsoNormal">- return NULL;<br> + /* Find the row using Geometric Progression. The highest bit set will give<br> + * the row number. num = a * r^(n-1) where num = size a = 4 r = 2<br> + */<br> + row = 31 - __builtin_clz(x>>1);<br> +<br> + /* Find the column using AP but using the row value<br> + * calculated using GP.<br> + */<br> + col =((x-(1<<(row+1)))/(1<<(row-1)))+1;<br> + col += (size%(1<<PAGE_SIZE_SHIFT<<(row-1)))?1:0;<br> +<br> + /* Finding the index value using calculated row and col number */<br> + index = ((row-1)<<2) + col + 2;<o:p></o:p></p> </blockquote> <div> <p class="MsoNormal"><o:p> </o:p></p> </div> <div> <p class="MsoNormal">I think this can probably also be a lot simpler. How about something like this:<o:p></o:p></p> </div> <div> <p class="MsoNormal"><o:p> </o:p></p> </div> <div> <p class="MsoNormal">pages = DIV_ROUND_UP(size, PAGE_SIZE);<o:p></o:p></p> </div> <div> <p class="MsoNormal">/* Steal this from anv_allocator.c */<o:p></o:p></p> </div> <div> <p class="MsoNormal">pages_log2 = ilog2_round_up(pages);<o:p></o:p></p> </div> <div> <p class="MsoNormal">row = pages_log2 - 1;<o:p></o:p></p> </div> <div> <p class="MsoNormal">col = DIV_ROUND_UP(pages, (1 << (pages_log2 - 2)));<o:p></o:p></p> </div> <div> <p class="MsoNormal">index = row * 4 + col;<o:p></o:p></p> </div> <div> <p class="MsoNormal"><o:p> </o:p></p> </div> </div> <div> <blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in"> <p class="MsoNormal">+ }<br> +<br> + /* Checking the error condition */<br> + bucket = (index >= 0 && index < bufmgr->num_buckets)?(&bufmgr->cache_bucket[index]):NULL;<br> + return bucket;<br> }<br> <br> int<br> <span class="gmail-hoenzb"><span style="color:#888888">--</span></span><span style="color:#888888"><br> <span class="gmail-hoenzb">2.7.4</span><br> <br> <span class="gmail-hoenzb">_______________________________________________</span><br> <span class="gmail-hoenzb">mesa-dev mailing list</span><br> <span class="gmail-hoenzb"><a href="mailto:mesa-dev@lists.freedesktop.org">mesa-dev@lists.freedesktop.org</a></span><br> <span class="gmail-hoenzb"><a href="https://lists.freedesktop.org/mailman/listinfo/mesa-dev" target="_blank">https://lists.freedesktop.org/mailman/listinfo/mesa-dev</a></span></span><o:p></o:p></p> </blockquote> </div> <p class="MsoNormal"><o:p> </o:p></p> </div> </div> </div> </div> </body> </html>