What is Pointer-chasing and how it is related to BFS

Question

While reading a PPT on BFS (Breadth First Searching) I found that BFS can be used where we have " pointer-chasing" . What exactly is a pointer chasing and how is it related to BFS?

Answer 1

Pointers imply a graph on your data. BFS (breadth first search) is an algorithm to search in that graph.

Pointer chasing is just another word for following lots of pointers.

Answer 2

From the hardware perspective (CPU), pointer-chasing is bad for performance because memory reads are in effect serialized in the CPU (ie no ILP). You can't start a read (ie a load instr) until the prior one is done (since the prior load gives us the address for the next load and so on....).