Success! Find is slow no more

[Michael Brown]

On Thursday, 23 May 2019 at 00:16:16 UTC, H. S. Teoh wrote:
> On Wed, May 22, 2019 at 11:52:12PM +0000, Brian Schott via 
> Digitalmars-d wrote:
>> On Wednesday, 22 May 2019 at 23:24:47 UTC, H. S. Teoh wrote:
>> > But if your code shows improvement with ldc/gdc, *then* we 
>> > have something interesting to talk about.
>> 
>> Cloning the repository and running "make ldc" on my machine 
>> gives the following:
>> 
>> Search in Alice in Wonderland
>>        std: 178 ±13
>>     manual: 124 ±10
>>   A2Phobos: 100 ±0
>>      Chris: 121 ±10
>>     Andrei: 172 ±11
>>    Andrei2: 116 ±8
>>     Faster: 143 ±10
> [...]
>
> Interesting! So A2Phobos (which version does it refer to?) is 
> faster in all these cases. Looks like that's what we should 
> merge. The `Faster` algorithm doesn't seem to do very well, I'm 
> guessing because the manual optimizations have confused LDC's 
> optimizer enough that it's unable to produce good code.
>
>
> T

Hi All,

Just installed LDC, Yes - ldc not producing SIMD instructions on 
the loops, which it is for the other methods. Rewriting the loops 
to the code below gives.

Search in Alice in Wonderland
        std: 122 ±4
     manual: 113 ±2
   A2Phobos: 100 ±0
      Chris: 152 ±3
     Andrei: 161 ±3
    Andrei2: 118 ±2
     Faster: 113 ±2
Search in random short strings
        std: 125 ±13
     manual: 126 ±13
   A2Phobos: 120 ±9
      Chris: 129 ±11
     Andrei: 103 ±4
    Andrei2: 134 ±19
     Faster: 102 ±3
Mismatch in random long strings
        std: 117 ±7
     manual: 166 ±62
   A2Phobos: 105 ±7
      Chris: 211 ±84
     Andrei: 170 ±76
    Andrei2: 118 ±9
     Faster: 111 ±8
Search random haystack with random needle
        std: 116 ±8
     manual: 139 ±32
   A2Phobos: 109 ±13
      Chris: 169 ±35
     Andrei: 131 ±29
    Andrei2: 116 ±8
     Faster: 112 ±9
  (avg slowdown vs fastest; absolute deviation)
CPU ID: GenuineIntel Celeron(R) Dual-Core CPU       T3500  @ 
2.10GHz

Still - A solid second place, against A2Phobos. Wondering if it 
has some tricks its using I could incorp.

CODE


T[] faster_find(T)(T[] haystack, T[] needle)
{
     if (needle.length == 0) return haystack[$..$];
	if (needle.length > haystack.length) return haystack[$..$];

	immutable end = needle.length - 1;
	size_t j = end, skip = 0;
	
     while(++j < haystack.length)
     {
         if (haystack[j] != needle[end]) continue;
		
         for(size_t i = 1, k = 0; i < needle.length; ++i, ++k) {
             if (haystack[j - needle.length + i] != needle[k]) {
				while (skip < end && needle[end - 1 - skip] != needle[end]) { 
++skip; }
				j += skip;
				goto main_loop2;
			}
         }
		return haystack[j - end .. $];
     }
     return haystack[$ .. $];

	main_loop2: while(++j < haystack.length)
     {
         if (haystack[j] != needle[end]) continue;
		
         for(size_t i = 1, k = 0; i < needle.length; ++i, ++k) {
             if (haystack[j - needle.length + i] != needle[k]) {
				j += skip;
				continue main_loop2;
			}
         }
		return haystack[j - end .. $];
     }
     return haystack[$ .. $];
}