replace function efficiency

Here's some general hints:

Save a ton of memory and copying by making the changes in-place.  You can do it if
you first scan the text for your pattern and just record those places (can even be done right
in the text if the pattern is long enough.  Then go back and make the changes.  If the
replacement string is longer than the original, you'll have to grow the memory bloack and process the text backwards,  otherwise process it forwards.  This saves a ton of string moves and temporaries and copies.

Search for the least likely character in your search string.  This will give you the fewest false hits.

Don't restore the whole buffer after each replace, just copy the minimum needed.

If the outptu text is going into some sequential consumer task, then you can optimize things even more
by passing on the data without ever having actually made a complete copy of it.

Hope this helps,


grg99

the data it returns is then dumped out and then sent over a tcp/ip connection.  my main problem is the search speed.  if you could create the code for it i'd love you guys even more :)

btw, the programmer who built this was killed in a car accident a year or so ago.. I can do some coding 2 years of college stuff but not really to indepth info on c/c++ so i'm dumbfound on this.

The calling function should check the value of the pointer to haystack after the function returns.  If it's the same (t == x), then no substitutions occured.  Do not free(t).  If (t != x) then at least one substitution occured and you must free(t).  In my test, 25 million iterations took 111 seconds on a 700 MHz P3 running RHL7.2.

main () {

    char *t, *x;

    int i;
    time_t s, e;

    printf ("%lu\n", s = time(NULL));

    for (i = 0; i < 25000000; i++)
    {
        x = "This is a test of substituting %%CODE%% with 'new value' everywhere that %%CODE%% is seen";
        t = replace (x, "%%CODE%%", "new value");
        if (t != NULL && t != x) free (t);
    }

    printf ("%lu\n", e = time(NULL));
    printf ("%lu\n", e - s);


}
"test.c" 78L, 1550C written
[root@pp170a tmp]# cc test.c -o test
[root@pp170a tmp]# ./test
1057788609
1057788711
102

err...102 seconds

looks promising only problem is i get this error.


email_func.cpp: In function `char * replace(char *, char *, char *)':
email_func.cpp:139: ANSI C++ forbids implicit conversion from `void *' in assignment

this is a freebsd box using gmake.. any ideas?  it throws a erorr saying run stdlib.h which is already called anyway.  that line thats spitting the error is this line


if ((newbuf = malloc (newlen + 1)) != NULL)

You can explicity typecast the call to malloc() as in:

if ((newbuf = (char *) malloc(newlen + 1)) != NULL)
{
    /* blah, blah */
}

OR even more paranoid:

if ((newbuf = (char *) malloc(newlen + 1)) != (char *) NULL)
{
    /* blah, blah */
}

I tend to think that the first one of these two will correct the problem.

Same code on linux takes 5 seconds.
I'll test it using the same "strings" as cgi-in used just for comparison.

Here it is with 25 million iterations using the same strings as cgi-bin used:
58 seconds.

pb@linux:/home/pb/test> time ./r
[This is a test of substituting new value with 'new value' everywhere that new value is seen]
   58.72s real    58.60s user     0.04s system
pb@linux:/home/pb/test>

Nice implementation and the length of the string makes a big difference.  I used zebada's strings using my algorithm and ET dropped from 102 down to 69 seconds.  His compiled on mine and runs in 59 seconds.

email_func.cpp: In function `char * replace(char *, char *, char *)':
email_func.cpp:165: ANSI C++ forbids implicit conversion from `void *' in assignment
email_func.cpp:171: warning: value computed is not used
email_func.cpp:171: warning: value computed is not used
email_func.cpp:176: ANSI C++ forbids implicit conversion from `void *' in assignment
email_func.cpp:190: ANSI C++ forbids implicit conversion from `void *' in assignment

each one of those ANSI errors is where a malloc is.. guys wanna help me out with the type casting on it?

Change to:
matchList = (char **)malloc(GRAIN*sizeof(char *));
if ( (tmp=(char **)realloc(matchList,GRAIN*matchListSize*sizeof(char *)))==NULL ) {

result = (char *)malloc(resultLength+1);
Note the number of asterisks is different in the first two!

What does line 171 contian?
I'm guessing it's *s++ which should be changed to s++

Hey cgi, you said you were running on PIII 700 and it runs in 59 seconds.
I'm running P4 (I said PIII before - actually its a P4) 1.5GHz and it runs in 58 seconds.
Go figure! I wasted my money :(

I can't claim to have thought up the method I used - I just implemented grg99's comment.

Paul

I am suggesting a solution which should work faster with a little expense in terms of memory

 tmpstr=(char *) malloc(strlen(str)+strlen(val)*4086);      ------------ get rid of this malloc ... if your function won't be called from
                                                                                          -------------two or more processes then use a static array big enough
                                                                                          -------------for your needs .... you have already cut down on 3 million
                                                                                          ------------- mallocs and free which is substantial execution time


#define BIG_ENOUGH_MEMORY 1024

char * replace(char * str,char *code,char * val){
char * needle, *track;
static char tmpstr [BIG_ENOUGH_MEMORY];
tmpstr = '\0';
track = str;

 while(  ( needle = strstr(track,code) ) != NULL  )  //as long as we have code in str
          {
           strncat ( tmpstr, track, needle - track );          // add everything from previous find uptill this find
           strcat ( tmpstr, val);                                        // add val
           track = needle + strlen (code);                       // advance track to end this find
          }
strcat ( tmpstr, track);                                               // add last part of str after last find
return tmpstr;
}

I haven't compiled/tested the code but I feel it should be a good start atleast

The static is a good idea - getting rid of the malloc/free is a good saving.

But the strncat, strlen and strcat inside the loop - now that is wasteful - especially if the strings are not small.
Each time one of those functions is called it has to iterate a counter over the entire length of the string looking for the null terminator.
I would be interested to see a working version of your code to see if it is quicker or not.

Regards
Paul

If BIG_ENOUGH_MEMORY isn't big enough, the program is vulnerable to a buffer overrun, isn't it?

I just tested Sunnycoder's suggestion and it does the 25,000,000 iterations in 20 seconds. That's better then twice as fast.

malloc() is the speed killer.

However, I then ran a test where the string length is about 10K and there are 120 substitutions to be done.
The code with the malloc did 25,000 iterations in 2.5 seconds.
The code with the strcat, strlen did 25,000 iterations in 13.7 seconds.
(25,000,000 would have taken too long)

So for short strings <1K, I'd say go with Sunnycoder's solution,
for longer strings (>1K) go with the one I submitted.

Or better still use a static (as Sunnycoder suggests) in my solution - just make it big enough to hold the biggest string you expect to encounter.

Regards
Paul

It would also help if we knew how often the input file changes,
how often the patterns to search for change, and how often the
replacement strings change.

Or can we form a queue of files to be changed-- sort them
by similarities so we can minimize the number of repeated searches.
In other words, if we have a backlog of say 50 files to do,
if we can identify that TEN of the input files are the same one,
with only changes in the stuff to substitute, we only have to
search ONCE, and do the ten replacements in parallel,
or just refer to a cached list of places to replace text.
Similarly for replacements, if we can identify similar input files,
and/or similar replacements to be made, we can reduce the
work by a HUGE factor, without even encroaching on any
changes in the search/replace algorithms.






 The idea is we may be able to cache
some of the information we get from the searches, or even
cache the replaced output.  That would bring the time down to zero.

the string changes once a day. the times that it replaces a token is 1 to 25 depends on the string.  there are also 2 or 3 diff tokens that have to be ran through and sorted.  right now it looks like

res = replace(res,"%%TOKEN1%%",replaceFirst)
res = replace(res,"%%TOKEN2%%",replacedSecond)