With the next couple of slides, I'm not sure I understand how we end up saving space in terms of the number of lines in the directory itself. Do we not still need to have M lines in the directory, and it's that the size of each line (the data contained in it) is no longer the P bit-wide vector, but instead the pointers and data itself is what's stored?
By using sparse directories, we only need to save one pointer in each directory entry (the first item of the linked list). That's less than Limited Pointer Schemas, which need to store a list of pointers. Based on observation that most directory entries are idle, this method would be more efficient.
Right, but a key point here is that there are no directory entries for uncached memory lines in the sparse directory. We ONLY have directory entries for lines in cache. This is being discussed thoroughly on slide 31, but basically a processor quickly looks up if a line is in the directory, and if so takes the appropriate action.
This is made possible because each entry needs only one pointer, so we can quickly change the directory entries at low cost, since our directory no longer has a dedicated space for each memory line.