Compiler optimization of INTERN similar to what's in CCL

Bug #1814924 reported by Paul F. Dietz on 2019-02-06
6
This bug affects 1 person
Affects Status Importance Assigned to Milestone
SBCL
Undecided
Douglas Katzman

Bug Description

CCL has a compiler macro for INTERN that optimizes the common case of a constant package designator.

In CCL, this works as follows:

(1) Maintain a 1-1 mapping from simple strings (package names or nicknames) to package-ref objects.
(2) Each package-ref is a structure containing the unique (up to EQUAL) string that maps to it, and the package it refers to.
(3) The compiler macro expands to a LOAD-TIME-VALUE expression that builds this structure.
(4) There is also a MAKE-LOAD-FORM for the structure.
(5) When a package is defined or redefined, any mappings for relevant names are updated so the package field is still valid (it may be NIL if the package gets deleted.)

This makes these common calls to intern fast, and has a noticeable effect on the speed of applications, in particular ACL2.

Unfortunately, package local nicknames complicate this picture, since the package is no longer just a function of the package name, but also of the value of *PACKAGE*. PLNs are being added to CCL (thanks phoe!), so changes to recover the speed improvement were suggested (by me) at their github. The easiest might be this:

(6) Add a boolean field to the package-ref structure that is true iff this string is involved in PLNs somehow (that is, it is used as a PLN in some package that has been loaded into the system). If this field is true, default back to the current explicit lookup (that is, disable the optimization).

With this change, the common case of no PLNs becomes fast again.

Also: it may be desirable to have PLNs be prohibited for names or nicknames of standard packages.

Douglas Katzman (dougk) wrote :

Do you have a benchmark that presents some compelling evidence that we're slow because of the implicit FIND-PACKAGE (as part of intern) per se?

a most-recently-used cache on name -> package that is also sensitive to *package* would be lot simpler, and localized to find-package.

Michał Herda (phoe-krk) wrote :

> Also: it may be desirable to have PLNs be prohibited for names or nicknames of standard packages.

The current SBCL code signals a continuable error in that case.

Paul F. Dietz (paul-f-dietz) wrote :

I don't have a benchmark for SBCL, but CCL saw noticeable slowdown for ACL2. The cache in FIND-PACKAGE would still require a string comparison.

Users could get some speedup by using (load-time-value (find-package :foo)) instead of :foo as the package designator, but that changes the meaning of the program.

Paul F. Dietz (paul-f-dietz) wrote :

dougk: should I test how that does with multiple threads?

Douglas Katzman (dougk) wrote :

sure, why not. You will want the next change as well - https://sourceforge.net/p/sbcl/sbcl/ci/2a65fb2aa66acc0dfdb11ec4f8601d457d49d543/

I can see a small window of opportunity for a glitch involving the wrong result in concurrent threads if package-local-nicknames are involved. If you can expose such a glitch then I definitely need to fix it soonish, but I probably will want to start thinking about how to fix it now.

Douglas Katzman (dougk) on 2019-02-13
Changed in sbcl:
status: New → Fix Committed
assignee: nobody → Douglas Katzman (dougk)
To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Other bug subscribers