Hidden version of searchsortedfirst

General Usage
, , ,
1

In the Julia source code, there is an undocumented version of searchsortedfirst:

function searchsortedfirst(v::AbstractVector, x, lo::T, hi::T, o::Ordering)::keytype(v) where T<:Integer

I need a function like this, in which I can specify lo and hi (the bounds of the range to be searched). But because this one is not in the docs, I worry that it is not intended for general use and might go away with the next release of Julia. Should I write my own function?

1 Like
2

It might be that someone simply forgot to include it in the docs. The function searchsortedfirst is public, so I’d guess it will remain.

Anyway, you can do e.g.

searchsortedfirst(@view(v[lo:hi]), x) + lo - 1
2 Likes
3

In my (bounded) understanding, this is a helper function to the documented searchsortedfirst signature. I’m not the authority, but I would consider it an internal method of the exported function (but it didn’t need to be named something like _searchsortedfirst because it didn’t conflict, I guess, or because the author didn’t think to). Given that it’s completely un-mentioned in the docs and not exercised in the unit tests, I wouldn’t consider it bullet-proof public interface.

That said, it wouldn’t surprise me if that method is still intact 15 years from now. But if you want an ironclad solution, it’s probably safer to use @view and the documented interface as suggested by the above poster.

You can find similar probably-private methods in methods(sort!) and probably numerous other functions, too.

If you’re doing repeated advancing searches and not expecting to skip large sections of your data, you might also be interested in findnext. I find the searchsorted methods have underwhelming performance on small or medium searches because of their poor memory access pattern and inability to SIMD.

2 Likes
4

This is kind of a gray zone IMO.

When a binding is marked with public and export, it’s public API. In the case of a function, according to the following discussion, that means all methods are public API, too:

So “private methods”/“internal methods” do not exist as a concept, from that specific and formal perspective, it seems.

However, it is also true that many private methods do de facto exist, not only in packages, but also in Base (as already pointed out above). After all, both public and the exact meaning of public API was only introduced with Julia v1.11.

In any case, it is certain that private methods are a bad practice, because:

  • The concept seems to conflict with the new public API rules.

  • It introduces unnecessary concerns about method ambiguity.

  • It pollutes the output of reflection functionality such as methods.

  • Additional methods reduce compiler performance.

Regarding the specific method in question here, IMO it would be better not to rely on it, and it could perhaps be deleted if a PkgEval run indicates that action would not break any packages. The signature does not follow the usual searchsortedfirst interface, so I’d say the method is harmful punning, and might have been intended to be a separate function in the first place.

3 Likes
5

One more point: cycles in the call graph (on the level of functions, not methodinstances; we’re not talking about recursion here) can lead to history dependence in type inference. If compilation of the inner method is triggered independently before the outer method, type inference will often achieve better results than if the outer method is compiled first.

Details/links: Type instability in nested quadgk calls - #21 by danielwe

2 Likes