public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug libstdc++/62318] New: optimization of string searches using Nigel Horspool's Boyer-Moore-Horpool algorithm
@ 2014-08-31  6:48 jmichae3 at yahoo dot com
  2014-08-31  6:50 ` [Bug libstdc++/62318] " jmichae3 at yahoo dot com
                   ` (5 more replies)
  0 siblings, 6 replies; 7+ messages in thread
From: jmichae3 at yahoo dot com @ 2014-08-31  6:48 UTC (permalink / raw)
  To: gcc-bugs

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62318

            Bug ID: 62318
           Summary: optimization of string searches using Nigel Horspool's
                    Boyer-Moore-Horpool algorithm
           Product: gcc
           Version: 4.9.1
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: jmichae3 at yahoo dot com

optimization of string searches using Nigel Horspool's Boyer-Moore-Horpool
algorithm is what I would like to see. right now it's just a plain old, slow
O(n) loop. in just about any OS, at least half of the funcrtions are string
functions.

the C library should be modified as well, so should the same in objc and objc++
and whatever compiler in GNU compiler set you can put it in.

in C libraries I typically see simple while loops. this can be done much better
with only a little more code, the algorithm is very short.

this could be sped WAY up using this algorithm. google Nigel Horspool and see
if you can get permission to use his algorithm.

this could apply to <algorithm>'s std::find(), std::string.find()
and you would not need to change the function signature.

there are probably other uses for this algorithm I am not thinking of right
now, but if you put your thinking cap on to see where this could fit, I am sure
you could find some choice places for it.

"1980 Practical Fast Searching in Strings" under Publications
http://webhome.cs.uvic.ca/~nigelh/

if you are compiling an OS or OS kernel with this, I would suspect you would
see at least a 2-3x+ general performance improvement, maybe a lot more (though
I have done no testing) due to the fact that most every OS API call has some
sort of string parameter in it. 

Donald Knuth's The Art Of Computer Programming volumes 1-5 has quite an array
of algorithms, and it's (as far as I know) a well known set that's been around
for years.


^ permalink raw reply	[flat|nested] 7+ messages in thread
end of thread, other threads:[~2014-10-29 18:24 UTC | newest]

Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-08-31  6:48 [Bug libstdc++/62318] New: optimization of string searches using Nigel Horspool's Boyer-Moore-Horpool algorithm jmichae3 at yahoo dot com
2014-08-31  6:50 ` [Bug libstdc++/62318] " jmichae3 at yahoo dot com
2014-08-31  7:37 ` schwab@linux-m68k.org
2014-08-31 12:32 ` manu at gcc dot gnu.org
2014-09-01 15:34 ` joseph at codesourcery dot com
2014-09-21  8:47 ` jmichae3 at yahoo dot com
2014-10-29 18:33 ` redi at gcc dot gnu.org

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).