> Pardon- it starts making sense if the table (arg+data) is more than 3 > pages (of whatever size the paging system supports).
Did we even mention separating the keys from the data? When you want to take advantage of the cache for searching the keys, you don't want to pollute it with data you were not looking for. > consider a 40 element table with each being 1000 on a 2K paging system- > > space required: 20 pages > > sequential - AVG 10 pages referenced > binary/AVL - 6 pages referenced > > with key 50 and data 950 (=1000) > > 2 pages referenced > = 1 page for key and 1 for the item (regardless > of method) Your key size is more than what I would have taken as an example, but anyway. There's 5 keys per cache line (we do make sure not wrap, right?) and in total 8 cache lines. Sequential search will on avg inspect 20 keys so touch 4 cache lines, worst case 8. Binary search would avg inspect 6 keys; worst case 6 cache lines. If you have the table row Unless doing many searches per transaction through the table, I would ignore the chances that lines are cache from the previous search. My guts feeling was already that you'd need two orders of magnitude more keys (and shorter ones) to make a difference. Say 4000 keys of 8 byte each. That's 125 cache lines. Sequential search hits avg of 63, binary search hits at most 12. Considering that binary search is not that much harder than sequential, I would say we have a winner. When it takes 8 byte pointers (sorted) to the actual key, then each test takes another L1 miss for the key, so we're still off better with 24 cache lines. I would think that doing 2000 more CLC instructions might put more weight on the scale than 40 L1 misses. But both sit on the same side anyway. Interesting research (and entirely different) would be how cache affects the performance of various sorting algorithms... Rob ---
