[PATCH] New benchmark strlen-walk

[Wilco Dijkstra]

Siddhesh Poyarekar wrote:

> A comment in the test provides the rationale for the benchmark; to
> summarize it focuses on testing strlen with small to medium sized
> inputs with different sizes mixed in and walking backwards to try and
> trick the prefetcher.  The numbers are kinda stable; I'm not super happy
> but they're close enough to make out a general performance
> characteristic.

I don't believe walking backwards will fool a modern prefetcher. I would just
shuffle the array a bit (eg. swap arr[i] with arr[rand()%n] for all indices). Doing
that significantly increases runtime, showing that it is harder to prefetch.

Another issue is this:

+      cnt--;
+      if (cnt == 0)
+       {
+         cur_cnt = cur_cnt << 1;
+         cnt = cur_cnt;
+         maxlen >>= 1;
+         if (maxlen == 0)
+           maxlen = orig_maxlen;
+       }
+      len = maxlen + rand () % 8;

The result is that strings in length 1-16 are hugely overrepresented. If we
have N entries when maxlen is 16, we get N values in the range 16-24.
However we will get 30N values in the range 1-16 rather than the expected
2N. So the if should check maxlen==4 and reset (or something similar).

Wilco