loops - Case where goto's cannot be removed (optimization)

[anon.asdf]

Hi!

The following code is a snippet where the goto's cannot be removed
"without increasing code-size, or decreasing performance".

/*********A**************/
int var_other_thread;
// value changed by another thread

int var_this_thread;

int array[100];

#define EQUAL \
var_this_thread == var_other_thread

#define NOT_EQUAL \
var_this_thread != var_other_thread

void myfuncA(void)
{
if (EQUAL) goto label2;

label1:
var_this_thread = var_other_thread;

label2:
array[var_this_thread] = 1;
if (NOT_EQUAL) goto label1;
}
/***********************/

Actually one goto can be removed without worsening code-size or
performance:

/*********B**************/
#define EQUAL \
var_this_thread == var_other_thread

void myfuncB(void)
{
if (EQUAL)
goto here;
while(1) {
var_this_thread = var_other_thread;
here:
array[var_this_thread] = 1;
if (EQUAL)
break;
}
}
/***********************/

In terms of machine code, myfuncB(void) will be the same as
myfuncA(void), right???


hmm... the above example is not so good.
I just realized that an optimization would be to leave the first
conditional and always force the assignment, right? Example below:
->
/*********C**************/
#define NOT_EQUAL \
var_this_thread != var_other_thread

void myfuncC(void)
{
do {
var_this_thread = var_other_thread;
array[var_this_thread] = 1;
} while (NOT_EQUAL);
}
/***********************/

-anon.asdf

 

[Eric Sosman]

Hi!

The following code is a snippet where the goto's cannot be removed
"without increasing code-size, or decreasing performance".

/*********A**************/
int var_other_thread;
// value changed by another thread

int var_this_thread;

int array[100];

#define EQUAL \
var_this_thread == var_other_thread

#define NOT_EQUAL \
var_this_thread != var_other_thread

void myfuncA(void)
{
if (EQUAL) goto label2;

label1:
var_this_thread = var_other_thread;

label2:
array[var_this_thread] = 1;
if (NOT_EQUAL) goto label1;
}
/***********************/

void myfuncA(void)
{
do {
array[var_this_thread = var_other_thread] = 1;
} while (NOT_EQUAL);
}

Argument: The test for EQUAL is wasted, because if
the two variables are equal it does no harm to copy one
to the other. Yes, it takes time -- but eliminating the
test and the conditional jump saves time, so it is by no
means obvious that there's a net loss.

<off-topic>

Of course, neither the original nor my rewrite is
any use at all in an actual multi-threaded program. And
before anybody mentions it, no: `volatile' doesn't help.

Actually one goto can be removed without worsening code-size or
performance:

/*********B**************/
#define EQUAL \
var_this_thread == var_other_thread

void myfuncB(void)
{
if (EQUAL)
goto here;
while(1) {
var_this_thread = var_other_thread;
here:
array[var_this_thread] = 1;
if (EQUAL)
break;
}
}
/***********************/

This doesn't remove a goto; it just changes the
way it's spelled.

In terms of machine code, myfuncB(void) will be the same as
myfuncA(void), right???

You'll need to ask your compiler; the C language
itself cannot answer the question.

hmm... the above example is not so good.

"Herein he was right."

I just realized that an optimization would be to leave the first
conditional and always force the assignment, right? Example below:
->
/*********C**************/
#define NOT_EQUAL \
var_this_thread != var_other_thread

void myfuncC(void)
{
do {
var_this_thread = var_other_thread;
array[var_this_thread] = 1;
} while (NOT_EQUAL);
}
/***********************/

How about that? You arrived at the same answer I
did, and disproved your own assertion that the gotos
could not be removed. Inquiring minds want to know:
Having refuted your own thesis, why did you press Send?

 

[anon.asdf]

How about that? You arrived at the same answer I
did, and disproved your own assertion that the gotos
could not be removed. Inquiring minds want to know:
Having refuted your own thesis, why did you press Send?

Hi Eric!

Thank's for your kind reply. I hit send, since I wanted to know if the
code structure (in terms of "if" and "goto") could be reformed, to an
equivalent that does not use goto.
(It is not possible.)

I wanted an analysis of code structure (in terms of "if" and "goto")
and not the contents...
which were badly chosen (and I did not take the time to change it -
sorry.): still the contents did reveal that one optimization - which
is interesting nonetheless

- anon.asdf

 

[anon.asdf]

I wanted an analysis of code structure (in terms of "if" and "goto")
and not the contents...
which were badly chosen (and I did not take the time to change it -
sorry.): still the contents did reveal that one optimization - which
is interesting nonetheless

Here is an example with better "content":

/*******************/

/* think of var_other_thread
as increasing steadily from 0 to 100
in another thread.

var_this_thread is handled in this code!
Think of it as 0 initially.
*/

#define NEARBY_BELOW \
(var_this_thread >= var_other_thread - 2) \
&& (var_this_thread <= var_other_thread) \

#define NOT_NEARBY_BELOW \
(var_this_thread < var_other_thread - 2) \
|| (var_this_thread > var_other_thread)

/* only limited range is used -
we're not going to fall of (wrap around)
the (overflow) ends
*/

void myfuncA(void)
{
if (NEARBY_BELOW) goto label2;

label1:
var_this_thread = var_other_thread - 2;

label2:
array[var_this_thread] = 1;
if (NOT_NEARBY_BELOW) goto label1;

var_this_thread++;
}
/*******************/

(one goto could be removed - as was shown in the original post /
**B**/)

- Albert

 

[Army1987]

Hi!

The following code is a snippet where the goto's cannot be removed
"without increasing code-size, or decreasing performance".

/*********A**************/
int var_other_thread;
// value changed by another thread

int var_this_thread;

int array[100];

#define EQUAL \
var_this_thread == var_other_thread

#define NOT_EQUAL \
var_this_thread != var_other_thread

void myfuncA(void)
{
if (EQUAL) goto label2;

label1:
var_this_thread = var_other_thread;

label2:
array[var_this_thread] = 1;
if (NOT_EQUAL) goto label1;
}
/***********************/

void myfuncA(void)
{
do {
array[var_this_thread = var_other_thread] = 1;
} while (NOT_EQUAL);
}

Argument: The test for EQUAL is wasted, because if
the two variables are equal it does no harm to copy one
to the other. Yes, it takes time -- but eliminating the
test and the conditional jump saves time, so it is by no
means obvious that there's a net loss.

<off-topic>

Of course, neither the original nor my rewrite is
any use at all in an actual multi-threaded program. And
before anybody mentions it, no: `volatile' doesn't help.

</off-topic>

Why doesn't it?

 

[Eric Sosman]

Army1987 wrote On 08/14/07 17:11,:

]

<off-topic>

Of course, neither the original nor my rewrite is
any use at all in an actual multi-threaded program. And
before anybody mentions it, no: `volatile' doesn't help.

</off-topic>

Why doesn't it?

<off-topic>

In a system with multiple CPU's, multiple paths to
multiple levels of memory (possibly NUMA), reordering of
memory transactions, and all the other go-fast gimmickry,
how long does it take for CPU 0 to observe that CPU 17
has written a new value to location X? If CPU 17 writes
to X and then to Y, will CPU 0 necessarily observe X
change before Y, or might it see Y change before X?

Visit comp.programming.threads for more details on
why `volatile' is neither necessary nor sufficient for
thread synchronization.

</off-topic>

 

[christian.bau]

Thank's for your kind reply. I hit send, since I wanted to know if the
code structure (in terms of "if" and "goto") could be reformed, to an
equivalent that does not use goto.
(It is not possible.)

Of course the code can be written without goto's. It has been proven
more than 30 years ago that any bit of code using goto's can be
rewritten without them (however, it is not necessarily an
improvement

 

[Flash Gordon]

Here is an example with better "content":

void myfuncA(void)
{
if (NEARBY_BELOW) goto label2;

label1:
var_this_thread = var_other_thread - 2;

label2:
array[var_this_thread] = 1;
if (NOT_NEARBY_BELOW) goto label1;

var_this_thread++;
}
/*******************/

(one goto could be removed - as was shown in the original post /
**B**/)

- Albert

Well, if I've not made any mistakes...
void myfuncA(void)
{
switch (NEARBY_BELOW) {
do {
case 0: var_this_thread = var_other_thread - 2;
default: array[var_this_thread] = 1;
} while (NOT_NEARBY_BELOW);
}
var_this_thread++;
}

Not even one goto statement. Of course, it is late at night so I probabl
have made a mistake. No repeated conditions. A loop construct to
implement the loop.

 

[JimS]

On Tue, 14 Aug 2007 16:00:38 -0400, Eric Sosman wrote:

void myfuncA(void)
{
do {
array[var_this_thread = var_other_thread] = 1;
} while (NOT_EQUAL);
}

Argument: The test for EQUAL is wasted, because if
the two variables are equal it does no harm to copy one
to the other. Yes, it takes time -- but eliminating the
test and the conditional jump saves time, so it is by no
means obvious that there's a net loss.

<off-topic>

Of course, neither the original nor my rewrite is
any use at all in an actual multi-threaded program. And
before anybody mentions it, no: `volatile' doesn't help.

</off-topic>

Why doesn't it?

volatile doesn't guarantee atomicity of operations.
If I write

volatile int x = 0;
x++;

That might likely come out as

mov reg,[x]
inc reg
mov [x],reg

then there's no reason that another thread can't come along in between
those operations and change [x].

Jim

 

[anon.asdf]

Well, if I've not made any mistakes...
void myfuncA(void)
{
switch (NEARBY_BELOW) {
do {
case 0: var_this_thread = var_other_thread - 2;
default: array[var_this_thread] = 1;
} while (NOT_NEARBY_BELOW);
}
var_this_thread++;

}

Not even one goto statement. Of course, it is late at night so I probabl
have made a mistake. No repeated conditions. A loop construct to
implement the loop.

Hi Flash! That's really good! -Albert

 

[Flash Gordon]

Well, if I've not made any mistakes...
void myfuncA(void)
{
switch (NEARBY_BELOW) {
do {
case 0: var_this_thread = var_other_thread - 2;
default: array[var_this_thread] = 1;
} while (NOT_NEARBY_BELOW);
}
var_this_thread++;

}

Not even one goto statement. Of course, it is late at night so I probabl
have made a mistake. No repeated conditions. A loop construct to
implement the loop.

Hi Flash! That's really good! -Albert

No it isn't, it's absolutely horrible
It actually breaks one thing I would expect to be in any serious coding
standard, namely it jumps in to a loop.
If you like it I suggest you search for Duffs Device which was my
inspiration.