translate at warp speed

Summary: -------- Jack Parker, Robert Minter, and I have been having some fun developing a reasonably general purpose Informix 4GL callable function for doing substring search and replace. Calling syntax for this function is: CALL translate ( old, new, stringin ) RETURNING stringout or LET stringout = translate ( old, new, stringin ) Jack and Robert's 4GL functions work well, but this is such a low-level function that I thought to try writing it in C. The result is largely what I expected, the C version runs 15-20 times faster than the 4GL versions. If you do this type of string translation only a few times in your program, you would probably want to use either Jack's or Robert's functions, which were posted earlier. This way, your entire program can be in 4GL, and you don't need to worry about the minor differences in parameter fetching sequence, which I discuss below. However, for those of you who may need to do such translations thousands or more times, I offer my C version for your use. Please see the notes below regarding parameter fetching. For those who care, I also describe below the method I used to time-test the various functions. Happy computing. Alan Popiel C source code: O / ===============================X--------------------------------------------- O \\ /* Author: R. Alan Popiel * Date: 12 Nov 1993 * * usage: * CALL translate ( old, new, strin ) RETURNING strout * LET strout = translate ( old, new, strin ) * * translate() replaces all occurences of 'old' in 'strin' with 'new', * returning the result in 'strout' * this function is callable from Informix 4GL * * maximum lengths of input and output strings: * old, new are limited to 256 characters * strin, strout are limited to 512 characters */ #include <string.h> #define SPACE ' ' translate (nparms) int nparms; { char old[257]; /* old pattern to seek */ char new[257]; /* new pattern to replace 'old' */ char strin[513]; /* string in which to do replacement */ char strout[513]; /* resulting string */ int lo, ln, ls; /* string lengths */ char *sin, *sout; /* pointers for 'strin', 'strout' */ char *pfound; /* pointer to 'old' in 'strin' */ int offset; /* number of chars between sin and pfound */ /* fetch arguments; note that 'nparms', number of arguments, is NOT checked for correct value 3 */ popquote( strin, sizeof(strin) ); popquote( new, sizeof(new) ); popquote( old, sizeof(old) ); /* initializations */ ls = strlen( strin ); ln = strlen( new ); lo = strlen( old ); sin = strin; /* 'aliases' for input and output strings */ sout = strout; strout[0] = NULL; /* trim off trailing blanks */ while ( strin[ls-1] == SPACE ) ls--; strin[ls] = NULL; while ( new[ln-1] == SPACE ) ln--; new[ln] = NULL; while ( old[lo-1] == SPACE ) lo--; old[lo] = NULL; /* loop until input string is exhausted */ while ( *sin != NULL ) { pfound = strstr( sin, old ); if ( pfound != NULL ) { /* 'old' found in 'strin' */ offset = pfound - sin; strncpy( sout, sin, offset ); /* copy up to 'old' */ sout = sout + offset; strcpy( sout, new ); /* copy 'new' to 'strout' */ sout = sout + ln; sin = pfound + lo; /* position past 'old' in 'strin' */ } else { /* no more 'old' exist in 'strin' */ strcpy( sout, sin ); /* copy the end of 'strin' to 'strout' */ break; } } /* end while loop on input string */ pushquote( strout, sizeof(strout)-1 ); return(1); } /* end function 'translate' */ O / ===============================X--------------------------------------------- O \\ Parameter fetching notes: ------------------------- The above 'popquote()' and 'pushquote()' work with Informix C4gl version 2.10. Jack Parker tells me that for Informix C4gl 4.10, he needed to change the code to this: /* fetch arguments */ popint(&ls); popquote( strin, ls ); popint(&ln); popquote( new, ln ); popint(&lo); popquote( old, lo ); ... retquote( strout ); Therefore, if you use my function, I *strongly* recommend that you compile the following empty function and look at the C code generated by your version of the c4gl compilation script. BTW, this is the empty function that I used in the timing tests. FUNCTION empty ( a, b, c ) DEFINE a, b CHAR(256), c CHAR(512), d CHAR(512) RETURN d END FUNCTION Timing trivia: -------------- To time the various versions of the 'translate' function, I wrote a test driver main routine in 4GL which does the following: 1. opens a report file; 2. outputs to the report before starting the loop described below; the report saves the time (from the report TIME keyword) in a global variable; 3. calls the function 1000 times in a FOR loop (except that the C version was called 10,000 times); 4. outputs to the report after the loop; the report computes the elapsed time using the TIME keyword and the value saved in step 2, and divides by the loop count to get the time per function execution; 5. the report-loop-report sequence was repeated for four test cases: a. the empty function, to compute the function call and loop overhead; b. new substring shorter than old substring; c. new substring longer than old substring; d. new substring same size as old substring; 6. closes the report. The input string was 66 or 72 bytes long; the old and new substrings were 9 and 6 bytes, 6 and 9 bytes, and 9 and 9 bytes for tests 5b, 5c, 5d, respectively. In all cases, two occurrences of the old substring were replaced by the new substring. The timing results below are for a Sun SPARCstation SLC, running Informix compiled 4GL version 2.10. Your mileage may vary. empty function call and loop overhead: 0.5-0.6 ms per call Jack's first version, with extend and compact: 70, 49, 35 ms per call Robert's version: 45, 41, 39 ms per call Jack's third version: 39, 42, 33 ms per call Alan's version, in C: 1.8, 1.2, 1.3 ms per call Call and loop overhead has been subtracted out of all function times. Except for the overhead test, times are for lengths new < old, new > old, and new = old, respectively. Jack Parker sent me his timing results, run on an HP 9000/847. Relative orders of magnitude between the various techniques were similar, except: his server class machine beat the tar out of my workstation class machine, Robert's version ran slowest, and the odd slow time (70 ms on my machine) did not appear in his results. This might be because of different com- pilers / instr