More questions (relating to global doubts)

Hi again.

Quite a long time since I last wrote here.

Once again, and as my self-tutoring life progresses, I find myself with some questions which I will ask you.

I've been trying to develop basic Standard C++ (and also C) library functions. About two seconds (wohoo) ago I finished string.h (or cstring or whatefver you may wish).

During the developing of its functions I stumbled across some doubts.
i.e. - In the following piece of code:

Code:

---

if(*--ptr_str2==*ptr_str1++) ptr_str2=(char*)str2;
else return --ptr_str1-str1;

---

Alright it's out of context, but picture that only. Is that piece of code faster than:

Code:

---

if(*--ptr_str2==*ptr_str1) { ptr_str1++; ptr_str2=(char*)str2; }
else return ptr_str1-str1;

---

Answering myself, I think it depends on the case. If the if statement becomes true, then I _think_ i spare time in doing what I do in the second sample of code, but, when it evaluates to false, I have to decrement it again (or maybe just subtract one to it in a logical expression...), lowering performance.

I would like to post the whole code from all my functions and get an opinion from the 'experts', just to check if I'm going in the right direction. If you allow me to do it, in my next post I will paste the code here. For now, if it wouldn't bother you really much, I'd like you to comment on my implementation of strspn:

Code:

---

size_t strspn ( const char * str1, const char * str2 ) {
char* ptr_str1=(char*)str1,* ptr_str2=(char*)str2;
while(*ptr_str1) {
while(*ptr_str2++!=*ptr_str1 && (*ptr_str2)) ;
if(*--ptr_str2==*ptr_str1++) ptr_str2=(char*)str2;
else return --ptr_str1-str1;
}
return ptr_str1-str1;
}

---

Do you think it is ok? How could it be improved? What are the major performance hits?

Also (once again, not posting the WHOLE code), could you also comment on the following, please?

Code:

---

/* strrchr - Return a pointer to the last occurence of character in str. */
const char * strrchr ( const char * str, int character ) {
char* ptr_str=(char*)str;
while (*ptr_str++) ; /* Go to the end of the string */
while (*--ptr_str!=(char)character && (*ptr_str)) ;
if(*ptr_str!=(char)character) return NULL;
return ptr_str;
}

---

Thanks in advance, sorry if I sound too 'crazy' or 'rhetorical'.

Your optimizer makes it hard to give you a sure-fire answer that is fair. All things equal, however, the code that requires the least opcodes to run, and the least expensive combination of opcodes will surely be "faster"

Have you verified that your strrchr function works correctly? It seems to me that it returns NULL always.

Code:

---

while (*--ptr_str!=(char)character && (*ptr_str)) ;

---

Not sure if referencing ptr_str twice here while decrementing it is undefined behaviour. In any case I don't see anything here that would stop it going beyond the start of the buffer if the character is not found anywhere in the string. C-style strings are not null-terminated at both ends...

When corrected it would look perhaps something like:

Code:

---

for (--ptr_str; *ptr_str != character && ptr_str != str; --ptr_str);

---

In which case it appears that it might be slightly slower than the following (though this might depend heavily on the type of input)

Code:

---

const char* StrrChr (const char* str, int character)
{
    const char* result = 0;
    while (*str) {
        if (*str == character)
            result = str;
        ++str;
    }
    return result;
}

---

The worst case for both is reversed. When the string doesn't contain the character, this is about twice as fast, since it traverses the string only once. It the string contains only the searched characters, this is a bit slower, because it does more checks and assignments (but apparently not twice as slow). In the average case, with the character appearing occasionally, this might be slightly faster.

Quote:

---

Originally Posted by anon

Have you verified that your strrchr function works correctly? It seems to me that it returns NULL always.

Code:

---

while (*--ptr_str!=(char)character && (*ptr_str)) ;

---

Not sure if referencing ptr_str twice here while decrementing it is undefined behaviour. In any case I don't see anything here that would stop it going beyond the start of the buffer if the character is not found anywhere in the string. C-style strings are not null-terminated at both ends...

When corrected it would look perhaps something like:

Code:

---

for (--ptr_str; *ptr_str != character && ptr_str != str; --ptr_str);

---

In which case it appears that it might be slightly slower than the following (though this might depend heavily on the type of input)

Code:

---

const char* StrrChr (const char* str, int character)
{
    const char* result = 0;
    while (*str) {
        if (*str == character)
            result = str;
        ++str;
    }
    return result;
}

---

The worst case for both is reversed. When the string doesn't contain the character, this is about twice as fast, since it traverses the string only once. It the string contains only the searched characters, this is a bit slower, because it does more checks and assignments (but apparently not twice as slow). In the average case, with the character appearing occasionally, this might be slightly faster.

---

Hi, thanks for your answer.

I did check the function and it worked. I've been implementing all of them based on the c++ reference at cplusplus.com. I've tested all of them with the given examples and corrected some bugs when I altered them. I also compared their behavior to the standard ones (talking about GCC and its libs here).

You are right saying it returns NULL. I'm trying to think about what could have happened, I am totally sure it worked. Maybe I just changed the code somewhere, awkward...


Looking at the code I get it. During some of my copy+pasting I added:

Code:

---

&& (*ptr_str)

---

Now since we were at 0 it couldn't ever iterate so it just stopped (well, you got it.)

Relating the 'going past the buffer' issue, here's my workaround which I think fixes everything that's mentioned:

Code:

---

const char * strrchr ( const char * str, int character ) {
char* ptr_str=(char*)str;
while (*ptr_str++) ; /* Go to the end of the string */
while (*--ptr_str!=(char)character && ((char*)str!=ptr_str)) ;
if(*ptr_str==(char)character)
return ptr_str;
else return NULL;
}

---

Do you think it is ok like this?

Also, I do not think it is undefined behaviour when I think of it as assembly code. Reading from left to right, since I've got to the conclusion that both TenDRA and GCC do this (reading from left to right). I think saying x && y is not the same as y && x. (but that's just me).

Thanks allot.

C++ guarantees that the left side of && is evaluated before the right, so the behavior is defined.

It appears that the problem was that you first loop sets ptr_str to point beyond the null-terminator (one beyond the array should be legal as long as you don't dereference it). So when you are coming back the first character you inspect is the terminator.

My doubt was not about whether && is evaluated from left to right, but rather is it guaranteed that the side-effects are applied (str_ptr decremented) before the right-hand-value is evaluated. It seems that it would be.

----

A style issue is with the casts. Why don't you declare your stuff with the correct type to begin with, e.g

Code:

---

//char* ptr_str=(char*)str;

const char* ptr_str = str;

---

Quote:

---

Originally Posted by anon

My doubt was not about whether && is evaluated from left to right, but rather is it guaranteed that the side-effects are applied (str_ptr decremented) before the right-hand-value is evaluated. It seems that it would be.

---

Yes, that is guaranteed.

And always remember the main mantra of good development, which reads: never use globals.

Quote:

---

Originally Posted by jwenting

And always remember the main mantra of good development, which reads: never use globals.

---

I think that is a little too specific to be a "main mantra" ;)

Maybe "strive for loose coupling and high cohesion" would be more like it.

Quote:

---

Originally Posted by Jorl17

Hi, thanks for your answer.

I did check the function and it worked. I've been implementing all of them based on the c++ reference at cplusplus.com. I've tested all of them with the given examples and corrected some bugs when I altered them. I also compared their behavior to the standard ones (talking about GCC and its libs here).

You are right saying it returns NULL. I'm trying to think about what could have happened, I am totally sure it worked. Maybe I just changed the code somewhere, awkward...


Looking at the code I get it. During some of my copy+pasting I added:

Code:

---

&& (*ptr_str)

---

Now since we were at 0 it couldn't ever iterate so it just stopped (well, you got it.)

Relating the 'going past the buffer' issue, here's my workaround which I think fixes everything that's mentioned:

Code:

---

const char * strrchr ( const char * str, int character ) {
char* ptr_str=(char*)str;
while (*ptr_str++) ; /* Go to the end of the string */
while (*--ptr_str!=(char)character && ((char*)str!=ptr_str)) ;
if(*ptr_str==(char)character)
return ptr_str;
else return NULL;
}

---

Do you think it is ok like this?

Also, I do not think it is undefined behaviour when I think of it as assembly code. Reading from left to right, since I've got to the conclusion that both TenDRA and GCC do this (reading from left to right). I think saying x && y is not the same as y && x. (but that's just me).

Thanks allot.

---

Quote:

---

Originally Posted by anon

It appears that the problem was that you first loop sets ptr_str to point beyond the null-terminator (one beyond the array should be legal as long as you don't dereference it). So when you are coming back the first character you inspect is the terminator.

My doubt was not about whether && is evaluated from left to right, but rather is it guaranteed that the side-effects are applied (str_ptr decremented) before the right-hand-value is evaluated. It seems that it would be.

----

A style issue is with the casts. Why don't you declare your stuff with the correct type to begin with, e.g

Code:

---

//char* ptr_str=(char*)str;

const char* ptr_str = str;

---

---

Well, since nobody ever taught me programming and all i've learned came from the web I lack some basic stuff...

I thought that by declaring it const we'd actually be saying "No changes may be made.". So i figured that declaring it const would just turn the compiler's pointing errors at me :)

One more thing that I did not know was that while passing a pointer as const, incrementing it does not increment the 'real' pointer. Why does that happen, could you please tell me?

I think it happens because what we pass is a copy of our pointer instead of it. So, we end up with a pointer that points to the same thing, except that it is not the previous one.

This means that in my implementation of strncpy (for example):

Code:

---

char * strncpy ( char * destination, const char * source, size_t num ) {
char* ptr_src=(char*)source,* ptr_dest=destination;
while(num-- && (*ptr_dest++=*ptr_src++) && (*ptr_src) && (num)) ;
while(num--) (*ptr_dest++)=0; /* padd remaining destination with 0's. */
return destination;
}

---

I would be able to do something like:

Code:

---

char * strncpy ( char * destination, const char * source, size_t num ) {
while(num-- && (*destination++=*source++) && (*source) && (num)) ;
while(num--) (*destination++)=0; /* padd remaining destination with 0's. */
return destination;
}

---

Right? Or am I wrong?
Thanks allot.

Parameters passed in are copies from the calling code, so you can do your second version of strncpy().

Also, const char * means that you are not going to change whatever the pointer points at, not that you can't change the pointer itself. That would be "char * const".

--
Mats

Quote:

---

Originally Posted by Jorl17

One more thing that I did not know was that while passing a pointer as const, incrementing it does not increment the 'real' pointer. Why does that happen, could you please tell me?

---

What do you mean?

Quote:

---

Originally Posted by laserlight

What do you mean?

---

I think Jorl doesn't understand "pass by value" of pointers. Of course, const has nothing to do with this concept at all.

--
Mats

Quote:

---

I thought that by declaring it const we'd actually be saying "No changes may be made.". So i figured that declaring it const would just turn the compiler's pointing errors at me

One more thing that I did not know was that while passing a pointer as const, incrementing it does not increment the 'real' pointer. Why does that happen, could you please tell me?

I think it happens because what we pass is a copy of our pointer instead of it. So, we end up with a pointer that points to the same thing, except that it is not the previous one.

---

With pointers there are two things, the pointer itself (address) and what is at the pointed address. When you pass a pointer to the function, it indeed receives a copy, so if you make the pointer itself point elsewhere, this will not affect the pointer in the main program.

With const's there are several variants:

Code:

---

//what is pointed at cannot be modified
const Type* p;
Type const* p;

//the pointer itself cannot be made to point elsewhere, the refered value can
Type * const p;

//neither can be modified
const Type* const p;
Type const* const p;

---

Note that your C-style (this is C++ board) casts cast away constness. If you were to actually take advantage of the lack of const and actually attempt to modify the pointed-at string contents, your program might crash - e.g if the argument is a pointer to string literal. All the cast achieves is shut the compiler up, so it would allow you to make that mistake.

Quote:

---

Originally Posted by matsp

I think Jorl doesn't understand "pass by value" of pointers. Of course, const has nothing to do with this concept at all.

--
Mats

---

Yes indeed, it hasn't got anything at all got to do with const, it was a totally unrelated querstion.

Quote:

---

Originally Posted by anon

With pointers there are two things, the pointer itself (address) and what is at the pointed address. When you pass a pointer to the function, it indeed receives a copy, so if you make the pointer itself point elsewhere, this will not affect the pointer in the main program.

With const's there are several variants:

Code:

---

//what is pointed at cannot be modified
const Type* p;
Type const* p;

//the pointer itself cannot be made to point elsewhere, the refered value can
Type * const p;

//neither can be modified
const Type* const p;
Type const* const p;

---

Note that your C-style (this is C++ board) casts cast away constness. If you were to actually take advantage of the lack of const and actually attempt to modify the pointed-at string contents, your program might crash - e.g if the argument is a pointer to string literal. All the cast achieves is shut the compiler up, so it would allow you to make that mistake.

---

Thanks for your explanation.

About posting C-style code in a c++ board is due to the fact that what I am trying to reimplement is the whole standard library (both c++ and c).

Relating to the constness that really helped me, I think I never saw something as well explained and simple as that anywhere.

Since I'm in a terrible wave of asking questions, in my following piece of code:

Code:

---

return ptr_str1-str1;

---

This will return the difference between pointers. I got that, used it, ok. But why does this happen? I think it happens because what we are returning is the difference between the addresses of the pointers and, since they both started from the same place, we get the difference in a decimal number. Am I wrong?

Also, if I am right, then what would happen if I hadn't used a char (1 byte, right?) but a dword for example. Would it still return the correct value? Or is it that the difference in memory would be four times as large?

Really, really thanks again:

Jorl

Pointer arithmetic is valid only with subtract and only for pointers that point to the same block of memory (sure, you can do it for other pointers too, since the compiler doesn't actually check it - but the result is undefined, and quite often meaningless).

So ptr1 - ptr2 is valid if ptr1 and ptr2 are pointing to the same original block of memory. And you will get the "number of elements" between the two points - not the number of bytes between. So if it's char, int, struct FILE, or some other functions, it won't make any difference. Pointer arithmetic on void * is undefined.

--
Mats

Quote:

---

Originally Posted by matsp

Pointer arithmetic is valid only with subtract and only for pointers that point to the same block of memory (sure, you can do it for other pointers too, since the compiler doesn't actually check it - but the result is undefined, and quite often meaningless).

So ptr1 - ptr2 is valid if ptr1 and ptr2 are pointing to the same original block of memory. And you will get the "number of elements" between the two points - not the number of bytes between. So if it's char, int, struct FILE, or some other functions, it won't make any difference. Pointer arithmetic on void * is undefined.

--
Mats

---

Right, thanks.

One last question to wrap everything up (for now). Are the following implementations of memcpy and memove ok? I'm not quite sure if memmove is meant to do that.

Code:

---

/* memcpy - Copy memory from source to destination with the length of num. */
void * memcpy ( void * destination, const void * source, size_t num ) {
char* ptr_src=(char*)source,* ptr_dest=(char*)destination;
while(num--) *ptr_dest++ = *ptr_src++;
return destination;
}
/* memmove - Copy memory from source to destination with the length of num using a secondary buffer. This is useful for overlapping memory blocks. */
void * memmove ( void * destination, const void * source, size_t num ) {
char* buffer = new char [num];
memcpy((void*)buffer, source, num);
memcpy(destination, (void*)buffer, num);
delete[] buffer;
return destination;
}

---

And so I thank you once more and guarantee to you that this is the last topic to be discussed, not to bother you that much.

Jorl17

Edit: About the functions, I haven't altered them to fix the casts and all that, so don't comment on that please, I'm already fixing it :)

Quote:

---

Originally Posted by laserlight

I think that is a little too specific to be a "main mantra" ;)

Maybe "strive for loose coupling and high cohesion" would be more like it.

---

Globals are evil, period.
Company I used to work for had a plaque on the wall (they were a Progress shop, where globals were quite normal) reading "the only good global is an eliminated global".

I'm sorry but who else in this thread are discussing using globals? I take "global doubt" in the title to mean "general questions"...

Besides, as OP is reimplementing the standard C/C++ library, it does use globals (rand/srand, std::cout and friends) and static buffers/variables, so what can you do?

Code:

---

void * memmove ( void * destination, const void * source, size_t num ) {
char* buffer = new char [num];
memcpy((void*)buffer, source, num);
memcpy(destination, (void*)buffer, num);
delete[] buffer;
return destination;
}

---

1. Standard C functions should not use C++ functionality.
2. What if the user tries to copy 1GB of memory - you will most likely fail the new.

The normal memmove deterimens if the copy is overlapping, and if so, copies in a direction that avoids overwriting the data, otherwise just call memcpy() in the first place.

Also, your memcpy() is FAR from the optimal performance.

--
Mats

How does memmove determine overlaps?

Quote:

---

Originally Posted by matsp

Code:

---

void * memmove ( void * destination, const void * source, size_t num ) {
char* buffer = new char [num];
memcpy((void*)buffer, source, num);
memcpy(destination, (void*)buffer, num);
delete[] buffer;
return destination;
}

---

1. Standard C functions should not use C++ functionality.
2. What if the user tries to copy 1GB of memory - you will most likely fail the new.

The normal memmove deterimens if the copy is overlapping, and if so, copies in a direction that avoids overwriting the data, otherwise just call memcpy() in the first place.

Also, your memcpy() is FAR from the optimal performance.

--
Mats

---

Right, so replace c++ syntax with C syntax, shouldn't be too harsh. How can I copy memory without allocating new one? And how would I determine if they overlap? Would it be done using pointer arithmetic? Why is memcpy such a performance hit atm?

Quote:

---

Originally Posted by anon

How does memmove determine overlaps?

---

Comparing the range of source, source+len with destination, destination+length. If destination or destination+ len is within source to source + length, then it is an overlap.

--
Mats

Quote:

---

Originally Posted by Jorl17

Right, so replace c++ syntax with C syntax, shouldn't be too harsh. How can I copy memory without allocating new one?

---

By copying in the opposite direction of there is an overlap. (so start at source+length-1 and copy to destination+length-1 - the same way you would do if you have an array that you want insert something into - you start at the back and copy each down one up to the point where you want the empty location).

Quote:

---

And how would I determine if they overlap? Would it be done using pointer arithmetic?

---

Check out my reply to anon.

Quote:

---

Why is memcpy such a performance hit atm?

---

Because it is copying a byte at a time, which is quite slow on all machines. It is correct (and correctness is better than performance).

Some of the work I did with Mike Wall at AMD is published here. It's not EXACTLY memcopy, but it explains some of the basic principles
http://www.amd.com.cn/CHCN/Processor...9_7451,00.html
(Scroll to the bottom for a 2002 presentation about "Block Prefetching").

--
Mats

Ok, thanks. Not quite sure I got it, but I'll read some articles and take a look at some implementations.

Thanks for the link and thanks for everybody's help.

If I have any questions I'll just start a new topic and be even MORE evil :P

Jorl

Quote:

---

Some of the work I did with Mike Wall at AMD is published here.

---

O_o

True to my nature, I read that for funsies. I found a bug, let's call it a bug, in my code preventing the performance I had expected because of that. So, yea, thanks for that. ^_^

Soma

Just to tell you I finally understood all the fuzz about overlapping memory blocks.

following: http://www.student.cs.uwaterloo.ca/~...8c-source.html

The inline code explanation there is absolutely amazing for me. I'd been playing with remote controls trying to represent memory blocks here but didn't seem to understand a thing!

Jorl

And as you can see, the linked memmov use "long" size if possible - it's only doing the simplest form of aligned copies, but that will be very close to "sizeof(long)" times faster than a char copy.

--
Mats

Indeed I noticed that as soon as I saw it :)

Here's my attempt:

Code:

---

const char*
strrchr( const char* str, int val )
{
    const char*
        ptr;
    for( ptr = 0; *str; ++str )
    {
        if( *str == val )
            ptr = str;
    }
    return ptr;
}

char*
strncpy( char* dst, const char* src, size_t len )
{
    char*
        cpy = dst;
    while( len-- )
    {
        *cpy++ = *src++;
    }
    *cpy = 0;
    return dst;
}


size_t
strspn( const char* str, const char* pat )
{
    const char*
        bas = str;
    int
        fnd = 1;
    for( ; *str && fnd; ++str )
    {
        fnd = 0;
        for( const char* ptr = pat; *ptr; ++ptr )
        {
            if( *str == *ptr )
            {
                fnd = 1;
                break;
            }               
        }
    }
    return str - bas;
}

---