[Mesa-dev] [PATCH] radv: Use a sort for rebuilding the sparse buffer bo list.

[Bas Nieuwenhuizen]

Yep, funny that it did not hang during my testing.

Thanks!

On Tue, Dec 19, 2017 at 7:50 PM, Eric Engestrom
<eric.engestrom at imgtec.com> wrote:
> On Tuesday, 2017-12-19 09:02:57 +0100, Bas Nieuwenhuizen wrote:
>> It uses slightly more memory (though still bounded by the number
>> of mapped ranges), but gives less quadratic behavior.
>>
>> Cuts 4 minutes from the runtime of the CTS *.sparse.* tests.
>> ---
>>  src/amd/vulkan/winsys/amdgpu/radv_amdgpu_bo.c | 45 ++++++++++++++-------------
>>  1 file changed, 24 insertions(+), 21 deletions(-)
>>
>> diff --git a/src/amd/vulkan/winsys/amdgpu/radv_amdgpu_bo.c b/src/amd/vulkan/winsys/amdgpu/radv_amdgpu_bo.c
>> index 9ec4b4fb561..f3fb4ea6068 100644
>> --- a/src/amd/vulkan/winsys/amdgpu/radv_amdgpu_bo.c
>> +++ b/src/amd/vulkan/winsys/amdgpu/radv_amdgpu_bo.c
>> @@ -88,31 +88,34 @@ radv_amdgpu_winsys_virtual_unmap(struct radv_amdgpu_winsys_bo *bo,
>>       radv_amdgpu_winsys_bo_destroy((struct radeon_winsys_bo *)range->bo);
>>  }
>>
>> +static int bo_comparator(const void *ap, const void *bp) {
>> +     struct radv_amdgpu_bo *a = *(struct radv_amdgpu_bo *const *)ap;
>> +     struct radv_amdgpu_bo *b = *(struct radv_amdgpu_bo *const *)bp;
>> +     return (a > b) ? 1 : (a < b) ? -1 : 0;
>> +}
>> +
>>  static void
>>  radv_amdgpu_winsys_rebuild_bo_list(struct radv_amdgpu_winsys_bo *bo)
>>  {
>> -     bo->bo_count = 0;
>> -     for (uint32_t i = 0; i < bo->range_count; ++i) {
>> -             bool found = false;
>> -             if (!bo->ranges[i].bo)
>> -                     continue;
>> -
>> -             for(uint32_t j = 0; j <  bo->bo_count; ++j) {
>> -                     if (bo->bos[j] == bo->ranges[i].bo) {
>> -                             found = true;
>> -                             break;
>> -                     }
>> -             }
>> -
>> -             if (!found) {
>> -                     if (bo->bo_capacity == bo->bo_count) {
>> -                             bo->bos = realloc(bo->bos,
>> -                                               (bo->bo_capacity + 1) * sizeof(struct radv_amdgpu_bo *));
>> -                             ++bo->bo_capacity;
>> -                     }
>> -                     bo->bos[bo->bo_count++] = bo->ranges[i].bo;
>> -             }
>> +     if (bo->bo_capacity < bo->range_count) {
>> +             uint32_t new_count = MAX2(bo->bo_capacity * 2, bo->range_count);
>> +             bo->bos = realloc(bo->bos, new_count * sizeof(struct radv_amdgpu_winsys_bo *));
>> +             bo->bo_capacity = new_count;
>>       }
>> +
>> +     uint32_t temp_bo_count = 0;
>> +     for (uint32_t i = 0; i < bo->range_count; ++i)
>> +             if (bo->ranges[i].bo)
>> +                     bo->bos[temp_bo_count++] = bo->ranges[i].bo;
>> +
>> +     qsort(bo->bos, temp_bo_count, sizeof(struct radv_amdgpu_winsys_bo *), &bo_comparator);
>
> I think this should be `bo_comparator`, without the `&`; last minute
> change before sending the patch?
>
>> +
>> +     uint32_t final_bo_count = 1;
>> +     for (uint32_t i = 1; i < temp_bo_count; ++i)
>> +             if (bo->bos[i] != bo->bos[i - 1])
>> +                     bo->bos[final_bo_count] = bo->bos[i];
>
> missing `++` on `final_bo_count`, right?
>
> Other that that, looks good to me:
> Reviewed-by: Eric Engestrom <eric.engestrom at imgtec.com>
>
>> +
>> +     bo->bo_count = final_bo_count;
>>  }
>>
>>  static void
>> --
>> 2.15.1
>>