String Concatenation With strcpy

Hello, I'm having difficulty's making string concatenation with strcpy or anything that copy's memory from one section to another to work.

I'm attempting to write a performance-based string library for a side-project, and after reviewing my options for string concatenation, strcat/wcscat was not an option.

This is the property of microsoft:


However, its easy to see why I would want to avoid using strcat/wcscat whenever possible. The amount of branching and looping done is not-linear in terms of assembler code, and there is much overhead when continuously jumping in code.

I've created a C++ class that handles the string, therefore I know at which index of the character array the pointer points to, that I want to insert data. Therefore I've used strcpy and or memcpy to achieve this task.

However there is a slight problem.



I've created a test:



which results in the following output:



As you see the first string is concatenated perfectly, but the second one appears as it doesn't happen at all. The wcscat/strcat function work without fail, all the time. However something is happening that I just havent quite yet spotted.

The Add() function simply allocates the space needed with realloc(), the (*this)(Index) is an operator operator(int) which returns the value ((FTCHAR*)Data)[Index]

My guess is you forgot to copy the \0 if you're basing the amount to copy on the number of characters.

Or you overcounted it, and ended up with a string in memory which looks like
"hello\0world\0"
That would have all the appearance of "world" being completely missing from the output.

Also,
strcat( dest, src );

Can be replaced with
size_t len = strlen(dest);
strcpy( &dest[len], src );

Which, if you keep len up to date as a class member variable should be pretty good.

Not linear? How do you figure?

If performance is paramount, lose the C style strings and adopt Pascal style.

Agreed.

If you creating your own string class you don't have to stick with the C string convention, an unterminated array and a count member would be more efficient. You should probably not use the string library as the basis for anything - you have already found strcat() to be wanting, and it is, but not only in the way you think - the MS implementation you posted is sub-optimal, presumably relying on compiler optimisation to 'fix' it. Do the copy using an unrolled loop and Duff's Device(with the Stroustrup modification) - it aint't pretty but it is efficient - not for 'every day' code I suggest!

Clifford

The class implementation is an array itself. It extends an array class, more specifically a template array class. The first data-member is a pointer a void pointer in the array class, thus I can simply use the object itself as a string.

Its a dynamically adjusting array, if you mean unterminated in that sense. At some point since the string is used for all sorts of purposes include File I/O, or other contents outputted, it has to have a null-terminating character at some point. Otherwise some very nasty errors arise from accessing unallocated memory.

Its not very original but the Memcpy function is an assembler optimized function:


You can appreciate the fact that it copy's in sets of 4, and copy's the trailing bytes single by single to a maximum of 3 at any given point of time.

This assembly assumes NO overlapping buffers.

I hope to eliminate the string library eventually, however branching is something I wouldn't want to touch ever using inline assembly.


Non linear code in assembler, results from the If, While, For, and possibly other pieces of high-level language programming. When it comes to assembler, you want to eliminate branching, eliminate ifs.

Using ifs, whiles, and for's usually result in assembler looking like:

test <register>,<register>

or some other comparison operator of an instruction set, the following instruction being

jmp <addr>

to execute a condition statement.

A loop simply jumps back to the initial portion of the loop

Addr:
<do>
jmp <Addr>

with the condition evaluation being sometime before the jump or inside the area jumping outside of the loop.

Branching is considered poor in terms of performance optimization, see the memcpy above. Although it is repetitive no overhead is spent on a jump instruction.

You may want to read: Branch Elimination Guide

For further information about non-linear assembler code.




Thanks, I used your advice and found that there was a null-terminator somewhere inbetween. Go figure Thank you for your assistance.

Thus proving once again that you should be looking to make it right before trying to make it fast. How much time have you spent chasing this bug you added seeking a few extra clock ticks?

I mean, if there is any file access going on in your program then messing around with the nano-seconds of processor instruction timing isn't going to make a bean of difference to the milliseconds (1E6 times slower) that disk seek times are measured in.

To be honest, this reeks of premature optimisation.

a) is your program finished and fully debugged?

b) do you have real world data to test with (not test samples)?

c) have you run your finished program with real data under a profiling tool - if not, you're just guessing.

Why should you wait until the program is finished?
1. The program may be quick enough for its purpose anyway.
2. The profiler will tell you where the real problems are, not just where your subjective guesses think they might be.
3. Since the program already works, you have a baseline to test any "optimisations" to see whether they are in fact an improvement and also bug free in themselves.

http://www.prism.uvsq.fr/~cedb/local_copies/lee.html
Mostly, I just stick to the first couple of points and let today's optimising compilers figure out all the little tricks which can improve the code.

Just ensure it has one not considered as part of the length.

The suggestion to use strlen, rather than running out to the nul from the beginning, is inane, as that's precisely what strlen does. The best advice given in this thread is by Salem, regarding optimization. Additional material on that may be found in the Commonly Asked Questions thread, by a fellow named Mitakeet.

Indeed at some point, but that can be added only when necessary, after the pattern of the standard string::c_str() function for example. For output, if you overload ostream::operator<<, you don't need a special terminator as your overloaded function would be aware of the internal representation (via a friend relationship).

Clifford

While the memcpy function is optimized, you have to assume that you already know the length of the string you are appending. If you do not, you will have to use strlen. In which case you should just use strcat. If you know the length of your strings without having to use strlen, then memcpy is certainly the faster option.