classification
Title: Frozen modules are looked up using a linear search.
Type: performance Stage: needs patch
Components: Interpreter Core Versions: Python 3.11
process
Status: open Resolution:
Dependencies: Superseder:
Assigned To: Nosy List: barry, brett.cannon, corona10, eric.snow, lemburg, rhettinger, steve.dower
Priority: normal Keywords:

Created on 2021-09-15 17:42 by eric.snow, last changed 2021-09-24 10:59 by corona10.

Messages (9)
msg401863 - (view) Author: Eric Snow (eric.snow) * (Python committer) Date: 2021-09-15 17:42
When looking up a frozen modules, we loop over the array of frozen modules until we find a match (or don't).  See find_frozen() in Python/import.c.  The frozen importer sits right after the builtin importer and right before the file-based importer.  This means the import system does that frozen module lookup every time import happens (where it isn't a builtin module), even if it's a source module.
msg401864 - (view) Author: Eric Snow (eric.snow) * (Python committer) Date: 2021-09-15 17:44
Realistically, I doubt this will ever be a problem.  The list of frozen modules is fairly small and the loop in the C code is a lightweight.  So it isn't that big of a deal relative to the other costs involved in import.  Even if the number of frozen modules grows dramatically, it's unlikely to be a problem.

So we should probably close this.  Mostly I opened this so folks with the same observations could find it.  I'll close the issue in a few days in case I missed something.
msg402198 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2021-09-20 06:55
If you close this out, consider adding a prominent comment so that the issue will be on the minds of people looking at this code.
msg402232 - (view) Author: Eric Snow (eric.snow) * (Python committer) Date: 2021-09-20 14:11
On Mon, Sep 20, 2021 at 12:55 AM Raymond Hettinger
<report@bugs.python.org> wrote:
> If you close this out, consider adding a prominent comment so that the issue will be on the minds of people looking at this code.

Good idea!
msg402431 - (view) Author: Dong-hee Na (corona10) * (Python committer) Date: 2021-09-22 13:12
I thought about the Trie implementation for this case.
But as Eric said, it can be overkilling for this time.
msg402433 - (view) Author: Marc-Andre Lemburg (lemburg) * (Python committer) Date: 2021-09-22 13:22
Perhaps a frozen dict could be used instead of the linear search.

This could then also be made available as sys.frozen_modules for inspection by applications and tools such as debuggers or introspection tools trying to find source code (and potentially failing at this).

Not urgent, though.
msg402447 - (view) Author: Eric Snow (eric.snow) * (Python committer) Date: 2021-09-22 15:43
On Wed, Sep 22, 2021 at 7:12 AM Dong-hee Na <report@bugs.python.org> wrote:
> I thought about the Trie implementation for this case.

On Wed, Sep 22, 2021 at 7:22 AM Marc-Andre Lemburg
<report@bugs.python.org> wrote:
> Perhaps a frozen dict could be used instead of the linear search.
>
> This could then also be made available as sys.frozen_modules for inspection by applications and tools such as debuggers or introspection tools trying to find source code (and potentially failing at this).

Both are worth exploring later.  FWIW, I was also considering
_Py_hashtable_t (from Include/internal/pycore_hashtable.h).
msg402505 - (view) Author: Steve Dower (steve.dower) * (Python committer) Date: 2021-09-23 16:21
Could we add a compile-time requirement (most likely checked in tests, rather than at build) that _PyImport_FrozenModules be sorted? Then we can at least bail out of the loop early, and one day someone could make it a binary search.
msg402552 - (view) Author: Dong-hee Na (corona10) * (Python committer) Date: 2021-09-24 10:59
> Then we can at least bail out of the loop early, and one day someone could make it a binary search.

I like this idea if we can guarantee the order :)
History
Date User Action Args
2021-09-24 10:59:10corona10setmessages: + msg402552
2021-09-23 16:21:43steve.dowersetnosy: + steve.dower
messages: + msg402505
2021-09-22 15:43:36eric.snowsetmessages: + msg402447
2021-09-22 13:22:03lemburgsetnosy: + lemburg
messages: + msg402433
2021-09-22 13:12:34corona10setnosy: + corona10
messages: + msg402431
2021-09-20 14:11:16eric.snowsetmessages: + msg402232
2021-09-20 06:55:56rhettingersetstatus: pending -> open
nosy: + rhettinger
messages: + msg402198

2021-09-15 17:44:16eric.snowsetstatus: open -> pending

messages: + msg401864
2021-09-15 17:42:12eric.snowcreate