Reply To: Searching

Another email from the OP, now containing source code which I have put in DropBox at https://www.dropbox.com/s/9jggxl33qu5wrny/Implementors.c. I will try to improve my Mill guesstimate in another post after looking at the code more closely.
=============================================================================

Hi Ivan,

I’m not the expert for discussing TLB thrashing or thrashing in the D$1 in a forum, and therefore take the liberty and send the small source code file of the experiment together with my observations. All parameters (# of nodes, dword distance/page(s) between nodes, # of dword vantage points, # of repetitions of the run against the same data) can be configured by passing named parameters through the compiler. The experiment is compiled with the -m32 option and -O3 for gcc, on Vista and on Ubuntu (gcc versions are in the .c source).

There appears no noticeable difference between taking a) 1 dwords, b) 3 dword, c) etc, k) 8191 dwords of distance between the linked nodes, so I cannot say that anything was observable regarding the page size or TLB.

The experiment was run for combinations of 144 comparisons, divided into n = 3,4,6,8,12,18,24,36,48 vantage points and the corresponding m = 48,36,24,18,12,8,6,4,3 entries in the linked list, that is: n*m = 144 was kept constant. There appears a rather small (< 1/3) difference and this could be attributed to the variable cost of loop control; but YMMV.A completely difference problem space is to increase the number of comparisons, since this grows quadratic. I simply have no tool for measuring what effect was caused by what, and therefore leave it at that.I will study your detailed response in the forum for which thank your very much.With kind regards,Klaus D. Witzel