strlen in a for loop with malloc-ed char*

what is wrong with this code? someone told me there is a BAD practice with
that strlen in the for loop, but i don't get it exactly. Could anyone
explain me in plain english,please?

char *reverse(char *s)
{
int i;
char *r;
if(!s) return NULL;//ERROR
r=calloc(strlen(s)+1,sizeof(char));
if(!r) return NULL;
for(i=0;i<strlen(s);i++)
*(r+i) = *(s+strlen(s)-1-i);
return r;
}

--
it's not right. it's not even wrong

On Tue, 19 Oct 2004 18:53:37 +0000, apropo wrote:
[color=blue]
> what is wrong with this code? someone told me there is a BAD practice with
> that strlen in the for loop, but i don't get it exactly. Could anyone
> explain me in plain english,please?[/color]
You calculate the strlen() many times, which really isn't needed[color=blue]
> char *reverse(char *s)
> {
> int i;
> char *r;[/color]
size_t len;[color=blue]
> if(!s) return NULL;//ERROR[/color]
len = strlen(s);
r=calloc(len+1,sizeof(char));[color=blue]
> if(!r) return NULL;[/color]
for(i=0;i<len;i++)
*(r+i) = *(s+len-1-i);[color=blue]
> return r;
> }[/color]

apropo wrote:
[color=blue]
> what is wrong with this code? someone told me there is a BAD practice with
> that strlen in the for loop, but i don't get it exactly. Could anyone
> explain me in plain english,please?
>
> char *reverse(char *s)
> {
> int i;
> char *r;
> if(!s) return NULL;//ERROR
> r=calloc(strlen(s)+1,sizeof(char));
> if(!r) return NULL;
> for(i=0;i<strlen(s);i++)
> *(r+i) = *(s+strlen(s)-1-i);
> return r;
> }
>[/color]

Computing something within a loop that is invarient is wasteful.
The length of "s" isn't changed by this function, so you might
consider taking it in as a const char * to reflect that. Anyway,
more normal would be to do:

size_t len = strlen(s);

And then use len where you are using strlen(s). It is possible
that the optimizer might fix this for you, but why ask for
trouble?

The code isn't "wrong", just burns CPU where it need not.
The calloc is also slightly wasteful, in that you are zeroing
out the memory you are about to fill in just to get the nul
termination, you could just have r[len] = '\0'; after mallocing it.
Whatever.

-David

"apropo" <flavius_aspra@yahoo.com> wrote[color=blue]
>
> for(i=0;i<strlen(s);i++)
> *(r+i) = *(s+strlen(s)-1-i);
>[/color]
Imagine that the string s is huge. Then remember how the computer will
implement strlen() (write the function yourself, if you are not sure).

Are you familiar with Big O notation for algorithms? This tells you how many
operations you need for a given size of input. For instance to multiply by
repeated adding is O(N); you need to add the numbers as often as the smaller
is large. To use the algorithm you were taught at primary school is O(log
N), since the numbers of operations you require goes up by the number of
digits. The adding algorithm is OK for numbers up to ten or so, but for
large numbers the primary school way is far superior.

Similarly, your code is OK for fairly short strings, but for long ones you
will slow things down considerably. Can you work out its Big O notation?

David Resnick wrote:

[color=blue]
> Computing something within a loop that is invarient is wasteful.
> The length of "s" isn't changed by this function, so you might
> consider taking it in as a const char * to reflect that.[/color]

Are some compilers sophisticated enough to be able to detect this
condition and optimize away that strlen() call?

Brian

Default User wrote:[color=blue]
> David Resnick wrote:
>
>
>[color=green]
>>Computing something within a loop that is invarient is wasteful.
>>The length of "s" isn't changed by this function, so you might
>>consider taking it in as a const char * to reflect that.[/color]
>
>
>
> Are some compilers sophisticated enough to be able to detect this
> condition and optimize away that strlen() call?[/color]

The compiler doesn't necessarily know what your strlen() does; after all
you can write it yourself!

Robert[color=blue]
>
>
>
> Brian[/color]

On Tue, 19 Oct 2004, Robert Harris wrote:[color=blue]
> Default User wrote:[color=green]
>> David Resnick wrote:[color=darkred]
>>> Computing something within a loop that is invarient is wasteful.
>>> The length of "s" isn't changed by this function, so you might
>>> consider taking it in as a const char * to reflect that.[/color]
>>
>> Are some compilers sophisticated enough to be able to detect this
>> condition and optimize away that strlen() call?[/color]
>
> The compiler doesn't necessarily know what your strlen() does; after
> all you can write it yourself![/color]

Not in standard C. IIRC, attempting to redefine a standard library
function invokes undefined behavior. (And AFAIK it's quite possible that
the above optimization is the /only/ reason such redefinitions were made
undefined.)

-Arthur

Robert Harris wrote:
[color=blue]
> Default User wrote:[color=green]
> > David Resnick wrote:
> >
> >
> >[color=darkred]
> > > Computing something within a loop that is invarient is wasteful.
> > > The length of "s" isn't changed by this function, so you might
> > > consider taking it in as a const char * to reflect that.[/color]
> >
> >
> >
> > Are some compilers sophisticated enough to be able to detect this
> > condition and optimize away that strlen() call?[/color]
>
> The compiler doesn't necessarily know what your strlen() does; after
> all you can write it yourself![/color]

What do you mean? It knows its signature:

size_t strlen(const char *s)

Therefore it knows that it doesn't change s. It also knows what
strlen() does (as it is a standard library function).

Brian

"Default User" <first.last@boeing.com.invalid> writes:
[color=blue]
> What do you mean? It knows its signature:
>
> size_t strlen(const char *s)
>
> Therefore it knows that it doesn't change s.[/color]

Not true. A function parameter's const-ness does not allowed the
compiler to assume that the function will not modify the
argument. It is perfectly valid for it to cast away the
const-ness and modify it anyway (as long as the object that it
refers to is not actually defined as const). `const' in function
parameters is a social contract between the caller and the
callee, not a constraint made by the standard.
--
Ben Pfaff
email: blp@cs.stanford.edu
web: http://benpfaff.org

Ben Pfaff wrote:
[color=blue]
> "Default User" <first.last@boeing.com.invalid> writes:
>[color=green]
> > What do you mean? It knows its signature:
> >
> > size_t strlen(const char *s)
> >
> > Therefore it knows that it doesn't change s.[/color]
>
> Not true. A function parameter's const-ness does not allowed the
> compiler to assume that the function will not modify the
> argument. It is perfectly valid for it to cast away the
> const-ness and modify it anyway (as long as the object that it
> refers to is not actually defined as const). `const' in function
> parameters is a social contract between the caller and the
> callee, not a constraint made by the standard.[/color]

Ok, good point. Looking at n689, it specifies what strlen() does, but
doesn't say that it is forbidden to change the string. It would be a
pretty perverse implementation with a poor QOS.

Brian

apropo wrote:
[color=blue]
> what is wrong with this code? someone told me there is a BAD practice with
> that strlen in the for loop, but i don't get it exactly. Could anyone
> explain me in plain english,please?
>
> char *reverse(char *s)
> {
> int i;
> char *r;
> if(!s) return NULL;//ERROR
> r=calloc(strlen(s)+1,sizeof(char));
> if(!r) return NULL;
> for(i=0;i<strlen(s);i++)[/color]

Every time you go through the loop, you get the length of the string again.
Since it's not going to change, this is a huge waste of time (turns an O(n)
algorithm into an O(n^2) !). Save strlen(s) to a local variable once, then
use that instead.
[color=blue]
> *(r+i) = *(s+strlen(s)-1-i);
> return r;
> }
>[/color]

Default User wrote:[color=blue]
>
> Ok, good point. Looking at n689, it specifies what strlen() does, but
> doesn't say that it is forbidden to change the string. It would be a
> pretty perverse implementation with a poor QOS.
>[/color]

A standard compliant strlen is not allowed to change the string.
If a function can do whatever it wants as long as the standard
does not specify that it cannot then it is impossible to write a
strictly conforming program that uses any standard functions.

In fact the standard only specifies what operators do, not what
they cannot do! It would in fact be impossible to write any strictly
conforming program at all with the possible exception of

int main(void)
{
return 0;
}

But then again, the standard does not specify completely what return
cannot do.

Relating to the point above. The compiler can optimise out calls to
strlen because it knows the implementation. In general it cannot do this
with functions unless it can deduce that no side effects are taking
place and that is impossible by just looking at the prototype. It is
possible (sometimes) if the compiler has access to the implementation of
a function.

--
Thomas.

"Arthur J. O'Dwyer" <ajo@nospam.andrew.cmu.edu> wrote in message
news:Pine.LNX.4.60-041.0410191642160.7937@unix49.andrew.cmu.edu...[color=blue]
>
> On Tue, 19 Oct 2004, Robert Harris wrote:[color=green]
> > Default User wrote:[color=darkred]
> >> David Resnick wrote:
> >>> Computing something within a loop that is invarient is wasteful.
> >>> The length of "s" isn't changed by this function, so you might
> >>> consider taking it in as a const char * to reflect that.
> >>
> >> Are some compilers sophisticated enough to be able to detect this
> >> condition and optimize away that strlen() call?[/color]
> >
> > The compiler doesn't necessarily know what your strlen() does; after
> > all you can write it yourself![/color]
>
> Not in standard C. IIRC, attempting to redefine a standard library
> function invokes undefined behavior. (And AFAIK it's quite possible that
> the above optimization is the /only/ reason such redefinitions were made
> undefined.)[/color]

Ok.. so if i want to use my own 'strlen' (my_strlen) instead of standard
one(or any function defined by standard )can I not do that ?

Something like
#ifdef strlen
#undef strlen
#define strlen my_strlen

Cant afford to change all the places where i have called strlen !

- Ravi

[color=blue]
>
> -Arthur[/color]

Thomas Stegen wrote:
[color=blue]
> Relating to the point above. The compiler can optimise out calls to
> strlen because it knows the implementation. In general it cannot do this
> with functions unless it can deduce that no side effects are taking
> place and that is impossible by just looking at the prototype. It is
> possible (sometimes) if the compiler has access to the implementation of
> a function.[/color]
It would also have to perform a bit heuristic to determin that calls
to strlen could be done fewer times than actual started. This can
quickly become nontrivial.

Ravi Uday wrote:
[color=blue]
> Ok.. so if i want to use my own 'strlen'
> (my_strlen) instead of standard
> one(or any function defined by standard )can I not do that ?
>
> Something like
> #ifdef strlen
> #undef strlen
> #define strlen my_strlen
>
> Cant afford to change all the places where i have called strlen ![/color]

That doesn't do anything if strlen isn't implemented as a macro.
It doesn't have to be and I think that strlen usually isn't.

I don't know if redefining standard macros yields undefined behavior.
It seems like a bad idea.

--
pete

Hiho,

pete wrote:[color=blue]
> Ravi Uday wrote:
>[color=green]
>> Ok.. so if i want to use my own 'strlen'
>>(my_strlen) instead of standard
>>one(or any function defined by standard )can I not do that ?
>>
>> Something like
>> #ifdef strlen
>> #undef strlen
>> #define strlen my_strlen
>>
>> Cant afford to change all the places where i have called strlen ![/color][/color]

Umh, the standard says strlen is a function so you cannot do this.
Apart from that: If you "hide" this nice trick of yours in a
general header file and other people are not aware of that then
they expect strlen (read: my_strlen) to behave like strlen (read:
strlen). If you really want to do something along these lines,
use a macro with a name like STRLEN or even a function pointer
called, for example, StrLenPtr. Thus, your intent becomes clearer.
Do not use names starting with str as these are reserved for
future library extensions.

[color=blue]
> That doesn't do anything if strlen isn't implemented as a macro.[/color]

Unfortunately, if you do it "right", it does:

#include <string.h>

#ifdef strlen
#undef strlen
#endif
#define strlen(STR) my_strlen(STR)

size_t my_strlen(const char *s)
{
return 0;
}

int main (void)
{
strlen("test");

return 0;
}

compiles and a look at the preprocessor output shows that
strlen("test");
becomes
my_strlen("test");

You can have very funny effects if you use my_strlen() in very
rare cases as wrapper for strlen() but #define strlen before
you define my_strlen(). Then, everything works most of the time
but in some cases you have either recursive calls to my_strlen
without end or seemingly arbitrary results or whatever.
Nice trap.

[color=blue]
> It doesn't have to be and I think that strlen usually isn't.[/color]

Yep.
[color=blue]
> I don't know if redefining standard macros yields undefined behavior.
> It seems like a bad idea.[/color]

Definitely! I'd even go as far and declare it a Bad Idea...

Cheers
Michael

Michael Mair wrote:[color=blue]
>
> Hiho,
>
> pete wrote:[color=green]
> > Ravi Uday wrote:[/color][/color]
[color=blue][color=green][color=darkred]
> >> Something like
> >> #ifdef strlen
> >> #undef strlen
> >> #define strlen my_strlen[/color][/color][/color]
[color=blue][color=green]
> > That doesn't do anything if strlen isn't implemented as a macro.[/color]
>
> Unfortunately, if you do it "right", it does:[/color]

Thank you.

--
pete

In article <I5unA1.1u3@news.boeing.com>, "Default User" <first.last@boeing.com.invalid> writes:[color=blue]
> Robert Harris wrote:
>[color=green]
> > Default User wrote:[color=darkred]
> > >
> > > Are some compilers sophisticated enough to be able to detect this
> > > condition and optimize away that strlen() call?[/color]
> >
> > The compiler doesn't necessarily know what your strlen() does; after
> > all you can write it yourself![/color]
>
> What do you mean? It knows its signature:
>
> size_t strlen(const char *s)
>
> Therefore it knows that it doesn't change s.[/color]

The special case of standard functions aside, and the case of casting
away constness aside, this still isn't sufficient to optimize away
the call to a function. The function could have side effects besides
altering its parameters.

The *only* reason why an implementation might be able to optimize
away calls to standard functions is because it knows exactly what
they do. That's the only sufficient guarantee. (Note that this
also requires the restriction against redefining them.)

Of course, an implementation could introduce an extension - such as
a pragma - to denote "pure" functions which have no side effects and
make no use of external state and so could be similarly optimized
away when called repeatedly with the same parameters.[1] However,
standard C has no such facility.

1. Note that a function with no side effects must be a function only
of its input. Maintaining any kind of state between calls would be
a side effect. The restriction against using external state is
necessary to exclude things like clock(), which has no side effects
(except indirectly the one of taking non-zero execution time) but
should not be optimized away, as its return value changes over time.

--
Michael Wojcik michael.wojcik@microfocus.com

The surface of the word "profession" is hard and rough, the inside mixed with
poison. It's this that prevents me crossing over. And what is there on the
other side? Only what people longingly refer to as "the other side".
-- Tawada Yoko (trans. Margaret Mitsutani)

In article <I5uKGK.LBp@news.boeing.com>, first.last@boeing.com.invalid says...[color=blue]
> David Resnick wrote:
>
>[color=green]
> > Computing something within a loop that is invarient is wasteful.
> > The length of "s" isn't changed by this function, so you might
> > consider taking it in as a const char * to reflect that.[/color]
>
>
> Are some compilers sophisticated enough to be able to detect this
> condition and optimize away that strlen() call?[/color]

Not any of the majors, including gcc, lcc-win32 and MSVC. See a recent
thread on loop invariants in comp.programming for empirical data based
upon this same question.

--
Randy Howard (2reply remove FOOBAR)

In article <MPG.1be099a97fa554c0989b31@news.verizon.net>,
randyhoward@FOOverizonBAR.net says...[color=blue]
> In article <I5uKGK.LBp@news.boeing.com>, first.last@boeing.com.invalid says...[color=green]
> > David Resnick wrote:
> >
> >[color=darkred]
> > > Computing something within a loop that is invarient is wasteful.
> > > The length of "s" isn't changed by this function, so you might
> > > consider taking it in as a const char * to reflect that.[/color]
> >
> >
> > Are some compilers sophisticated enough to be able to detect this
> > condition and optimize away that strlen() call?[/color]
>
> Not any of the majors, including gcc, lcc-win32 and MSVC. See a recent
> thread on loop invariants in comp.programming for empirical data based
> upon this same question.[/color]

Correction, I didn't mean to imply that lcc is a "major" compiler, it
just happened to come up near the end of the thread and I included it
as a result.

--
Randy Howard (2reply remove FOOBAR)

<snip>[color=blue]
> Unfortunately, if you do it "right", it does:
>
> #include <string.h>
>
> #ifdef strlen
> #undef strlen
> #endif
> #define strlen(STR) my_strlen(STR)
>[/color]

But you just said re-defining any standard functions is a UB. !!
So does the 'right' code you posted correct ?
[color=blue]
> size_t my_strlen(const char *s)
> {
> return 0;
> }
>
> int main (void)
> {
> strlen("test");
>
> return 0;
> }
>
> compiles and a look at the preprocessor output shows that
> strlen("test");
> becomes
> my_strlen("test");[/color]

<snip>
[color=blue][color=green]
> > I don't know if redefining standard macros yields undefined behavior.
> > It seems like a bad idea.[/color]
>
> Definitely! I'd even go as far and declare it a Bad Idea...[/color]

My requirement is simple.
I am asked to replace all calls to 'strlen' by another user defined function
'my_strlen'
One way is to manually go and replace all of them. Which is a very tedious
(more than 500 entries !!) approach.
Other way is to undefine it at the start of the .c/.h and redifine with
my_strlen !!
Is there a way to accomplish this ?.

Thanks,
- Ravi

Hiho,

Ravi Uday wrote:[color=blue]
> <snip>
>[color=green]
>>Unfortunately, if you do it "right", it does:
>>
>>#include <string.h>
>>
>>#ifdef strlen
>>#undef strlen
>>#endif
>>#define strlen(STR) my_strlen(STR)[/color]
>
> But you just said re-defining any standard functions is a UB. !!
> So does the 'right' code you posted correct ?[/color]

Umh, sorry, sometimes sarcasm and such like do not transport
as well as one would hope.
- I do not expect the
#ifdef strlen
#undef strlen
#endif
sequence to do anything, as strlen() usually is not #define'd
(you snipped that part of my and pete's answer). However, I wanted
to point out to pete and you, how it could be done, _even_ if I
think it terribly _wrong_.
I showed you how to do what you should _never_ do, for the mentioned
reasons (which you snipped as well).
- My code works in this example and works not for the cases I pointed
out...
[color=blue]
>
>[color=green]
>>size_t my_strlen(const char *s)
>>{[/color][/color]
.... take for example the function body
return strlen(s);
This does not work and leads to infinite recursion.
Just read once again what I have written.
[color=blue][color=green]
>> return 0;
>>}
>>
>>int main (void)
>>{
>> strlen("test");
>>
>> return 0;
>>}
>>
>>compiles and a look at the preprocessor output shows that
>>strlen("test");
>>becomes
>>my_strlen("test");[/color]
>
>
> <snip>
>[color=green][color=darkred]
>>>I don't know if redefining standard macros yields undefined behavior.
>>>It seems like a bad idea.[/color]
>>
>>Definitely! I'd even go as far and declare it a Bad Idea...[/color]
>
> My requirement is simple.
> I am asked to replace all calls to 'strlen' by another user defined function
> 'my_strlen'
> One way is to manually go and replace all of them. Which is a very tedious
> (more than 500 entries !!) approach.
> Other way is to undefine it at the start of the .c/.h and redifine with
> my_strlen !!
> Is there a way to accomplish this ?.[/color]

Well, if you want my opinion: Find and replace all occurrences of
strlen which are a word (or have no a-zA-Z0-9_ at the beginning or end
of them) using sed or the editor of your choice.
Replace them either by a macro name or by my_strlen.
Nearly all good programming editors will permit you to use regular
expressions and handle all opened files or even all files of a type
in a directory in that way. This is a matter of five minutes:
four to try it out in one test document for all cases you can think of,
one to apply it to your source code and save it -- and these are
very generous time estimates.
<OT>
If you use nedit, TextPad or have a UNIX like environment, I will
happily provide you with an easy way to do it. Write me an e-mail.
Otherwise: Editors have manuals and most of them online help.
</OT>
If you work with an editor which cannot do that: Switch to something
useful.

Cheers
Michael
--
E-Mail: Mine is a gmx dot de address.

Michael Mair wrote:[color=blue]
>
> Hiho,
>
> pete wrote:[color=green]
> > Ravi Uday wrote:
> >[color=darkred]
> >> Ok.. so if i want to use my own 'strlen'
> >>(my_strlen) instead of standard
> >>one(or any function defined by standard )can I not do that ?
> >>
> >> Something like
> >> #ifdef strlen
> >> #undef strlen
> >> #define strlen my_strlen[/color][/color][/color]
[color=blue][color=green]
> > I don't know if redefining standard macros
> > yields undefined behavior.
> > It seems like a bad idea.[/color]
>
> Definitely! I'd even go as far and declare it a Bad Idea...[/color]

I think that it's undefined behavior regardless of whether or not
strlen is implemented as a macro.

N869
7.1.3 Reserved identifiers
[#1] Each header declares or defines all identifiers listed
in its associated subclause, and optionally declares or
defines identifiers listed in its associated future library
directions subclause and identifiers which are always
reserved either for any use or for use as file scope
identifiers.

-- Each macro name in any of the following subclauses
(including the future library directions) is reserved
for use as specified if any of its associated headers
is included; unless explicitly stated otherwise (see
7.1.4).
-- All identifiers with external linkage in any of the
following subclauses (including the future library
directions) are always reserved for use as identifiers
with external linkage.

--
pete

pete wrote:[color=blue]
> Michael Mair wrote:
>[color=green]
>>pete wrote:[color=darkred]
>>>I don't know if redefining standard macros
>>>yields undefined behavior.
>>>It seems like a bad idea.[/color]
>>
>>Definitely! I'd even go as far and declare it a Bad Idea...[/color]
>
> I think that it's undefined behavior regardless of whether or not
> strlen is implemented as a macro.
>
> N869
> 7.1.3 Reserved identifiers
> [#1] Each header declares or defines all identifiers listed
> in its associated subclause, and optionally declares or
> defines identifiers listed in its associated future library
> directions subclause and identifiers which are always
> reserved either for any use or for use as file scope
> identifiers.
>
> -- Each macro name in any of the following subclauses
> (including the future library directions) is reserved
> for use as specified if any of its associated headers
> is included; unless explicitly stated otherwise (see
> 7.1.4).
> -- All identifiers with external linkage in any of the
> following subclauses (including the future library
> directions) are always reserved for use as identifiers
> with external linkage.[/color]

Thank you; moreover, the standard has five items in the list
the last of which is IMO more "useful" in this case:

-- Each identifier with file scope listed in any of the following
subclauses (including the future library directions) is
reserved for use as a macro name and as an identifier with
file scope in the same name space if any of its associated
headers is included.

Cheers,
Michael
--
E-Mail: Mine is a gmx dot de address.

<snip>
[color=blue]
> Well, if you want my opinion: Find and replace all occurrences of
> strlen which are a word (or have no a-zA-Z0-9_ at the beginning or end
> of them) using sed or the editor of your choice.
> Replace them either by a macro name or by my_strlen.
> Nearly all good programming editors will permit you to use regular
> expressions and handle all opened files or even all files of a type
> in a directory in that way. This is a matter of five minutes:
> four to try it out in one test document for all cases you can think of,
> one to apply it to your source code and save it -- and these are
> very generous time estimates.
> <OT>
> If you use nedit, TextPad or have a UNIX like environment, I will
> happily provide you with an easy way to do it. Write me an e-mail.
> Otherwise: Editors have manuals and most of them online help.
> </OT>[/color]

Whats your mail id..I work on UNIX, you could mail me at the addr
in my message.

[color=blue]
> If you work with an editor which cannot do that: Switch to something
> useful.
>
>
> Cheers
> Michael
> --
> E-Mail: Mine is a gmx dot de address.[/color]

strlen in a for loop with malloc-ed char*

Post your reply

Question stats

Most Active

Most Questions Answered

Top Questions

Latest Questions

Similar topics

More