> Hash tables tend to scatter the data throughout the memory.
Yes, but the critical point is the number of fetches that you have to make
while "searching" a hash bucket to get the item you need. In fact, with
604 you can measure the cost of TLB reloads in terms of memory accesses
and it is typically one memory access to load the TLB (there are of course
pathological cases). Also, there is always the chance that the PTE is
cached in L2.
> On the other hand loading a new page table entry from the tree structure
> can be implemented in software in around 20 cycles depending of the
> architecture.
I am suspicious of workloads that show that it is possible for software
TLB reloads to be faster than hardware reloads with otherwise similar
hardware. On the other hand, allowing the details of the reload to be
mostly software defined is a nice thing even if it eats up some
performance. If the software reload can be broken up into chunks that can
perhaps be better scheduled in the execution pipelines then there might be
some gain (but I am skeptical of this happening very often). 603 has no
TLB reload hardware (though it has hardware assist to decode the data it
fetches on behalf of a TLB miss). This was done to simplify the design
and reduce the amount of silicon real estate. If a dumb TLB miss
implementation allows a design to use the next size larger cache then you
have the makings of an argument though.
Ed Welbon; welbon@bga.com;
"He had bought a large map representing the sea,
Without the least vestige of land:
And the crew was much pleased when they found it to be
A map they could all understand."