Storage of char in 64 bit machine

[aruna.mysore]

Hi all,

I have a simple definitioin in a C file something like this.

main()
{
char a;
.......
int k;
}

Since character is 8 bit, how is it stored in the machine in a 64 bit
machine. If it is word aligned, what about the rest of the bytes. What
about the retrievel of the char c, will it be expensive. Is it
expensive w.r.t read or write.

Thanx and Regards,
Aruna

[Mark McIntyre]

On Wed, 16 Aug 2006 20:03:57 -0400, in comp.lang.c , Mikhail Teterin
<us****@aldan.a lgebra.comwrote :

>Keith Thompson wrote:

>I, for one, will ignore any attachments posted to this newsgroup.

I have not spent much time on this group, but, so far, I have not seen
anything that would make me truly saddened by your decision...

As you say, you've not spent much time here if you think Keith's
contributions are worth little.

>I will consider changing this policy only if there's a general consensus
among the regulars that text-only attachments are acceptable.

You are confirming my impression, that the actual merits of text-only
attachments are secondary (or even fully irrelevant) to your decision, with
the annoyance over my violating the unwritten and unofficial "rules of the
club" being the primary...

You're incorrect.
--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

[Walter Roberson]

In article <1940995.IL8L2S CWzz@misha>,
Mikhail Teterin <us****@aldan.a lgebra.comwrote :

>We went from "don't do this, you idiot, the compiler is much better
optimizing, than you will ever be" to "yeah, it is 4-6 times faster to do
things your way, but it is still not worth the effort".

No we didn't. We went from "Don't do this, you idiot, that's
non-portable" to -you- saying "Yeah, but it's faster".

A couple of people then {perhaps unwisely} said "a good strcmp() can
probably do just as well", and you produced a benchmark that appeared
to show that your code is measurably faster... at least for the systems
you tried.

This was followed by a collective "So what if it executes faster?
The time differences is small enough to be inconsequential for most
systems, and in the meantime you've written unclear code that will
likely break on future systems. Paul Hsieh is the only one who
said that it's worth exploring, and it isn't clear that he is taking
into account relative costs of maintaince and execution time.

>I think, this is a considerable progress for one thread and will shut up for
a while...

You haven't really answered to the costs vs portability concerns.
You mooted about banks and funds, but I pointed out that if
the execution time of the comparison was really such a key factor
then you wouldn't have used this approach at all.

Sooo... the space we are in right now is "Here's a non-portable
and less-clear hack that's often faster" and you wanting general
approval for your cleverness... or at the very least, you wanting
people to be content to have such hacks be topical here.

The only progress that I see that you've made is Paul Hseih's
"don't take the naysaying too seriously". Paul is [to me] obviously
fairly knowledgable in some areas, but it -looks- to me as if he
often ends up in arguments, and I get the -impression- that a fair
number of people don't pay careful attention to him (possibly
because of the -way- he says things...)
--
"It is important to remember that when it comes to law, computers
never make copies, only human beings make copies. Computers are given
commands, not permission. Only people can be given permission."
-- Brad Templeton

[Keith Thompson]

Mikhail Teterin <us****@aldan.a lgebra.comwrite s:

We went from "don't do this, you idiot, the compiler is much better
optimizing, than you will ever be" to "yeah, it is 4-6 times faster to do
things your way, but it is still not worth the effort".

I think, this is a considerable progress for one thread and will shut up for
a while...

Looking back in this thread's history, you weren't the OP, but you did
bring up something that triggered a lot of discussion:

| So, comparing, say, 4-char arrays (like currency codes) can NOT be done in
| the following way?
|
| typedef union {
| char acCUR[4];
| int32_t iCUR;
| } xCUR;
|
| int
| CurEqual(xCUR *c1, xCUR *c2)
| {
| if (c1->iCUR == c2->iCUR)
| printf("Same currency %s\n", c1->acCUR);
| else
| printf("%s and %s are different\n",
| c1->acCUR, c2->acCUR);
| }
|
| Having to call a strcmp() in such cases seems like a bad waste to me, but I
| don't see, how the compiler could possibly optimize such a code without the
| trick above...

In this case, it seems to me that there are solutions better than
either using strcmp() or pretending that a char[4] is an int32_t.

Presumably you want the operation of comparing two currency codes to
be as fast as possible, because that operation is a bottleneck in your
application.

You can probably achieve this by storing and comparing the currency
codes *as integers*. One simple way to do this is to compute the
numeric codes arithmetically from the string values. I think you said
that all the currency codes are two characters; if so, it's as simple
as:

numeric_code = (string_code[0] << CHAR_BIT) + string_code[1];

and the reverse conversion is also quite simple.

Note that the values of the numeric codes could vary with different
character sets, and if you store them in files, they could vary with
system byte ordering.

This avoids the need for strcmp() *and* it doesn't depend on type
punning.

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Old Wolf]

Lew Pitcher wrote:

Assume the code fragment...

{ /* A */
char aa; int ab, ac;
char ad;
{ /* B */
char ae;
}
}

In the nesting level I've called "A", the compiler /may/ optimize the
allocations of aa, ab, ac, and ad so that aa and ad are adjacent in
"memory".
However, because variable ae is declared within a different "level" of
the code, I doubt that most compilers would "optimize" its allocation
to occupy another 8 bits within that 64bit allocation that aa and ad
potentially occupy.

Every compiler I've ever used allocates all local variables,
on all "levels", at the start of the function (by advancing the
stack pointer a set amount). It doesn't declare new stack
frames for code blocks within the same function, or
anything like that.

[Dik T. Winter]

In article <1940995.IL8L2S CWzz@mishaMikha il Teterin <us****@aldan.a lgebra.comwrite s:

We went from "don't do this, you idiot, the compiler is much better
optimizing, than you will ever be" to "yeah, it is 4-6 times faster to do
things your way, but it is still not worth the effort".

You quoted a gain of 0.0000000071303 7 seconds per comparison in EOD
processing at a bank. Even if in that EOD processing 1000 million of
such comparisons are made, your net gain is about 7 seconds. I think
that is peanuts compared to the total time required for EOD processing.

I would think that in the EOD process the comparisons are a small fraction
of the total time involved. Say 10% (which is, eh, quite large in my
opinion). If we reduce that by a factor 5, the total time will be
reduced by only 8%.

But even *if* it is significant, there are better methods to increase
speed. Set up a table with all existing currencies, and use indexing.
When a transaction is entered, look up the index numbers for the
transaction (takes about 0.00003 seconds if there are two currencies
involved), and use those indices for the remainder.

Even when loading a full table of conversion rates between two currencies,
the finding of an index would be peanuts (0.0003 seconds gain with your
method). I would think that reading the rates themselves would take
much more time.

This is called micro-optimisation. Optimising a part of the program
that does not use a significant amount of time compared to the
remainder. You should start at the bottle-necks, and for that you
have to measure what the bottle-necks are. Profile the program.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, [phone]
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

[Edmond Dantes]

Walter Roberson wrote:

In article <1940995.IL8L2S CWzz@misha>,
Mikhail Teterin <us****@aldan.a lgebra.comwrote :

>>We went from "don't do this, you idiot, the compiler is much better
optimizing, than you will ever be" to "yeah, it is 4-6 times faster to do
things your way, but it is still not worth the effort".

No we didn't. We went from "Don't do this, you idiot, that's
non-portable" to -you- saying "Yeah, but it's faster".

There must be an equivalent of the old aphorism, "penny-wise, pound-foolish"
that can be applied to optimizing code.

Today, with rare exception, there is hardly the need to optimize assembly
code by hand. I could see it for, say, an embedded system running on
limited resources where it may make sense. But in general? Nope.

--
-- Edmond Dantes, CMC
And Now for something Completely Different:
http://mini-cooper.ReallyHotOrNot.com
http://washers.industrialtips.com
http://embroidery.womencraft.com
http://commodity.yourtruemoney.com
http://Linux.Internet69.com
http://Honda.ReallyHotOrNot.com
http://playset.GadgetRUs.com
Posted Via Usenet.com Premium Usenet Newsgroup Services
----------------------------------------------------------
** SPEED ** RETENTION ** COMPLETION ** ANONYMITY **
----------------------------------------------------------
http://www.usenet.com

[Stephen Sprunk]

"Mikhail Teterin" <us****@aldan.a lgebra.comwrote in message
news:2432497.Jq 3QulhsxS@misha. ..

Stephen Sprunk wrote:

>The implementation is likely to have a very, very clever strcmp() that
will perform at least as well as your code (possibly doing the same thing
internally, if it's known to be safe) and likely even better if the
compiler is reasonably modern due special knowledge and treatment of
common functions/idioms.

Well, here are some benchmarks comparing the use of strcmp() to
compare short character strings (4 characters).

....

It seems, that for the limited cases like this -- when the strings are of
the same length and fit nicely into an integer type -- treating them as
such
is hugely beneficial. And, contrary to authoritative assertions posted in
this thread, compiler is NOT able to detect such cases.

Okay, I retract my statement. The compiler does a good job with strcmp(),
but it'll never be as fast as your version because the compiler has no way
to know that the strings will _always_ be exactly of length 3, so it has to
test for '\0' several times. That difference of knowledge will easily
account for the 3x-5x difference in execution speed.

I am curious if the following has a substantially different speed from your
version:

-------
/* NOTE: c1 and c2 must point to strings of exactly 3 chars */
int
CurEqual(char *c1, char *c2)
{
/* catch people calling this function with bad params */
assert((strlen( c1)==3) && (strlen(c2)==3) );

/* Note: & is safe here since == always returns 0 or 1, and
it's likely to be faster than && */
if ((c1[0]==c2[0])&(c1[1]==c2[1])&(c1[3]==c2[3]))
printf("Same currency %s\n", c1);
else
printf("%s and %s are different\n", c1, c2);
}
-------

This version looks, to me, like it's fully portable and should be
substantially faster than strcmp(), at least when NDEBUG is defined.

S

--
Stephen Sprunk "God does not play dice." --Albert Einstein
CCIE #3723 "God is an inveterate gambler, and He throws the
K5SSS dice at every possible opportunity." --Stephen Hawking

--
Posted via a free Usenet account from http://www.teranews.com

[Mikhail Teterin]

Stephen Sprunk wrote:

if ((c1[0]==c2[0])&(c1[1]==c2[1])&(c1[3]==c2[3]))

Yes, it is faster than strcmp(), of course. But still slower than the
int-compare. I added two more functions to the test:

int
comp_mem(const char cur1[4], const char cur2[4])
{
return memcmp(cur1, cur2, sizeof cur1) == 0;
}

int
comp_Sprunk(con st char cur1[4], const char cur2[4])
{
return cur1[0] == cur2[0] && cur1[1] == cur2[1]
&& cur1[2] == cur2[2];
}
Here are the results:

FreeBSD/i386 (Pentium D @3GHz):
str: used 1091883 microseconds
int: used 404868 microseconds
Sprunk: used 590683 microseconds
memcmp: used 4424082 microseconds

FreeBSD/amd64 (opteron 244):
str: used 1402967 microseconds
int: used 392841 microseconds
Sprunk: used 617995 microseconds
memcmp: used 1571644 microseconds

Solaris8/sparc (@900MHz)
str: used 730000 microseconds
int: used 130000 microseconds
Sprunk: used 160000 microseconds
memcmp: used 560000 microseconds

AIX/powerpc
str: used 3200000 microseconds
int: used 710000 microseconds
Sprunk: used 820000 microseconds
memcmp: used 2990000 microseconds

Linux/i386 (Xeon @3GHz)
str: used 1060000 microseconds
int: used 390000 microseconds
Sprunk: used 530000 microseconds
memcmp: used 3520000 microseconds

What puzzles me, actually, is the poor performance of memcmp() vs. strcmp(),
but that's it -- no other surprises...

This version looks, to me, like it's fully portable and should be
substantially faster than strcmp(), at least when NDEBUG is defined.

Agreed about the strcmp, but portability is something, my version is not,
actually, lacking either. I'm unaware of a general-purpose platform, with
non-8 CHAR_BIT. And if int32_t is missing, well, that's a compile-time
error, not a run-time disaster...

-mi

[CBFalconer]

Stephen Sprunk wrote:

>

.... snip ...

>
I am curious if the following has a substantially different speed
from your version:

-------
/* NOTE: c1 and c2 must point to strings of exactly 3 chars */
int
CurEqual(char *c1, char *c2)
{
/* catch people calling this function with bad params */
assert((strlen( c1)==3) && (strlen(c2)==3) );
/* Note: & is safe here since == always returns 0 or 1,
and it's likely to be faster than && */
if ((c1[0]==c2[0])&(c1[1]==c2[1])&(c1[3]==c2[3]))
printf("Same currency %s\n", c1);
else
printf("%s and %s are different\n", c1, c2);
}
-------

This version looks, to me, like it's fully portable and should be
substantially faster than strcmp(), at least when NDEBUG is defined.

Lets cut that down to the essentials, and make it compilable:

int ceq(const char *c1, const char *c2)
{
return (*c1 == *c2) & (c1[1] == c2[1]) & (c1[2] == c2[2]);
}

with the same comments about & as yours. This must perform at
least 4 indexing operations, 6 dereferences, 3 comparisons, and 2
bit ands.

Now, lets analyze a normal comparison, without the limitations on
length etc. operating on the same length 3 strings:

int ceq(const char *c1, const char *c2)
{
while (*c1 && (*c1 == *c2)) {
c1++; c2++;
}
return *c1 == *c2;
}

In the best case, *c1 != *c2, assuming reasonable register
allocations, there will be 2 dereferences, one zero test, and one
comparison. The loop is never executed. Note that for random
strings this is the MOST LIKELY result. Much faster.

In the worst case, there is no difference, and all three components
have to be checked. For the same allocation assumptions, there
will be 7 dereferences, 4 zero tests, 3 comparisons, and 6 pointer
increments, followed by a final comparison.

You will have to do an unholy number of calls to these routines to
measure the difference with most clock systems resolution. Have
fun. Don't forget that execution speed is data dependant so you
will need to generate bags and bags of random strings. I suggest
the Mersenne Twister to do that, but you will have to compensate
for string generation time.

--
"The power of the Executive to cast a man into prison without
formulating any charge known to the law, and particularly to
deny him the judgement of his peers, is in the highest degree
odious and is the foundation of all totalitarian government
whether Nazi or Communist." -- W. Churchill, Nov 21, 1943

[websnarf]

CBFalconer wrote:

Stephen Sprunk wrote:
... snip ...

I am curious if the following has a substantially different speed
from your version:

-------
/* NOTE: c1 and c2 must point to strings of exactly 3 chars */
int
CurEqual(char *c1, char *c2)
{
/* catch people calling this function with bad params */
assert((strlen( c1)==3) && (strlen(c2)==3) );
/* Note: & is safe here since == always returns 0 or 1,
and it's likely to be faster than && */
if ((c1[0]==c2[0])&(c1[1]==c2[1])&(c1[3]==c2[3]))
printf("Same currency %s\n", c1);
else
printf("%s and %s are different\n", c1, c2);
}
-------

This version looks, to me, like it's fully portable and should be
substantially faster than strcmp(), at least when NDEBUG is defined.

Lets cut that down to the essentials, and make it compilable:

int ceq(const char *c1, const char *c2)
{
return (*c1 == *c2) & (c1[1] == c2[1]) & (c1[2] == c2[2]);
}

with the same comments about & as yours. This must perform at
least 4 indexing operations, 6 dereferences, 3 comparisons, and 2
bit ands.

A modern CPU will perform these operations substantially in *PARALLEL*.
In fact the full schedule in an OOO machine like an Athlon (3-way
subscalar, with free offsets) looks something like this:

Cycle 1: r0 <- load(c1) ||| r1 <- load (c2)
Cycle 2: r2 <- load(c1+4) ||| r3 <- load (c2+4)
Cycle 3: f1 <- cmp(r0, r1) ||| r4 <- load (c1+8) ||| r5 <- load (c2+8)
Cycle 4: r6 <- f1 ||| f2 <- cmp (r2, r3)
Cycle 5: r7 <- f2 ||| f3 <- cmp (r4, r5)
Cycle 6: r8 <- and(r6, r7) ||| r9 <- f3
Cycle 7: ra <- and(r8, r9) ||| return

Every cycle performs at least two operations with only cycles 4 and 5
being somewhat less efficient due to the way the x86 architecture works
(you have to copy from the flags to the register.) This tells us that
you should instead use the expression:

static int cneq (const char * c1, const char * c2) {
return (c1[0] - c2[0]) | (c1[1] - c2[1]) | (c1[2] - c2[2]);
}

This leads us to:

Cycle 1: r0 <- load(c1) ||| r1 <- load(c2)
Cycle 2: r2 <- load(c1+4) ||| r3 <- load(c2+4)
Cycle 3: r6 <- sub(r0, r1) ||| r4 <- load(c1+8) ||| r5 <- load(c2+8)
Cycle 4: r7 <- sub(r2, r3)
Cycle 5: r8 <- sub(r4, r5) ||| r9 <- ior(r6, r7)
Cycle 6: ra <- ior(r8, r9) ||| return

which is a cycle faster.

Now, lets analyze a normal comparison, without the limitations on
length etc. operating on the same length 3 strings:

int ceq(const char *c1, const char *c2)
{
while (*c1 && (*c1 == *c2)) {
c1++; c2++;
}
return *c1 == *c2;
}

In the best case, *c1 != *c2, assuming reasonable register
allocations, there will be 2 dereferences, one zero test, and one
comparison.

And *one branch prediction*. In any event, lets take a look:

Cycle 1: r0 <- load(c1) ||| r1 <- load (c1)
Cycle 2: r2 <- load(c2+4)
Cycle 3: f0 <- cmp(r0, 0) ||| ifnz(f0) goto LEnd;

{ Now at this point a branch prediction is made, which costs
either 0 or 10 clocks, and splits into two cases. }

Cycle 4/14: r3 <- load(c1) ||| r4 <- load(c2)
Cycle 5/15: noop
Cycle 6/16: f2 <- cmp(r3, r4)
Cycle 7/17: r5 <- f2 ||| return

{ or: }

Cycle 4/14: f1 <- cmp(r1, r2) ||| ifnz(f1) goto LEnd;

{ Now at this point a branch prediction is made, which costs
either 0 or 10 clocks, and splits into two cases. }

Cycle 5/15: r3 <- load(c1) ||| r4 <- load(c2)
Cycle 6/16: noop
Cycle 7/17: f2 <- cmp(r3, r4)
Cycle 8/18: r5 <- f2 ||| return

etc. So your *best* case costs basically 7 clocks anyways. (Once you
either start predicting wrong, or enter the loop, you are clearly much
worse.) These are highly idealized models of the Athlon machine, so
real results may be different. It might be interesting to see the real
world results.

[...] The loop is never executed. Note that for random
strings this is the MOST LIKELY result. Much faster.

It highly depends on the random distribution. The branch prediction
penalty could *easily* dominate. For example, if there were only two
or three really common strings (USD, Euros, and Yen, say) but no
discernable pattern in those actual cases, then you could easily tend
to get the branch prediction wrong around 30% of the time, which
translates to an average of 3 clocks extra.

In the worst case, there is no difference, and all three components
have to be checked. For the same allocation assumptions, there
will be 7 dereferences, 4 zero tests, 3 comparisons, and 6 pointer
increments, followed by a final comparison.

I haven't done the bench, and clearly you haven't either. Care to put
money on this claim?

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/