Bug #1587983 reported by Andrzej Walczak on 2016-06-01
This bug affects 2 people
Affects Status Importance Assigned to Milestone
Douglas Katzman

Bug Description

The SB-EXT:CANCEL-FINALIZATION function is implemented as a linear lookup using DELETE over **finalizer-store**. When a transfer of ownership is required this result in an O(n*c) complexity with n - the number of objects registered by SB-EXT:FINALIZE and c - the number of calls to CANCEL-FINALIZATION.

The purpose of the FINALIZE/CANCEL-FINALIZATION functionality is to manage the life-cycle of foreign objects and resources in a much easier, Lisp like fashion without RAII or WITH-FOO like patterns. On the other hand, the O(n*c) complexity makes it useless for larger projects or applications. The surprising behavior can be graded as a bug since it can cause a substantial degradation in service.

Here is a small benchmark to reproduce the bug.

(defpackage final-test (:use #:cl #:sb-ext))
(in-package #:final-test)

(defstruct dummy)

(declaim (fixnum *finalized-count*))
(defglobal *finalized-count* 0)

(defun garbage (&key (cancel t))
  (let ((garbage (loop repeat 100000 collect (make-weak-pointer (make-dummy)))))
    (map () (lambda (g)
               (finalize g (lambda () (incf *finalized-count*))))
    (when cancel
      (map () #'cancel-finalization garbage))
    (gc :full t)


This is in the current SBCL head (

uname -a
Linux <redacted> 3.13.0-71-generic #114-Ubuntu SMP Tue Dec 1 02:34:22 UTC 2015 x86_64 x86_64 x86_64 GNU/Linux

We have attached a patch for code/final.lisp that has been tested to be working with a recent SBCL on many of quicklisp packages using TRIVIAL-GARBAGE and on a huge internal Lisp project. The patch adds a hash-table lookup, reducing the complexity by O(n). With the patch the above benchmark completes within just few seconds.

Douglas Katzman (dougk) wrote :

I'd like to see whether there's a way to not store the finalized objects in both a list and hashtable. The hashtable should be enough, but no existing flavor of hashtable will work.
A weak-keyed table obviously loses the finalizers, and an EQ table keyed by explicit (make-weak-pointer key) would not work for a variety of reasons.
I don't think it should be terribly hard to concoct a new flavor of hashtable that supports EQ-comparison, deletion, and key weakness without losing the values. I'll think about how to do that

Hi Doug!

Can we have this patched in, first?
It can be fixed later with a new specialized implementation of the hashtable mentioned in #2.

Douglas Katzman (dougk) wrote :

I'd like to propose a changed finalizer API.

A new subtype of weak pointer shall have one additional slot for the finalizer function (or list of functions if there is more than one for the same finalized object).

MAKE-WEAK-POINTER returns the familiar weak-pointer, but MAKE-FINALIZER would return this new kind of weak-pointer with the additional slot.
To cancel finalization is completely trivial: set the functions in the finalizer object to NIL.
RUN-PENDING-FINALIZERS can delete the finalizer that has no functions in it when it encounters it (after GC breaks the weak-pointer) just as it would for a finalizer that has functions to run. There's no difference there. Aside from the new object type, there's another low-level change: GC must build a list of finalizer actions for Lisp to run in post-gc. That's easy; it already has explicit knowledge of the weak-pointers that it smashed on any GC cycle.

Is there a drawback to this approach? Importantly, will consumers of this API end up having to build their own hash-table of object to finalizer? If so, this is not a huge win, though I still like the idea of handing the user a cookie.

The current API has the advantage that it is using the default pointers without extra cost when applied to normal code flow.

The CANCEL part and the FINALIZATION are done only in special cases - i.e. when the standard memory management and object life-cycle fails to kick in - e.g. because of some error.

Without the FINALIZE we need to use lot's of unwind-protect and object juggling between threads.

I understand that replacing the hash-table with a new pointer structure is cleaner. My concerns here are just from optimization point of view. Please, convince me.

Another concern about the new API is the support in the old/deprecated API.
E.g. trivial-garbage uses said API and changes to it would need to propagate.

Douglas Katzman (dougk) wrote :
Changed in sbcl:
assignee: nobody → Douglas Katzman (dougk)
importance: Undecided → Medium
status: New → Fix Committed
Changed in sbcl:
status: Fix Committed → Fix Released
To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Other bug subscribers