Possible efficiency improvements in annotation binary searches

[MikeEdgar]

There may be a possible minor improvement in the binary searching done in AnnotationInstance by special-casing arrays of length 0 and 1, and using lambdas for the comparators. The use of the lambda relies on the fact that Arrays.binarySearch will pass the array entries as the first parameter of the comparator (AnnotationInstance#value(String) already relies on this). It should result in an allocation-free search.

For example:

static AnnotationInstance binarySearch(AnnotationInstance[] annotations, DotName name) {
    if (annotations.length == 0) {
        return null;
    }

    if (annotations.length == 1) {
        return annotations[0].name().equals(name) ? annotations[0] : null;
    }

    // Relies on binarySearch passing array entries as the first comparator parameter
    int i = Arrays.binarySearch(annotations, null, (entry, x) -> entry.name().compareTo(name));
    return i >= 0 ? annotations[i] : null;
}

Also, the create method AnnotationInstance instantiates an AnnotationValue name comparator which maybe could be a constant.

[Ladicek]

Passing a lambda to Arrays.binarySearch() would only be allocation-free if sufficient inlining && scalar replacement of aggregates happened, otherwise the Comparator has to be instantiated. I'm fairly sure the current way (with a constant Comparator) leads to less allocations than what you propose.

Also, thanks for noticing what AnnotationInstance.value() does -- that certainly relies on an unspecified implementation detail. I'm not going to change it at the moment, but I also don't want this to expand.

[MikeEdgar]

Passing a lambda to Arrays.binarySearch() would only be allocation-free if sufficient inlining && scalar replacement of aggregates happened, otherwise the Comparator has to be instantiated.

I was looking at this yesterday locally and the compiler generated this method (and a similar one for String/AnnovationValue) in the bytecode when using the lambdas. I was interpreting it as avoiding the allocation, but I'm certainly no expert on this. Either way, without a proper key passed to binarySearch it relies on the implementation detail, which as you say should not be expanded in the code.

  private static synthetic int lambda$0(org.jboss.jandex.DotName arg0, org.jboss.jandex.AnnotationInstance entry, org.jboss.jandex.AnnotationInstance x);
    0  aload_1 [entry]
    1  invokevirtual org.jboss.jandex.AnnotationInstance.name() : org.jboss.jandex.DotName [187]
    4  aload_0 [arg0]
    5  invokevirtual org.jboss.jandex.DotName.compareTo(org.jboss.jandex.DotName) : int [486]
    8  ireturn

[Ladicek]

Yes, the lambda body is generated as a synthetic method in the declaring class. However, there needs to be a Comparator instance (unless, again, sufficient inlining and scalar replacement of aggregates occur), so at least one allocation has to happen. If the lambda captures variables from lexical scope, I think each use requires new allocation.