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

[Jean-Philippe Paradis]

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)]

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

[Jan Moringen (scymtym)]

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)]

Updated patch.

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