Skip to content

util/ra: use adjacency matrix for undirected graph

Konstantin Lazukin requested to merge GL/mesa:adj_mtx_opt into main

Since this graph is actually not oriented, its adjacency matrix can be represented using less than half bits required by full adjacency matrix. It reduces memory consumption and number of cache misses. It also simplifies logic of growing this matrix - no need to touch adjacency bits for previously allocated number of nodes.

Move adjacency bits from nodes to graph to reduce the number of allocations.

No changes to shader-db.

Reviewed-by: Emma Anholt emma@anholt.net

Reviewed-by: Ian Romanick ian.d.romanick@intel.com

Signed-off-by: Kostiantyn Lazukin kostiantyn.lazukin@globallogic.com

Edited by Konstantin Lazukin

Merge request reports