[PATCH] New benchmark strlen-walk

[Siddhesh Poyarekar]

On 08/15/2018 08:28 PM, Wilco Dijkstra wrote:
> 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.

Let me try this and get back to you.

> 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).

I didn't work too hard to control this because of the assumption that < 
16 bytes is a very common size for strings passed to strlen() and a bit 
more bias towards it won't hurt.  I can try to control it a bit more.

Thanks,
Siddhesh