CGAL users discussion list

[Marc Glisse <>]

On Fri, 2 Mar 2012, Stefan Schirra wrote:

> On 02.03.2012 16:08, Marc Glisse wrote:
> > On Fri, 2 Mar 2012, Zohar wrote:
> >
> > > 1. Why is the Simple_Cartesian better than the Cartesian?
> > >
> > > I found in the doc of simple_cart:
> > >
> > > "In contrast to Cartesian, no reference counting is used internally. This
> > > eases debugging, but may slow down algorithms that copy objects
> > > intensively."
> >
> > It is not better in general. When the number type is double, the heavy 
> > reference
> > counting machinery has only drawbacks (copying a pair of double takes no 
> > time):
> > dynamic allocation, thread-unsafe. When the number type is something heavy 
> > (say
> > mpq_class or some other bignum that is not already reference-counted) and 
> > you do
> > a lot a copying objects around, it can be a life-saver.
>
> Sorry Marc, I do not fully agree.

Well, I agree that we disagree ;-)

> Thread-safety is certainly an issue. However, even copying pairs of doubles 
> takes some time.

When the compiler can't detect it is unnecessary (which it often can with 
double, but not with heavy types).

> It is not clear whether it takes more time than copying a 
> pointer and incrementing an int.

Hmm...

Let me cheat a little bit: it would (will?) be even more true with points 
stored as SSE/AVX vectors.

> Even if it would, your application must copy a lot, because of the 
> indirection in the access operations (cache effects are an issue as 
> well).

Yes, indirections make reference-counting slower. Ok, a pointer takes less 
space than a pair of double, so if you manipulate many points directly 
(not through a reference) without ever looking at their coordinates, 
Simple_cartesian can take a tiny bit more cache. On the other hand, it 
takes a lot less memory and is thus still likely to be more cache 
efficient.

> So it depends. For more, probably somewhat outdated, 
> information on this issue, see "S. Schirra; A Case Study on the Cost of 
> Geometric Computing. In Algorithm Engineering and Experimentation (ALENEX99), 
> pages 156-176, 1999. Springer, Berlin. Note: LNCS 1619.

Cool, your paper agrees that for double, Simple_cartesian is faster than 
Cartesian (which is all I claimed in my email).

> For "heavy number types", you can usually use Simple_cartesian, because 
> mpq_class and other bignum integers already use reference counting 
> themselves! So you don't copy bignums anyway.

I precisely chose mpq_class as an example because it is *NOT* 
reference-counted. You are confusing it with Gmpq (which wastes a lot of 
time in memory allocations, but that's a discussion for another day).

--
Marc Glisse