search

KhronosGroup / Vulkan-ValidationLayers

Vulkan Validation Layers (VVL)
https://vulkan.lunarg.com/doc/sdk/latest/linux/khronos_validation_layer.html
Other
727 stars 396 forks source link

O(n^2) algorithm in `CoreChecks::RecordCmdCopyBuffer` #8224

Open Axel-Reactor opened 3 days ago

Axel-Reactor commented 3 days ago

Environment:

Describe the Issue

The checks in CoreChecks::RecordCmdCopyBuffer effectively hang the validation layers when calling vkCmdCopyBuffer with ~100 of regions.

Expected behavior

O(log(n))

spencer-lunarg commented 2 days ago

@arno-lunarg has this been fixed in the refactor from last SDK?

arno-lunarg commented 1 day ago

not at all, I will take a look but for now it is not a priority. Also @Axel-Reactor could you tell me what n refers to here please? I am guessing it is the number of texels to check. For this particular validation, the goal is to parse every texels from the copy source regions, and make sure they are in the [0, 1] range. That is what the validation compute shader does, and it does it in O(n) time (Maybe you got that O(n^2) from looking at the compute shader and seeing the nested for loops?).

As I cannot make any guess on texel values to speed up the search for a faulty texel, I do not think I can get down to a O(log(n)) algorithm, but if you have an idea it would be welcomed!

What I can definitely look at is how memory is accessed, it may not be cache friendly