[GiNaC-list] Term ordering stability, tinfo keys and all that.

[Alexei Sheplyakov]

On Mon, Aug 11, 2008 at 04:50:54PM +0200, Jens Vollinga wrote:

> well, I don't quite agree but maybe I am misinterpreting the quotation 
> marks ;-). If you want to handle large expression, then use FORM.

No way. Its programming language is extremly brain dead. It has a lot
of stupid "features", i.e. it unconditionally expands every expression.
It lacks basic polynomial operations (gcd, collect, to name few). FORM
is impossible to extend. Last, but not least, FORM is a proprietary software.

> what a simple manipulation is depends on whom you ask.

Sure, hence the quotation marks. An example of a "simple" manipulation
is reading an input expression, or adding several expressions and collecting
similar terms. Apparently not every CAS is able to to this, see e.g.
http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=407109

> > The order of expressions (in particular, symbols) is not stable. This is
> > a price for a fast comparison of expressions. 

> Additional nitpicking: that is not quite true.

I don't agree. The purpose of custom GiNaC RTTI ("tinfo keys") is exactly fast
ordering of expressions. A long(er) explanation follows.

The purpose of hash function is to quickly guess if two expressions are NOT
the same in order to minimize the number of (expensive) element-to-element
comparison operations. Notice that two expressions of different type are always
different. Hence the need for an efficient ordering operation for _types_.
IOW, we need a fast RTTI. Standard C++ library provides RTTI, but in ancient
versions of GNU C++ library ordering operation (i.e. typeinfo::before() method)
was very slow, because it was implemented as a comparison of (mangled) type
names. Hence GiNaC invented its own (fast) RTTI with tinfo keys.

As a side note, RTTI implementation in the up to date versions of GNU libstdc++
is much better. It uses the technique similar to GiNaC's tinfo keys, although
it's a bit more complicated (since it needs to handle multiple inheritence
and other obscure stuff). As a matter of fact, using it instead of our custom
RTTI doesn't yeld any measurable overhead. So we can stick with standard C++
RTTI. This won't solve term ordering "issue", but writing new GiNaC classes
would be easier.

> I mentioned the reasons for non-stability in my last email.

The only missing part is why GiNaC needs those "tinfo keys" in first place...

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-list/attachments/20080811/2db7b2a4/attachment.sig