K&R2 ex. 2-4: Heathfield's gross inefficiency

[Chris McDonald]

I can't find any evidence that this is what either of them meant. You
do have any, or this simply a device to get a good row going?

Both Hoare and Knuth consider the choice of data structure and/or
algorithm to be at the heart of good software design. It seems
extraordinarily unlikely that either would consider this something to
be avoided.

My comment was in reply to Antoninus's who, as I interpreted it,
suggested RH's code to have problems due to premature optimization.

Antoninus then stated that we "should just write well-engineered code
in the first place ...", and we all thought "well, of course, ...."

 

[Chris McDonald]

refacoring is only a part of optimization.

Only an incompetent would NOT consider efficiency (read optimization) at
a very early stage in ANY SW design.

Note the early != premature. And this is my point.

All agreed;
of note, the http://en.wikipedia.org/wiki/Code_refactoring discussion of
refactoring doesn't even mention refactoring as a form of optimization
(for runtime space or time), just as restructuring to better support
the static code's manipulation.

 

[jfbode1029]

On May 12, 8:46 pm, (e-mail address removed) wrote:
[snip]

char *squeezeImpl (char *s1, char *s2)
{
    char *tmp;

    if (*s1 == 0)
        return s1;

    tmp = strpbrk(s1, s2);

    if (!tmp)
    {
        return s1;
    }
    else if (tmp == s1)
    {
        memmove(s1,s1+1,strlen(s1));
        return squeezeImpl(s1, s2);
    }
    else if (tmp != (s1 + strlen(s1) + 1))
    {
        *tmp = 0;
        return strcat(s1, squeezeImpl(++tmp, s2));
    }

}

void squeeze(char *s1, char *s2)
{
   strcpy(s1, squeezeImpl(s1, s2));

}

God I love being an idiot in public. I just realized all of that crap
could be replaced with the following:

void squeeze(char *s1, char *s2)
{
char *tmp = NULL;
while (tmp = strpbrk(s1, s2))
{
*tmp = 0;
strcat(s1, ++tmp);
}
}

Too much Haskell on the brain. Anyway, it's useless for Heathfield's
original purpose, but it takes 30% less time on average than Twink's
version and is 80% less ugly (strpbrk() notwithstanding). I think it
illustrates a very important point which doesn't show up enough in
tutorial material; the standard library is your friend, so use it as
much as possible.

 

[Antoninus Twink]

  int seen[UCHAR_MAX+1];
  memset(seen, 0, (UCHAR_MAX+1) * sizeof *seen);

I don't see how someone could write such atrocious code as these two
lines, and then have the gall to criticize somebody else's code.

As you will probably guess, the memset is cruft left over from an
earlier version of the function - I started out having the seen buffer
dynamically allocated and preserved between calls to avoid having to
recompute it if the function was called twice with the same s2.

Unlike Heathfield, I'm perfectly happy to accept that this is ugly and
should be replace with a simple initializer - something I'd have done
myself in due course when I noticed it.

 

[Antoninus Twink]

Anyway, it's useless for Heathfield's original purpose, but it takes
30% less time on average than Twink's version and is 80% less ugly
(strpbrk() notwithstanding).

I can't reproduce anything like this timing... is it possible that your
profiler is missing the time spent in the shared library functions
strpbrk() and strcat()?

I used this test code:

int main(int argc, char **argv)
{
int iter, i, j, len = (argc > 1) ? atoi(argv[1]) : 10;
char *s[2], *s1;
s[0] = malloc(len+1);
s[1] = malloc(len+1);
s1 = malloc(len+1);
for(iter=0; iter < 1<<20; iter++) {
for(i=0; i<2; i++)
for(j=0; j<len; j++)
s[j] = 'a' + drand48() * 26;
s[0][len]=s[1][len]=0;
strcpy(s1, s[0]);
squeezeRH(s1, s[1]);
strcpy(s1, s[0]);
squeezeAT(s1, s[1]);
strcpy(s1, s[0]);
squeezeJFB(s1, s[1]);
}
return 0;
}

I compiled it statically so that standard library calls get included in
the profile:
gcc -O2 -pg -static a.c -o a

For the short strings case (similar to Heathfield's testbed),
corresponding to a command line argument of 10, I found:

% cumulative self self total
time seconds seconds calls ms/call ms/call name
26.34 0.27 0.27 1048576 0.00 0.00 squeezeRH
20.49 0.48 0.21 strpbrk
13.66 0.62 0.14 1048576 0.00 0.00 squeezeAT
6.83 0.90 0.07 strcat
0.00 1.03 0.00 1048576 0.00 0.00 squeezeJFB

Totals: RH 0.27
JFB 0.28
AT 0.14

What about slightly longer strings? Here's the profile with a command
line argument of 80, standard length of a line in a text file.

% cumulative self self total
time seconds seconds calls s/call s/call name
56.59 11.38 11.38 strpbrk
16.42 14.68 3.30 1048576 0.00 0.00 squeezeRH
12.54 17.20 2.52 strcat
1.94 18.86 0.39 1048576 0.00 0.00 squeezeJFB
1.84 19.23 0.37 1048576 0.00 0.00 squeezeAT

Totals: RH 3.30
JFB 14.29
AT 0.37

Of course, when it comes to longer strings (command line argument of
500), the linear time algorithm wipes the floor with the two quadratic
algorithms.

% cumulative self self total
time seconds seconds calls s/call s/call name
84.32 399.60 399.60 strpbrk
7.52 435.21 35.62 strcat
4.46 456.34 21.13 1048576 0.00 0.00 squeezeRH
0.41 467.68 1.94 1048576 0.00 0.00 squeezeJFB
0.27 472.43 1.30 1048576 0.00 0.00 squeezeAT

Totals: RH 21.13
JFB 437.16
AT 1.30

I think it illustrates a very important point which doesn't show up
enough in tutorial material; the standard library is your friend, so
use it as much as possible.

I think the important point it illustrates is that making a good choice
algorithm should be your number one priority, and everything else will
often pretty well take care of itself.

 

[user923005]

Anyway, it's useless for Heathfield's original purpose, but it takes
30% less time on average than Twink's version and is 80% less ugly
(strpbrk() notwithstanding).

I can't reproduce anything like this timing... is it possible that your
profiler is missing the time spent in the shared library functions
strpbrk() and strcat()?

I used this test code:

int main(int argc, char **argv)
{
  int iter, i, j, len = (argc > 1) ? atoi(argv[1]) : 10;
  char *s[2], *s1;
  s[0] = malloc(len+1);
  s[1] = malloc(len+1);
  s1 = malloc(len+1);
  for(iter=0; iter < 1<<20; iter++) {
    for(i=0; i<2; i++)
      for(j=0; j<len; j++)
        s[j] = 'a' + drand48() * 26;
    s[0][len]=s[1][len]=0;
    strcpy(s1, s[0]);
    squeezeRH(s1, s[1]);
    strcpy(s1, s[0]);
    squeezeAT(s1, s[1]);
    strcpy(s1, s[0]);
    squeezeJFB(s1, s[1]);
  }
  return 0;

}

I compiled it statically so that standard library calls get included in
the profile:
gcc -O2 -pg -static a.c -o a

For the short strings case (similar to Heathfield's testbed),
corresponding to a command line argument of 10, I found:

  %   cumulative   self              self     total          
 time   seconds   seconds    calls  ms/call  ms/call  name    
 26.34      0.27     0.27  1048576     0.00     0.00  squeezeRH
 20.49      0.48     0.21                             strpbrk
 13.66      0.62     0.14  1048576     0.00     0.00  squeezeAT
  6.83      0.90     0.07                             strcat
  0.00      1.03     0.00  1048576     0.00     0.00  squeezeJFB

Totals: RH  0.27
        JFB 0.28
        AT  0.14

What about slightly longer strings? Here's the profile with a command
line argument of 80, standard length of a line in a text file.

  %   cumulative   self              self     total          
 time   seconds   seconds    calls   s/call   s/call  name    
 56.59     11.38    11.38                             strpbrk
 16.42     14.68     3.30  1048576     0.00     0.00  squeezeRH
 12.54     17.20     2.52                             strcat
  1.94     18.86     0.39  1048576     0.00     0.00  squeezeJFB
  1.84     19.23     0.37  1048576     0.00     0.00  squeezeAT

Totals: RH   3.30
        JFB 14.29
        AT   0.37

Of course, when it comes to longer strings (command line argument of
500), the linear time algorithm wipes the floor with the two quadratic
algorithms.

  %   cumulative   self              self     total          
 time   seconds   seconds    calls   s/call   s/call  name    
 84.32    399.60   399.60                             strpbrk
  7.52    435.21    35.62                             strcat
  4.46    456.34    21.13  1048576     0.00     0.00  squeezeRH
  0.41    467.68     1.94  1048576     0.00     0.00  squeezeJFB
  0.27    472.43     1.30  1048576     0.00     0.00  squeezeAT

Totals: RH   21.13
        JFB 437.16
        AT    1.30

I think it illustrates a very important point which doesn't show up
enough in tutorial material; the standard library is your friend, so
use it as much as possible.

I think the important point it illustrates is that making a good choice
algorithm should be your number one priority, and everything else will
often pretty well take care of itself.

For a student exercise such as those found in K&R2, clarity should be
paramount.
Given that two simple routines have the same clarity, then efficiency
becomes important.
Efficiency can be measured in terms of speed of execution and also
space consumed.
My profile is found at the bottom in a comment.

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

void sofsqueeze(char *s, const char *t)
{
int i,
j,
k;
int found = 0;
for (i = j = 0; s != '\0'; i++) {
found = 0;
for (k = 0; t[k] != '\0' && (found == 0); k++) {
if (t[k] == s) {
found = 1;
}
}
if (found == 0) {
s[j++] = s;
}
}
s[j] = '\0';
}

void iansqueeze(char s1[], const char s2[])
{
int i;

for (i = 0; s2 != '\0'; i++) {
int j,
k;
for (k = j = 0; s1[k] != '\0'; k++) {
if (s2 != s1[k])
s1[j++] = s1[k];
}
s1[j] = '\0';
}
}

void simplesqueeze(char original[], const char squeeze[])
{
int i,
j,
k;
int k_length = (int) strlen(squeeze);
for (k = 0; k < k_length; k++) {
for (i = j = 0; original != '\0'; i++) {
if (original != squeeze[k])
original[j++] = original;
}
original[j] = '\0';
}
}

void atsqueeze(char *s1, const char *s2)
{
char *t;
int seen[UCHAR_MAX + 1] =
{0};
for (; *s2; s2++)
seen[(unsigned char) *s2] = 1;
for (t = s1; *s1; s1++)
if (!seen[(unsigned char) *s1])
*t++ = *s1;
*t = '\0';
}

/* k&r2, p47 squeeze */
static void krsqueeze(char s[], int c)
{
int i,
j;
for (i = j = 0; s != '\0'; i++)
if (s != c)
s[j++] = s;
s[j] = '\0';
}

void bartsqueeze(char s1[], const char s2[])
{
while (*s2)
krsqueeze(s1, *s2++);
}

void hartersqueeze(char *s1, const char *s2)
{
int i,
j,
k;
for (k = 0; s2[k] != '\0'; k++) {
for (i = j = 0; s1 != '\0'; i++) {
if (s1 != s2[k]) {
s1[j++] = s1;
}
}
}
s1[j] = 0;
}

void jbsqueeze(char *s1, const char *s2)
{
char *tmp = NULL;
while (tmp = strpbrk(s1, s2)) {
*tmp = 0;
strcat(s1, ++tmp);
}
}

/*
* Exercise 2-4 Page 48
*
* Write an alternate version of squeeze(s1,s2) that deletes each
* character in s1 that matches any character in the string s2.
*
*/

/* squeeze2: delete all characters occurring in s2 from string s1. */

void squeeze2(char s1[], const char s2[])
{
int i,
j,
k;
int instr2 = 0;

for (i = j = 0; s1 != '\0'; i++) {
instr2 = 0;
for (k = 0; s2[k] != '\0' && !instr2; k++) {
if (s2[k] == s1) {
instr2 = 1;
}
}

if (!instr2) {
s1[j++] = s1;
}
}
s1[j] = '\0';
}

/* test driver */

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

static char OriginalWord[256];
static char sofSqueezedWord[256];
static char ianSqueezedWord[256];
static char simpleSqueezedWord[256];
static char atSqueezedWord[256];
static char bartSqueezedWord[256];
static char harterSqueezedWord[256];
static char jbSqueezedWord[256];
static char rhSqueezedWord[256];

extern void sofsqueeze(char *, const char *);
extern void iansqueeze(char *, const char *);
extern void simplesqueeze(char *, const char *);
extern void atsqueeze(char *, const char *);
extern void bartsqueeze(char *, const char *);
extern void hartersqueeze(char *, const char *);
extern void jbsqueeze(char *, const char *);
extern void squeeze2(char *, const char *);

static const char letters[] =
{
'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h',
'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p',
'q', 'r', 's', 't', 'u', 'v', 'w', 'x',
'y', 'z', 'A', 'B', 'C', 'D', 'E', 'F',
'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N',
'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V',
'W', 'X', 'Y', 'Z',
};

static char used_letters[UCHAR_MAX + 1];

int main(void)
{
FILE *words = fopen("/dannfast/e_drive/dict/big.dict", "r");
int i;
for (i = 1; i < sizeof letters; i++) {
memcpy(used_letters, letters, i);
used_letters = 0;
while (fgets(OriginalWord, sizeof OriginalWord, words)) {
char *where = strchr(OriginalWord, '\n');
if (where)
*where = 0;
strcpy(sofSqueezedWord, OriginalWord);
strcpy(ianSqueezedWord, OriginalWord);
strcpy(simpleSqueezedWord, OriginalWord);
strcpy(atSqueezedWord, OriginalWord);
strcpy(bartSqueezedWord, OriginalWord);
strcpy(harterSqueezedWord, OriginalWord);
strcpy(jbSqueezedWord, OriginalWord);
strcpy(rhSqueezedWord, OriginalWord);
sofsqueeze(sofSqueezedWord, used_letters);
iansqueeze(ianSqueezedWord, used_letters);
simplesqueeze(simpleSqueezedWord, used_letters);
atsqueeze(atSqueezedWord, used_letters);
bartsqueeze(bartSqueezedWord, used_letters);
hartersqueeze(harterSqueezedWord, used_letters);
jbsqueeze(jbSqueezedWord, used_letters);
squeeze2(rhSqueezedWord, used_letters);
#ifdef CHECK_WORDS
if (strcmp(sofSqueezedWord, ianSqueezedWord) != 0)
printf("Bad output -> Original(%s), letters removed
(%s), sof(%s), ian(%s)\n", OriginalWord, used_letters,
sofSqueezedWord, ianSqueezedWord);
if (strcmp(sofSqueezedWord, simpleSqueezedWord) != 0)
printf("Bad output -> Original(%s), letters removed
(%s), sof(%s), simple(%s)\n", OriginalWord, used_letters,
sofSqueezedWord, simpleSqueezedWord);
if (strcmp(sofSqueezedWord, atSqueezedWord) != 0)
printf("Bad output -> Original(%s), letters removed
(%s), sof(%s), at(%s)\n", OriginalWord, used_letters, sofSqueezedWord,
atSqueezedWord);
if (strcmp(sofSqueezedWord, bartSqueezedWord) != 0)
printf("Bad output -> Original(%s), letters removed
(%s), sof(%s), bart(%s)\n", OriginalWord, used_letters,
sofSqueezedWord, bartSqueezedWord);
if (strcmp(sofSqueezedWord, harterSqueezedWord) != 0)
printf("Bad output -> Original(%s), letters removed
(%s), sof(%s), harter(%s)\n", OriginalWord, used_letters,
sofSqueezedWord, harterSqueezedWord);
if (strcmp(sofSqueezedWord, jbSqueezedWord) != 0)
printf("Bad output -> Original(%s), letters removed
(%s), sof(%s), jb(%s)\n", OriginalWord, used_letters, sofSqueezedWord,
jbSqueezedWord);
if (strcmp(sofSqueezedWord, rhSqueezedWord) != 0)
printf("Bad output -> Original(%s), letters removed
(%s), sof(%s), rh(%s)\n", OriginalWord, used_letters, sofSqueezedWord,
rhSqueezedWord);
#endif
}
}
return 0;
}
/*
Function Name,Exclusive Samples,Exclusive Samples %,
"main",31,19.75,
"sofsqueeze",12,7.64,
"atsqueeze",11,7.01, {calls memset}
"fgets",10,6.37,
"jbsqueeze",10,6.37, {calls strpbrk}
"simplesqueeze",10,6.37,
"_read_nolock",9,5.73,
"krsqueeze",9,5.73, {called by bartsqueeze}
"squeeze2",9,5.73,
"strpbrk",9,5.73, {called by jbsqueeze}
"hartersqueeze",8,5.10,
"iansqueeze",7,4.46,
"memset",7,4.46, {called by atsqueeze}
"___newctype",5,3.18,
"strchr",4,2.55,
"__security_check_cookie",2,1.27,
"_unlock_file",2,1.27,
"_lock_file",1,0.64,
"bartsqueeze",1,0.64, {calls krsqueeze}
" ?? ?? ::FNODOBFM::`string'",0,0.00,
"__tmainCRTStartup",0,0.00,
"_filbuf",0,0.00,
"_GlobalFree@4",0,0.00,
"_read",0,0.00,

Type,Root Function Name,Function Name,Inclusive Samples,Exclusive
Samples,Inclusive Samples %,Exclusive Samples %,
"Root"," ?? ?? ::FNODOBFM::`string'"," ?? ?? ::FNODOBFM::`string'",
157,0,100.00,0.00,
"Callee"," ?? ?? ::FNODOBFM::`string'","_GlobalFree@4",
157,0,100.00,0.00,
"Root","___newctype","___newctype",5,5,3.18,3.18,
"Caller","___newctype","_lock_file",3,3,1.91,1.91,
"Caller","___newctype","_unlock_file",2,2,1.27,1.27,
"Root","__security_check_cookie","__security_check_cookie",
2,2,1.27,1.27,
"Caller","__security_check_cookie","strpbrk",2,2,1.27,1.27,
"Root","__tmainCRTStartup","__tmainCRTStartup",157,0,100.00,0.00,
"Caller","__tmainCRTStartup","_GlobalFree@4",157,0,100.00,0.00,
"Callee","__tmainCRTStartup","main",157,31,100.00,19.75,
"Root","_filbuf","_filbuf",9,0,5.73,0.00,
"Caller","_filbuf","fgets",9,0,5.73,0.00,
"Callee","_filbuf","_read",9,0,5.73,0.00,
"Root","_GlobalFree@4","_GlobalFree@4",157,0,100.00,0.00,
"Caller","_GlobalFree@4"," ?? ?? ::FNODOBFM::`string'",
157,0,100.00,0.00,
"Callee","_GlobalFree@4","__tmainCRTStartup",157,0,100.00,0.00,
"Root","_lock_file","_lock_file",4,1,2.55,0.64,
"Caller","_lock_file","fgets",4,1,2.55,0.64,
"Callee","_lock_file","___newctype",3,3,1.91,1.91,
"Root","_read","_read",9,0,5.73,0.00,
"Caller","_read","_filbuf",9,0,5.73,0.00,
"Callee","_read","_read_nolock",9,9,5.73,5.73,
"Root","_read_nolock","_read_nolock",9,9,5.73,5.73,
"Caller","_read_nolock","_read",9,9,5.73,5.73,
"Root","_unlock_file","_unlock_file",4,2,2.55,1.27,
"Caller","_unlock_file","fgets",4,2,2.55,1.27,
"Callee","_unlock_file","___newctype",2,2,1.27,1.27,
"Root","atsqueeze","atsqueeze",18,11,11.46,7.01,
"Caller","atsqueeze","main",18,11,11.46,7.01,
"Callee","atsqueeze","memset",7,7,4.46,4.46,
"Root","bartsqueeze","bartsqueeze",10,1,6.37,0.64,
"Caller","bartsqueeze","main",10,1,6.37,0.64,
"Callee","bartsqueeze","krsqueeze",9,9,5.73,5.73,
"Root","fgets","fgets",27,10,17.20,6.37,
"Caller","fgets","main",27,10,17.20,6.37,
"Callee","fgets","_filbuf",9,0,5.73,0.00,
"Callee","fgets","_lock_file",4,1,2.55,0.64,
"Callee","fgets","_unlock_file",4,2,2.55,1.27,
"Root","hartersqueeze","hartersqueeze",8,8,5.10,5.10,
"Caller","hartersqueeze","main",8,8,5.10,5.10,
"Root","iansqueeze","iansqueeze",7,7,4.46,4.46,
"Caller","iansqueeze","main",7,7,4.46,4.46,
"Root","jbsqueeze","jbsqueeze",21,10,13.38,6.37,
"Caller","jbsqueeze","main",21,10,13.38,6.37,
"Callee","jbsqueeze","strpbrk",11,9,7.01,5.73,
"Root","krsqueeze","krsqueeze",9,9,5.73,5.73,
"Caller","krsqueeze","bartsqueeze",9,9,5.73,5.73,
"Root","main","main",157,31,100.00,19.75,
"Caller","main","__tmainCRTStartup",157,31,100.00,19.75,
"Callee","main","atsqueeze",18,11,11.46,7.01,
"Callee","main","bartsqueeze",10,1,6.37,0.64,
"Callee","main","fgets",27,10,17.20,6.37,
"Callee","main","hartersqueeze",8,8,5.10,5.10,
"Callee","main","iansqueeze",7,7,4.46,4.46,
"Callee","main","jbsqueeze",21,10,13.38,6.37,
"Callee","main","simplesqueeze",10,10,6.37,6.37,
"Callee","main","sofsqueeze",12,12,7.64,7.64,
"Callee","main","squeeze2",9,9,5.73,5.73,
"Callee","main","strchr",4,4,2.55,2.55,
"Root","memset","memset",7,7,4.46,4.46,
"Caller","memset","atsqueeze",7,7,4.46,4.46,
"Root","simplesqueeze","simplesqueeze",10,10,6.37,6.37,
"Caller","simplesqueeze","main",10,10,6.37,6.37,
"Root","sofsqueeze","sofsqueeze",12,12,7.64,7.64,
"Caller","sofsqueeze","main",12,12,7.64,7.64,
"Root","squeeze2","squeeze2",9,9,5.73,5.73,
"Caller","squeeze2","main",9,9,5.73,5.73,
"Root","strchr","strchr",4,4,2.55,2.55,
"Caller","strchr","main",4,4,2.55,2.55,
"Root","strpbrk","strpbrk",11,9,7.01,5.73,
"Caller","strpbrk","jbsqueeze",11,9,7.01,5.73,
"Callee","strpbrk","__security_check_cookie",2,2,1.27,1.27,

*/

 

[jfbode1029]

Anyway, it's useless for Heathfield's original purpose, but it takes
30% less time on average than Twink's version and is 80% less ugly
(strpbrk() notwithstanding).

I can't reproduce anything like this timing... is it possible that your
profiler is missing the time spent in the shared library functions
strpbrk() and strcat()?
[snip]


I compiled it statically so that standard library calls get included in
the profile:
gcc -O2 -pg -static a.c -o a

Well, crap -- like I said, I must love being an idiot in public, I do
it often enough. I had mistakenly assumed that the time spent in the
library calls was counted in the time spent in the function. That is
obviously not the case.

But, given how life has been going the last couple of weeks, this is
typical. Getting old sucks.

 

[jameskuyper]

(e-mail address removed) wrote:
....

typical. Getting old sucks.

It's better than the only alternative. :-}

 

[jfbode1029]

(e-mail address removed) wrote:

...


It's better than the only alternative. :-}

Yeah, but throw drooling senility into the equation and it gets a lot
less appealing.

 

[user923005]

Yeah, but throw drooling senility into the equation and it gets a lot
less appealing.

Before you order the seppiku knives, let's consider the function and
the context:

Here is the jb character removal function:

void jbsqueeze(char *s1, const char *s2)
{
char *tmp = NULL;
while (tmp = strpbrk(s1, s2)) {
*tmp = 0;
strcat(s1, ++tmp);
}
}

The context is a student instruction exercise.
The final result is that this is clearly the best solution for the
purposes of demonstrating the concept. It's short, clear, clean,
understandable.

If there were some real need to perform set extraction in actual
production code, and if a profile revealed that this technique was
lacking in performance to the point that it was below specification
then it would be time to look at alternatives. This function was
fastest in my profiles:

void iansqueeze(char s1[], const char s2[])
{
int i;

for (i = 0; s2 != '\0'; i++) {
int j,
k;
for (k = j = 0; s1[k] != '\0'; k++) {
if (s2 != s1[k])
s1[j++] = s1[k];
}
s1[j] = '\0';
}
}

and it has a certain elegance.

So I have two clear winners in the contest. Your solution was the
clearest, simplest, and easiest to debug and maintain. Since 80% of
software cost is maintenance, that makes it a clear winner. It is
unlikely that a routine like this can be a bottleneck in real
production code. Be that as it may, the other elegant solution was
also the fastest. It's not much more complicated.

Now, on the down-side we are early in the book and so I do not think
that the string functions have been covered yet. So, despite the
clear elegance of your solution, it would probably be a better answer
if it were posed later in the book. While your solution was the
slowest, it was about the same speed as A.T.'s "optimization" {the
second slowest solution} on my hardware. Mr. Heathfield's solution
was about twice as fast as A.T.'s.

Function Name,Exclusive Samples,Exclusive Samples %,
"main",31,19.75,
"sofsqueeze",12,7.64,
"atsqueeze",11,7.01, {calls memset} 7.01 + 4.46 = 11.47%
"fgets",10,6.37,
"jbsqueeze",10,6.37, {calls strpbrk} 6.37 + 5.73 = 12.1%
"simplesqueeze",10,6.37,
"_read_nolock",9,5.73,
"krsqueeze",9,5.73, {called by bartsqueeze}
"squeeze2",9,5.73,
"strpbrk",9,5.73, {called by jbsqueeze}
"hartersqueeze",8,5.10,
"iansqueeze",7,4.46,
"memset",7,4.46, {called by atsqueeze}
"___newctype",5,3.18,
"strchr",4,2.55,
"__security_check_cookie",2,1.27,
"_unlock_file",2,1.27,
"_lock_file",1,0.64,
"bartsqueeze",1,0.64, {calls krsqueeze}
" ?? ?? ::FNODOBFM::`string'",0,0.00,
"__tmainCRTStartup",0,0.00,
"_filbuf",0,0.00,
"_GlobalFree@4",0,0.00,
"_read",0,0.00,

When it comes to student exercises, I think it is always nice to
examine alternatives. I think that A.T.'s solution is also
interesting and it might profile differently on different hardware.
It also may improve with different compilers or with different CPUs or
with different data input domains than those that I tried. A few
years ago there were a bunch of GCD algorithms posted, with Paul
Hsieh's subtraction GCD easily beating my modular mathematics
version. I tried the same routines a few months ago and now the
modular version is faster (no doubt due to the 64 bit math operations
being much faster with a 64 bit compiler on a 64 bit OS).

So what is true today may or may not be true tomorrow.

 

[Richard Bos]

Yeah, but throw drooling senility into the equation and it gets a lot
less appealing.

Sure, but we're not all called Falconer.

Richard

 

[Keith Thompson]

Sure, but we're not all called Falconer.

Was that really necessary?

 

[jacob navia]

Alzheimer's cannot be diagnosed except at postmortem.

This goes really too far. This type of attacks aren't justified
whatever the views of Mr Falconer are.

We can have disagreements, even heated discussions but this is
just trying to harm people personally.

 

[Guest]

This goes really too far. This type of attacks aren't justified
whatever the views of Mr Falconer are.

We can have disagreements, even heated discussions but this is
just trying to harm people personally.

Good for you Jacob. Thlid and spass used to be play ground
insults. Asbergers and Alzheimer's shouldn't be used as
casual invective.

 

[Keith Thompson]

Good for you Jacob. Thlid and spass used to be play ground
insults. Asbergers and Alzheimer's shouldn't be used as
casual invective.

I agree. (It's conceivable that GCG's advice was meant kindly, but
this isn't the place for it.)

 

[Richard Bos]

Was that really necessary?

Given that other humungous thread up ^ there, frankly, _YES_.

Richard

 

[Keith Thompson]

Given that other humungous thread up ^ there, frankly, _YES_.

Bullshit. Or are you using the word "necessary" in some way that I'm
not familiar with?

 

[Antoninus Twink]

CBF wasn't so dense in the past and changes in this should be looked
into by a professional because they can stop them before they get
really bad.

Well, let's hope for his sake that he wasn't so dense in the past.

The truth is, saying that CBF has senile dementia or that Kiki has
chronic Asperger's/OCD isn't invective or insult, but a simple statement
of fact. In both cases, knowing the cause of the problem /should/ help
us understand and make allowances for the symptoms.

Unfortunately, neither CBF nor KT are willing to help themselves. Some
autistic people are self-aware enough to realize that they have problems
with social interactions, and they deliberately try to behave in a way
that may not seem "natural" to them, but is what (they rationalize) is
expected in ordinary human interaction. KT does not seem to be one of
them.

Similarly, some people whose faculties are failing because of old age
realize his, maybe even feel embarrassed or uncomfortable about it, and
live a quiet life with their loved ones. CBF prefers to parade his
decaying mental acuity to the world in an exceptionally crabby and
obstreperous way.

So yes, we should probably all make more allowances for these problems,
which are no laughing matter, and I'm as guilty as anyone in not doing
so. But on the other hand, the people with the problems could make their
lives a whole lot more pleasant if they tried to help themselves.