is_backtrack_cause is very expensive to evaluate

[jbylund]

What's the problem this feature will solve?

The provider's is_backtrack_cause method is currently pretty expensive to evaluate (44% inclusive, profile)

pip/src/pip/_internal/resolution/resolvelib/provider.py

Lines 239 to 248 in e46888b

	@staticmethod
	def is_backtrack_cause(
	identifier: str, backtrack_causes: Sequence["PreferenceInformation"]
	) -> bool:
	for backtrack_cause in backtrack_causes:
	if identifier == backtrack_cause.requirement.name:
	return True
	if backtrack_cause.parent and identifier == backtrack_cause.parent.name:
	return True
	return False

Conceptually it's "is this identifier in this set of names & parent's names", but because it drives a sort (in part) we scan the entire list many times (additionally, the .name property of some of these objects is expensive).

Describe the solution you'd like

I'd like to implement is_backtrack_cause in a way that we can ask identifier in constant_time_lookup_datastructure. Draft of an idea in #10621.

Alternative Solutions

I looked at implementing this in resolvelib a little bit, but my impression is that resolvelib doesn't want to be so opinionated about what these objects are?

Code of Conduct

• I agree to follow the PSF Code of Conduct.