[CLN-list] Smart pointers, C++, and all that

[Alexei Sheplyakov]

Dear Bruno,

On Sun, Sep 28, 2008 at 11:28:37AM +0200, Bruno Haible wrote:
 
> The reasons why CLN uses smart pointers for everything are:
> 
> 1) Its main purpose is to allow the formulation of mathematical algorithms
>    directly in C++. As in a scripting language. Without requiring the
>    programmer to think in terms of memory allocation.

First of all, smart pointers or not, but thinking about complexity of 
operations (in particular, memory allocation) is unavoidable. Smart pointers
make some operations cheap, but other operations suddenly become expensive.
Case in point: people expect operator+= to be efficient, but in fact it's not
(because it does a copy), so they get very confused. See e.g.

http://www.ginac.de/pipermail/ginac-list/2008-August/001396.html

Secondly, those who don't want to think about memory allocation should
not use a low level programming language (such as C++).

> The programming model
>    of a scientist in this case is to manipulate opaque values that are
>    elements of rings. CLN brings the philosophy of computer algebra
>    languages into C++.

Unfortunately the reality is a bit different from this model. One need
to learn that some common operations are (unexpectedly) expensive for no
obvious reason. (Of course, the reason becomes clear as one learns about
memory allocation, smart pointers, and all that).

> 2) When you do computations with polynomials, you need a maximum of sharing
>    of the polynomial representations.

Not really. Sharing makes data immutable. Thus any simple modification (such
as multiplication by a constant, changing a single coefficient, taking a
derivative) ends up doing a copy. Making a copy (even a shallow one) requires
maintaining reference counts which is prohibitively expensive w.r.t. the cost
of the modification itself. As a result a correctly written user code needs
tons of RAM and/or works way too slow for no "obvious" reason.

For example, the same univariate GCD code works about 3 -- 10 times faster
(and uses less memory) if I use std::vector<cl_I> instead of cl_UP.

That's why I think "smart pointers everywhere" approach is wrong.

> In systems where deep copying of polynomials is the default, you cannot do
> computations as large as those possible in Maple - because you run out of
> memory earlier.

I'm afraid your theory is a bit observationally challenged. Those Ma... and 
Ma......... things often run out of memory while reading the input 
expressions (which can be process with either GiNaC or FORM), let alone doing
something useful.
 
> In this light, set_coeff and finalize must be implemented as copy-on-write
> operations: create a deep copy implicitly when the reference count is > 1.
> No explicit method for deep copying is then needed at all.

I don't think copy-on-write (univariate) polynomials is a good idea.

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/cln-list/attachments/20080930/c040432b/attachment.sig