Iterative search for revision should be a binary search

[smoelius]

dylint/dylint/src/package_options/revs.rs

Lines 166 to 168 in 6852355

	// smoelius: To reiterate a comment from package_options/mod.rs, the `find` below is an
	// iterative search and it is causing this test to become increasingly slow. As of this writing,
	// the test takes around two minutes. The search should be a binary search.

Referenced comment:

dylint/dylint/src/package_options/mod.rs

Lines 118 to 119 in 6852355

	// smoelius: The next iterative search is a bottleneck. It should be a binary
	// search.

[suratkhan]

@smoelius is this task still available? I would like to give it a try. Can I get assigned?

[smoelius]

@suratkhan It is still available. Honestly, though, I worry that this issue could be tricky and would require someone with experience with git2.

Rather than assign it to you, would you like to just work on it and see how it goes?

[suratkhan]

yeah sure, I can give a try. If I can make it work then I'll send a PR where you can give further review and instructions.

Do you have any other guideline before starting other than git2?

[smoelius]

Do you have any other guideline before starting other than git2?

I haven't thought about this hard enough, but Revs will likely need a completely new API, something like a slice's binary_search: https://doc.rust-lang.org/std/primitive.slice.html#method.binary_search

Notably, these two uses of find should be made to use the new API:

• dylint/dylint/src/package_options/mod.rs

  Lines 120 to 124 in 6852355

  	iter.find(|result| {
  	result
  	.as_ref()
  	.map_or(true, |rev| rev.version == clippy_utils_version)
  	})

• dylint/dylint/src/package_options/revs.rs

  Lines 175 to 178 in 6852355

  	.find(|rev| {
  	rev.as_ref()
  	.map_or(true, |rev| rev.version == example.version)
  	})

I'm noticing now that both of those find uses check the revision's version. So the new API might take a version as an argument.

I haven't verified this, but I suspect the slowness of the current API comes from all the checkouts:

dylint/dylint/src/package_options/revs.rs

Lines 90 to 91 in 6852355

	self.repository
	.checkout_tree(commit.as_object(), None)

So performing a checkout only when necessary is something I would try.

If you find that something else is contributing to the slowness, I would be interested.

Thank you very much for working on this.