A
Alex Buell
Somewhere I have a routine written in assembler that copies strings
very quickly. It's intelligent enough to know about these special cases.
Somewhere I have a routine written in assembler that copies strings
very quickly. It's intelligent enough to know about these special cases.
I
Ian Collins
Alex said:
For a good example, have a look at
http://cvs.opensolaris.org/source/xref/on/usr/src/lib/libc/i386/gen/memcpy.s#27
P
persenaama
Somewhere I have a routine written in assembler that copies strings
Can we take a look at the code and do somekind of estimate where the
tie-breaker case is concerning the string length?
Can we take a look at the code and do somekind of estimate where the
tie-breaker case is concerning the string length?
P
persenaama
For a good example, have a look at
Basicly it does count/4 "rep movsd" followed by count%4 "rep movsb" for
the leftover bytes, this is not very useful for asciiz strings as the
trailing zero must be detected and correctly handled. The code does not
align the source or destination address either.
The case which was being discussed was somekind of optimized strcat()
variant, using asciiz style strings as input.
This might be of help, for dealing multiple chars at a time:
void example(unsigned int* p)
{
unsigned int v = 0;
for ( ; !v; )
{
unsigned int u = *p++;
v = (u - 0x01010101) & ~u & 0x80808080;
}
// ...
}
Assuming the sizeof(unsigned int) == 4 on a particular platform and
that char is 8 bits, the above snip of code would scan four characters
at a time for trailing zero. The code can be easily modified to handle
strcat(), strcpy(), strlen() .. what is missing is handling alignment,
which is trivial this is just demonstrating a concept.
Basicly it does count/4 "rep movsd" followed by count%4 "rep movsb" for
the leftover bytes, this is not very useful for asciiz strings as the
trailing zero must be detected and correctly handled. The code does not
align the source or destination address either.
The case which was being discussed was somekind of optimized strcat()
variant, using asciiz style strings as input.
This might be of help, for dealing multiple chars at a time:
void example(unsigned int* p)
{
unsigned int v = 0;
for ( ; !v; )
{
unsigned int u = *p++;
v = (u - 0x01010101) & ~u & 0x80808080;
}
// ...
}
Assuming the sizeof(unsigned int) == 4 on a particular platform and
that char is 8 bits, the above snip of code would scan four characters
at a time for trailing zero. The code can be easily modified to handle
strcat(), strcpy(), strlen() .. what is missing is handling alignment,
which is trivial this is just demonstrating a concept.
A
Alex Buell
Seems I was incorrect, the routine is strlen() which actually counts 4
bytes at a time and returns the total asciiz string length.
M
Malcolm
No the "mark", actually a Malcolm, said that profiling is about opcodes, orPhlip said:
more or less.
I can count the number of lines a procedure executes without a profiler. In
fact no profiler I know will give me a big O analysis of an algorithm
directly.
What I can't do without inordinate difficulty is determine exactly how long
each operation takes.
W
websnarf
Noah said:
They have the same end effect -- however they are not the same in
implementation.
Its a macro that uses sizeof() and "" inline concatenation to deduce
the length of the string and enforce the fact that it is a string
literal. It forms a special kind of bstring compatible structure using
pure stack or static memory. The resources are managed implicitely by
the state of the call stack.
It concatenates to a dynamic bstring (which, in this case, we assume is
passed in).
Constructs a CBString with constant equivalent to the const char *
initializer.
[...] does and what CBString:perator += does.
Its like bconcat for CBStrings.
Conceptually, they are, but by implementation they are not. In
particular there is no way to trick the C++ part into constructing the
contents of the string form purely stack or static memory unless you
actually use the C syntax.
Right, but it doesn't help, because you still need to call an extra
strlen(). (Or iterate character by character but you don't get to
leverage the compiler's highly optimized memcpy().)
Ok -- using syntax and concepts from C++ that are not just directly
lifted from C, how does one make a static CBString such as I have
shown? (You can drop the static decorator in the front, to make this
all just about the stack, and not static memory.)
N
Noah Roberts
Ok, I see where the difference is in the two code segments. You are
mistaking the stack for static variables apparently. Nothing keeps you
from doing this:
void f(CBString & str)
{
static CBString hi = "hi";
str += hi;
}
Besides that I fail to understand what exactly it is you think is
different. I have no idea what your functions do beyond your poor
attempt to describe them so there is no way to tell what you are
talking about. Simply put, you are completely mistaken about there
being no way to put a variable of any kind on the "stack" in C++. I
don't know how else to put it if you don't understand that. I still
can't figure out why you think otherwise.
K
Keith Thompson
persenaama said:
The text starting with "Somewhere I have" was written by Alex Buell.
persenaama, the lines that look like
are called attribution lines. Don't delete them *unless* you've
trimmed everything that person wrote from your followup. They make it
significantly easier to follow the discussion.
P
persenaama
void foo()
{
static const char * x = "hi";
}
void bar()
{
const char * y = "hi";
}
The difference between foo() and bar() is that the pointer object y is
in the stack while the pointer object x isn't. The string literal isn't
in the stack in either case.
However, in C++, you cannot really say that as there is no concept of
stack in C++ it is just commonly understood that a stack is a very
practical and common implementation of local scoped objects with auto
storage within a function.
I think I have to re-read what this was really about as I seem to miss
the point what stack has to do with the string literal.
I
Ian Collins
Alex said:
Something like:
http://cvs.opensolaris.org/source/xref/on/usr/src/lib/libc/i386/gen/strlen.s#27
?
K
Keith Thompson
persenaama said:void foo()
{
static const char * x = "hi";
}
void bar()
{
const char * y = "hi";
}
The difference between foo() and bar() is that the pointer object y is
in the stack while the pointer object x isn't. The string literal isn't
in the stack in either case.
However, in C++, you cannot really say that as there is no concept of
stack in C++ it is just commonly understood that a stack is a very
practical and common implementation of local scoped objects with auto
storage within a function.
I think I have to re-read what this was really about as I seem to miss
the point what stack has to do with the string literal.
C has no concept of "stack" either; the word appears nowhere in the C
standard. Objects with automatic storage duration are commonly
allocated on something called a "stack" (i.e., a contiguously
addressed chunk of memory that grows and shrinks in a stack-like
manner), and their lifetime follows stack-like last-in first-out
behavior. But it's entirely legal, and not unheard of, for the local
variables of a function to be allocated from a "heap" (also a word
that appears nowhere in the C standard).
I *think* it's exactly the same in C++, but I'm less familiar with it
than I am with C.
N
Noah Roberts
persenaama said:I think I have to re-read what this was really about as I seem to miss
the point what stack has to do with the string literal.
I've been trying to follow this guy's line of reasoning from the moment
he said C and C++ implementations where different wrt the stack and
local variables and even at that I can't figure out wtf he is talking
about. If you figure it out, let me know.
B
Bo Persson
Of course there is!
And what makes you think that the C++ compiler cannot compute
std::strlen("Hi") at compile time? Or optimize memcpy for a constant
size parameter?
Mine sure does!
It doesn't have to use any static or macro tricks, just properly
optimize the normal std::string.
Bo Persson
A
Alex Buell
Yes, that's quite similar.
W
websnarf
Noah said:
Right but this is a static, and it executes a construction at init
time.
Uhh ... strlen(), etc is called one way or another for CBStrings is
all. I am not a C++ person, so I neglected to consider that C++ allows
for additional init-time function calls (the older portable C standard
doesn't allow this). A static construction, essentially removes the
resource issue, so this makes the point of my example moot.
Right ... if only they were open source and documented ... oh wait,
they are.
Whatever dude. What I am saying is the construction implicitely calls
new/delete (or equivalent) which cannot make a language or runtime
based distinction between a string literal and a string. So, using C
and preprocessor tricks, creating auto-initialization contents with
string literals (that cannot be string variables) is possible. In C++
because construction/destruction is uniform, you can pay a penalty from
extra flags, or are forced to find some other solution to pull the same
sort of trick.
bsStatic(s) is defined as follows:
#define bsStatic(s) { -__LINE__, sizeof("" s "")-1, "" s ""}
(or something like that, I am at a cyber cafe right now so its not
worth it to check it.) As you can see, this takes a string literal,
not a string variable, and it is just a compile time constant
construction. So you can just throw this into a stack variable, and
not worry about when it is going to be deleted, or freed or whatever.
(As a small point, if its non-static, a pure C compiler can fill this
into the auto-variable without holding a static copy in memory. Like,
s.mlen = -__LINE__; s.slen = 0; s.data = ""; without holding the
{-__LINE__, 0, ""} anywhere in memory.)
The use of static in C++ looks like an acceptable alternative stand in
in practice, obviously; presumably, delete need never be called on it.
N
Noah Roberts
No, it doesn't. Construction of an object in no way implies new.
Construction of an object will only make a call to new if the object
allocates something on the heap. This again, is no different that in
C. It has nothing to do with the compiler...the programmer is in
complete control here.
In other words, you are just plain wrong.
B
Bo Persson
No, no, no.
You are just retelling the old stories about the bloated C++ against
the fast, small, optimal C language. This is what makes the fuel of
the language wars!
My favourite test involves these two C++ strings, construct one from a
literal, and copy it to another (only works for short literals):
std::string whatever = "abcd";
0040276A mov eax,dword ptr [string "abcd" (434734h)]
0040276F mov dword ptr [esp+28Ch],eax
00402776 mov byte ptr [esp+2A7h],bl
0040277D mov dword ptr [esp+2A8h],ebp
00402784 mov byte ptr [esp+290h],bl
std::string whatever2 = whatever;
0040278B mov dword ptr [esp+33Ch],eax
00402792 mov byte ptr [esp+357h],bl
00402799 mov dword ptr [esp+358h],ebp
004027A0 mov byte ptr [esp+340h],bl
Actual assembly code from the free VC++ Express Edition. Check out the
code bloat!
Or try this larger example of where C++ templates runs *much* faster
than optimized C code:
B. Stroustrup "Learning Standard C++ as a New Language"
http://www.research.att.com/~bs/new_learning.pdf
Bo Persson
M
Michael Mair
Bo Persson schrieb:
Note: "Optimized C Code" is misleading in this case.
You probably meant "Simple C code compiled at highest optimization
level" -- I initially understood "C code tailored to the specific
task, profiled and hand-optimized"
Cheers
Michael
Note: "Optimized C Code" is misleading in this case.
You probably meant "Simple C code compiled at highest optimization
level" -- I initially understood "C code tailored to the specific
task, profiled and hand-optimized"
Cheers
Michael
B
Bo Persson
Michael Mair said:Bo Persson schrieb:
Note: "Optimized C Code" is misleading in this case.
You probably meant "Simple C code compiled at highest optimization
level" -- I initially understood "C code tailored to the specific
task, profiled and hand-optimized"
Sorry about that. I really meant "Using the highly optimized functions
of the C standard library".
The theme of the paper is of course that C++ can (sometimes
run 5 times faster than C, *without* resorting to application specific
coding, profiling, or hand-optimized code. You just use:
std::sort(buf.begin(), buf.end());
and the compiler will expand the sort template, and inline functions
as appropriate. You just cannot do that with qsort.
My claim was that the same effect can be seen for std::string.
Sometimes it is much faster that C-style string functions, because the
compiler does some of the work at compile time.
In my particular case, and with some lucky constant propagation from
preceding code, this string constructor results in 5 assembly
instructions:
__forceinline
basic_string(const value_type* _String,
const allocator_type& _Allocator =
allocator_type() ) : _Parent(_Allocator)
{
const size_type _StringSize = traits_type::length(_String);
if (_MySmallStringCapacity < _StringSize)
{
_Construct(_String, _StringSize);
}
else
{
traits_type::copy(_MySmallString._Buffer, _String,
_StringSize);
_SetSmallStringCapacity();
_SetSize(_StringSize);
}
}
------
std::string whatever = "abcd";
0040276A mov eax,dword ptr [string "abcd" (434734h)]
0040276F mov dword ptr [esp+28Ch],eax
00402776 mov byte ptr [esp+2A7h],bl
0040277D mov dword ptr [esp+2A8h],ebp
00402784 mov byte ptr [esp+290h],bl
Not bad for a code bloating template!
Bo Persson