Searching for inittab in create_builtin is needlessly exhaustive

[itamaro]

Feature or enhancement

Proposal:

In create_builtin, the loop for searching a match in the inittab array is needlessly exhaustive:

cpython/Python/import.c

Lines 2357 to 2367 in 9d34623

	struct _inittab *found = NULL;
	for (struct _inittab *p = INITTAB; p->name != NULL; p++) {
	if (_PyUnicode_EqualToASCIIString(info.name, p->name)) {
	found = p;
	}
	}
	if (found == NULL) {
	// not found
	mod = Py_NewRef(Py_None);
	goto finally;
	}

Specifically, once a match is found, there's no point to continue looping the entire array.

This is fairly minor and unnoticeable with a small number of inittab extensions, but can become noticeable with thousands of inittab extensions, and it's also a trivial optimization (just add break, PR incoming), so why not.

Has this already been discussed elsewhere?

This is a minor feature, which does not need previous discussion elsewhere

Links to previous discussion of this feature:

No response

Linked PRs

• gh-140641: Break out of inittab search on match #140642

[itamaro]

I did basic benchmarking using 10k extensions (see code in https://github.com/itamaro/embedded-python-demo-inittab-scaling), with added timing around the search block.

As expected, before this change, the time is more or less constant, and is a function of the total number of inittab entries:

With this change, the search time is linear with the position of the matching entry: