anti-aliasing

[Malcolm McLean]

A proposed new function

int alias(void *ptr1, size_t len1, void *ptr1, size_t len2)

Returns true if the pointers overlap.

On most machines it can be trivially implemented. However it has to be a
standard library function because it is not necessarily legal to compare two
address from different objects.

The advantages:

An unintelligent implementation simply executes the user's error-handling
code if an unwanted alias is passed. An intelligent implementation can
detect that the two pointers cannot possibly be aliases, and generate moe
efficient code.

However the restrictions do not percolate up to calling code. There is no
need to declare every pointer parameter "restict" just because somewhere you
call a library string copy.

 

[santosh]

A proposed new function

int alias(void *ptr1, size_t len1, void *ptr1, size_t len2)

Returns true if the pointers overlap.

Who will specify the len1 and len2 parameters?

 

[Serve Laurijssen]

A proposed new function

int alias(void *ptr1, size_t len1, void *ptr1, size_t len2)

Returns true if the pointers overlap.

On most machines it can be trivially implemented. However it has to be a
standard library function because it is not necessarily legal to compare
two address from different objects.

The advantages:

An unintelligent implementation simply executes the user's error-handling
code if an unwanted alias is passed. An intelligent implementation can
detect that the two pointers cannot possibly be aliases, and generate moe
efficient code.

However the restrictions do not percolate up to calling code. There is no
need to declare every pointer parameter "restict" just because somewhere
you call a library string copy.

Not sure about the use of such a function. aliasing is about compiletime
optimization. You want a compiler to generate code like:

if (alias(...))
{
// do "slow" code
}
else
{
// do "fast" code
}

not sure if that would speed things up

 

[Richard Heathfield]

Malcolm McLean said:

A proposed new function

int alias(void *ptr1, size_t len1, void *ptr1, size_t len2)

invades my namespace. Please call it something else, e.g. isalias.

Thanks.

 

[Guest]

Malcolm McLean said:

invades my namespace. Please call it something else, e.g. isalias.

Unless you want to puts its declaration only in <ctype.h>, that also
invades the user namespace.

 

[Arthur J. O'Dwyer]

A proposed new function

int alias(void *ptr1, size_t len1, void *ptr1, size_t len2)

Returns true if the pointers overlap.

You mean "returns true if any of the first 'len1' bytes of the
object pointed to by 'ptr1' overlaps with any of the first 'len2'
bytes pointed to by 'ptr2'," perhaps with an exception that if
'ptr1' or 'ptr2' is null, the return value is false, or perhaps
it'd be better to leave that behavior undefined.
Basically I'm saying that we must require 'ptr1' to actually
point to an object of at least 'len1' bytes, and likewise 'ptr2'
and 'len2'.

The problem with the name (easily fixed) has been noticed already.
I'd suggest 'memalias', since this is a function that deals with blocks
of memory.

I'd prefer the function to return 1 on success, instead of merely
"true" (non-zero).

On most machines it can be trivially implemented. However it has to be a
standard library function because it is not necessarily legal to compare
two addresses from different objects.

True.

The advantages:

An unintelligent implementation simply executes the user's error-handling
code if an unwanted alias is passed. An intelligent implementation can
detect that the two pointers cannot possibly be aliases, and generate moe
efficient code.

However the restrictions do not percolate up to calling code. There is no
need to declare every pointer parameter "restict" just because somewhere you
call a library string copy.

I don't follow you. It sounds like you're describing (poorly) a
/feature/ of the new function: that the user can write

if (memalias(p1, 10, p2, 10))
memmove(p1, p2, 10);
else
memcpy(p1, p2, 10);

But that's not an /advantage/; in fact in this case (and probably in
most real-world cases with a good compiler) it's a disadvantage, because
it suggests to the user that he will get better performance from the
above obfuscated code than from a simple and readable

memmove(p1, p2, 10);

when in fact the reverse is true.

Maybe if you post an example of code that would benefit from this
new function, the advantages will become clearer.

HTH,
-Arthur

 

[Malcolm McLean]

You mean "returns true if any of the first 'len1' bytes of the
object pointed to by 'ptr1' overlaps with any of the first 'len2'
bytes pointed to by 'ptr2'," perhaps with an exception that if
'ptr1' or 'ptr2' is null, the return value is false, or perhaps
it'd be better to leave that behavior undefined.
Basically I'm saying that we must require 'ptr1' to actually
point to an object of at least 'len1' bytes, and likewise 'ptr2'
and 'len2'.

The problem with the name (easily fixed) has been noticed already.
I'd suggest 'memalias', since this is a function that deals with blocks
of memory.

I'd prefer the function to return 1 on success, instead of merely
"true" (non-zero).


I don't follow you. It sounds like you're describing (poorly) a
/feature/ of the new function: that the user can write

if (memalias(p1, 10, p2, 10))
memmove(p1, p2, 10);
else
memcpy(p1, p2, 10);

But that's not an /advantage/; in fact in this case (and probably in
most real-world cases with a good compiler) it's a disadvantage, because
it suggests to the user that he will get better performance from the
above obfuscated code than from a simple and readable

memmove(p1, p2, 10);

when in fact the reverse is true.

Maybe if you post an example of code that would benefit from this
new function, the advantages will become clearer.

We've got an array of employees, and a list of candidates stored in a linked
list. When a candiate is successful, we want to copy his name over to one of
the employee fields.

Now in fact the candiadate list and the employee list cannot overlap. But
they are generated in widely dispersed parts of a big program. Using
restrict syntax

void employ(restrict EMPLOYEE *employees, int N, restrict EMPLOYEE
*candidate)

we hacve got to percolate up the restrict through all the program.

However do this

void employ(EMPLOYEE *employees, int N, EMPLOYEE *candidate)
{
if(memsame(employees, N * sizeof(EMPLOYEE), candidate, sizeof(EMPLOYEE))
{
/* something has gone deeply wrong if candidate already in our list of
employees. Debug code. */
assert(0);
}
/* compiler knows that at this point no alias */
/* call fast no-alias version of strcpy */
strcpy(emplyees[N-1].name, candidate->name);
}

 

[Arthur J. O'Dwyer]

[big snip]

We've got an array of employees, and a list of candidates stored in a linked
list. When a candiate is successful, we want to copy his name over to one of
the employee fields.

Now in fact the candiadate list and the employee list cannot overlap. But
they are generated in widely dispersed parts of a big program. Using
restrict syntax

void employ(restrict EMPLOYEE *employees, int N, restrict EMPLOYEE
*candidate)

we hacve got to percolate up the restrict through all the program.

I don't think that's true (that is, I think at worst you'd have to
explicitly cast to 'restrict EMPLOYEE *' in the call, and I'm not sure
that's required either), but let it pass.

However do this

void employ(EMPLOYEE *employees, int N, EMPLOYEE *candidate)
{
if(memsame(employees, N * sizeof(EMPLOYEE), candidate, sizeof(EMPLOYEE))
{
/* something has gone deeply wrong if candidate already in our
list of employees. Debug code. */
assert(0);
}
/* compiler knows that at this point no alias */
/* call fast no-alias version of strcpy */
strcpy(emplyees[N-1].name, candidate->name);
}

There is no "fast no-alias version" of strcpy. The strcpy function
by definition /is/ "fast no-alias"; trying to strcpy overlapping objects
results in undefined behavior. Therefore, as I originally said, the
programmer is complicating and pessimizing his code by adding that
"memsame" call. The compiler certainly is not helped by it.
All you're doing is adding another assertion. Adding assertions may be
an admirable goal, but you could probably assert further up the call stack
for better effect.

Maybe if you post an example of code that would /benefit/ from this
new function, the advantages will become clearer.

-Arthur

 

[Christopher Layne]

Not sure about the use of such a function. aliasing is about compiletime
optimization. You want a compiler to generate code like:

if (alias(...))
{
// do "slow" code
}
else
{
// do "fast" code
}

not sure if that would speed things up

Also not sure if the programmer needs to even know about these kind of things.
A good implementation should do it on it's own.

 

[SM Ryan]

# A proposed new function
#
# int alias(void *ptr1, size_t len1, void *ptr1, size_t len2)
#
# Returns true if the pointers overlap.
#
# On most machines it can be trivially implemented. However it has to be a
# standard library function because it is not necessarily legal to compare two
# address from different objects.

Wrong. It has to be in the standard if you want it implemented
everywhere. Gets in the standard if it can be implemented by all
committee members and they are sufficiently motivated.

It's legal on my machine to compare any two pointers. The standard
is not the only or ultimate authority. It is simply a common reference
point so that two people say they are using the same standard
(ANSI or ISO or CCITT or IFIP or POSIX or IEEE or cetera), then
they have communicated alot of information in a few words about
their expectations of what they can share.

 

[Walter Roberson]

It's legal on my machine to compare any two pointers.

If I produce a binary and you load it down onto your machine, then
will your machine execute it differently than my machine (assuming
the same architecture)?

I seem to be a bit fuzzy as to how one would write code that would
detect that it was running on *your* machine, rather than
someone else's machine. What about machines that you are leasing,
what happens on them? And on machines that you are renting? How about
shared hosting service -- the function is legal when it is executed
on behalf of an account you are paying for, but not legal for
other people?

What happens if some code on one of your machines attempts to do
something that -you- have defined as illegal?

It's your machine, and so of course it is your rules, your say as to
what is "legal" or not on -your- machine -- but doesn't it all get
pretty messy to keep your rules disentangled from the rules of the
various standards?


It seems to me that most of us are content with letting this
kind of thing be *implementation specific*, rather than having the
behaviour defined according to some ill-defined property rights...

 

[Random832]

It's legal on my machine to compare any two pointers.

[snip strawman nonsense]
It seems to me that most of us are content with letting this
kind of thing be *implementation specific*, rather than having the
behaviour defined according to some ill-defined property rights...

This is a rather perverse way of interpreting his statement. It's much
more straightforward to say "my machine is an example of a class of
machines on which this operation is supported" (or, if you want to be
very pedantic, "my machine is an example of a class of machines on which
implementations which support this operation are naturally supported by
the underlying hardware" or even "my machine is one on which the only
implementations installed on it do support this operation") - making
a claim about his machine certainly does not imply that that claim is
true _because_ it is his machine.

 

[Malcolm McLean]

void employ(EMPLOYEE *employees, int N, EMPLOYEE *candidate)
{
if(memsame(employees, N * sizeof(EMPLOYEE), candidate,
sizeof(EMPLOYEE))
{
/* something has gone deeply wrong if candidate already in our
list of employees. Debug code. */
assert(0);
}
/* compiler knows that at this point no alias */
/* call fast no-alias version of strcpy */
strcpy(emplyees[N-1].name, candidate->name);
}

There is no "fast no-alias version" of strcpy. The strcpy function
by definition /is/ "fast no-alias"; trying to strcpy overlapping objects
results in undefined behavior. Therefore, as I originally said, the
programmer is complicating and pessimizing his code by adding that
"memsame" call. The compiler certainly is not helped by it.
All you're doing is adding another assertion. Adding assertions may be
an admirable goal, but you could probably assert further up the call stack
for better effect.

Maybe if you post an example of code that would /benefit/ from this
new function, the advantages will become clearer.

If you want to be fussy about it, stcpy does have an implict restrict.

So try this real function I wrote the other day.

int rectangle(unsigned char *rgba, int width, int height, double x1, double
y1, double x2, double y2, unsigned char *col)
{

int i;
int ii;
double temp;
int offset;

if(x1 > x2)
{
temp = x1;
x1 = x2;
x2 = temp;
}
if(y1 > y2)
{
temp = y1;
y1 = y2;
y2 = temp;
}
if(x1 < 0)
x1 = 0;
if(x2 > width - 1)
x2 = width-1;
if(y1 < 0)
y1 = 0;
if(y2 > height - 1)
y2 = height -1;

for(i=(int)y1;i<= (int) y2; i++)
for(ii = (int) x1; ii<= (int) x2; ii++)
{
offset = (i * width + ii) * 4;
rgba[ offset ] = ((int) col[0] * col[3] + rgba[offset] * (255 -
col[3]))/255;
rgba[ offset + 1] = (((int) col[1]) * col[3] + rgba[offset+1] * (255 -
col[3])) / 255;
rgba[ offset + 2] = (((int) col[2]) * col[3] + rgba[offset+2] * (255 -
col[3])) / 255;
}

return 0;
}

Fortunately it is not a bottleneck function, but it could easily be. The
problem for the compiler is that col - the rectangle colour - could easily
be an alias for the draw space. So it has got to either take risks or read
the colour from memory on each pixel.
So add a "memsame" at the front of the function, and the compiler can
optimise the code.

 

[Serve Laurijssen]

Fortunately it is not a bottleneck function, but it could easily be. The
problem for the compiler is that col - the rectangle colour - could easily
be an alias for the draw space. So it has got to either take risks or read
the colour from memory on each pixel.
So add a "memsame" at the front of the function, and the compiler can
optimise the code.

how exactly do you think the compiler can optimize things better by adding a
function call to your code?
restrict comes closer. If the function turns out to be a bottleneck you can
make another function with restricted pointers

 

[Malcolm McLean]

how exactly do you think the compiler can optimize things better by adding
a function call to your code?
restrict comes closer. If the function turns out to be a bottleneck you
can make another function with restricted pointers

After a call to memsame() fails, the pointers have an implicit restrict.
So effectively what we are doing is binding the restrict at run time rather
than at ccompile time. It makes it more difficult for the compiler to
optimise, but the benefit is that you then don't have restrict poisoning
clogging up you whole call tree.

A naive compiler cannot use the information to optimise, but the function is
so cheap that it can be inlined with very low cost.

 

[SM Ryan]

(e-mail address removed)-cnrc.gc.ca (Walter Roberson) wrote:

# I seem to be a bit fuzzy as to how one would write code that would
# detect that it was running on *your* machine, rather than

The genitive is not the same as the possessive. Learn to speaking
english good. If you are using a Macintosh OS 10.4, then you are
using my machine.

 

[Serve Laurijssen]

After a call to memsame() fails, the pointers have an implicit restrict.
So effectively what we are doing is binding the restrict at run time
rather than at ccompile time.

Can you give an example on how you envision that it should work in real
code?
Either I'm missing something here or it just isnt possible what you want.

A compiler cant optimize at runtime, or well C compilers cant
The only thing I can see how the function could work is like

void foo(char *p1, char *p2)
{
if (memsame(p1,p2))
memmove();
else
memcpy();
}

but then you provide the optimization which can be handled more gracefully
by

void foo(char *p1, char *p2) { memmove(); }
void kungfoo(char * restrict p1, char * restrict p2) { memcpy(); }

And the compiler also knows it can do the usual aliasing optimizations on
the restrict version.
I really dont see a use for such a function.

 

[Malcolm McLean]

Can you give an example on how you envision that it should work in real
code?
Either I'm missing something here or it just isnt possible what you want.

A compiler cant optimize at runtime, or well C compilers cant
The only thing I can see how the function could work is like

void foo(char *p1, char *p2)
{
if (memsame(p1,p2))
memmove();
else
memcpy();
}

That is exactly how it is. A modern memcpy() is probably written just like
that to allow aliases and efficinet copying of non-aliases. It can't be done
portably in A|NSI C, because of the pointers to different objects not
comparing rule.

but then you provide the optimization which can be handled more gracefully
by

void foo(char *p1, char *p2) { memmove(); }
void kungfoo(char * restrict p1, char * restrict p2) { memcpy(); }

And the compiler also knows it can do the usual aliasing optimizations on
the restrict version.
I really dont see a use for such a function.

The problem is we've got this.

high_level_function(MYTYPE *ptr1, MYTYPE *ptr2)
{
kungfoo(ptr1, ptr2);
}

sorry, says the compiler. Make that high_level_function(restrict MYTYPE
*ptr1, restrict MYTYPE *ptr2).

Then every caller of high_level_function must ensure that parameters are
restricted. However that can be hard to arrange. So the whole program grinds
up in a mass of difficulties.

This way, we go

high_level_function(MYTYPE *ptr1, MYTYPE *ptr2)
{
if(memsame(ptr1, sizeof *ptr1, ptr2, sizeof ptr2))
foo()
else
kungfoo();
}

So we are handling the problem at runtime rather than compile time, which
isn't in itself ideal, but it buys us an escape from restrict poisoning.

 

[Christopher Layne]

(e-mail address removed)-cnrc.gc.ca (Walter Roberson) wrote:

# I seem to be a bit fuzzy as to how one would write code that would
# detect that it was running on *your* machine, rather than

The genitive is not the same as the possessive. Learn to speaking
english good. If you are using a Macintosh OS 10.4, then you are
using my machine.

Really - and our current use and allocation of dynamic memory is exactly the
same?

 

[Christopher Layne]

That is exactly how it is. A modern memcpy() is probably written just like
that to allow aliases and efficinet copying of non-aliases. It can't be done
portably in A|NSI C, because of the pointers to different objects not
comparing rule.

google: opensolaris, memcpy.s