The quest for fastest strstr-like function in C
-
Hi to all C programmers, my desire is with help of more experienced guys/girls to boost the following function:
// ### Mix(2in1) of Karp-Rabin & Boyer-Moore-Horspool algorithm [
// Caution: For better speed the case 'if (cbPattern==1)' was removed, so Pattern must be longer than 1 char.
char * Railgun_Quadruplet (char * pbTarget,
char * pbPattern,
unsigned long cbTarget,
unsigned long cbPattern)
{
char * pbTargetMax = pbTarget + cbTarget;
register unsigned long ulHashPattern;
unsigned long ulHashTarget;
unsigned long count;
unsigned long countSTATIC;
// unsigned long countRemainder;/*
const unsigned char SINGLET = *(char *)(pbPattern);
const unsigned long Quadruplet2nd = SINGLET<<8;
const unsigned long Quadruplet3rd = SINGLET<<16;
const unsigned long Quadruplet4th = SINGLET<<24;
*/
unsigned char SINGLET;
unsigned long Quadruplet2nd;
unsigned long Quadruplet3rd;
unsigned long Quadruplet4th;unsigned long AdvanceHopperGrass; long i; //BMH needed int a, j, bm\_bc\[ASIZE\]; //BMH needed unsigned char ch; //BMH needed// unsigned char lastch, firstch; //BMH needed
if (cbPattern > cbTarget) return(NULL);// Doesn't work when cbPattern = 1
// The next IF-fragment works very well with cbPattern>1, OBVIOUSLY IT MUST BE UNROLLED(but crippled with less functionality) SINCE either cbPattern=2 or cbPattern=3!
if ( cbPattern<4) { // This IF makes me unhappy: it slows down from 390KB/clock to 367KB/clock for 'fast' pattern. This fragment(for 2..3 pattern lengths) is needed because I need a function different than strchr but sticking to strstr i.e. lengths above 1 are to be handled.
pbTarget = pbTarget+cbPattern;
ulHashPattern = ( (*(char *)(pbPattern))<<8 ) + *(pbPattern+(cbPattern-1));
// countSTATIC = cbPattern-2;if ( cbPattern==3) {
for ( ;; )
{
if ( ulHashPattern == ( (*(char *)(pbTarget-3))<<8 ) + *(pbTarget-1) ) {
if ( *(char *)(pbPattern+1) == *(char *)(pbTarget-2) ) return((pbTarget-3));
}
if ( (char)(ulHashPattern>>8) != *(pbTarget-2) ) pbTarget++;
pbTarget++;
if (pbTarget > pbTargetMax)
return(NULL);
}
} else {
}
for ( ;; )
{
// The line below gives for 'cbPattern'>=1:
// Karp_Rabin_Kaze_4_OCTETS_hits/Karp_Rabin_Kaze_4_OCTETS_clocks: 4/543
// Karp_Rabin_Kaze_4_OCTETS performance: 372KB/clock
/*
if ( (ulHashPattern -
Hi to all C programmers, my desire is with help of more experienced guys/girls to boost the following function:
// ### Mix(2in1) of Karp-Rabin & Boyer-Moore-Horspool algorithm [
// Caution: For better speed the case 'if (cbPattern==1)' was removed, so Pattern must be longer than 1 char.
char * Railgun_Quadruplet (char * pbTarget,
char * pbPattern,
unsigned long cbTarget,
unsigned long cbPattern)
{
char * pbTargetMax = pbTarget + cbTarget;
register unsigned long ulHashPattern;
unsigned long ulHashTarget;
unsigned long count;
unsigned long countSTATIC;
// unsigned long countRemainder;/*
const unsigned char SINGLET = *(char *)(pbPattern);
const unsigned long Quadruplet2nd = SINGLET<<8;
const unsigned long Quadruplet3rd = SINGLET<<16;
const unsigned long Quadruplet4th = SINGLET<<24;
*/
unsigned char SINGLET;
unsigned long Quadruplet2nd;
unsigned long Quadruplet3rd;
unsigned long Quadruplet4th;unsigned long AdvanceHopperGrass; long i; //BMH needed int a, j, bm\_bc\[ASIZE\]; //BMH needed unsigned char ch; //BMH needed// unsigned char lastch, firstch; //BMH needed
if (cbPattern > cbTarget) return(NULL);// Doesn't work when cbPattern = 1
// The next IF-fragment works very well with cbPattern>1, OBVIOUSLY IT MUST BE UNROLLED(but crippled with less functionality) SINCE either cbPattern=2 or cbPattern=3!
if ( cbPattern<4) { // This IF makes me unhappy: it slows down from 390KB/clock to 367KB/clock for 'fast' pattern. This fragment(for 2..3 pattern lengths) is needed because I need a function different than strchr but sticking to strstr i.e. lengths above 1 are to be handled.
pbTarget = pbTarget+cbPattern;
ulHashPattern = ( (*(char *)(pbPattern))<<8 ) + *(pbPattern+(cbPattern-1));
// countSTATIC = cbPattern-2;if ( cbPattern==3) {
for ( ;; )
{
if ( ulHashPattern == ( (*(char *)(pbTarget-3))<<8 ) + *(pbTarget-1) ) {
if ( *(char *)(pbPattern+1) == *(char *)(pbTarget-2) ) return((pbTarget-3));
}
if ( (char)(ulHashPattern>>8) != *(pbTarget-2) ) pbTarget++;
pbTarget++;
if (pbTarget > pbTargetMax)
return(NULL);
}
} else {
}
for ( ;; )
{
// The line below gives for 'cbPattern'>=1:
// Karp_Rabin_Kaze_4_OCTETS_hits/Karp_Rabin_Kaze_4_OCTETS_clocks: 4/543
// Karp_Rabin_Kaze_4_OCTETS performance: 372KB/clock
/*
if ( (ulHashPatternIf you cool down the processor using Liquid Nitrogen, you should be able to achieve BACON time matches. Add a
CListCtrlbased front end and Robert's your Mother's Brother.
Panic, Chaos, Destruction. My work here is done. Drink. Get drunk. Fall over - P O'H OK, I will win to day or my name isn't Ethel Crudacre! - DD Ethel Crudacre I cannot live by bread alone. Bacon and ketchup are needed as well. - Trollslayer Have a bit more patience with newbies. Of course some of them act dumb - they're often *students*, for heaven's sake - Terry Pratchett
-
If you cool down the processor using Liquid Nitrogen, you should be able to achieve BACON time matches. Add a
CListCtrlbased front end and Robert's your Mother's Brother.
Panic, Chaos, Destruction. My work here is done. Drink. Get drunk. Fall over - P O'H OK, I will win to day or my name isn't Ethel Crudacre! - DD Ethel Crudacre I cannot live by bread alone. Bacon and ketchup are needed as well. - Trollslayer Have a bit more patience with newbies. Of course some of them act dumb - they're often *students*, for heaven's sake - Terry Pratchett
BINGO!
'As programmers go, I'm fairly social. Which still means I'm a borderline sociopath by normal standards.' Jeff Atwood
-
If you cool down the processor using Liquid Nitrogen, you should be able to achieve BACON time matches. Add a
CListCtrlbased front end and Robert's your Mother's Brother.
Panic, Chaos, Destruction. My work here is done. Drink. Get drunk. Fall over - P O'H OK, I will win to day or my name isn't Ethel Crudacre! - DD Ethel Crudacre I cannot live by bread alone. Bacon and ketchup are needed as well. - Trollslayer Have a bit more patience with newbies. Of course some of them act dumb - they're often *students*, for heaven's sake - Terry Pratchett
-
Hi to all C programmers, my desire is with help of more experienced guys/girls to boost the following function:
// ### Mix(2in1) of Karp-Rabin & Boyer-Moore-Horspool algorithm [
// Caution: For better speed the case 'if (cbPattern==1)' was removed, so Pattern must be longer than 1 char.
char * Railgun_Quadruplet (char * pbTarget,
char * pbPattern,
unsigned long cbTarget,
unsigned long cbPattern)
{
char * pbTargetMax = pbTarget + cbTarget;
register unsigned long ulHashPattern;
unsigned long ulHashTarget;
unsigned long count;
unsigned long countSTATIC;
// unsigned long countRemainder;/*
const unsigned char SINGLET = *(char *)(pbPattern);
const unsigned long Quadruplet2nd = SINGLET<<8;
const unsigned long Quadruplet3rd = SINGLET<<16;
const unsigned long Quadruplet4th = SINGLET<<24;
*/
unsigned char SINGLET;
unsigned long Quadruplet2nd;
unsigned long Quadruplet3rd;
unsigned long Quadruplet4th;unsigned long AdvanceHopperGrass; long i; //BMH needed int a, j, bm\_bc\[ASIZE\]; //BMH needed unsigned char ch; //BMH needed// unsigned char lastch, firstch; //BMH needed
if (cbPattern > cbTarget) return(NULL);// Doesn't work when cbPattern = 1
// The next IF-fragment works very well with cbPattern>1, OBVIOUSLY IT MUST BE UNROLLED(but crippled with less functionality) SINCE either cbPattern=2 or cbPattern=3!
if ( cbPattern<4) { // This IF makes me unhappy: it slows down from 390KB/clock to 367KB/clock for 'fast' pattern. This fragment(for 2..3 pattern lengths) is needed because I need a function different than strchr but sticking to strstr i.e. lengths above 1 are to be handled.
pbTarget = pbTarget+cbPattern;
ulHashPattern = ( (*(char *)(pbPattern))<<8 ) + *(pbPattern+(cbPattern-1));
// countSTATIC = cbPattern-2;if ( cbPattern==3) {
for ( ;; )
{
if ( ulHashPattern == ( (*(char *)(pbTarget-3))<<8 ) + *(pbTarget-1) ) {
if ( *(char *)(pbPattern+1) == *(char *)(pbTarget-2) ) return((pbTarget-3));
}
if ( (char)(ulHashPattern>>8) != *(pbTarget-2) ) pbTarget++;
pbTarget++;
if (pbTarget > pbTargetMax)
return(NULL);
}
} else {
}
for ( ;; )
{
// The line below gives for 'cbPattern'>=1:
// Karp_Rabin_Kaze_4_OCTETS_hits/Karp_Rabin_Kaze_4_OCTETS_clocks: 4/543
// Karp_Rabin_Kaze_4_OCTETS performance: 372KB/clock
/*
if ( (ulHashPatternI did read what was stated, but along with question the code being the fastest (to my knowledge) fits well in 'clever code' context, obviously you don't think so, so feel free to delete it. And I didn't expect such negative reactions from old members, maybe you are too versed in C to disregard such code without giving even the tiny argument.
Get down get down get down get it on show love and give it up What are you waiting on?
-
I did read what was stated, but along with question the code being the fastest (to my knowledge) fits well in 'clever code' context, obviously you don't think so, so feel free to delete it. And I didn't expect such negative reactions from old members, maybe you are too versed in C to disregard such code without giving even the tiny argument.
Get down get down get down get it on show love and give it up What are you waiting on?
Sanmayce wrote:
obviously you don't think so
Now, now, we all act like this because your post started with a "here's my best code, can someone improve it?" that classified as programming question. I suggest you changed it to something like "Here's a code to optimize xxx how's your opinion about it?". I'm sure you'll get much better response that way.
Excuse me for my improper grammar and typos. It's because English is my primary language, not my first language. My first languages are C# and Java. VB, ASP, JS, PHP and SQL are my second language. Indonesian came as my third language. My fourth language? I'm still creating it, I'll let you know when it's done! :-D
-
BINGO!
'As programmers go, I'm fairly social. Which still means I'm a borderline sociopath by normal standards.' Jeff Atwood
are you kidding?
-
are you kidding?
No. I was kidding, he was calling bingo as I hit almost every CP meme in a single post. I missed out the delightful Miss Hayek[^].
Panic, Chaos, Destruction. My work here is done. Drink. Get drunk. Fall over - P O'H OK, I will win to day or my name isn't Ethel Crudacre! - DD Ethel Crudacre I cannot live by bread alone. Bacon and ketchup are needed as well. - Trollslayer Have a bit more patience with newbies. Of course some of them act dumb - they're often *students*, for heaven's sake - Terry Pratchett
-
No. I was kidding, he was calling bingo as I hit almost every CP meme in a single post. I missed out the delightful Miss Hayek[^].
Panic, Chaos, Destruction. My work here is done. Drink. Get drunk. Fall over - P O'H OK, I will win to day or my name isn't Ethel Crudacre! - DD Ethel Crudacre I cannot live by bread alone. Bacon and ketchup are needed as well. - Trollslayer Have a bit more patience with newbies. Of course some of them act dumb - they're often *students*, for heaven's sake - Terry Pratchett
You forgot a latex suit mention. :-O
If you vote me down, my score will only get lower
-
You forgot a latex suit mention. :-O
If you vote me down, my score will only get lower
It is a "Latex Appendage Suit" and I'm not going near it after John...
Panic, Chaos, Destruction. My work here is done. Drink. Get drunk. Fall over - P O'H OK, I will win to day or my name isn't Ethel Crudacre! - DD Ethel Crudacre I cannot live by bread alone. Bacon and ketchup are needed as well. - Trollslayer Have a bit more patience with newbies. Of course some of them act dumb - they're often *students*, for heaven's sake - Terry Pratchett
-
It is a "Latex Appendage Suit" and I'm not going near it after John...
Panic, Chaos, Destruction. My work here is done. Drink. Get drunk. Fall over - P O'H OK, I will win to day or my name isn't Ethel Crudacre! - DD Ethel Crudacre I cannot live by bread alone. Bacon and ketchup are needed as well. - Trollslayer Have a bit more patience with newbies. Of course some of them act dumb - they're often *students*, for heaven's sake - Terry Pratchett
In the words of Hong Kong Phooey..... Could be!
If you vote me down, my score will only get lower