Re: Can we implement ctype functions through table?
Another negative thing about the table driven C type functions is that in the PROTECTED build, there will need to be two ctyle look-up tables: One in user space and one in kernel space. So the overhead will 512, not 256, bytes in that configuration. Perhaps we would use the macros inside of the OS and the lookup table outside of the OS? #ifdef __KERNEL__ # define isdigit(c) ((c) >= '0' && (c) <= '9') #else # define isdigit(c) ((table((unsigned)c) & __DIGIT_MASK) != 0) #endif Then perhaps we could avoid the duplicate kernel-space lookup table?
Re: Can we implement ctype functions through table?
Macros that evaluate their parameters more than once are dangerous for a
variety of reasons.
On Wed, Jul 29, 2020 at 11:32 AM David Sidrane wrote:
> K&R warns against using macros in loops. Experienced programmers (especially
> embedded) know not to write code like shown in the "reason" for needing this
> change.
True, but at the call site, use of a macro looks just like a function call, so
good macro writing is to make sure it works just like a function call, no
matter where it's used.
Furthermore, over time, the implementation of a macro could change from macro
to function, or from function to macro. Or you might build the application
software on NuttX one day and on a PC OS the next. So if the macro ends up
being used in a loop, it might not be because the programmer is inexperienced,
but because the implementation (or the platform) changed after the code was
written.
Also, you don't know where/how these macros are being used. Perhaps someone is
using a 3rd party library that uses these macros and assumes they are safe.
Because of all these reasons, it is very important, when writing macros, to
make sure they can be used in all possible scenarios without causing problems.
That includes:
* Evaluating parameters once.
* If the macro is multiple statements, as opposed to an expression, wrapping
those statements in do { ... } while (0).
I think these things are the responsibility of the macro writer, not the macro
caller.
Regarding isalpha() and friends:
On Wed, Jul 29, 2020 at 2:54 AM Xiang Xiao wrote:
> 2.Change macro to normal function and lose some performance
> 3.Change macro to inline function and some old compilers may generate
> the bloat code
Given all of the above, and the various concerns voiced here, I think option 2
looks best/safest in the context of embedded systems. While some here might
gawk at the performance penalty of a function call, I agree with Greg that:
> Most released, deeply embedded software does not do a lot of string
> processing. So I could imagine that a motor control system that only
> has a couple of uses of ctype functions but would pay a pretty big size
> penalty for using a table.
I think function call overhead isn't quite as horrible as its reputation might
suggest. In fact, if you have macros that evaluate their parameters more than
once, you potentially get a much bigger performance penalty. (I just recently
discovered use of min() and max() macros in code I maintain. Those are
implemented as ((a) < (b)) ? (a) : (b). And the parameters passed to these
macros at the call site were the results of function calls, those functions
were making time-consuming calculations, and they were being executed
redundantly because of the macros evaluating their parameters more than once!
That is a much bigger performance penalty!
On Wed, Jul 29, 2020 at 8:42 AM spudaneco wrote:
> I would consider option 3 to be the worst choice. That could bloat can be
> enormous and unacceptable as I have seen in the past. I saw growth by many
> kbyte in such cases. Not a good compromise.
I wonder if there exists a good solution for the inline function problem that
will be C89 compliant, avoid the code bloat, and not create a maintenance
nightmare. I don't know what that is yet, but if we find a solution, it will
be helpful for other things besides the isalpha() (and friends) macros.
Nathan
RE: Can we implement ctype functions through table?
Is the example code a port from a bigger system?
K&R warns against using macros in loops. Experienced programmers (especially
embedded) know not to write code like shown in the "reason" for needing this
change.
At this point the acid test is sizeof(how many macros) == "256 | 512" (If we
cannot use MPU)
I still feel it should be a CONFIG setting and default it to the table,
describe the pit falls in Knonfig if it is changed to a macros and document
the code bloat in the README.
This will save past users on Nuttx, on constrained system, to have a chance
to fix running out of FLASH space when isalpha() is used one (properly).
Maybe this is not as important to companies with their own chip foundries,
but we still need to be inclusive.
David
-Original Message-
From: Xiang Xiao [mailto:xiaoxiang781...@gmail.com]
Sent: Tuesday, July 28, 2020 11:54 PM
To: dev@nuttx.apache.org
Subject: RE: Can we implement ctype functions through table?
The new option just make the situation worse. The same code works in
some configurations, but breaks in other configurations.
Since the standard confirmation is the most important principle for
NuttX, we have three options:
1.Implement ctype function with table and add 256 byte to ROM
2.Change macro to normal function and lose some performance
3.Change macro to inline function and some old compilers may generate
the bloat code
all ctype functions are one line code, so option 3 may be a good compromise.
> -Original Message-
> From: David Sidrane
> Sent: Tuesday, July 28, 2020 8:23 PM
> To: dev@nuttx.apache.org
> Subject: RE: Can we implement ctype functions through table?
>
> Xiang,
>
> If there is a small usage do you think flash will grow by 256 bytes? I
> would be surprised.
>
> Should you uses a config option?
>
> David
>
>
> -Original Message-
> From: Xiang Xiao [mailto:xiaoxiang781...@gmail.com]
> Sent: Monday, July 27, 2020 10:40 PM
> To: dev@nuttx.apache.org
> Subject: RE: Can we implement ctype functions through table?
>
> Decorate the table with IPTR and access the element through up_romgetc,
> just like printf series function.
>
> > -Original Message-
> > From: Gregory Nutt
> > Sent: Tuesday, July 28, 2020 12:44 PM
> > To: dev@nuttx.apache.org
> > Subject: Re: Can we implement ctype functions through table?
> >
> > What about platforms like AVR? That would not be a good decision for
> > AVR since it is a harvard machine and cannot access data in ROM
> > without special operations.
> >
> >
> > On 7/27/2020 9:55 PM, Xiang Xiao wrote:
> > > Hi all,
> > > For example, here is isspace implementation:
> > > # define isspace(c) \
> > > ((c) == ' ' || (c) == '\t' || (c) == '\n' || (c) == '\r' || \
> > > (c) == '\f' || (c) == '\v')
> > > The argument of c will evaluate 6 times, which make the following
> > > code suddenly fail:
> > > while (end != begin)
> > >{
> > > If (!isspace(*--end))
> > >{
> > > break;
> > >}
> > >}
> > > But it work well with other libc implementation, because all other
> > > libc utilize a table to classify the char type:
> > > https://github.com/bminor/newlib/blob/master/newlib/libc/include/cty
> > > pe
> > > .h#L97
> > > https://github.com/bminor/glibc/blob/master/ctype/ctype.h#L197
> > > and the argument only need evaluate once.
> > > So my question is: can we implement ctype functions through table to
> > > improve the compatibility?
> > > Yes, the table need take more 256 bytes ROM space, but the complex
> > > expression used in NuttX also bloat the code size, especially
> > > considering ctype function is used very frequently.
> > >
> > > Thanks
> > > Xiang
> > >
Re: Can we implement ctype functions through table?
Another negative thing about the table driven C type functions is that in the PROTECTED build, there will need to be two ctyle look-up tables: One in user space and one in kernel space. So the overhead will 512, not 256, bytes in that configuration. Also, a minor correction: The table look-up version would be something like # define isdigit(c) ( (table(c) & __DIGIT_MASK) != 0) Given c in a register that would boil down to something like: * get the address of the table * offset by (c) * Fetch table entry from FLASH (big performance hit) * AND with __DIGIT_MASK * compare with zero
Re: Can we implement ctype functions through table?
And if the macro versions are employed a few times then they would quickly grow larger than the table anyways. The table access is not free. There is overhead in both cases, depending primarily on the complexity of the ctype comparison. For is isdigit() the comparison is currently just: # define isdigit(c) ((c) >= '0' && (c) <= '9') Given c in a register that would boil down to something like the following: * compare c to '0' * branch if c < '0' * compare c to '9' * branch if c > '9' The table look-up version would be something like # define isdigit(c) ( (table(c) & __DIGIT_MASK) != 0) Given c in a register that would boil down to something like: * get the address of the table * offset by (c) * AND with __DIGIT_MASK * compare with zero * branch if zero So there is no dramatic size savings in that particular case. And the fetch from FLASH is a performance killer too. Reducing size is not a super strong argument of this change. There would be a substantial reduction in size for some larger more complex ctype functions, however. Like isalnum(): # define islower(c) ((c) >= 'a' && (c) <= 'z') # define isupper(c) ((c) >= 'A' && (c) <= 'Z') # define isalpha(c) (islower(c) || isupper(c)) # define isdigit(c) ((c) >= '0' && (c) <= '9') # define isalnum(c) (isalpha(c) || isdigit(c)) The only pressing argument for change is the fact that the argument is currently re-evaluated numerous times. That is a problem. Most released, deeply embedded software does not do a lot of string processing. So I could imagine that a motor control system that only has a couple of uses of ctype functions but would pay a pretty big size penalty for using a table.
Re: Can we implement ctype functions through table?
And if the macro versions are employed a few times then they would quickly grow larger than the table anyways. -- Lucas Vinicius Hartmann Subscription software is ransomware disguised. Em qua., 29 de jul. de 2020 às 10:41, Gregory Nutt escreveu: > > > What about platforms like AVR? That would not be a good decision for > > AVR since it is a harvard machine and cannot access data in ROM > > without special operations. > > This is not a show stopper, at least not for the AVR. While a > table-driven solution is not optimal for AVR, it will support access to > constant data in ROM if the data has the storage class IOBJ as defined > in include/nuttx/compiler.h. I don't know if the compiler will > automatically generate the correct instruction to access the table > across the bus bridge; I am not an AVR expert. There is a up_ function > may need to be used to access the ROM table??? > > AVR Memory: https://microchipdeveloper.com/8avr:memory > C Interface: > > http://ww1.microchip.com/downloads/en/AppNotes/Atmel-2575-C-Functions-for-Reading-and-Writing-to-Flash-Memory_ApplicationNote_AVR106.pdf > > Hmm.. I notice that compiler.h defines IOBJ as __flash but the above > document says: "The datatypes are actually used as __flashor > __farflashpointers (consequently 16 and 24 bit)." That should be change > to __farflash. > >
Re: Can we implement ctype functions through table?
On 7/29/2020 7:41 AM, Gregory Nutt wrote: What about platforms like AVR? That would not be a good decision for AVR since it is a harvard machine and cannot access data in ROM without special operations. This is not a show stopper, at least not for the AVR. While a table-driven solution is not optimal for AVR, it will support access to constant data in ROM if the data has the storage class IOBJ as defined in include/nuttx/compiler.h. I don't know if the compiler will automatically generate the correct instruction to access the table across the bus bridge; I am not an AVR expert. There is a up_ function may need to be used to access the ROM table??? AVR Memory: https://microchipdeveloper.com/8avr:memory C Interface: http://ww1.microchip.com/downloads/en/AppNotes/Atmel-2575-C-Functions-for-Reading-and-Writing-to-Flash-Memory_ApplicationNote_AVR106.pdf Hmm.. I notice that compiler.h defines IOBJ as __flash but the above document says: "The datatypes are actually used as __flashor __farflashpointers (consequently 16 and 24 bit)." That should be change to __farflash. Much clearer information here: https://gcc.gnu.org/onlinedocs/gcc/Named-Address-Spaces.html
Re: Can we implement ctype functions through table?
What about platforms like AVR? That would not be a good decision for AVR since it is a harvard machine and cannot access data in ROM without special operations. This is not a show stopper, at least not for the AVR. While a table-driven solution is not optimal for AVR, it will support access to constant data in ROM if the data has the storage class IOBJ as defined in include/nuttx/compiler.h. I don't know if the compiler will automatically generate the correct instruction to access the table across the bus bridge; I am not an AVR expert. There is a up_ function may need to be used to access the ROM table??? AVR Memory: https://microchipdeveloper.com/8avr:memory C Interface: http://ww1.microchip.com/downloads/en/AppNotes/Atmel-2575-C-Functions-for-Reading-and-Writing-to-Flash-Memory_ApplicationNote_AVR106.pdf Hmm.. I notice that compiler.h defines IOBJ as __flash but the above document says: "The datatypes are actually used as __flashor __farflashpointers (consequently 16 and 24 bit)." That should be change to __farflash.
RE: Can we implement ctype functions through table?
I would consider option 3 to be the worst choice. That could bloat can be
enormous and unacceptable as I have seen in the past. I saw growth by many
kbyte in such cases. Not a good compromise.Sent from Samsung tablet.
Original message From: Xiang Xiao
Date: 7/29/20 12:54 AM (GMT-06:00) To: dev@nuttx.apache.org Subject: RE: Can
we implement ctype functions through table? The new option just make the
situation worse. The same code works insome configurations, but breaks in other
configurations.Since the standard confirmation is the most important principle
forNuttX, we have three options:1.Implement ctype function with table and add
256 byte to ROM2.Change macro to normal function and lose some
performance3.Change macro to inline function and some old compilers may
generatethe bloat codeall ctype functions are one line code, so option 3 may be
a good compromise.> -Original Message-> From: David Sidrane
> Sent: Tuesday, July 28, 2020 8:23 PM> To:
dev@nuttx.apache.org> Subject: RE: Can we implement ctype functions through
table?>> Xiang,>> If there is a small usage do you think flash will grow by 256
bytes? I> would be surprised.>> Should you uses a config option?>> David>>>
-Original Message-> From: Xiang Xiao
[mailto:xiaoxiang781...@gmail.com]> Sent: Monday, July 27, 2020 10:40 PM> To:
dev@nuttx.apache.org> Subject: RE: Can we implement ctype functions through
table?>> Decorate the table with IPTR and access the element through
up_romgetc,> just like printf series function.>> > -Original Message->
> From: Gregory Nutt > > Sent: Tuesday, July 28, 2020
12:44 PM> > To: dev@nuttx.apache.org> > Subject: Re: Can we implement ctype
functions through table?> >> > What about platforms like AVR? That would not
be a good decision for> > AVR since it is a harvard machine and cannot access
data in ROM> > without special operations.> >> >> > On 7/27/2020 9:55 PM, Xiang
Xiao wrote:> > > Hi all,> > > For example, here is isspace implementation:> > >
# define isspace(c) \> > > ((c) == ' ' || (c) == '\t' || (c) == '\n' ||
(c) == '\r' || \> > > (c) == '\f' || (c) == '\v')> > > The argument of c
will evaluate 6 times, which make the following> > > code suddenly fail:> > >
while (end != begin)> > > {> > > If (!isspace(*--end))> > > {> >
> break;> > > }> > > }> > > But it work well with other
libc implementation, because all other> > > libc utilize a table to classify
the char type:> > >
https://github.com/bminor/newlib/blob/master/newlib/libc/include/cty> > > pe> >
> .h#L97> > > https://github.com/bminor/glibc/blob/master/ctype/ctype.h#L197> >
> and the argument only need evaluate once.> > > So my question is: can we
implement ctype functions through table to> > > improve the compatibility?> > >
Yes, the table need take more 256 bytes ROM space, but the complex> > >
expression used in NuttX also bloat the code size, especially> > > considering
ctype function is used very frequently.> > >> > > Thanks> > > Xiang> > >
RE: Can we implement ctype functions through table?
The new option just make the situation worse. The same code works in
some configurations, but breaks in other configurations.
Since the standard confirmation is the most important principle for
NuttX, we have three options:
1.Implement ctype function with table and add 256 byte to ROM
2.Change macro to normal function and lose some performance
3.Change macro to inline function and some old compilers may generate
the bloat code
all ctype functions are one line code, so option 3 may be a good compromise.
> -Original Message-
> From: David Sidrane
> Sent: Tuesday, July 28, 2020 8:23 PM
> To: dev@nuttx.apache.org
> Subject: RE: Can we implement ctype functions through table?
>
> Xiang,
>
> If there is a small usage do you think flash will grow by 256 bytes? I
> would be surprised.
>
> Should you uses a config option?
>
> David
>
>
> -Original Message-
> From: Xiang Xiao [mailto:xiaoxiang781...@gmail.com]
> Sent: Monday, July 27, 2020 10:40 PM
> To: dev@nuttx.apache.org
> Subject: RE: Can we implement ctype functions through table?
>
> Decorate the table with IPTR and access the element through up_romgetc,
> just like printf series function.
>
> > -Original Message-
> > From: Gregory Nutt
> > Sent: Tuesday, July 28, 2020 12:44 PM
> > To: dev@nuttx.apache.org
> > Subject: Re: Can we implement ctype functions through table?
> >
> > What about platforms like AVR? That would not be a good decision for
> > AVR since it is a harvard machine and cannot access data in ROM
> > without special operations.
> >
> >
> > On 7/27/2020 9:55 PM, Xiang Xiao wrote:
> > > Hi all,
> > > For example, here is isspace implementation:
> > > # define isspace(c) \
> > > ((c) == ' ' || (c) == '\t' || (c) == '\n' || (c) == '\r' || \
> > > (c) == '\f' || (c) == '\v')
> > > The argument of c will evaluate 6 times, which make the following
> > > code suddenly fail:
> > > while (end != begin)
> > >{
> > > If (!isspace(*--end))
> > >{
> > > break;
> > >}
> > >}
> > > But it work well with other libc implementation, because all other
> > > libc utilize a table to classify the char type:
> > > https://github.com/bminor/newlib/blob/master/newlib/libc/include/cty
> > > pe
> > > .h#L97
> > > https://github.com/bminor/glibc/blob/master/ctype/ctype.h#L197
> > > and the argument only need evaluate once.
> > > So my question is: can we implement ctype functions through table to
> > > improve the compatibility?
> > > Yes, the table need take more 256 bytes ROM space, but the complex
> > > expression used in NuttX also bloat the code size, especially
> > > considering ctype function is used very frequently.
> > >
> > > Thanks
> > > Xiang
> > >
RE: Can we implement ctype functions through table?
Xiang,
If there is a small usage do you think flash will grow by 256 bytes? I would
be surprised.
Should you uses a config option?
David
-Original Message-
From: Xiang Xiao [mailto:xiaoxiang781...@gmail.com]
Sent: Monday, July 27, 2020 10:40 PM
To: dev@nuttx.apache.org
Subject: RE: Can we implement ctype functions through table?
Decorate the table with IPTR and access the element through up_romgetc, just
like printf series function.
> -Original Message-
> From: Gregory Nutt
> Sent: Tuesday, July 28, 2020 12:44 PM
> To: dev@nuttx.apache.org
> Subject: Re: Can we implement ctype functions through table?
>
> What about platforms like AVR? That would not be a good decision for AVR
> since it is a harvard machine and cannot access data in
> ROM without special operations.
>
>
> On 7/27/2020 9:55 PM, Xiang Xiao wrote:
> > Hi all,
> > For example, here is isspace implementation:
> > # define isspace(c) \
> > ((c) == ' ' || (c) == '\t' || (c) == '\n' || (c) == '\r' || \
> > (c) == '\f' || (c) == '\v')
> > The argument of c will evaluate 6 times, which make the following code
> > suddenly fail:
> > while (end != begin)
> >{
> > If (!isspace(*--end))
> >{
> > break;
> >}
> >}
> > But it work well with other libc implementation, because all other libc
> > utilize a table to classify the char type:
> > https://github.com/bminor/newlib/blob/master/newlib/libc/include/ctype
> > .h#L97
> > https://github.com/bminor/glibc/blob/master/ctype/ctype.h#L197
> > and the argument only need evaluate once.
> > So my question is: can we implement ctype functions through table to
> > improve the compatibility?
> > Yes, the table need take more 256 bytes ROM space, but the complex
> > expression used in NuttX also bloat the code size, especially
> > considering ctype function is used very frequently.
> >
> > Thanks
> > Xiang
> >
RE: Can we implement ctype functions through table?
Decorate the table with IPTR and access the element through up_romgetc, just
like printf series function.
> -Original Message-
> From: Gregory Nutt
> Sent: Tuesday, July 28, 2020 12:44 PM
> To: dev@nuttx.apache.org
> Subject: Re: Can we implement ctype functions through table?
>
> What about platforms like AVR? That would not be a good decision for AVR
> since it is a harvard machine and cannot access data in
> ROM without special operations.
>
>
> On 7/27/2020 9:55 PM, Xiang Xiao wrote:
> > Hi all,
> > For example, here is isspace implementation:
> > # define isspace(c) \
> > ((c) == ' ' || (c) == '\t' || (c) == '\n' || (c) == '\r' || \
> > (c) == '\f' || (c) == '\v')
> > The argument of c will evaluate 6 times, which make the following code
> > suddenly fail:
> > while (end != begin)
> >{
> > If (!isspace(*--end))
> >{
> > break;
> >}
> >}
> > But it work well with other libc implementation, because all other libc
> > utilize a table to classify the char type:
> > https://github.com/bminor/newlib/blob/master/newlib/libc/include/ctype
> > .h#L97
> > https://github.com/bminor/glibc/blob/master/ctype/ctype.h#L197
> > and the argument only need evaluate once.
> > So my question is: can we implement ctype functions through table to
> > improve the compatibility?
> > Yes, the table need take more 256 bytes ROM space, but the complex
> > expression used in NuttX also bloat the code size, especially considering
> > ctype function is used very frequently.
> >
> > Thanks
> > Xiang
> >
Re: Can we implement ctype functions through table?
What about platforms like AVR? That would not be a good decision for
AVR since it is a harvard machine and cannot access data in ROM without
special operations.
On 7/27/2020 9:55 PM, Xiang Xiao wrote:
Hi all,
For example, here is isspace implementation:
# define isspace(c) \
((c) == ' ' || (c) == '\t' || (c) == '\n' || (c) == '\r' || \
(c) == '\f' || (c) == '\v')
The argument of c will evaluate 6 times, which make the following code suddenly
fail:
while (end != begin)
{
If (!isspace(*--end))
{
break;
}
}
But it work well with other libc implementation, because all other libc utilize
a table to classify the char type:
https://github.com/bminor/newlib/blob/master/newlib/libc/include/ctype.h#L97
https://github.com/bminor/glibc/blob/master/ctype/ctype.h#L197
and the argument only need evaluate once.
So my question is: can we implement ctype functions through table to improve
the compatibility?
Yes, the table need take more 256 bytes ROM space, but the complex expression
used in NuttX also bloat the code size, especially
considering ctype function is used very frequently.
Thanks
Xiang
