Do you have any results showing that this is actually faster than the current code?  Since it's purely a performance optimization, it seems like that should be a prerequisite.

src/arch/x86/tlb.cc (Diff revision 1)

This whole algorithm here is (1) a bit inscrutable and (2) looks potentially inefficient.  (1) could be fixed with some comments.  Should I be concerned about (2)?

Show all issues

1. Gabe Black April 9, 2012, 4:48 p.m. (April 9, 2012, 4:48 p.m.)

   Untrue. I have scruted it myself. The old algorithm had one nice property in that the list of TLB entries were always in LRU order. If you needed to free something, you'd just grab the last thing in the list which was automatically the oldest, since everything else would have more recently been moved to the head of the list when it was used. With this new scheme, I decided to instead just write an incrementing integer to each entry as it was accessed which is very easy. Then, in the relatively rare even that there was an eviction, you need to look through all the entries and find the one with the lowest sequence number. I use whether or not there's a trie node associated with the entry as a valid bit. I'm sure there are ways it can be more efficient, but this way isn't that bad and evictions should be rare. Finding the min of a small set of entries is also pretty quick compared to going through the whole page table walker mechanism to find the new entry.

2. Steve Reinhardt April 10, 2012, 4:22 a.m. (April 10, 2012, 4:22 a.m.)

   Ha... reminds me of this joke (this specific version from http://en.wikipedia.org/wiki/Mathematical_joke#Stereotypes_of_mathematicians ):
   
   A mathematics professor is giving a lecture to his students and writing equations on a blackboard. He says, "At this point, it is obvious that this equation can be derived from that one." He pauses, then turns his back on the class and spends an hour filling the entire blackboard with more work. Finally he turns and announces triumphantly, "Yes, I was correct; it is obvious!"
   
   Nevertheless, I think some comments are called for.
   
   I guess given that there's a net performance gain, the inefficiency of the replacement algorithm can be overlooked.  Nevertheless, this seems like something that could fall off a cliff given lots of replacements and/or a large TLB.  Might also be worth a warning in a comment.

src/arch/x86/vtophys.cc (Diff revision 1)

same comment here

Show all issues

1. Steve Reinhardt April 8, 2012, 10:38 a.m. (April 8, 2012, 10:38 a.m.)

   referring back to an earlier comment that somehow reviewboard dropped on me... the comment was attached to the earlier "Addr width", and said that (1) I doubt Addr is still the most appropriate type here and (2) "width" is not the most descriptive name either.  How about pageSizeBits or shiftBits or something like that?

2. Gabe Black April 9, 2012, 4:48 p.m. (April 9, 2012, 4:48 p.m.)

   How about making it an unsigned and calling it logBytes? I'll implement that.

3. Steve Reinhardt April 10, 2012, 4:22 a.m. (April 10, 2012, 4:22 a.m.)

   Looks good, thanks.

src/arch/x86/tlb.cc (Diff revision 4)

You've increased the number of comments here by infinity percent, so that's good, but this method still seems a little sparse...

src/arch/x86/tlb.cc (Diff revision 4)

Under what circumstances would size be 0?  Should we even allow construction of a zero-size TLB?

Show all issues

1. Gabe Black April 14, 2012, 10:33 a.m. (April 14, 2012, 10:33 a.m.)

   I was being paranoid, but it's probably not necessary/should be in the constructor.

src/arch/x86/tlb.cc (Diff revision 4)

So is this whole initial loop just to find an initial value for lru, so it's not undefined in the second loop where we look for the minimum value?  If so, wouldn't it be easier to just initialize a minLruSeq variable with UINT64_MAX and use that?

Also, wouldn't trieHandle be NULL only if the entry is invalid, in which case that's probably the entry we want to free up even if it's not LRU?

1. Gabe Black April 14, 2012, 10:33 a.m. (April 14, 2012, 10:33 a.m.)

   Yeah, this could be simplified a bit. I really don't like picking a fake max or min the real values are "sure" to beat out, because they aren't really certain to for all legal values, among other things. I'll take a different approach.

src/arch/x86/tlb.cc (Diff revision 4)

What happens if we take this early return?  Seems like in this case we didn't add anything to the free list, and the caller could be rather disappointed about that.

1. Gabe Black April 14, 2012, 10:33 a.m. (April 14, 2012, 10:33 a.m.)

   That would imply that everything was already free, so really this function shouldn't have been called at all.

src/arch/x86/tlb.cc (Diff revisions 4 - 5)

This should probably be

if (size == 0)
  fatal("...")

since this could be the result of user error (i.e., a poorly written config script) and not a program bug.

Show all issues

src/base/trie.hh (Diff revision 5)

Looks like you got these comment changes in the wrong changeset.

Of course, an easy fix is just to merge the changesets ;-).  (Sorry, I just can't help it.)

Show all issues

Ship It!