[Python-ideas] Multi-core reference count garbage collection

[Chris Angelico]

On Sat, Jul 21, 2018 at 6:44 AM, Jonathan Fine <jfine2358 at gmail.com> wrote:
> Hi Steve
>
> You wrote:
>> My understanding is that reference counting is both deterministic and
>> immediate. Shifting the reference counting into another thread so that
>> it becomes non-deterministic and potentially delayed doesn't sound like
>> an advantage to my naive understanding.
>
> The choice is not as simple as that. Here's an example.
>
> Suppose you and your friend want to sort a deck of cards. Here's an algorithm.
>
> * Divide the deck into two
> * Each person sorts their half deck
> * One of you does a merge of the two half decks
>
> This algorithm is non-deterministic. But for a large deck it's quicker
> than any deterministic algorithm.

Divide the deck into "first half" and "second half". Then sort the
half decks using a stable algorithm. Finally, merge the decks,
favouring cards from the first half. Voila! You now have a fully
deterministic and stable sort.

ChrisA