GCC code efficiency

Log in or register to post comments
Go To Last Post
16 posts / 0 new
Author
Message
fmaimon
fmaimon's picture
Level: Hangaround
Joined: Sat. Jul 28, 2001
Posts: 357 View posts
Location: Rio de Janeiro
#1
Posted by fmaimon: Thu. Mar 11, 2010 - 04:24 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Looks like GCC is generating code more efficiently than the code in the avr-libc library, at least in this case (isdigit from ). Nice!

			if (isdigit(uart_tmp))
     40c:	48 2f       	mov	r20, r24
     40e:	50 e0       	ldi	r21, 0x00	; 0
     410:	ca 01       	movw	r24, r20
     412:	c0 97       	sbiw	r24, 0x30	; 48
     414:	0a 97       	sbiw	r24, 0x0a	; 10
     416:	08 f0       	brcs	.+2      	; 0x41a 
     418:	92 c0       	rjmp	.+292    	; 0x53e <__stack+0x3f>



     40c:	48 2f       	mov	r20, r24
			// only if it is a number
			if ((uart_tmp >='0') && (uart_tmp <= '9'))
     40e:	80 53       	subi	r24, 0x30	; 48
     410:	8a 30       	cpi	r24, 0x0A	; 10
     412:	08 f0       	brcs	.+2      	; 0x416 
     414:	92 c0       	rjmp	.+292    	; 0x53a <__stack+0x3b>

Felipe Maimon

Tags:

Tools, Compilers and General Programming
Top
fmaimon
fmaimon's picture
Level: Hangaround
Joined: Sat. Jul 28, 2001
Posts: 357 View posts
Location: Rio de Janeiro
Posted by fmaimon: Thu. Mar 11, 2010 - 04:47 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

One more test case, now with isxdigit, comparing with an if and a switch statement. Again, gcc is more efficient than the library.

If

	if (((abc >='0') && (abc <= '9')) || \
 462:	89 2f       	mov	r24, r25
 464:	80 53       	subi	r24, 0x30	; 48
 466:	8a 30       	cpi	r24, 0x0A	; 10
 468:	30 f0       	brcs	.+12     	; 0x476 
 46a:	81 51       	subi	r24, 0x11	; 17
 46c:	86 30       	cpi	r24, 0x06	; 6
 46e:	18 f0       	brcs	.+6      	; 0x476 
 470:	91 56       	subi	r25, 0x61	; 97
 472:	96 30       	cpi	r25, 0x06	; 6
 474:	18 f4       	brcc	.+6      	; 0x47c 
	    ((abc >='A') && (abc <= 'F')) || \
		((abc >='a') && (abc <= 'f')))

Switch

	switch (abc)
 484:	87 34       	cpi	r24, 0x47	; 71
 486:	30 f4       	brcc	.+12     	; 0x494 
 488:	81 34       	cpi	r24, 0x41	; 65
 48a:	38 f4       	brcc	.+14     	; 0x49a 
 48c:	80 53       	subi	r24, 0x30	; 48
 48e:	8a 30       	cpi	r24, 0x0A	; 10
 490:	38 f4       	brcc	.+14     	; 0x4a0 
 492:	03 c0       	rjmp	.+6      	; 0x49a 
 494:	81 56       	subi	r24, 0x61	; 97
 496:	86 30       	cpi	r24, 0x06	; 6
 498:	18 f4       	brcc	.+6      	; 0x4a0 
	{
		case '0'...'9':
		case 'A'...'F':
		case 'a'...'f':

isxdigit

	if (isxdigit(abc))
 4a8:	90 e0       	ldi	r25, 0x00	; 0
 4aa:	0e 94 9e 02 	call	0x53c	; 0x53c 
 4ae:	89 2b       	or	r24, r25
 4b0:	19 f0       	breq	.+6      	; 0x4b8 

0000053c :
 53c:	91 11       	cpse	r25, r1
 53e:	09 c0       	rjmp	.+18     	; 0x552 <__ctype_isfalse>
 540:	80 53       	subi	r24, 0x30	; 48
 542:	8a 50       	subi	r24, 0x0A	; 10
 544:	28 f0       	brcs	.+10     	; 0x550 
 546:	86 5c       	subi	r24, 0xC6	; 198
 548:	80 62       	ori	r24, 0x20	; 32
 54a:	81 56       	subi	r24, 0x61	; 97
 54c:	86 50       	subi	r24, 0x06	; 6
 54e:	b8 f7       	brcc	.-18     	; 0x53e 
 550:	08 95       	ret

Felipe Maimon

Top
stu_san
stu_san's picture
Level: Raving Lunatic
Joined: Fri. Dec 30, 2005
Posts: 2321 View posts
Location: Fort Collins, CO USA
Posted by stu_san: Thu. Mar 11, 2010 - 04:47 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

:roll: *sigh* So? Is the function isdigit() in a time critical part of your code? Are the extra cycles something that will make or break your code? If so, code it the way you did and rejoice that you have found a better solution.

I looked at the source for avr-libc's version of isdigit() - the interesting part is that the argument to isdigit() is an int, so the math that isdigit is doing is "correct" for the argument. I guess we can argue about whether an int is the proper argument, but I suspect that is given to us by a standard somewhere.

I admit that I am completely underwhelmed by your discovery.

Stu

Engineering seems to boil down to: Cheap. Fast. Good. Choose two. Sometimes choose only one.

Newbie? Be sure to read the thread Newbie? Start here!

Top
Koshchi
Koshchi's picture
Level: 10k+ Postman
Joined: Wed. Nov 17, 2004
Posts: 15658 View posts
Location: Vancouver, BC
Posted by Koshchi: Thu. Mar 11, 2010 - 04:57 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
I looked at the source for avr-libc's version of isdigit() - the interesting part is that the argument to isdigit() is an int

The arguments to all the functions in ctype.h take a int and return an int. This is how it is supposed to be, according to K&R.

Regards,
Steve A.

The Board helps those that help themselves.

Top
fmaimon
fmaimon's picture
Level: Hangaround
Joined: Sat. Jul 28, 2001
Posts: 357 View posts
Location: Rio de Janeiro
Posted by fmaimon: Thu. Mar 11, 2010 - 05:00 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Just a curiosity. It won't improve my code. I just found out about about those functions reading the manual and, as I'm using the if statement to check if the variable is betwen '0' and '9', I gave it a try. Usually the library is smaller than code generated from C so I was surprised when my code size increased.

Felipe Maimon

Top
Gold Markclawson
clawson's picture
Level: Moderator
Joined: Mon. Jul 18, 2005
Posts: 104959 View posts
Location: (using avr-gcc in) Finchingfield, Essex, England
Posted by clawson: Thu. Mar 11, 2010 - 05:04 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

What choice did isdigit() have anyway?:

extern int isdigit(int __c) __ATTR_CONST__;

its parameter must be taken as an int (even if you are actually testing a char) and it must return an int so both r25 and r24 were required along with SBIW's

Top
skeeve
skeeve's picture
Level: Raving Lunatic
Joined: Sun. Oct 29, 2006
Posts: 5631 View posts
Posted by skeeve: Thu. Mar 11, 2010 - 05:21 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

stu_san wrote:
I looked at the source for avr-libc's version of isdigit() - the interesting part is that the argument to isdigit() is an int, so the math that isdigit is doing is "correct" for the argument. I guess we can argue about whether an int is the proper argument, but I suspect that is given to us by a standard somewhere.
Correct. isdigit is required to work for EOF and for
every value in the common range of int and unsigned char.
On most systems, this is -1..255.
If sizeof(int)==1, it must also work on (int)(INT_MAX+1..UCHAR_MAX),
an implementation defined set.

Moderation in all things. -- ancient proverb

Top
bperrybap
bperrybap's picture
Level: Resident
Joined: Sun. May 3, 2009
Posts: 563 View posts
Location: Dallas, TX USA
Posted by bperrybap: Thu. Mar 11, 2010 - 07:03 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

My experience is that ctype functions usually generate poorer code than you can do on your own, especially when you are only using ASCII characters.
Some implementations take the easy way out and do a data table lookup.

I've often created my own cytpe replacement macros to replace the system supplied cytpe functions in embedded environments.
The only time I've ever had to use the ctype functions was when I was doing C code
decades ago on an IBM 370 which used EBCDIC characters.
That environment had many challenges for C,
one of them being no curly braces...
Can you say "digraphs" -....arhg....

Other than that, I've found that the ctype functions while very portable and "standard" don't really generate the best of code.

--- bill

Top
skeeve
skeeve's picture
Level: Raving Lunatic
Joined: Sun. Oct 29, 2006
Posts: 5631 View posts
Posted by skeeve: Thu. Mar 11, 2010 - 07:08 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

clawson wrote:
What choice did isdigit() have anyway?:

extern int isdigit(int __c) __ATTR_CONST__;

its parameter must be taken as an int (even if you are actually testing a char) and it must return an int so both r25 and r24 were required along with SBIW's

isdigit is also implemented as a macro.

(sizeof(__c)==1 ? not_EOF : maybe_EOF)

is a legitimate expansion, but not necessary.
In few, if any, implementations is (unsigned char)EOF a digit.
The assembly could have been two compare immediates and two branches.
It would have been at least as fast and used one less register.

Moderation in all things. -- ancient proverb

Top
EW
EW's picture
Level: Raving Lunatic
Joined: Thu. Mar 1, 2001
Posts: 4914 View posts
Location: Rocky Mountains
Posted by EW: Fri. Mar 12, 2010 - 04:57 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

If anyone finds a valid way to improve the code in avr-libc, patches are always welcome.

Eric Weddington
www.linkedin.com/in/ericweddington/

Top
bperrybap
bperrybap's picture
Level: Resident
Joined: Sun. May 3, 2009
Posts: 563 View posts
Location: Dallas, TX USA
Posted by bperrybap: Fri. Mar 12, 2010 - 10:08 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

EW wrote:
If anyone finds a valid way to improve the code in avr-libc, patches are always welcome.

Eric, would that potentially include some sort of ifdef/define compile time option that would allow the routines to be mapped to alternate functions/macros that might 'violate' the standard but still work when used for 8 bit ASCII characters?

--- bill

Top
Geoff
Geoff's picture
Level: Hangaround
Joined: Mon. Apr 24, 2006
Posts: 285 View posts
Location: Sydney, Australia
Posted by Geoff: Sun. Mar 14, 2010 - 11:07 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

stu_san wrote:
:roll: *sigh* So? Is the function isdigit() in a time critical part of your code? Are the extra cycles something that will make or break your code? If so, code it the way you did and rejoice that you have found a better solution.

I looked at the source for avr-libc's version of isdigit() - the interesting part is that the argument to isdigit() is an int, so the math that isdigit is doing is "correct" for the argument. I guess we can argue about whether an int is the proper argument, but I suspect that is given to us by a standard somewhere.

I admit that I am completely underwhelmed by your discovery.

Stu

In my opinion this sort of question should be treated more seriously, as Eric has done, rather than sarcastically. The reason why we have libraries is to avoid reinventing the wheel - the library should be the best way to do a task (at least most of the time). If it's not, then why have a library?

In this case the answer is simple - because ctype.h uses ints for parameters and return values. What I'm wondering is why ctype.h uses ints rather than chars. You should know how big the data is you're dealing with, should you not? And if it requires an int size then it's not going to be ASCII, ergo you don't need character type operations.

Last Edited: Sun. Mar 14, 2010 - 11:09 PM
Top
Koshchi
Koshchi's picture
Level: 10k+ Postman
Joined: Wed. Nov 17, 2004
Posts: 15658 View posts
Location: Vancouver, BC
Posted by Koshchi: Sun. Mar 14, 2010 - 11:19 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
What I'm wondering is why ctype.h uses ints rather than chars. You should know how big the data is you're dealing with, should you not? And if it requires an int size then it's not going to be ASCII, ergo you don't need character type operations.

Because that is what the C standard says it should be. Where in the C standard does it say that characters must be in ASCII?
Quote:
the library should be the best way to do a task

No, the library should provide generic ways of doing things. What is "best" depends on how you use it, which is in direct conflict with being generic.

Regards,
Steve A.

The Board helps those that help themselves.

Top
bperrybap
bperrybap's picture
Level: Resident
Joined: Sun. May 3, 2009
Posts: 563 View posts
Location: Dallas, TX USA
Posted by bperrybap: Mon. Mar 15, 2010 - 05:27 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

To me, it looks like the AVR libc ctype functions have been written to avoid the use of a data table.

As such it depends on comparing or doing math on character constants.
So won't the character constants in the ctype functions be based on the character set of the ctype source code as the ctype code is compiled?

Have I missed something?

So I guess it was lucky for those that want to use the ctype functions with ASCII characters,
that ASCII was the character set of the ctype source code when the ctype library code was compiled.

Given the library code seems to already be limited and hard coded for ASCII to save code space,
it would seem logical to go ahead and take the next step and convert all the functions to macros
to avoid the integer promotion and get better code in 8 bit AVR environments.

What would be the downside of doing this?

--- bill

Top
Gold Markclawson
clawson's picture
Level: Moderator
Joined: Mon. Jul 18, 2005
Posts: 104959 View posts
Location: (using avr-gcc in) Finchingfield, Essex, England
Posted by clawson: Mon. Mar 15, 2010 - 09:53 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

What would be the downside of doing this?

It contravenes the C standard that GCC does its best to adhere to. I guess like -std=gun99 there could be a command line switch to say "I'm wiling to forego complete standards compliance"

Top
skeeve
skeeve's picture
Level: Raving Lunatic
Joined: Sun. Oct 29, 2006
Posts: 5631 View posts
Posted by skeeve: Mon. Mar 15, 2010 - 05:04 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

clawson wrote:
Quote:

What would be the downside of doing this?

It contravenes the C standard that GCC does its best to adhere to. I guess like -std=gun99 there could be a command line switch to say "I'm wiling to forego complete standards compliance"
Done well, it wouldn't have to.
The standard explicitly allows hiding functions with macros.
// could use this if certain that it would not declare EOF a digit
#define __isdigit_uc(_uc) \
    ({ unsigned char ch=_c; '0'<=ch && ch<='9'; })

// use this if EOF might otherwise be
// declared a digit and _val might be EOF
#define __isdigit_rare(_val) \
    ({int val=_val; EOF!=val && __isdigit_uc(val); })

// EOF need only be considered if __isdigit_uc(EOF)
#define isdigit(_val) \
    (__isdigit_uc(EOF) ? __isdigit_rare(_val) : __isdigit_uc(_val))

In principle,
whether __isdigit_rare is ever used depends on the implementation.
In practice, I doubt that there are any such implementations.

Edit: corrected __isdigit_rare

Moderation in all things. -- ancient proverb

Top