how to optimize a for loop

[andreyvul]

I have this loop (all variables are pointers):
for (foo = bar; foo > baz; foo--)
*(foo+1) = *foo;
How do I optimize the pointer swap so that it uses -- and ++ or unary
+- instead of +1 (if possible - I don't want to have more #defines
than code)?
IOCCC winners can really help me with this

 

[user923005]

I have this loop (all variables are pointers):
for (foo = bar; foo > baz; foo--)
*(foo+1) = *foo;
How do I optimize the pointer swap so that it uses -- and ++ or unary
+- instead of +1 (if possible - I don't want to have more #defines
than code)?
IOCCC winners can really help me with this

memmove(foo+1, foo, len);

Note that memcpy() is not allowed here.

 

[andreyvul]

memmove(foo+1, foo, len);

Note that memcpy() is not allowed here.

Breaks my in-place mergesort, sorry. Same result as with this:
for (foo = bar + 1; foo > baz
*(foo) = *(--foo);
Though I'm guessing that's how memmove works in a two-liner.
Is there a way to optimize insertion sort's inner loop is what I
meant.
full sort code (t is a value variable):
/* ... divide and conquer ... */
for (;(start <= mid) && (mid + 1 <= end); start++) {
if (*start < *(mid + 1)) //sorted (current element belongs in 1st
half)
continue;
else { /* true inplace merge requires insersion-sort-like
* methods because a value from the second half is inserted to
* the current element */
//copy the first element in the second half to t
t = *(mid + 1);
//shift first half to the right (this is what I was trying to
optimize)
for (shift = mid; shift >= start; shift--)
*(shift + 1) = *shift;
//copy t to start
*start = t;
mid++;
}
}

 

[Keith Thompson]

I have this loop (all variables are pointers):
for (foo = bar; foo > baz; foo--)
*(foo+1) = *foo;
How do I optimize the pointer swap so that it uses -- and ++ or unary
+- instead of +1 (if possible - I don't want to have more #defines
than code)?
IOCCC winners can really help me with this

What makes you think that replacing "+1" with "++" is an optimization?

 

[Eric Sosman]

I have this loop (all variables are pointers):
for (foo = bar; foo > baz; foo--)
*(foo+1) = *foo;
How do I optimize the pointer swap so that it uses -- and ++ or unary
+- instead of +1 (if possible - I don't want to have more #defines
than code)?
IOCCC winners can really help me with this

Assuming the pointers are of the same type:

memmove (baz + 2, baz + 1, (bar - (baz + 1)) * sizeof *baz);

 

[andreyvul]

What makes you think that replacing "+1" with "++" is an optimization?

aesthetic obfuscation

 

[andreyvul]

Assuming the pointers are of the same type:

memmove (baz + 2, baz + 1, (bar - (baz + 1)) * sizeof *baz);

sort still fails
actual output: 1 1 3 1 1 1 1 3 1 1
intended output: 1 2 3 4 5 6 7 8 9 10
somehow memmove fails while iterated swap works. wierd.

 

[Jack Klein]

sort still fails
actual output: 1 1 3 1 1 1 1 3 1 1
intended output: 1 2 3 4 5 6 7 8 9 10
somehow memmove fails while iterated swap works. wierd.

Then there is an error in your code, which you have failed to
recognize.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://c-faq.com/
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++
http://www.club.cc.cmu.edu/~ajo/docs/FAQ-acllc.html

 

[Eric Sosman]

sort still fails
actual output: 1 1 3 1 1 1 1 3 1 1
intended output: 1 2 3 4 5 6 7 8 9 10
somehow memmove fails while iterated swap works. wierd.

Then something is wrong with your sort, or else I mis-
translated your loop (fencepost error, maybe?), or else the
assumption of identically-typed pointers is wrong. Show
some code -- and I don't mean the out-of-context partial
snippet you posted elsethread; I mean show a short, complete,
compilable program that demonstrates your problem. (I for
one have had it up to HERE with trying to debug paraphrases.)

 

[karthikbalaguru]

Breaks my in-place mergesort, sorry. Same result as with this:
for (foo = bar + 1; foo > baz
*(foo) = *(--foo);
Though I'm guessing that's how memmove works in a two-liner.
Is there a way to optimize insertion sort's inner loop is what I
meant.
full sort code (t is a value variable):
/* ... divide and conquer ... */
for (;(start <= mid) && (mid + 1 <= end); start++) {
if (*start < *(mid + 1)) //sorted (current element belongs in 1st
half)
continue;
else { /* true inplace merge requires insersion-sort-like
* methods because a value from the second half is inserted to
* the current element */
//copy the first element in the second half to t
t = *(mid + 1);
//shift first half to the right (this is what I was trying to
optimize)
for (shift = mid; shift >= start; shift--)
*(shift + 1) = *shift;
//copy t to start
*start = t;
mid++;
}
}

Will loop unrolling / loop unwinding help you here ?

Advantages:
1) Reduces the number of loop and also reduces the
number of jumps that was earlier present for
every iteration. So, this saves time interms of
loop manipulation.

But, it has its own disadvantages :
1)Pretty high Code size
2)Compiler has to allocate more registers to handle the variables in
the
unrolling mode.

Karthik Balaguru

 

[andreyvul]

memmove won't work because it only works one byte at a time. I'll try
changing the offset of the destination pointer by adding a sizeof.

 

[pete]

memmove won't work because it only works one byte at a time.

That may or may not be true,
depending on how memmove is implemented.
If memmove can determine that the memory being moved
is properly aligned for type int, and if (n) is large enough,
then memmove may be able to move most or all of the bytes,
in blocks of sizeof(int) bytes at a time.

 

[Eric Sosman]

andreyvul wrote On 11/01/07 13:22,:

memmove won't work because it only works one byte at a time.

First, that may or may not be true. memmove() might
work one byte at a time, or forty-two bytes at a time, or
one bit at a time, or by slow seepage of quantum-encoded
information through a semi-permeable osmotic membrane.
It copies the source bytes to the destination, and there's
no need to fret about the mechanism.

Second, the mechanism can't be the reason why it "won't
work." I repeat: memmove() copies the source to the
destination, and that is all it does. If you don't like
the results, it means you have done something wrong, and
that the same thing would still be wrong if you replaced
memmove() by some other equivalent.

I'll try
changing the offset of the destination pointer by adding a sizeof.

I have, over the years, seen other people who tried this
same strategy for getting code to work. They'd just keep
making semi-random half-understood tweaks until they got the
answers they expected. Oddly enough, it nearly always turned
out that the tweaks produced code that worked only on the
single test case they'd tried, and quite often even that much
success was dumb luck (wander off the end of an array and just
happen to find something that looks like a bigger value than
anything in the array, that sort of thing).

You need to learn to *reason* about your code instead
of just diddling with it aimlessly.

 

[user923005]

andreyvul wrote On 11/01/07 13:22,:


First, that may or may not be true. memmove() might
work one byte at a time, or forty-two bytes at a time, or
one bit at a time, or by slow seepage of quantum-encoded
information through a semi-permeable osmotic membrane.
It copies the source bytes to the destination, and there's
no need to fret about the mechanism.

Second, the mechanism can't be the reason why it "won't
work." I repeat: memmove() copies the source to the
destination, and that is all it does. If you don't like
the results, it means you have done something wrong, and
that the same thing would still be wrong if you replaced
memmove() by some other equivalent.

I would like to add to that:
Not only does memmove() copy from source to destination, but it is
literally the safest way possible to do it. It is guaranteed to work,
even if the source and destination overlap. It is guaranteed to work
even if the two pointers have different alignments. It is probably
also the fastest safe way to do it as well. Implementations that I
have seen use clever assembly to test for alignment and move large
memory segments big blocks at a time if it is convenient and safe to
do so. If the program does not work when memmove() is inserted, then
there are two distinct possibilities:
1. The memmove() function was not used correctly
2. The program is broken somewhere else.

I have, over the years, seen other people who tried this
same strategy for getting code to work. They'd just keep
making semi-random half-understood tweaks until they got the
answers they expected. Oddly enough, it nearly always turned
out that the tweaks produced code that worked only on the
single test case they'd tried, and quite often even that much
success was dumb luck (wander off the end of an array and just
happen to find something that looks like a bigger value than
anything in the array, that sort of thing).

You need to learn to *reason* about your code instead
of just diddling with it aimlessly.

I have seen the approach where putting a printf() into the code caused
the program to *cough* 'start working' and so the programmer that
inserted the printf() decided to leave it in and call the program
completed. The code review turned up the real cause of undefined
behavior, of course. "Trial and error" is a terrible way to program
and the consequences are almost always disaster.

 

[Barry Schwarz]

Breaks my in-place mergesort, sorry. Same result as with this:
for (foo = bar + 1; foo > baz
*(foo) = *(--foo);

Since this statement invokes undefined behavior while the memmove does
not, it is unlikely the results are the same, even if they appear to
be.