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.

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.

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.

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!

I thought about the Trie implementation for this case.
But as Eric said, it can be overkilling for this time.

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.

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

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.

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