[GiNaC-devel] GiNaC is not a C compiler [Was: Optimized C-style output]

[Sheplyakov Alexei]

Hello!

On Wed, Mar 21, 2007 at 08:55:07PM +0100, Stefan Weinzierl wrote:

> To avoid other misunderstandings, I did not propose to replace standard
> print_csrc output by something else. This should remain as it is.

Fine. Yet another printing format would not hurt, I guess...

> But I would like to see that GiNaC offers the opportunity that C code is
> generated in an additional  different way with temporary variables.

...however it should be properly documented. "Produce optimized C code"
sounds like "do everything very good", Simplify[], etc. The actual effect
is mostly unpredictable, because there is no definition of simplicity.
So, *please*, be accurate. E.g.

"const ex find_common_subex(const ex& e, exmap& repls)

Attempts to recursively find common subexpressions of e (in the sense of 
.is_equal()) and replace them with symbols. Replacement rules will be 
appended to repls. For instance,

ex e = log(sin(x+y)) + sin(x+y) + pow(sin(x+y), 2);
exmap repls;
e = find_common_subex(e, repls);
cout << e << endl;
// will print
// log(symbol10) + symbol10 + symbol10^2
for (exmap::const_iterator i = repls.begin(); i != repls.end(); ++i)
	cout << i->first << " = " << i->second << endl;
// will print 
// symbol10 = sin(x+y)

Doing this kind of transformation can take a long time. Note that
the matching is purely syntactic, so some kind of common subexpressions
are not detected, for example: 

ex e = x+y+log(x+y);
exmap repls;
e = find_common_subex(e, repls);
cout << e << endl;
// expression will be returned unchanged, the output will be
// x+y+log(x+y) 

This function can in some situations substantially improve C code
generated by print_csrc."

BTW there are somewhat similar functions in GiNaC -- to_polynomial(),
to_rational(). I think function for finding common subexpressions is
useful (not only for code generation).

> (I carefully try to avoid the word "optimized code" here,
> but that's what I mean.)

Don't tell this to compiler folks :)

> The decision which output format to use should be put into the hands of
> the user, he or she will know best what suits here needs.

To make the correct decision one should be properly informed.
Unfortunately the documentation you've supplied is not good enough
for this purpose.

> I will have a look at the excompiler.cpp file and see how it fits
> together.
> 
> There are also several good points which Alexei mentioned:
> 
> If expressions of type add and mul should be substituted or rather
> calculated on the fly is certainly worth a discussion.
> My experience would lead me towards substitution, but I admit that in
> different circumstances the conclusion could be the opposite.

Getting rid of temporaries often gives substantional performance boost,
so there is a special kind of C++ (template) libraries which are designed
exactly for this purpose -- expression template libraries (blitz++,
boost::ublas, tvmet, etc.). It is very difficult to algorithmically decide
which variant is better (making the decision might even take longer than
the calculation itself). Actually, this is what optimizing compilers do,
and that is why compilation takes a long time. BTW, sometimes turning
optimization off (as in -O0) makes the calculation faster.

> Maybe flags or a visitor object could fine-tune this behaviour on an
> individual basis.

E.g. instead of hard-coding MAX_SIZE make it the argument of the
function (with some default value). While we at it, the name is 
dangerous -- there are a lot of MAX_* macros in the kernel/glibc/whatever
headers, so let's type it in all smalls to be on the safe side.

> Collecting and running normal() on the coefficients is also something
> I do privately on expressions where I excpect improvements. As normal()
> involves a gcd computation I did not include it in the code generation
> routine.

Yes, gcd() is expansive. has() and other pattern matching functions are 
expansive too. There are not universal way...

Best regards,
 Alexei

-- 
All science is either physics or stamp collecting.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 827 bytes
Desc: Digital signature
Url : http://www.cebix.net/pipermail/ginac-devel/attachments/20070322/5c18decc/attachment.pgp