Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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?

like image 359
gpuguy Avatar asked Oct 09 '13 11:10

gpuguy


2 Answers

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.

like image 132
Peter G. Avatar answered Nov 02 '22 10:11

Peter G.


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....).

like image 7
waleed Avatar answered Nov 02 '22 10:11

waleed