EFFICIENCY question: need help from the C geniuses

[mark]

Hello-

i am trying to make the function addbitwise more efficient. the code
below takes an array of binary numbers (of size 5) and performs
bitwise addition. it looks ugly and it is not elegant but it appears
to work. using time, i measured it takes .041s to execute, which i
admit isnt much. but, the problem is that this procedure will be
called many, many times in my project (probably at least a few
thousand times, if not more) so thus, efficiency very is important.
any suggestions (and explanations)? thanks...!

mark.

int main()
{
int arr1[5];
int arr2[5];

arr1[0] = 0;
arr1[1] = 1;
arr1[2] = 0;
arr1[3] = 0;
arr1[4] = 0;

arr2[0] = 1;
arr2[1] = 0;
arr2[2] = 1;
arr2[3] = 1;
arr2[4] = 0;

addbitwise(arr1 , arr2);

exit(1);
}

int addbitwise(int x[], int y[])
{
int result[5];
int i, carry = 0;

for (i=4; i>=0; i--)
{
result[i] = x[i] ^ y[i]; /* result of the bitwise
add */

if (x[i] & y[i]) /* a carry has occured */
{
carry = 1;

if (i != 0) /* prevents final iteration */
{ /* from peeking out of bounds */
if (x[i-1] == 0)
{
x[i-1] = 1; /* replace the next 0 bit with the carry'd 1 */
carry = 0;
}

else if (y[i-1] == 0) /* peek at the next array bit */
{
y[i-1] = 1;
carry = 0;
}
}
}
}

return(carry);
}

_______________ ______
Mark Fonnemann
Boston College
B.A., Computer Science 2000
M.A., Mathematics 2002
_______________ ______

[Christian Bau]

In article <f6************ **************@ posting.google. com>,
no************@ yahoo.com (mark) wrote:

Christian Bau <ch***********@ cbau.freeserve. co.uk> wrote in message
news:<ch******* *************** ***********@slb-newsm1.svr.pol. co.uk>...

In article <f6************ **************@ posting.google. com>,
no************@ yahoo.com (mark) wrote:

Hello-

i am trying to make the function addbitwise more efficient. the code
below takes an array of binary numbers (of size 5) and performs
bitwise addition. it looks ugly and it is not elegant but it appears
to work. using time, i measured it takes .041s to execute, which i
admit isnt much. but, the problem is that this procedure will be
called many, many times in my project (probably at least a few
thousand times, if not more) so thus, efficiency very is important.
any suggestions (and explanations)? thanks...!

You measured the time to start and stop the program, nothing else.

then how would i measure the entire execution of the program...? i
used time ./a where a was the name of the executable.

With your program, the time between start and stop is almost exactly
zero. 0.041 seconds is about the time a cheap, modern PC takes to
execute lets say 40 to 100 million instructions. How many instructions
do you think your code needed?

To get a result that is anywhere near reasonable you could do something
like this:

static void test_function (void) {
/* Here goes the code you want to test */
}

int main (void) {
#define ITERATIONS 1
unsigned long i;
for (i = 0; i < ITERATIONS; ++i)
test_function ();
return 0;
}

Measure the time. Then double ITERATIONS, check how long it takes now.
Repeat until you can see that doubling ITERATIONS doubles the execution
time.

[Christian Bau]

In article <f6************ **************@ posting.google. com>,
no************@ yahoo.com (mark) wrote:

Arthur-

it may be trivial to you, but despite programming in C for several
years (pascal before that, atari basic before that) bitwise operators
always give me a problem. clearly, i could have defined it as two
integers and used the binary additive operator denoted '+' if that was
what i was trying to accomplish. however, my project works entirely
with bits, and as we all know, the byte is the smallest indivisble
unit defined in C.

that said, i'm kinda offended about the HW problem issue. i know that
many people probably use this group for answers. however, that is not
my case. i graduated from Boston College in 2000 with a degree in
computer science as denoted in my sig file. perhaps, this was
overlooked. as for the other "cheaters", well rather than criticize
just be assured that you can only fool people for so long about how
well/not well you can code. those people will get what they deserve
eventually. i see too few people here willing to let fate take its
part and i wonder if its insecurity.

I will in the future carefully check any CV to see whether it mentions
Boston College :-(

[CBFalconer]

mark wrote:

it may be trivial to you, but despite programming in C for several
years (pascal before that, atari basic before that) bitwise operators
always give me a problem. clearly, i could have defined it as two
integers and used the binary additive operator denoted '+' if that was
what i was trying to accomplish. however, my project works entirely
with bits, and as we all know, the byte is the smallest indivisble
unit defined in C.

Please do not toppost, and please do snip non-germane quotations.
Topposting is not condoned in this newsgroup.

IIRC your original (now lost due to topposting) appeared to be
simulating a serial full adder. I think I spotted some logical
errors, but we'll never know now.

If you don't explain why you want to do such things, many people
will suggest much more efficient methods, such as dealing with a
byte/short/int/long worth of bits at a time.

--
Chuck F (cb********@yah oo.com) (cb********@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!

[mark]

my views and actions don't reflect the views of my university. so,
please do not let this affect your judgment of the school. as for my
coding, i never had to resort to cheating while at the university. if
the problem was difficult, then i would merely end up with bloated
code. perhaps, there was cheating by other students in the program but
no more so than another university.

Christian Bau <ch***********@ cbau.freeserve. co.uk> wrote in message news:<ch******* *************** ***********@slb-newsm1.svr.pol. co.uk>...

I will in the future carefully check any CV to see whether it mentions
Boston College :-(

mark wrote:

that said, i'm kinda offended about the HW problem issue. i know that
many people probably use this group for answers. however, that is not
my case. i graduated from Boston College in 2000 with a degree in
computer science as denoted in my sig file. perhaps, this was
overlooked. as for the other "cheaters", well rather than criticize
just be assured that you can only fool people for so long about how
well/not well you can code. those people will get what they deserve
eventually. i see too few people here willing to let fate take its
part and i wonder if its insecurity.

[Paul Hsieh]

no************@ yahoo.com (mark) wrote:

I am trying to make the function addbitwise more efficient.

Under the assumption that x[] and y[] hold only the values 0 and 1
(which I gather from the algorithm and what you tried to say) try the
following:

int addbitwise(int x[], int y[]) {
int xx = x[4]+((x[3]+((x[2]+((x[1]+(x[0]<<1))<<1))<<1)) <<1);
int yy = y[4]+((y[3]+((y[2]+((y[1]+(y[0]<<1))<<1))<<1)) <<1);
return xx+yy >= 32;
}

BTW, this is not such a great newsgroup for seeking advice on code
optimization. The people who post here are C language lawyers. Even
the C geniuses here aren't going to give very insightful answers.
OTOH, I don't really know if there is a good code optimization
newsgroup anywhere.

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

[Thomas Matthews]

Paul Hsieh wrote:

no************@ yahoo.com (mark) wrote:

I am trying to make the function addbitwise more efficient.

Under the assumption that x[] and y[] hold only the values 0 and 1
(which I gather from the algorithm and what you tried to say) try the
following:

int addbitwise(int x[], int y[]) {
int xx = x[4]+((x[3]+((x[2]+((x[1]+(x[0]<<1))<<1))<<1)) <<1);
int yy = y[4]+((y[3]+((y[2]+((y[1]+(y[0]<<1))<<1))<<1)) <<1);
return xx+yy >= 32;
}

BTW, this is not such a great newsgroup for seeking advice on code
optimization. The people who post here are C language lawyers. Even
the C geniuses here aren't going to give very insightful answers.
OTOH, I don't really know if there is a good code optimization
newsgroup anywhere.

--
Paul Hsieh

But what are you optimizing for: Speed, Code Size, Readability,
Portability?

As many people here have stated, profile before optimizing. Much
time is spent in small areas of code. More often than not, the
critical factor is quality first, then the others.

At my work, we only optimize if we need space (to add more code)
or the execution takes too long. In many real-time embedded
systems, there is a fixed amount of time between critical events.
If the code execeeds its time window, then the event is missed
or a nice backlog develops.

Personally, if the OP's function needed full optimization, I
would write it in assembly language. I've found bit manipulation
easier in assembly language than C or other high level languages.

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.l earn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book

[Dan Pop]

In <79************ **************@ posting.google. com> qe*@pobox.com (Paul Hsieh) writes:

BTW, this is not such a great newsgroup for seeking advice on code
optimization . The people who post here are C language lawyers. Even
the C geniuses here aren't going to give very insightful answers.

Some of them are also experienced C programmers, willing to discuss
the optimisation vs portability trade-offs, when such discussions make
sense.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de

[Paul Hsieh]

Try this:

int addbitwise (int x[], int y[]) {
int xx, yy

xx = x[4] + ((x[3] + ((x[2] + ((x[1] + (x[0] << 1)) << 1)) << 1)) << 1);
yy = y[4] + ((y[3] + ((y[2] + ((y[1] + (y[0] << 1)) << 1)) << 1)) << 1);
return xx + yy >= 32;
}

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

[Paul Hsieh]

Th************* *************** @sbcglobal.net says...

Paul Hsieh wrote:

no************@ yahoo.com (mark) wrote:

I am trying to make the function addbitwise more efficient.
Under the assumption that x[] and y[] hold only the values 0 and 1
(which I gather from the algorithm and what you tried to say) try the
following:

int addbitwise(int x[], int y[]) {
int xx = x[4]+((x[3]+((x[2]+((x[1]+(x[0]<<1))<<1))<<1)) <<1);
int yy = y[4]+((y[3]+((y[2]+((y[1]+(y[0]<<1))<<1))<<1)) <<1);
return xx+yy >= 32;
}

BTW, this is not such a great newsgroup for seeking advice on code
optimization. The people who post here are C language lawyers. Even
the C geniuses here aren't going to give very insightful answers.
OTOH, I don't really know if there is a good code optimization
newsgroup anywhere.

--
Paul Hsieh

But what are you optimizing for: Speed, Code Size, Readability,
Portability?

In this case, I think I've won on all those except possibly portability to
systems for which integers are less than 6 bits.

Speed: If this routine doesn't waste the original or anyone else's post by at
least a factor of 2 I would be very very surprised.

Code Size: Its 3 lines. Even the object code is likely to be competitive if
not smaller -- a for loop for just 5 iterations?

Readability: The code obviously coallesces the 5 bits of each into a packed 2s
complement integer (horner's rule) then checks if the resulting add >= 32
(carries over to the 5th bit.) It actually takes some analysis to know for
sure that the other submissions actually does this.
As many people here have stated, profile before optimizing.
And how do you know the OP didn't do this?
[...] Personally, if the OP's function needed full optimization, I
would write it in assembly language. I've found bit manipulation
easier in assembly language than C or other high level languages.

That rule of thumb seems too rough. You use assembly language when your
compiler produced inadequate code and you can incurr the maintenance and non-
portability penalty of using assembly language.

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

[Christian Bau]

In article <MP************ ************@ne ws.sf.sbcglobal .net>,
qe*@pobox.com (Paul Hsieh) wrote:

Th************* *************** @sbcglobal.net says...

As many people here have stated, profile before optimizing.

And how do you know the OP didn't do this?

He used a unix tool to measure the total execution time of the program,
which was 0.041 seconds. The function in question was called once. I
would guess that the execution time of that function is less than a
microsecond, so the ratio overhead / execution time is about 41,000 to
1. If he replaced his function with yours which as a rough guess would
be ten times faster, then his measurement will still be 0.041 seconds.