This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH] improve string find algorithm
- From: Jakub Jelinek <jakub at redhat dot com>
- To: Jonathan Wakely <jwakely 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 16:43:57 +0100
- 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> <20170106151612.GC2966@redhat.com> <20170106152641.GP21933@tucnak> <20170106153422.GE2966@redhat.com>
- Reply-to: Jakub Jelinek <jakub at redhat dot com>
On Fri, Jan 06, 2017 at 03:34:22PM +0000, Jonathan Wakely wrote:
> > The description of Two-Way algorithm is in
> > http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260
> > Boyer-Moore in
> > http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm
>
> And in std::boyer_moore_searcher in <functional> :-)
> We also have std::boyer_moore_horspool_searcher in <functional>.
>
> We could try allocating memory in std::string::find() and fall back to
> the dumb algorithm if it fails, but we don't want to throw bad_alloc.
glibc memmem algorithm doesn't allocate any memory for short needles (< 32
chars) and for longer needles uses size_t shift_table[1U << CHAR_BIT];
automatic array (i.e. 1KB on 32-bits, 2KB on 64-bits).
Jakub