>> And I'm not sure how you would do a whole bunch of simple things 
>> *without* such objects.
> 
>   Exactly like hundreds of programming languages do.

OK, well how would you build (say) a linked list structure if the new 
node goes out of scope as soon as you get to the end of the function 
that creates it and adds it to the list?

>> I have no idea why after all these years people still think reference 
>> counting is a good idea. It's so trivial to find an example where it 
>> utterly fails...
> 
>   Care to give this trivial example?

OK, how about a double-linked list?

Every node (except the end ones) always has 2 other nodes pointing to 
it. Hence the reference count will never reach zero. QED.

Post a reply to this message

Orchid XP v3 <voi### [at] devnull> wrote:
> OK, well how would you build (say) a linked list structure if the new 
> node goes out of scope as soon as you get to the end of the function 
> that creates it and adds it to the list?

  It goes out of scope, but it has two references pointing to it
(one in the function and another in the list data structure). When
it goes out of scope in the function that simply decreases the
reference count by one.

> OK, how about a double-linked list?

> Every node (except the end ones) always has 2 other nodes pointing to 
> it. Hence the reference count will never reach zero. QED.

  The nodes at the ends of the list have only one.

-- 
                                                          - Warp

Post a reply to this message

Daniel Hulme <pho### [at] isticorg> wrote:
> I have no idea why after all these years people still think quicksort is
> a good idea. It's so trivial to find an example where it takes O(n^2)
> time.

  It's certainly not very trivial to find such an example of the choice
of pivot in the paritioning is smart. Simply making a median-of-3 pivot
choice makes finding such an example non-trivial. Moreover, if the
middle item of the median choice is taken with some randomization to it,
good luck finding a patological example.

  Moreover, quicksort is handy because it can easily be enhanced to
sort small partitions with insertion sort, making it noticeably faster.
(Heapsort, for instance, cannot be enhanced like this. Mergesort can be,
but the problem with mergesort is its additional memory requirements,
at least when sorting arrays.)

  Oh, but of course there's the array where every value is the same.
It's rather trivial to stop partitioning when no swaps were made.

  Sure, it's still possible for a pathological case to happen, but
finding one is not trivial.

-- 
                                                          - Warp

Post a reply to this message

> Daniel Hulme <pho### [at] isticorg> wrote:
> > I have no idea why after all these years people still think
> > quicksort is a good idea. It's so trivial to find an example where
> > it takes O(n^2) time.
> 
>   It's certainly not very trivial to find such an example of the
> choice of pivot in the paritioning is smart.

Thank you for illustrating my point :->

-- 
"Oh, Eeyore, you are wet!" said Piglet, feeling him.
Eeyore shook himself,  and asked somebody to explain to Piglet what hap-
pened when you had been inside a river for a long time.
    A. A. Milne, 'The House at Pooh Corner'    http://surreal.istic.org/

Post a reply to this message

Daniel Hulme <pho### [at] isticorg> wrote:
> > Daniel Hulme <pho### [at] isticorg> wrote:
> > > I have no idea why after all these years people still think
> > > quicksort is a good idea. It's so trivial to find an example where
> > > it takes O(n^2) time.
> > 
> >   It's certainly not very trivial to find such an example of the
> > choice of pivot in the paritioning is smart.

> Thank you for illustrating my point :->

  Your point? You said it's trivial to find such an example, and I said
it isn't. How does that illustrate your point? Unless you were being
sarcastic or something.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>>Every node (except the end ones) always has 2 other nodes pointing to 
>>it. Hence the reference count will never reach zero. QED.

>   The nodes at the ends of the list have only one.

Not necessarily. They're pointed to by the object that represents the 
list as a whole. What pointer would you drop to make the list 
garbage-collect with a reference-count GC?

If you have a "file" that points to its buffer, and its buffer points to 
its file, you have a loop. If you have a declaration object that points 
to the definition object and the definition object points to the 
declaration object, you have a loop. If the window instance points to 
the screen instance and the screen instance points to the window 
instance, you have a loop. If the treenode points to its children and 
the children point back up to the parent, you have a loop.

Plus, reference counting has very bad performance as well as being 
non-real-time and uninterruptable.

None of which has much to do with POV-Ray as such. ;-)

-- 
   Darren New / San Diego, CA, USA (PST)
     Just because you find out you are
     telepathic, don't let it go to your head.

Post a reply to this message

>>>> I have no idea why after all these years people still think
>>>> quicksort is a good idea. It's so trivial to find an example where
>>>> it takes O(n^2) time.
>>>   It's certainly not very trivial to find such an example of the
>>> choice of pivot in the paritioning is smart.
> 
>> Thank you for illustrating my point :->
> 
>   Your point? You said it's trivial to find such an example, and I said
> it isn't. How does that illustrate your point? Unless you were being
> sarcastic or something.

I think he's hinting that finding the right pivot is the "hard" part of 
the algorithm, and if you get that wrong you get poor performance...

Post a reply to this message

Orchid XP v3 <voi### [at] devnull> wrote:
> I think he's hinting that finding the right pivot is the "hard" part of 
> the algorithm, and if you get that wrong you get poor performance...

  But that doesn't make quicksort a bad sorting algorithm.

-- 
                                                          - Warp

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> Not necessarily. They're pointed to by the object that represents the 
> list as a whole. What pointer would you drop to make the list 
> garbage-collect with a reference-count GC?

  How do languages where there no concept of "new" (as in Java or C++)
nor a Java-style GC of dynamically allocated objects do it?

> Plus, reference counting has very bad performance as well as being 
> non-real-time and uninterruptable.

  Very bad performance? I think that incrementing/decrementing a counter
each time an object is copied doesn't increase too much of its slowness.
(Naturally in situations where you have to locally copy things a lot
you would not use dynamically allocated copies anyways, assuming the
language supports local instances.)

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:

> Darren New <dne### [at] sanrrcom> wrote:
> 
>>Not necessarily. They're pointed to by the object that represents the 
>>list as a whole. What pointer would you drop to make the list 
>>garbage-collect with a reference-count GC?
> 
> 
>   How do languages where there no concept of "new" (as in Java or C++)
> nor a Java-style GC of dynamically allocated objects do it?

They don't dynamically allocate and deallocate memory, I guess. I'm not 
sure what your questions means. What I'm saying is that having circular 
links between objects is not at all uncommon in languages that allow 
such. It's the natural way to represent many semi-independent entities 
(like screens/windows, frames/scrollbars, RPG objects/rooms, tree nodes, 
etc.).

Obviously, if you don't have dynamically-allocated objects, then you 
don't have to worry about circular references with reference-counting 
garbage collection. If you have dynamically-allocated objects *and* no 
GC, then obviously it's up to the programmer to free things without 
assistance, and programmed reference counting won't fix that.

>>Plus, reference counting has very bad performance as well as being 
>>non-real-time and uninterruptable.
> 
> 
>   Very bad performance? I think that incrementing/decrementing a counter
> each time an object is copied doesn't increase too much of its slowness.

Not true. You have to also account for the object's reference count 
overflowing, for example. Plus, you actually have to *free* the objects 
when the counter goes to zero. Generational GC doesn't have to do 
anything with objects that have been freed (which admittedly makes 
finalizers messy, but they are messy to handle "correctly" in any 
language and model). You can allocate 100,000 individual objects and 
free them all with one instruction. There's a reason why nobody uses 
reference-counted garbage collection for real any more.

-- 
   Darren New / San Diego, CA, USA (PST)
     Just because you find out you are
     telepathic, don't let it go to your head.

Post a reply to this message