Steel Bank Common Lisp

Wanted: More efficient FIND-RESTART that doesn't COMPUTE-RESTARTS

Reported by Jean-Philippe Paradis on 2011-04-23
6
This bug affects 1 person
Affects Status Importance Assigned to Milestone
SBCL
Low
Unassigned

Bug Description

I noticed that FIND-RESTART, when given a non-nil symbol, uses this naive strategy:

(find identifier (compute-restarts condition) :key #'restart-name)

So, we're consing up a list of every restart in existence, and then traverse the list to find the appropriate one.

This looks like it could be a performance problem in recursive code that establishes lots of restarts and then uses FIND-RESTART, perhaps repeatedly. You might cons up a list of hundreds of restarts when the one you were looking for was just under your nose.

Nikodemus Siivola (nikodemus) wrote :

Expressing both FIND-RESTART and COMPUTE-RESTARTS in terms of MAP-RESTARTS would probably work.

Changed in sbcl:
importance: Undecided → Low
status: New → Triaged
tags: added: optimization
Jan Moringen (scymtym) wrote :

The attached patch adds MAP-RESTARTS and uses it in FIND-RESTART and COMPUTE-RESTARTS. It also fixes https://bugs.launchpad.net/sbcl/+bug/774410.

The archive includes the results of simple timing experiments which show the performance improvement predicted by Nikodemus for the (FIND-RESTART SYMBOL) case. However, the results also show that fixing https://bugs.launchpad.net/sbcl/+bug/774410 (at least when implemented like I did) incurs a performance penalty in the (FIND-RESTART RESTART-INSTANCE) case.

The patch contains questions for the person reviewing it. Of particular importance (I think) is the question if/how INVOKE-RESTART, when given a RESTART instance, should check whether that restart is still active. ECL, CLISP, CCL and SBCL master behave differently with respect to this question and CLHS for INVOKE-RESTART is not very helpful.

Jan Moringen (scymtym) on 2013-04-17
tags: added: review
Jan Moringen (scymtym) wrote :

Updated patch.

This updated patch implements Christophe's suggestion of maintaining associated conditions in a slot of the RESTART structure.

Changed in sbcl:
status: Triaged → 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