Mailing List Archive: [issue45213] Frozen modules are looked up using a linear search.

[issue45213] Frozen modules are looked up using a linear search.

Sep 15, 2021, 10:42 AM

Post #1 of 9 (112 views)

New submission from Eric Snow <ericsnowcurrently@gmail.com>:

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.

----------
components: Interpreter Core
messages: 401863
nosy: barry, brett.cannon, eric.snow
priority: normal
severity: normal
stage: needs patch
status: open
title: Frozen modules are looked up using a linear search.
type: performance
versions: Python 3.11

_______________________________________
Python tracker <report@bugs.python.org>
<https://bugs.python.org/issue45213>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

[issue45213] Frozen modules are looked up using a linear search. [ In reply to ]

Sep 15, 2021, 10:44 AM

Post #2 of 9 (112 views)

Eric Snow <ericsnowcurrently@gmail.com> added the comment:

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.

----------
status: open -> pending

_______________________________________
Python tracker <report@bugs.python.org>
<https://bugs.python.org/issue45213>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

[issue45213] Frozen modules are looked up using a linear search. [ In reply to ]

Sep 19, 2021, 11:55 PM

Post #3 of 9 (112 views)

Raymond Hettinger <raymond.hettinger@gmail.com> added the comment:

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.

----------
nosy: +rhettinger
status: pending -> open

_______________________________________
Python tracker <report@bugs.python.org>
<https://bugs.python.org/issue45213>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

[issue45213] Frozen modules are looked up using a linear search. [ In reply to ]

Sep 20, 2021, 7:11 AM

Post #4 of 9 (111 views)

Eric Snow <ericsnowcurrently@gmail.com> added the comment:

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!

----------

_______________________________________
Python tracker <report@bugs.python.org>
<https://bugs.python.org/issue45213>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

[issue45213] Frozen modules are looked up using a linear search. [ In reply to ]

Sep 22, 2021, 6:12 AM

Post #5 of 9 (111 views)

Dong-hee Na <donghee.na@python.org> added the comment:

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

----------
nosy: +corona10

_______________________________________
Python tracker <report@bugs.python.org>
<https://bugs.python.org/issue45213>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

[issue45213] Frozen modules are looked up using a linear search. [ In reply to ]

Sep 22, 2021, 6:22 AM

Post #6 of 9 (111 views)

Marc-Andre Lemburg <mal@egenix.com> added the comment:

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.

----------
nosy: +lemburg

_______________________________________
Python tracker <report@bugs.python.org>
<https://bugs.python.org/issue45213>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

[issue45213] Frozen modules are looked up using a linear search. [ In reply to ]

Sep 22, 2021, 8:43 AM

Post #7 of 9 (111 views)

Eric Snow <ericsnowcurrently@gmail.com> added the comment:

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

----------

_______________________________________
Python tracker <report@bugs.python.org>
<https://bugs.python.org/issue45213>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

[issue45213] Frozen modules are looked up using a linear search. [ In reply to ]

Sep 23, 2021, 9:21 AM

Post #8 of 9 (111 views)

Steve Dower <steve.dower@python.org> added the comment:

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.

----------
nosy: +steve.dower

_______________________________________
Python tracker <report@bugs.python.org>
<https://bugs.python.org/issue45213>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

[issue45213] Frozen modules are looked up using a linear search. [ In reply to ]

Sep 24, 2021, 3:59 AM

Post #9 of 9 (111 views)

Dong-hee Na <donghee.na@python.org> added the comment:

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

----------

_______________________________________
Python tracker <report@bugs.python.org>
<https://bugs.python.org/issue45213>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com