algorithm API design question

[Timon Gehr]

On 09/30/2013 05:45 PM, Andrei Alexandrescu wrote:
> On 9/30/13 5:04 AM, Timon Gehr wrote:
>> On 09/30/2013 11:59 AM, Peter Alexander wrote:
>>> On Monday, 30 September 2013 at 09:15:22 UTC, Timon Gehr wrote:
>>>> On 09/30/2013 04:35 AM, Andrei Alexandrescu wrote:
>>>>> 2. We should statically specialize find(r1, r2) for the case r2 is an
>>>>> instance of Repeat. The specialization runs the tailored algorithm.
>>>>> The
>>>>> user is supposed to call e.g. find(r, repeat(x, k)) to benefit of the
>>>>> specialized algorithm.
>>>>>
>>>>
>>>> If the specialized algorithm runs faster, this should be done anyway.
>>>> What is the optimization that would the specialized algorithm run
>>>> faster though?
>>>
>>> This.
>>>
>>> The faster algorithm is to presumably jump along for random access
>>> ranges. e.g. if you are searching for xxxxxxxxxx then check r[9], if
>>> isn't x, check r[19] and so on. If it is x then check the preceding 10
>>> elements.
>>
>> Boyer-Moore will already do this (and more). I guess you can be sure to
>> get rid of the helper tables by specialising it manually. (But there is
>> no fundamental obstacle that would prevent the compiler to perform this
>> partial evaluation automatically).
>
> B-M has significant preprocessing costs, so it's not appropriate for all
> cases. A function specialized in finding runs would be optimal without
> preprocessing. Another way of looking at it: it's wasteful to pass
> repeat(x, k) into Boyer-Moore to have it rediscover what the caller knew
> already statically.
>
>
> Andrei
>

(My point was that the compiler knows it statically too, and the set of 
program transformations necessary to get rid of it in a standard 
Boyer-Moore implementation should be simple enough. Eg, any occurrence 
of needle[j]!=needle[i] will be known to be false. Probably current 
compilers will not inline array lookups and/or get rid of the allocation 
though.)