On Monday, 23 May 2016 at 14:47:22 UTC, qznc wrote:
> I see three options:
>
> 1. Remove dead bookkeeping code
> 2. Implement back() and popBack()
> 3. Use alternative splitter implementation (and implement back() and popBack())
>
> The third one would be the best, if it is really faster.

If the performance is really a problem (I think it's a micro optimization at best), then the best option is not to violate DRY. Have a template parameter, std.typecons.Flag, to turn off the back and popBack. Don't have two functions that are 95% the same code like filter and filterBidirectional.

On Sunday, 22 May 2016 at 18:56:30 UTC, qznc wrote:
> On Monday, 4 March 2013 at 19:11:17 UTC, Steven Schveighoffer wrote:
>> On Mon, 04 Mar 2013 12:35:23 -0500, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
>>
>>> That's comparable, please file an enh request.
>>
>> http://d.puremagic.com/issues/show_bug.cgi?id=9646

I think the actual slow thing is std.find, which splitter uses.

Benchmark: https://dpaste.dzfl.pl/1e31b6f95659

The output is:

std find    took    162167000
manual find took     99852000

Actually, std find should be faster, since it could use the Boyer Moore algorithm instead of naive string matching.

On 05/23/2016 03:11 PM, Jack Stouffer wrote:
> (I think it's a micro optimization at best)

splitter in the stdlib is likely to be very frequently useful, any bit of speedup we put in it is likely to pay off immensely. -- Andrei

On 05/23/2016 03:11 PM, qznc wrote:
> Actually, std find should be faster, since it could use the Boyer Moore
> algorithm instead of naive string matching.

Conventional wisdom has it that find() is brute force and that's that, but probably it's time to destroy. Selectively using advanced searching algorithms for the appropriate inputs is very DbI-ish.

There are a few nice precedents of blend algorithms, see e.g. http://effbot.org/zone/stringlib.htm.

Writing a generic subsequence search blend algorithm, one that chooses the right algorithm based on a combination of static and dynamic decisions, is quite a fun and challenging project. Who wanna?


Andrei

On Monday, 23 May 2016 at 22:19:18 UTC, Andrei Alexandrescu wrote:
> On 05/23/2016 03:11 PM, qznc wrote:
>> Actually, std find should be faster, since it could use the Boyer Moore
>> algorithm instead of naive string matching.
>
> Conventional wisdom has it that find() is brute force and that's that, but probably it's time to destroy. Selectively using advanced searching algorithms for the appropriate inputs is very DbI-ish.
>
> There are a few nice precedents of blend algorithms, see e.g. http://effbot.org/zone/stringlib.htm.
>
> Writing a generic subsequence search blend algorithm, one that chooses the right algorithm based on a combination of static and dynamic decisions, is quite a fun and challenging project. Who wanna?

I observed that Boyer-Moore from std is still slower. My guess is due to the relatively short strings in my benchmark and the need to allocate for the tables. Knuth-Morris-Pratt might be worthwhile, because only requires a smaller table, which could be allocated on the stack.

The overall sentiment seems to be that KMP vs BM depends on the input. This means an uninformed find function could only use heuristics. Anyway, Phobos could use a KnuthMorrisPrattFinder implementation next to the BoyerMooreFinder. I filed an issue [0].

Apart from advanced algorithms, find should not be slower than a naive nested-for-loop implementation.

[0] https://issues.dlang.org/show_bug.cgi?id=16066

On Monday, 23 May 2016 at 22:19:18 UTC, Andrei Alexandrescu wrote:
> On 05/23/2016 03:11 PM, qznc wrote:
>> Actually, std find should be faster, since it could use the Boyer Moore
>> algorithm instead of naive string matching.
>
> Conventional wisdom has it that find() is brute force and that's that, but probably it's time to destroy. Selectively using advanced searching algorithms for the appropriate inputs is very DbI-ish.

Since I work a lot with text, I use canFind etc. a lot. It'd be nice to be able to choose faster algorithms. People are often advised to use library functions instead of rolling their own, because library functions are optimized for speed, but this doesn't seem to be true of Phobos. Simple everyday tasks like string matching should be as fast as C.

> There are a few nice precedents of blend algorithms, see e.g. http://effbot.org/zone/stringlib.htm.
>
> Writing a generic subsequence search blend algorithm, one that chooses the right algorithm based on a combination of static and dynamic decisions, is quite a fun and challenging project. Who wanna?
>
>
> Andrei

On Tuesday, 24 May 2016 at 07:54:38 UTC, qznc wrote:
> On Monday, 23 May 2016 at 22:19:18 UTC, Andrei Alexandrescu wrote:
>> On 05/23/2016 03:11 PM, qznc wrote:
>>> Actually, std find should be faster, since it could use the Boyer Moore
>>> algorithm instead of naive string matching.
>>
>> Conventional wisdom has it that find() is brute force and that's that, but probably it's time to destroy. Selectively using advanced searching algorithms for the appropriate inputs is very DbI-ish.
>>
>> There are a few nice precedents of blend algorithms, see e.g. http://effbot.org/zone/stringlib.htm.
>>
>> Writing a generic subsequence search blend algorithm, one that chooses the right algorithm based on a combination of static and dynamic decisions, is quite a fun and challenging project. Who wanna?
>
> I observed that Boyer-Moore from std is still slower. My guess is due to the relatively short strings in my benchmark and the need to allocate for the tables. Knuth-Morris-Pratt might be worthwhile, because only requires a smaller table, which could be allocated on the stack.
>
> The overall sentiment seems to be that KMP vs BM depends on the input. This means an uninformed find function could only use heuristics. Anyway, Phobos could use a KnuthMorrisPrattFinder implementation next to the BoyerMooreFinder. I filed an issue [0].
>
> Apart from advanced algorithms, find should not be slower than a naive nested-for-loop implementation.
>
> [0] https://issues.dlang.org/show_bug.cgi?id=16066

From Phobos [1]:

        /* Preprocess #2: init skip[] */
        /* Note: This step could be made a lot faster.
        * A simple implementation is shown here. */
        this.skip = new size_t[needle.length];
        foreach (a; 0 .. needle.length)
        {
            size_t value = 0;
            while (value < needle.length
                   && !needlematch(needle, a, value))
            {
                ++value;
            }
            this.skip[needle.length - a - 1] = value;
        }

[1] https://github.com/dlang/phobos/blob/master/std/algorithm/searching.d#L335

On Tuesday, 24 May 2016 at 09:34:30 UTC, Chris wrote:
> On Tuesday, 24 May 2016 at 07:54:38 UTC, qznc wrote:
>> Apart from advanced algorithms, find should not be slower than a naive nested-for-loop implementation.
>>
>> [0] https://issues.dlang.org/show_bug.cgi?id=16066
>
> From Phobos [1]:
>
>         /* Preprocess #2: init skip[] */
>         /* Note: This step could be made a lot faster.
>         * A simple implementation is shown here. */
>         this.skip = new size_t[needle.length];
>         foreach (a; 0 .. needle.length)
>         {
>             size_t value = 0;
>             while (value < needle.length
>                    && !needlematch(needle, a, value))
>             {
>                 ++value;
>             }
>             this.skip[needle.length - a - 1] = value;
>         }
>
> [1] https://github.com/dlang/phobos/blob/master/std/algorithm/searching.d#L335

Unfortunately, it is slower. My current measurements [0]:

$ ./benchmark 10000000 10 # large haystack, few iterations
std find    took    753837231
manual find took    129561980
$ ./benchmark 10 10000000 # small haystack, many iterations
std find    took    721676721
manual find took    216418870

The nested-for-loop implementation is roughly 4 times faster!

Caveat: I'm not completely sure my benchmark is fair yet.

[0] https://github.com/qznc/find-is-too-slow

On 05/24/2016 06:44 AM, qznc wrote:
> On Tuesday, 24 May 2016 at 09:34:30 UTC, Chris wrote:
>> On Tuesday, 24 May 2016 at 07:54:38 UTC, qznc wrote:
>>> Apart from advanced algorithms, find should not be slower than a
>>> naive nested-for-loop implementation.
>>>
>>> [0] https://issues.dlang.org/show_bug.cgi?id=16066
>>
>> From Phobos [1]:
>>
>>         /* Preprocess #2: init skip[] */
>>         /* Note: This step could be made a lot faster.
>>         * A simple implementation is shown here. */
>>         this.skip = new size_t[needle.length];
>>         foreach (a; 0 .. needle.length)
>>         {
>>             size_t value = 0;
>>             while (value < needle.length
>>                    && !needlematch(needle, a, value))
>>             {
>>                 ++value;
>>             }
>>             this.skip[needle.length - a - 1] = value;
>>         }
>>
>> [1]
>> https://github.com/dlang/phobos/blob/master/std/algorithm/searching.d#L335
>>
>
> Unfortunately, it is slower. My current measurements [0]:
>
> $ ./benchmark 10000000 10 # large haystack, few iterations
> std find    took    753837231
> manual find took    129561980
> $ ./benchmark 10 10000000 # small haystack, many iterations
> std find    took    721676721
> manual find took    216418870
>
> The nested-for-loop implementation is roughly 4 times faster!
>
> Caveat: I'm not completely sure my benchmark is fair yet.
>
> [0] https://github.com/qznc/find-is-too-slow

One somewhat unrelated thing that can be done with Boyer-Moore: use a constant-length skip array instead of dynamic allocation. Upon saturation, continue with brute force. -- Andrei

On 05/24/2016 03:54 AM, qznc wrote:
> On Monday, 23 May 2016 at 22:19:18 UTC, Andrei Alexandrescu wrote:
>> On 05/23/2016 03:11 PM, qznc wrote:
>>> Actually, std find should be faster, since it could use the Boyer Moore
>>> algorithm instead of naive string matching.
>>
>> Conventional wisdom has it that find() is brute force and that's that,
>> but probably it's time to destroy. Selectively using advanced
>> searching algorithms for the appropriate inputs is very DbI-ish.
>>
>> There are a few nice precedents of blend algorithms, see e.g.
>> http://effbot.org/zone/stringlib.htm.
>>
>> Writing a generic subsequence search blend algorithm, one that chooses
>> the right algorithm based on a combination of static and dynamic
>> decisions, is quite a fun and challenging project. Who wanna?
>
> I observed that Boyer-Moore from std is still slower. My guess is due to
> the relatively short strings in my benchmark and the need to allocate
> for the tables. Knuth-Morris-Pratt might be worthwhile, because only
> requires a smaller table, which could be allocated on the stack.

There's also Rabin-Karp that can be used when the sought range is relatively short.

> The overall sentiment seems to be that KMP vs BM depends on the input.
> This means an uninformed find function could only use heuristics.
> Anyway, Phobos could use a KnuthMorrisPrattFinder implementation next to
> the BoyerMooreFinder. I filed an issue [0].

Great. I keep on thinking how the advanced algorithms should "kick in" only after a partial match was long enough and frequent enough. As long as the partial match is short and infrequent, brute force will do best.

> Apart from advanced algorithms, find should not be slower than a naive
> nested-for-loop implementation.
>
> [0] https://issues.dlang.org/show_bug.cgi?id=16066

Nice, thanks.


Andrei