[phobos] [dlang/phobos] a9d5b8: Improve speed of find for random access needles (s...

[GitHub via phobos]

  Branch: refs/heads/master
  Home:   https://github.com/dlang/phobos
  Commit: a9d5b8ca779d2dd89c8b49abae385e793d469e5d
      https://github.com/dlang/phobos/commit/a9d5b8ca779d2dd89c8b49abae385e793d469e5d
  Author: Andreas Zwinkau <zwinkau at kit.edu>
  Date:   2016-06-02 (Thu, 02 Jun 2016)

  Changed paths:
    M std/algorithm/searching.d

  Log Message:
  -----------
  Improve speed of find for random access needles (strings)

For find a string within a string, std.algorithm.searching.find was
unnecessarily slow. The reason is it created intermediate slices. A
naively written nested-for-loop implementation was a few times
faster.

For random access ranges (which strings are) this uses an index based
algorithm, which does not need to create an intermediate slice. Speed
is now comparable to the nested-for-loop implementation even in rather
pathological cases.

This might help with issue 9646.


  Commit: 5529e7afc335c4fe79b077941f56275b25065e87
      https://github.com/dlang/phobos/commit/5529e7afc335c4fe79b077941f56275b25065e87
  Author: Andrei Alexandrescu <andrei at erdani.com>
  Date:   2016-06-02 (Thu, 02 Jun 2016)

  Changed paths:
    M std/algorithm/searching.d

  Log Message:
  -----------
  Merge pull request #4362 from qznc/faster-find

Improve speed of find for random access needles (strings)


Compare: https://github.com/dlang/phobos/compare/e216c10b2ce0...5529e7afc335