Re: Slow GC after Scalar::Util::weaken (O)

Perl weak references are implemented as a singly-linked list. Destroying a weak reference is thus O(n) if you have n weak references to a particular variable. So destroying N weak references to the same variable is O(N**2).

Having 200k weak references to the same variable is not a normal use-case. I'm not surprised that it is slow.

- tye

Comment on Re: Slow GC after Scalar::Util::weaken (O)

Replies are listed 'Best First'.
Re^2: Slow GC after Scalar::Util::weaken (O) by ikegami (Patriarch) on Jun 03, 2010 at 18:30 UTC
According to Devel::Peek, it's an array rather than a linked list. That doesn't change the complexity, though. To delete weak ref #X: O(X) to locate + O(N-X) to delete = O(N) total Best, average and worse case to delete one weak ref of N is O(N). To delete all N weak refs: O(N) + O(N-1) + O(N-2) + ... + O(1) = O(N2) Best, average and worse case to delete all N weak refs is O(N2). A hash, on the other hand, would scale much better. Best, average and worse case to delete one weak ref of N is O(1). Best, average and worse case to delete all N weak refs is O(N). Update: Added analysis for hash.	[reply]

Replies are listed 'Best First'.

Re^2: Slow GC after Scalar::Util::weaken (O)
by ikegami (Patriarch) on Jun 03, 2010 at 18:30 UTC

According to Devel::Peek, it's an array rather than a linked list. That doesn't change the complexity, though.

To delete weak ref #X:
O(X) to locate + O(N-X) to delete
= O(N) total

Best, average and worse case to delete one weak ref of N is O(N).

To delete all N weak refs:
O(N) + O(N-1) + O(N-2) + ... + O(1)
= O(N**2)

Best, average and worse case to delete all N weak refs is O(N**2).

A hash, on the other hand, would scale much better.

Best, average and worse case to delete one weak ref of N is O(1).
Best, average and worse case to delete all N weak refs is O(N).

Update: Added analysis for hash.

[reply]