Thread: isdigit implementation

I'm looking for a quick implementation of ctype's isdigit. There's the classic range test between '0' and '9', but is there anything faster? (disregarding locale considerations)

I know most library implementations take a different approach, using look-up tables; however I've read that depending on the processor and whether these are loaded into cache it can be either faster or slower. Can anyone add to this?

Originally Posted by @nthony

I'm looking for a quick implementation of ctype's isdigit. There's the classic range test between '0' and '9', but is there anything faster?

I was interested to read that someone would thing there would be. It is hard to understand why you would want to optimize something so simple BUT, if you really want to know, try that and isdigit several million times in a loop and use either a stopwatch or difftime().

Okay, I did it. It took *a lot* more than just a few million iterations to get a meaningful duration tho:

Code:

#include <stdio.h>
#include <time.h>
#include <ctype.h>

int check_digit (char c) {
	if ((c>='0') && (c<='9')) return 1;
	return 0;
}

int main() {
	int i,j,r;
	double lapse;
	time_t start=time(NULL), end;
	for (i=0; i<50000000; i++) {
		for (j=33; j<127; j++) 
			r=check_digit(j);
			//r=isdigit(j);	
	}
	end=time(NULL);
	if (end != start) lapse=difftime(end,start);
	printf("%d seconds\n",(int)lapse);
	return 0;
}

The results:

"check_digit" (the classic method):
4.7 billion times took 32 seconds.

isdigit took 24 seconds.

(Fedora Core 10 on Intel "dual" 2.2Ghz, but this is not threaded...)

I tried a lookup table this way:

Code:

int lookup[128];

int check_II (int c) {
	if (c-48 == lookup[c]) return 1;
	return 0;
}

int main() {
	int i,j,r;
	double lapse;
	time_t start, end;

	for (i=0; i<128; i++) lookup[i]=9999;
	for (i=0; i<10; i++) lookup[i+48]=i;
	start=time(NULL);
	for (i=0; i<25000000; i++) {
		for (j=33; j<127; j++) 
			//r=check_digit(j);
			r=check_II(j);
			//r=isdigit(j);	
	}
	end=time(NULL);

And, interestingly, it clocked in with the same time as the "classic" method (32 seconds).

Originally Posted by MK27

Okay, I did it. It took *a lot* more than just a few million iterations to get a meaningful duration tho:

Code:

#include <stdio.h>
#include <time.h>
#include <ctype.h>

int check_digit (char c) {
	if ((c>='0') && (c<='9')) return 1;
	return 0;
}

int main() {
	int i,j,r;
	double lapse;
	time_t start=time(NULL), end;
	for (i=0; i<50000000; i++) {
		for (j=33; j<127; j++) 
			r=check_digit(j);
			//r=isdigit(j);	
	}
	end=time(NULL);
	if (end != start) lapse=difftime(end,start);
	printf("%d seconds\n",(int)lapse);
	return 0;
}

The results:

"check_digit" (the classic method):
4.7 billion times took 32 seconds.

isdigit took 24 seconds.

(Fedora Core 10 on Intel "dual" 2.2Ghz, but this is not threaded...)

you could have done

Code:

int check_digit (char c) {
	return (c>='0') && (c<='9');
}

Originally Posted by ಠ_ಠ

you could have done

Oh sure. That saves 2 seconds (1/16).

Originally Posted by MK27

Oh sure. That saves 2 seconds (1/16).

Interesting. Are you compiling with speed optimisations turned on?

Originally Posted by MK27

I tried a lookup table this way:
And, interestingly, it clocked in with the same time as the "classic" method (32 seconds).

Hmm, that is interesting. From a look in ctype.h, I believe mingw/GCC uses a look-up table of bitmasks, along the lines of:

Code:

#define BIT_MASK_ISDIGIT 0x01
int lookup[128];

int check_II (int c) {
	return lookup[c] & BIT_MASK_ISDIGIT;
}

int main() {
	int i,j,r;
	double lapse;
	time_t start, end;

	for ( i='0'; i<='9'; ++i) lookup[i] |= BIT_MASK_ISDIGIT;
	start=time(NULL);
	for (i=0; i<25000000; i++) {
		for (j=33; j<127; j++) 
			//r=check_digit(j);
			r=check_II(j);
			//r=isdigit(j);	
	}
	end=time(NULL);

I'm not at home right now, if anyone can check if this is an improvement.

Originally Posted by laserlight

Interesting. Are you compiling with speed optimisations turned on?

I can't find that button -- is it near the dvd burner?

I just tried -O3 -O2 and -O and they all result in a runtime of 0 seconds. Hmmm. I never use these flags. Perhaps something is wrong with them.

Originally Posted by tabstop

If he did, would the loop even exist?

?????????

Originally Posted by tabstop

That's the point of optimization -- don't do things you don't have to do. gcc is smart enough to realize that there's no point in computing r -- you don't keep the value or use the value in any way, so it's gone. Once that happens, it looks at the loop, realizes that there are no statements inside the loop and eliminates the loop. If you maybe put in an accumulator variable and add r to it each time, it will actually do the loop.

Ah. I had to put in r or gcc gripes about the isdigit() call being "a statement with no effect"*. So to be fair, I figured all the tests should make a real assignment.

Hopefully that is that all you meant by "If he did, would the loop even exist?" ?-- I was suddenly thinking, "Do this without a loop...I thought I already understood C somewhat..."

Anyway, at -O the classic method is down to 15 seconds, at -O3 7 seconds.

Originally Posted by @nthony

I'm not at home right now, if anyone can check if this is an improvement.

At -O3 it is midway between my two lame-ass methods (6-7 seconds) and isdigit (2 seconds), which is to say 4 seconds. With no optimization: 25 seconds.

Here's something really bizarre tho. To make use of r, I used r+=function and then output "printf("%d digits found in %d seconds\n",r,(int)lapse);", just to make sure that the correct 500000000 digits are found.

[root~/C] ./a.out
500000000 digits found in 7 seconds
[root~/C] gcc -O3 test.c
[root~/C] ./a.out
500000000 digits found in 4 seconds
[root~/C] gcc -O3 test.c
[root~/C] ./a.out
1797783552 digits found in 2 seconds
[root~/C] gcc -O3 test.c
[root~/C] ./a.out
500000000 digits found in 6 seconds


The oddball here is produced by isdigit() !!!! ????

[edit] ah -- isdigit returns 2048, not 1 (the same for all 10 digits)...which implies.....