On Mon, 6 Jul 2009, Gerhard Fiedler wrote:

> sergio masci wrote:
> > 

> Yes. You can send this to your marketing department -- I never can
> remember which way it is :)

Ok I'll be sure to pass this on to the left side of my desk :-)

> > 
> > Yes this point seems to elude most programmers.
> > 
> > [loop optimization ...]
> > 
> > Now if we introduce a function the above optimisations break
> > e.g.
> > 	for (j=0; j<10; j++)
> > 	{	arr[j] = sin(j);
> > 	}
> > 
> > This is because the compiler doesn't really know anything about the
> > function. It can analyse the function and depending on how complex
> > the function is it might be able to optimise the loop a little but in
> > the case of a well optimised sine function optimisation becomes very
> > limited.
> > 
> > If however the compiler "knows" about the sin function (because the 
> > compiler writer has given it special attributes that the compiler can 
> > use) it could optimise this loop by building a lookup table at compile 
> > time as:
> > static	xxx
> > 	own_sin_tbl[] = {sin(0), sin(1), ...
> > 
> > 	for (j=0; j<10; j++)
> > 	{	arr[j] = own_sin_tbl[j];
> > 	}
> 
> Here you have a point, but I'd say that this code (as C code for a small
> micro) is badly written. Really badly. arr[j] should be initialized with
> compile-time constants, not at run-time. You can say that this is the
> compiler's job, but the problem is, again, that there are so many
> different ways to calculate sin(). The compiler doesn't know which one I
> think is adequate for my purposes; do I need 2 digits precision, or 6,
> or 12? The code size and/or execution time of the function varies
> substantially with the required precision.

You are explicitly seeing sin() where I have tried highlighting the brick 
wall between the compiler and the knowledge excapsulated in a library 
function.

I chose sin because to a great many people it is a black box which they 
can relate to rather than some complex function that I'd invent as an 
example.

Yes the compiler writer could allow the programmer to attach a ton of 
attributes to a library function to help it understand the function better 
but that's not the point. The point is to make it simpler for a programmer 
to write good code that is easy to maintain - to allow the compiler to 
extract the necessary information from the function itself without the 
programmer needing to add extra attributes - which like comments might 
actually be at odds with the code and be wrong (yet something else to 
debug).

Yes the compiler could try to evaluate the 'blackbox' function at compile 
time in order to generate a compile time constant but this is not the 
point. It is a way of getting the same result as would be obtained as a 
side effect "of the point".

Let's try something a little bit more interesting:

void delete_item(int pos, int *len, int arr[])
{
	int	j;

	for (j=pos; j<*len; j++)
	{
		arr[j] = arr[j+1];
	}

	*len--;
}

void insert_item(int pos, int val, int *len, int arr[])
{
	int	j;

	for (j=*len-1; j>pos; j--)
	{
		arr[j] = arr[j-1];
	}

	*len++;

	arr[pos] = val;
}

main()
{
...
	delete_item(pos, &len, arr);
	insert_item(pos, val, &len, arr);
...
}


Now how would you give the compiler enough information in the attributes 
of the functions to be able to automatically optimise the above into the 
equivalent of:

	replace_item(pos, &len, arr);

I can see how you would do this easily if the compiler actually new the 
intent of delete_item and insert_item.

A far more concrete example would be that of having multitasking built 
into the language rather than as a bolt-on library. XCSB knows about 
multitasking and generates optimised code around it. You don't need to 
generate several stacks and functions that need to be re-enterent just in 
case they are being used in several tasks. Don't you think that's a 
benefit? I mean the fact that you can get tight efficient multitasking 
code written in a HLL to work on something as small as a 16F628?

> 
> 
> > The important point here is not to focus on the sine function itself
> > but on the fact that a function is involved. Using functions (and
> > this is primarilly what libraries use) hinders the compilers ability
> > to analyse the intent of the programmer. Whereas having the compiler
> > understand more of the source allows it to better analyse the intent.
> 
> Yes, I get that. But the compiler can't know a few things around my
> requirements, and I may be better able to choose which function
> implementation is more adequate.
> 
> Regarding the intent, a good definition of a library function (think the
> C++ standard library) explains quite clearly the intent. It doesn't nail
> down the implementation details of the functions, though. C doesn't do
> it, but there's nothing in the above that would prevent a compiler to
> actually call at compile time the library function to calculate that
> array. It doesn't have to be built in for that; it just has to know
> which library to use (at compile time). 
> 
> 
> > Going a bit further, if I wrote a simple search function such as
> > 
> > struct MY_STRUCT
> > 	{	int	id;
> > 		int	mask1, mask2;
> > 	};
> > 
> > int search(int x, int cnt, struct MY_STRUCT arr[])
> > {
> > 	int	j;
> > 
> > 	for (j=0; j<cnt; j++)
> > 	{
> > 		if (x == arr[j].id)
> > 		{	return j;
> > 		}
> > 	}
> > 
> > 	return -1;
> > }
> > 
> > then I could use this in C as:
> > 
> > static const struct MY_STRUCT predef_arr[] =
> > 	{
> > 		{ 5, 0xfe, 0x11},
> > 		{ 7, 0xfc, 0x22},
> > 		{11, 0xe1, 0x33},
> > 	};
> > 
> > static const int predef_cnt = 3;
> > 
> > main()
> > {
> > ...
> > 
> > 	mask1 = 0xff;
> > 	mask2 = 0x00;
> > 
> > 	res = search(7, predef_cnt, predef_arr);
> > 
> > 	if (res != -1)
> > 	{
> > 		mask1 = predef_arr[res].mask1;
> > 		mask2 = predef_arr[res].mask2;
> > 	}
> > ...
> > }
> > 
> > now if search were actually part of the language as in:
> > 
> > 	res = SEARCH ARRAY=predef_arr LENGTH=predef_cnt WITH KEY=id FOR 7;
> > 
> > then the compiler would be in the position to simply generate the 
> > equivalent of:
> > 
> > main()
> > {
> > ...
> > 
> > 	mask1 = 0xfc;
> > 	mask2 = 0x22;
> > ...
> > }
> 
> This doesn't require that SEARCH is part of the compiler; it merely
> requires that the semantics of SEARCH are well-defined. It could just as
> well be a library function with semantics that are specified so that the
> compiler can know what to do. 
> 
> But again, like above with the sin() example, code like this should
> actually be compile-time constants, not run-time calculations. The
> program writer should clearly distinguish between values that are known
> before the program runs and values that are dependent on run-time
> events. The examples you showed are only relevant if the programmer
> doesn't do this.

This was a trivial example but consider a much more real case where the 
above code would actually exist in a library as part of the 'init' 
sequence of a module. Ideally the programmer would be insulated from 
having to build large complex static tables within his/her main line. This 
should all be taken care of by the library writer / maintainer.

You must have come across some horrible libraries yourself where several 
things need to be declared as "#defines" before the corresponding header 
of the library is included into your main line for the sake of efficiency.

> 
> 
> > Ok so from all this you might get the impression that what I'm talking
> > about is purely optimisation related, it's not. It's about making it
> > easier for the programmer to write correct code and the compiler to
> > understand the code and so catch mistakes at compile time - good
> > optimisation is actually a side effect.
> 
> I get this, but I think a library with clearly defined semantics goes a
> long ways towards that. And a programmer who clearly distinguishes
> between stuff that's known at compile time and stuff that can only be
> known when the program runs also helps.
> 
> 
> > Having built-in types such as LIST, STACK, STRING greatly enhance the 
> > compilers ability to track correct usage and reduce source code size 
> > making it easier for the programmer to see the wood for the trees.
> 
> Right, but again... The C++ standard library, for example, has quite
> good implementations of standard containers, yet I find myself creating
> my own containers or using different containers from other libraries,
> for specific requirements that the standard containers don't satisfy. A
> list or stack is a concept, with many different possible implementations
> that satisfy different requirements. And I suspect that the smaller the
> micro it runs on, the more limited the resources are, the more important
> are the differences between different implementations. 
> 

The standard template library is still a brick wall to the compiler. It 
can do a lot of optimisations in situ which give the illusion that the 
compiler understands what the intent is but the reallity is that the 
compiler is just blindly reducing intermediate code as much as it can 
(kind of like macros on steroids) and then using what's left to generate 
the executable. It's not looking for special patterns of use and 
optimising at a high level which is what YOU are doing when you create 
your special optimised containers.

Another way to look at this, say you write:

	unsigned char x, j;

	x = j * 2;

The compiler can actually replace "* 2" by "<< 1" because it looks for the 
special combination "* 2" operating on an integer. Also the compiler could 
optimise "x = j << 1" for the PIC into

	rlf j,w
	movwf x

because it sees the combination of '=' and '<< 1'

If you replaced the operators '=' and '*' with 'assign' and 'mult' such 
that the above was re-written as

	assign(&x, mult(j, 2));

how would you give the compiler enough information on the above 
functions to be able to do the same level of optimisation as before?

And forgetting about optimisation completely, what about promoting 
integers to floats?

e.g.
	float	x;
	int	y, z;

	x = y / z;

here a decent language / compiler could see that the result result needs 
to be a float and promot y and z to floats and perform a floating point 
division. How would you do that with library functions (even allowing for 
overloading)?

How would the compiler do the promotion here?

	assign(&x, div(y, z));


Friendly Regards
Sergio Masci
-- 
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist