From: Szabolcs Nagy <Szabolcs.Nagy@arm.com>
To: Rich Felker <dalias@libc.org>, Wilco Dijkstra <Wilco.Dijkstra@arm.com>
Cc: nd <nd@arm.com>, Zack Weinberg <zackw@panix.com>,
GNU C Library <libc-alpha@sourceware.org>
Subject: Re: [PATCH v2] Improve performance of strstr
Date: Thu, 18 Apr 2019 16:16:37 +0000 [thread overview]
Message-ID: <9f411780-4dea-940e-8f98-38357445bc1e@arm.com> (raw)
In-Reply-To: <20190418152003.GL23599@brightrain.aerifal.cx>
On 18/04/2019 16:20, Rich Felker wrote:
> On Thu, Apr 18, 2019 at 01:51:14PM +0000, Wilco Dijkstra wrote:
>>> i think even doing memcmp at every byte position is not a
>>> denial of service concern if the needle is <= 256 bytes.
>>> (maybe we should use a lower limit? <= 64?)
>>
>> It couldn't be since its worst case isn't actually much worse (~2.2 times for
>
> The worst is 40x, and it's going to be much much worse on archs
> without big vectors.
40x happens on an input where twoway is fast and new algo is slow,
there are examples the other way around.
if we compare the worst known case of twoway to worst known case
of new algo then the slow down is < 2x according to
https://sourceware.org/ml/libc-alpha/2019-04/msg00404.html
(bad needle 1 is bad for twoway, bad needle 2 is bad for new algo)
next prev parent reply other threads:[~2019-04-18 16:16 UTC|newest]
Thread overview: 33+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-12-31 21:01 [PATCH v2] Improve performance of strstr Wilco Dijkstra
2018-12-31 21:24 ` Rich Felker
2019-01-02 13:40 ` Wilco Dijkstra
2019-02-01 15:40 ` Wilco Dijkstra
2019-03-06 16:55 ` Wilco Dijkstra
2019-03-18 17:17 ` Wilco Dijkstra
2019-04-12 15:50 ` Wilco Dijkstra
2019-04-12 16:19 ` Szabolcs Nagy
2019-04-12 16:49 ` Wilco Dijkstra
2019-04-12 17:16 ` Rich Felker
2019-04-15 10:24 ` Wilco Dijkstra
2019-04-15 14:40 ` Rich Felker
2019-04-15 18:02 ` Wilco Dijkstra
2019-04-15 20:15 ` Zack Weinberg
2019-04-16 0:13 ` Rich Felker
2019-04-16 16:40 ` Szabolcs Nagy
2019-04-16 17:01 ` Szabolcs Nagy
2019-04-16 18:07 ` Szabolcs Nagy
2019-04-16 20:56 ` Rich Felker
2019-04-17 14:24 ` Szabolcs Nagy
2019-04-17 15:10 ` Rich Felker
2019-04-18 13:51 ` Wilco Dijkstra
2019-04-18 15:20 ` Rich Felker
2019-04-18 16:16 ` Szabolcs Nagy [this message]
2019-04-18 16:37 ` Wilco Dijkstra
2019-04-18 17:02 ` Rich Felker
2019-04-16 22:52 ` Wilco Dijkstra
2019-04-16 23:40 ` Rich Felker
2019-04-16 23:49 ` Wilco Dijkstra
2019-04-17 0:37 ` Rich Felker
2019-04-17 0:54 ` Wilco Dijkstra
2019-04-17 2:22 ` Rich Felker
2019-04-17 15:06 ` Wilco Dijkstra
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/libc/involved.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=9f411780-4dea-940e-8f98-38357445bc1e@arm.com \
--to=szabolcs.nagy@arm.com \
--cc=Wilco.Dijkstra@arm.com \
--cc=dalias@libc.org \
--cc=libc-alpha@sourceware.org \
--cc=nd@arm.com \
--cc=zackw@panix.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).