This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: [PATCH] improve string find algorithm
- From: Jonathan Wakely <jwakely at redhat dot com>
- To: Jakub Jelinek <jakub at redhat dot com>
- Cc: Aditya Kumar <aditya dot k7 at samsung dot com>, libstdc++ at gcc dot gnu dot org, gcc-patches at gcc dot gnu dot org, hiraditya at msn dot com
- Date: Fri, 6 Jan 2017 15:16:12 +0000
- Subject: Re: [PATCH] improve string find algorithm
- Authentication-results: sourceware.org; auth=none
- References: <1481132816-31162-1-git-send-email-aditya.k7@samsung.com> <CGME20170106133507epcas2p15eaabe5ca279349c9f3603a6c2bb61d8@epcas2p1.samsung.com> <20170106133502.GB2966@redhat.com> <016101d2682b$136dc890$3a4959b0$@samsung.com> <20170106150928.GO21933@tucnak>
On 06/01/17 16:09 +0100, Jakub Jelinek wrote:
On Fri, Jan 06, 2017 at 08:42:15AM -0600, Aditya Kumar wrote:
Yes, we do.
Sorry for the mistake, it happened because I first wrote this for
libcxx (https://reviews.llvm.org/D27068) and while porting that line
got missed.
Shouldn't find at least in the case where it is narrow char string
just use C library memmem? That implements a Two-Way searching algorithm
with some improvements from Boyer-Moore.
Otherwise, consider what even your modified version will do for
#include <string>
int main() {
(std::string(10000000, 'a')+"b").find(std::string(1000000, 'a')+"b");
}
Yes, I have an incomplete local patch that checks for memmem and uses
it where possible. This change would still be valuable for non-GNU
targets though.
Or does the C++ library need to reinvent everything implemented in the C
library?
In this case yes, because strstr doesn't take the length of the
strings into account, and memmem isn't standard. Because std::string
knows its length we can do better than strstr for some cases, such as
std::string(1000, 'a').find(std::string(1001, 'a')).