www.digitalmars.com         C & C++   DMDScript  

D - 'argument constrained' functions

reply Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:
The compiler could do some more optimizations if it had some way to know
that certain functions would always return the same value given the same
arguments.

For example, strchr() (or the D equivalent) returns a certain value that
is always the same based on its arguments.  However, random() does not.

Thus, the compiler can't optimize the following code (without hacking in
knowledge of the library):

if(strchr(buf,'\n') != NULL)
    *strchr(buf,'\n') = '\0';

However, if we could give the compiler the right hints, then it could
make the optimization:

char *temp = strchr(buf,'\n');
if(temp != NULL)
    *temp = '\0';

--
The Villagers are Online! villagersonline.com

.[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ]
.[ (a version.of(English).(precise.more)) is(possible) ]
?[ you want.to(help(develop(it))) ]
Nov 20 2001
parent reply Russell Borogove <kaleja estarcion.com> writes:
Russ Lewis wrote:
 
 The compiler could do some more optimizations if it had some way to know
 that certain functions would always return the same value given the same
 arguments.
 
 For example, strchr() (or the D equivalent) returns a certain value that
 is always the same based on its arguments.  However, random() does not.
 
 Thus, the compiler can't optimize the following code (without hacking in
 knowledge of the library):
 
 if(strchr(buf,'\n') != NULL)
     *strchr(buf,'\n') = '\0';
 
 However, if we could give the compiler the right hints, then it could
 make the optimization:
 
 char *temp = strchr(buf,'\n');
 if(temp != NULL)
     *temp = '\0';

strchr() might not be the best example, since the buffer might be non-const: if (strchr( buf, '\n' ) != NULL) { buf[5] = '\0'; // is buf "the same" as it was before? *strchr( buf, '\n' ) = '\0'; } You'd want any intervening statement that had a possibility of modifying one of the relevant arguments to prevent the optimization. That would basically be _any_ function call or write through _any_ pointer, as well as more obvious modifications, I think. But what you suggest does apply to, say, trig functions and whatnot. There's a Perl module called "memoize" that caches function return values at runtime to let you turn expensive yet consistent operations into associative-array lookups. It turns out that expensive yet consistent operations are really pretty rare... :) -RB
Nov 20 2001
next sibling parent Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:
 strchr() might not be the best example, since the buffer might be
 non-const:

  if (strchr( buf, '\n' ) != NULL)
  {
     buf[5] = '\0';
     // is buf "the same" as it was before?
     *strchr( buf, '\n' ) = '\0';
  }

 You'd want any intervening statement that had a possibility of
 modifying one of the relevant arguments to prevent the optimization.
 That would basically be _any_ function call or write through _any_
 pointer, as well as more obvious modifications, I think.

Right, I was assuming that modifying the array would be considered, by the compiler, as modifying the argument. Sorry I wasn't clear. And yes, you're right...changing the value of nearly any variable accessed through the pointer (unless the compiler could trace back and know a lot about that pointer) would have to mean invalidating the array.
 But what you suggest does apply to, say, trig functions and
 whatnot.

True.
 There's a Perl module called "memoize" that caches function return
 values at runtime to let you turn expensive yet consistent operations
 into associative-array lookups. It turns out that expensive yet
 consistent operations are really pretty rare... :)

Yeah, I suppose so. Yet every little bit helps - if it doesn't make the language too complex :( -- The Villagers are Online! villagersonline.com .[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ] .[ (a version.of(English).(precise.more)) is(possible) ] ?[ you want.to(help(develop(it))) ]
Nov 21 2001
prev sibling parent reply "Walter" <walter digitalmars.com> writes:
"Russell Borogove" <kaleja estarcion.com> wrote in message
news:3BFAF031.84865AEB estarcion.com...
 But what you suggest does apply to, say, trig functions and
 whatnot.

This is already done in better C compilers (DMC <g>) with trig and string functions that are built-in to the compiler, such as strlen() and sin().
Nov 24 2001
parent reply Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:
Walter wrote:

 "Russell Borogove" <kaleja estarcion.com> wrote in message
 news:3BFAF031.84865AEB estarcion.com...
 But what you suggest does apply to, say, trig functions and
 whatnot.

This is already done in better C compilers (DMC <g>) with trig and string functions that are built-in to the compiler, such as strlen() and sin().

Right, I figured that. gcc also has a lot of knowledge of printf and will throw warnings if you pass the wrong types. But it seems to me that such library-specific optimizations are ugly and (hopefully) unnecesary, if we could design the language such that the function definition contained the necessary information. Then anybody's library can be optimized, not just stdlib. -- The Villagers are Online! villagersonline.com .[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ] .[ (a version.of(English).(precise.more)) is(possible) ] ?[ you want.to(help(develop(it))) ]
Nov 26 2001
parent a <a b.c> writes:
Russ Lewis wrote:
 
 Walter wrote:
 
 "Russell Borogove" <kaleja estarcion.com> wrote in message
 news:3BFAF031.84865AEB estarcion.com...
 But what you suggest does apply to, say, trig functions and
 whatnot.

This is already done in better C compilers (DMC <g>) with trig and string functions that are built-in to the compiler, such as strlen() and sin().

Right, I figured that. gcc also has a lot of knowledge of printf and will throw warnings if you pass the wrong types. But it seems to me that such library-specific optimizations are ugly and (hopefully) unnecesary, if we could design the language such that the function definition contained the necessary information. Then anybody's library can be optimized, not just stdlib.

I second this. If you have to build function specific opitmization or handler for certain functions into the compiler then the somebody has screwed up. I think that is one of the biggest reasons I dispise C's *printf functions. At least with printf it was safety checking. You would be locking out external libraies from a useful optimization technique. Lint like tools can be made to test safety. To work around this in libraries would require coaching libraries users (possibly exposing property that should be inside the "black box") or using a preprocessor/precompiler. How able a compiler hint or function property of some kind? It wouldn't need to be implemented right out of the gate. Dan
Nov 27 2001