Re: Count string in string with loop increase 2, why is this not faster?

Subject	Re: Count string in string with loop increase 2, why is this not faster?
Newsgroups	comp.lang.c
References	(3 earlier) <eWhdC.310374$Og3.127736@fx11.am4> <323b5966-2f70-43b0-82af-48ae15f00ed3@googlegroups.com> <87po5m1983.fsf@bsb.me.uk> <c8f04906-878b-466d-9be4-dfbe1afd7eb2@googlegroups.com> <dkkdC.405473$NO7.218043@fx43.am4>
From	bartc <bc@freeuk.com>
Message-ID	<VpkdC.1521855$OX.7252@fx47.am4> (permalink)
Organization	virginmedia.com
Date	2018-02-03 15:19 +0000

Show all headers | View raw

On 03/02/2018 15:13, bartc wrote:
> On 03/02/2018 14:38, Bart Smissaert wrote:
>>> Are you sure that both your strings are UTF-16 encoded and with the same
>> byte order?
>>
>> 100% sure as they are normal string variables in VBA.
>>
>>> I tested with string like this:
>>
>>      strSearch = 
>> "abababababababababababababababababababababababababababababababababababababababab" 
>>
>>
>>
>> strFind = "abab" or strFind = "baba"
> 
> OK, I think I've found the issue. If you take out the memcmp part of the 
> two main loops of each function, then one is executed 77 times, the 
> other 39 times, which is what you might have expected.
> 
> But as it is, each is executed 20 times.

Using "abab". With "baba", one was 21 times, the other 20.

The following is the test setup I used, with various bits of code that I 
commented in or out as I did various tests.

(This was done with a compiler that I don't think supports wide strings 
so they were expanded manually.)

----------------------------------------

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char 
*searchstr8="abababababababababababababababababababababababababababababababababababababababab";
short searchstr16[500];

char *findstr8="abab";
//char *findstr8="baba";
//char *findstr8="fish";
short findstr16[10];

int nmemcmp1;
int nmemcmp2;

int test1(unsigned char *strSearch, unsigned char *strFind, int nSearch, 
int nFind)
{
     int i = 0;
     int countstring = 0;

     if (nSearch == 0 || nFind == 0) {
         return 0;
     }

     for (i = 0; i <= nSearch - nFind; i++) {
////printf("1: i=%d\n",i);
++nmemcmp1;
         if (memcmp(strSearch + i, strFind, nFind) == 0) {
             countstring++;
             i += nFind - 1;
         }
     }

     return countstring;
}

int test2(unsigned char *strSearch, unsigned char *strFind, int nSearch, 
int nFind)
{
     int i = 0;
     int countstring = 0;

     if (nSearch == 0 || nFind == 0) {
         return 0;
     }

     for (i = 0; i <= nSearch - nFind; i += 2) {
//printf("2: i=%d\n",i);
++nmemcmp2;
         if (memcmp(strSearch + i, strFind, nFind) == 0) {
             countstring++;
             i = i + (nFind - 2);
         }
     }

     return countstring;
}

int main(void) {
int nfind, nsearch, i, count;

nsearch=strlen(searchstr8);
for (i=0; i<nsearch; ++i) searchstr16[i] = searchstr8[i]; // assume ascii

nfind=strlen(findstr8);
for (i=0; i<nfind; ++i) findstr16[i] = findstr8[i];

//for (i=0; i<1000000; ++i) {
for (i=0; i<1; ++i) {
     count += test1((char*)searchstr16,(char*)findstr16, nsearch, nfind);
//  count += test2((char*)searchstr16,(char*)findstr16, nsearch, nfind);
}

printf("Nsearch = %d\n",nsearch);
printf("Nfind   = %d\n",nfind);
printf("Count   = %d\n",count);
printf("MEMCMP1 = %d\n",nmemcmp1);
printf("MEMCMP2 = %d\n",nmemcmp2);
puts("");
}

Thread

csiph-web