Highly efficient string reversal code

[Richard Heathfield]

Re: Highly efficient string reversal code

Peter Nilsson said:

Richard<rgr...@ gmail.comwrote:

<snip>

>To get me started on the path of righteousness can
>you point out where I should learn/read that in the
>n1256.txt? As, frankly, I find the standard document
>quite daunting and confusing.

>
Your path to righteousness begins with not slagging off
people who are prepared to do what you can't or won't.

He also needs to learn to understand viewpoints that he doesn't agree with,
or at least accept that they are held honestly and for good reason.

He needs to stop believing his own caricatures of those positions, e.g.
turning moderate claims such as "I do sometimes use debuggers but normally
I can find bugs quicker some other way" and "I have on occasion found bugs
in a program simply by reading the source" into the ludicrous "I never use
debuggers because I can find all the bugs in a 500KLOC program by printing
it out, why can't you, duh"[1].

He needs to stop arrogantly insulting the motivations and character of
practically all those in the group who disagree with him, and he needs to
drop the hypocrisy of accusing others of arrogance when he is just about
the most arrogant person here.

I hope he does do all these things, but I'm not holding my breath. Perhaps
someone could clue me in if he ever does decide to join clc civilisation?



[1] Exact wording of original may differ from illustration. Stocks may go
up as well as down. Battery hens not included. Keep away from children. If
you do not accept this licence agreement and wish to claim the $5 refund,
send $20 to cover our expenses. Avoid direct exposure to sunlight. And all
the other disclaimers I can think of (or rather, the ones I can't think
of).

--
Richard Heathfield <http://www.cpax.org.uk >
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[Flash Gordon]

Re: Highly efficient string reversal code

Richard wrote, On 23/09/08 07:40:

Peter Nilsson <airia@acay.com .auwrites:
>

>Richard<rgr... @gmail.comwrote :

<snip>

Now back to "undefined" .
>
And my code.
>

>>while(p-- s)

>
Where does "undefined" in any shape or form indicate that there will be
knock on effects outside of the value of the variable in question
considering it is not used anymore? And if that variable is not used
anymore does it really matter? Its like using (or not using rather) an
uninitialised pointer.
>
Yes, I know "undefined" can mean "anything", but lets stay real here for
a moment. Possibly "undefined" is "defined" to mean "undefined for that
variable in question".
>
Or?

It means the behaviour of the program, not just that variable, is undefined.

One reason it might cause the program to abort is that the object
pointed to might be at the beginning of a page or section or whatever
and the processor could trap on decrementing past the beginning of the
page. This would be eminently sensible behaviour and help on detecting
certain classes of bugs. Depending on the processor design it might be
easier to trap on the calculation than the dereference. As to why the
trap might occur at some unexpected time, the optimiser might have
rearranged the code with the assumption that you don't invoke undefined
behaviour by calculating a pointer to before the beginning of an object.
--
Flash Gordon
If spamming me sent it to smap@spam.cause way.com
If emailing me use my reply-to address
See the comp.lang.c Wiki hosted by me at http://clc-wiki.net/

[Nick Keighley]

Re: Highly efficient string reversal code

On 23 Sep, 01:01, Keith Thompson <ks...@mib.orgw rote:

Richard<rgr...@ gmail.comwrites :

[creating a pointer to one-before the start of an array is UB]

And which now makes me ask if this is UDB too:

>
(UDB meaning Undefined Behavior; the more common abbreviation around
here is UB.)
>

unsigned int i=0;
while(i--){
}

>

While I would not normally do such things I know they exist all over the
place. Keeping in mind that the -- value is never actually used.

>
No, why would you think the behavior might be undefined?  Decrementing
an unsigned object with the value 0 simply sets it to UINT_MAX.

Richard's post is easier to understand if you remember that he
thinks pointers are integers and that his debugger confirms it.

:-)


--
Nick Keighley

[Nick Keighley]

Re: Highly efficient string reversal code

On 23 Sep, 07:40, Richard<rgr...@ gmail.comwrote:

Peter Nilsson <ai...@acay.com .auwrites:

Richard<rgr...@ gmail.comwrote:

>>An object pointer can have only 4 different kinds of
>>values:
>>1    Address of an object
>>2    One more than the address of an object
>>3    null pointer value
>>4    indeterminate value

>

       5    Address of a function

>

OK, I learnt something there. I have been too lazy with
certain aspects (and I'm not referring to the silly zero
length error there) of my C coding and I never, ever
considered a line like

>

while(p-- s)

>

to have UDB risks. ...
<snip>
To get me started on the path of righteousness can
you point out where I should learn/read that in the
n1256.txt? As, frankly, I find the standard document
quite daunting and confusing.

>

Your path to righteousness begins with not slagging off
people who are prepared to do what you can't or won't.

>
Hold on - I still dont hold with the other version from cbf. Frankly any
prodding he gets is his own fault - he spends 90% of his posts doing
much the same. And I dont slag off correct code either.

was cbf's code incorrect?

I do however
slag off ridiculous bullying and silly preening with such claims as "I
dont need a debugger and neither do you" or "your debugger uses numbers
for pointers? Really"? etc etc etc . It makes this group a very tense
and strange place to be at times.

well you don't exactly help


<snip>

--
Nick Keighley

[Nick Keighley]

Re: Highly efficient string reversal code

On 23 Sep, 05:55, CBFalconer <cbfalco...@yah oo.comwrote:

"lovecreatesbea ...@gmail.com" wrote:

My version

>

char *reverse(char *p)

<snip>

Much better.  It still doesn't handle a NULL input,

since NULL isn't a valid string nor should it.
At best NULL should assert

and has the
error of returning the string pointer rather than the string
length.  Which is only an error in optimization, not coding.

....is only an error of opinion


--
Nick Keighley

[Nick Keighley]

Re: Highly efficient string reversal code

On 23 Sep, 05:51, CBFalconer <cbfalco...@yah oo.comwrote:

"lovecreatesbea ...@gmail.com" wrote:

pete <pfil...@mindsp ring.comwrote:

>
... snip ...
>

It's undefined when attempting to reverse a zero length string.

>

How to reverse a zero length string for it has only a single
NULL terminating character : )

note: NULL is not a character. '\0' *is* a character.

The reverse function quits if this is the case.

>
Not mine, which was posted earlier.  It also considers a NULL
passed in as indicating an empty string, and returns 0 (for input
length).

which I consider a bug


--
Nick Keighley

[Nick Keighley]

Re: Highly efficient string reversal code

On 22 Sep, 19:42, dominantuberg.. .@ymail.com wrote:

Hello, I'm a highly experienced expert C programmer and I've written
this code to reverse a string in place. I think you could all learn
something from it!
>
int reverse(char* reverseme){
   int retval=-1;
   if(retval!=NULL ){
      int len=strlen(retv al){
      if(len>0){
         int half=len>>1;
         for(;retval<hal f;retval++){
            reverseme[retval]^=reverseme[len-(retval+1)];
            reverseme[len-(retval+1)]=reverseme[retval];
            reverseme[retval]^=reverseme[len-(retval+1)];

for newbies: don't do this. It is a very stupid way to swap two
integers.

         }
      }
   }
   return retval;
>
}

missing }

--
Nick Keighley

[Bartc]

Re: Highly efficient string reversal code

<dj3vande@csclu b.uwaterloo.ca. invalidwrote in message
news:gb966o$cok $1@rumours.uwat erloo.ca...

In article <9DUBk.61567$E4 1.7240@text.new s.virginmedia.c om>,
Bartc <bc@freeuk.comw rote:

>>
>><dj3vande@csc lub.uwaterloo.c a.invalidwrote in message
>>news:gb8vs6$a mh$1@rumours.uw aterloo.ca...
>>

>>Since the subject has come up, here's one I've been waiting for an
>>excuse to post:

>
[...]
>

>>I tested your reverse function against the simplest reverse function of my
>>own I could knock up. Mine was 6 to 20 times faster that yours, to reverse
>>a
>>77-character string one million times on my machine.
>>
>>So if there is a point to your version, I haven't quite grasped it.

>
I'd rather give my version to somebody who's posting an obvious
homework problem than yours.

Nobody mentioned homework. Anyway there are plenty of versions of this
around; my code is practically identical to that in K&R2.

>
Once you untangle it, it also demonstrates a few code-structure ideas
that are quite useful to have wrapped your brain around (not that
reversing a string in C is really a _good_ way to illustrate those),
and I like to think it provides a nifty example of how to build working
approximations to some high-level abstractions that C doesn't provide
natively.

I've had a brief look, although I really think you need to lay out your code
better.

--
Bartc

[vippstar@gmail.com]

Re: Highly efficient string reversal code

On Sep 23, 11:19 am, Nick Keighley <nick_keighley_ nos...@hotmail. com>
wrote:

On 23 Sep, 05:51, CBFalconer <cbfalco...@yah oo.comwrote:
>

"lovecreatesbea ...@gmail.com" wrote:

The reverse function quits if this is the case.

>

Not mine, which was posted earlier. It also considers a NULL
passed in as indicating an empty string, and returns 0 (for input
length).

>
which I consider a bug

Depends on the documentation. Do you consider it a bug if strlen(NULL)
returns 0?
I'd just document that NULL shouldn't be passed to such function; what
it does after that is not important. (ie returning 0 or dereferencing
a null pointer)

[James Kuyper]

Re: Highly efficient string reversal code

Richard wrote:

Peter Nilsson <airia@acay.com .auwrites:
>

>Richard<rgr... @gmail.comwrote :

....

>>while(p-- s)

>
Where does "undefined" in any shape or form indicate that there will be
knock on effects outside of the value of the variable in question
considering it is not used anymore? And if that variable is not used
anymore does it really matter? Its like using (or not using rather) an
uninitialised pointer.
>
Yes, I know "undefined" can mean "anything", but lets stay real here for
a moment. Possibly "undefined" is "defined" to mean "undefined for that
variable in question".
>
Or?

Or, it means that the compiler is allowed to perform optimizations
elsewhere in your program, based upon the assumption that your code does
not have undefined behavior.

Specifically, your use of 'p--' at that point in the program can be used
by the compiler as an indication that p does NOT point at the start of
the array. As a result, if there is a previous statement that uses 'p',
and the compiler can verify that the value of 'p' should not be changed
between that previous statement and the entry to your while() loop, then
the compiler is free to optimize that previous use of 'p', by making
that same assumption.

For example, if that previous statement were

q = (p+3)-1;

the compiler would be free to rearrange that as

q = (p-1)+3;

Now, I'm not claiming that this is actually an optimization. There's no
obvious benefit to that rearrangement, it's just the simplest example I
could think of, of a legal rearrangement with potentially fatal
consequences. The point is, that because you use 'p--' later on in the
code, the compiler is free to investigate such rearrangements at this
earlier point in the code. If it finds a rearrangement that it prefers
over the original code, it is permitted to use it.

This is true even if the compiler is compiling for a platform where
calculating p-1 would abort the program if p happens to point at the
beginning of a memory segment. The original version of the code is
carefully written to avoid that problem, but because of the later use of
'p--', the compiler is allowed to rearrange it on the assumption that
p-1 has defined behavior. If p-1 and p+3 both have defined behavior,
then the behavior of (p+3)-1 and (p-1)+3 are both guaranteed to be
identical to p+2.

This is an example of why it's a mistake to assume that the consequences
of writing a code construct with undefined behavior are restricted to
the execution of that particular code construct. This is why the
standard standard specifies that it is the behavior of your ENTIRE
program that is undefined, not just the behavior of the particular
construct that makes it undefined.

And yes, this is a "real world" issue; modern compiler technology does
include the ability to perform optimizations at locations in the code
that are far away from the site of the code construct that gives them
permission to perform the optimization.

[Chris Dollin]

Re: Highly efficient string reversal code

vippstar@gmail. com wrote:

On Sep 23, 11:19 am, Nick Keighley <nick_keighley_ nos...@hotmail. com>
wrote:

>On 23 Sep, 05:51, CBFalconer <cbfalco...@yah oo.comwrote:
>>

"lovecreatesbea ...@gmail.com" wrote:
>
The reverse function quits if this is the case.

>>

Not mine, which was posted earlier. It also considers a NULL
passed in as indicating an empty string, and returns 0 (for input
length).

>>
>which I consider a bug

>
Depends on the documentation. Do you consider it a bug if strlen(NULL)
returns 0?
I'd just document that NULL shouldn't be passed to such function; what
it does after that is not important. (ie returning 0 or dereferencing
a null pointer)

Or exploding.

--
'It changed the future .. and it changed us.' /Babylon 5/

Hewlett-Packard Limited registered office: Cain Road, Bracknell,
registered no: 690597 England Berks RG12 1HN

[James Kuyper]

Re: Highly efficient string reversal code

CBFalconer wrote:

Ben Bacarisse wrote:

>"lovecreatesbe a...@gmail.com" <lovecreatesbea uty@gmail.comwr ites:
>>

... snip ...

>>My version
>>>
>>char *reverse(char *p) {
>> char *p1, *p2, ch;
>>>
>> for (p1 = p; *(p1 + 1); p1++) ;

>If p points to an empty string this, too, is probably UB. It may
>not be -- one would have to see the call, but you should not even
>risk this. A call like: char test[10]; test[0] = 0; reverse(test);
>is bad news!

>
I think that is OK. The above for does nothing except set p1 == p.

No, it dereferences p+1. If p points at an empty string "", then p+1
points one past the end of the array, and the behavior of dereferencing
p+1 is undefined. Furthermore, if p points at "\0Hello, world!", the
loop given above will leave p1 pointing at the '!', which is not where
it should be pointing.

[Richard Heathfield]

Re: Highly efficient string reversal code

Nick Keighley said:

On 23 Sep, 07:40, Richard<rgr...@ gmail.comwrote:

<snip>

>I do however
>slag off ridiculous bullying and silly preening with such claims as "I
>dont need a debugger and neither do you" or "your debugger uses numbers
>for pointers? Really"? etc etc etc . It makes this group a very tense
>and strange place to be at times.

>
well you don't exactly help

Well, it doesn't exactly matter, since nobody with any sense pays the
slightest attention to what he says. The above paragraph is so exaggerated
that it would not be unreasonable to accuse him of lying. The "bullying"
claims are just ludicrous, and he's far more sinning than sinned against
in this respect. As for debuggers, I don't recall *anyone* saying that
they don't need a debugger, and I certainly don't recall anyone saying
that "you" (FWVO "you") don't need a debugger either. And the reason I
don't recall anyone saying these things is extraordinarily likely to be
because nobody did.

If he wants to talk to grownups, he's going to have to learn to treat them
like grownups, and to behave like a grownup - which, among other things,
means learning to understand and respect the opinions of others, even
though one might disagree with them.

--
Richard Heathfield <http://www.cpax.org.uk >
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[pete]

Re: Highly efficient string reversal code

CBFalconer wrote:

Ben Bacarisse wrote:

>"lovecreatesbe a...@gmail.com" <lovecreatesbea uty@gmail.comwr ites:
>>

... snip ...

>>My version
>>>
>>char *reverse(char *p) {
>> char *p1, *p2, ch;
>>>
>> for (p1 = p; *(p1 + 1); p1++) ;

>If p points to an empty string this, too, is probably UB. It may
>not be -- one would have to see the call, but you should not even
>risk this. A call like: char test[10]; test[0] = 0; reverse(test);
>is bad news!

>
I think that is OK. The above for does nothing except set p1 == p.

If p points to a null byte
which is also the last byte of an object,
then *(p1 + 1) is undefined.

--
pete

[pete]

Re: Highly efficient string reversal code

Peter Nilsson wrote:

Richard<rgr...@ gmail.comwrote:

>>>>>An

>>>>>object pointer

>>>>> can have only 4 different kinds of
>>>>>values:
>>>>>1 Address of an object
>>>>>2 One more than the address of an object
>>>>>3 null pointer value
>>>>>4 indeterminate value

>
5 Address of a function

Not an object pointer.

--
pete