[PATCH v2 3/3] wcsmbs: Ensure wcstr worst-case linear execution time (BZ 23865)

[DJ Delorie]

Adhemerval Zanella Netto <adhemerval.zanella@linaro.org> writes:
>>> +    for (; repeat > 0; repeat--)
>>> +      {
>>> +	FOR_EACH_IMPL (impl, 0)
>>> +	  check_result (impl, haystack, needle, haystack + 1);
>>> +      }
>> 
>> What is the purpose of the repeat loop?  This function is only called
>> once, and not timed...
>> 
>> The test itself is OK.
>
> I copied this tests from gnulib (9411c5e467cf60f6295b9fed306029f341a0f24f)
> and my understanding is to enforce that wcsstr won't take too much time
> by triggering a timeout.  These kind of pattern are slower for newer 
> implementation compared to the current one.
>
> The repeat number is indeed arbitrary and depending of the hardware should 
> not make any different (on my box I only see some different with way larger
> inputs).

My point is, there isn't anything in the test that either (1) computes
how long the test takes, or (2) has a way to FAIL the test if the
timings are off.  I.e. you are not testing for the bug you're fixing.

Given how common it is to set TIMEOUTFACTOR to some large value when
running tests, I don't think relying on a timeout - for anything other
than "infinite time" - is reasonable.

>>> +	FOR_EACH_IMPL (impl, 0)
>>> +	  check_result (impl, haystack, needle, NULL);
>>> +      }
>>> +
>>> +    free (needle);
>>> +  }
>> 
>> Test OK but question the repeat look.

Same here.

>>> +    FOR_EACH_IMPL (impl, 0)
>>> +      check_result (impl, haystack, needle, haystack + m);
>> 
>> Without timing it, how do we test that it is not quadratic?
>
> Because on current implementation it takes forever (about 4 minutes
> on my box) due the input sizes.

Same here.  Nobody will notice the 4 minute test time in a scripted CI
environment unless the test returns FAIL.