son - java stream ejemplos

Java lambdas 20 veces más lento que las clases anónimas

Question

He visto muchas preguntas aquí sobre el rendimiento de las lambdas de Java, pero la mayoría de ellas dicen "Las lambdas son un poco más rápidas, pero se vuelven más lentas cuando se usan cierres" o "Los tiempos de calentamiento versus ejecución son diferentes" u otras cosas similares.

Sin embargo, golpeé una cosa bastante extraña aquí. Considere este problema de LeetCode :

Dado un conjunto de intervalos no superpuestos, inserte un nuevo intervalo en los intervalos (fusionar si es necesario).

Puede suponer que los intervalos se ordenaron inicialmente según sus horas de inicio.

El problema fue etiquetado con fuerza, por lo que supuse que un enfoque lineal no es lo que quieren allí. Así que decidí encontrar una forma inteligente de combinar la búsqueda binaria con modificaciones en la lista de entrada. Ahora el problema no es muy claro al modificar la lista de entrada: dice "insertar", aunque la firma requiere devolver una referencia a la lista, pero no importa eso por ahora. Aquí está el código completo, pero solo las primeras líneas son relevantes para esta pregunta. Estoy guardando el resto aquí solo para que cualquiera pueda probarlo:

public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
    int start = Collections.binarySearch(intervals, newInterval,
                                         (i1, i2) -> Integer.compare(i1.start, i2.start));
    int skip = start >= 0 ? start : -start - 1;
    int end = Collections.binarySearch(intervals.subList(skip, intervals.size()),
                                       new Interval(newInterval.end, 0),
                                       (i1, i2) -> Integer.compare(i1.start, i2.start));
    if (end >= 0) {
        end += skip; // back to original indexes
    } else {
        end -= skip; // ditto
    }
    int newStart = newInterval.start;
    int headEnd;
    if (-start - 2 >= 0) {
        Interval prev = intervals.get(-start - 2);
        if (prev.end < newInterval.start) {
            // the new interval doesn''t overlap the one before the insertion point
            headEnd = -start - 1;
        } else {
            newStart = prev.start;
            headEnd = -start - 2;
        }
    } else if (start >= 0) {
        // merge the first interval
        headEnd = start;
    } else { // start == -1, insertion point = 0
        headEnd = 0;
    }
    int newEnd = newInterval.end;
    int tailStart;
    if (-end - 2 >= 0) {
        // merge the end with the previous interval
        newEnd = Math.max(newEnd, intervals.get(-end - 2).end);
        tailStart = -end - 1;
    } else if (end >= 0) {
        newEnd = intervals.get(end).end;
        tailStart = end + 1;
    } else { // end == -1, insertion point = 0
        tailStart = 0;
    }
    intervals.subList(headEnd, tailStart).clear();
    intervals.add(headEnd, new Interval(newStart, newEnd));
    return intervals;
}

Esto funcionó bien y fue aceptado, pero con un tiempo de ejecución de 80 ms, mientras que la mayoría de las soluciones fueron de 4-5 ms y algunas de 18-19 ms. Cuando los busqué, todos eran lineales y muy primitivos. No es algo que uno esperaría de un problema etiquetado como "difícil".

Pero aquí viene la pregunta: mi solución también es lineal en el peor de los casos (porque las operaciones de agregar / borrar son tiempo lineal). ¿Por qué es eso más lento? Y luego hice esto:

    Comparator<Interval> comparator = new Comparator<Interval>() {
        @Override
        public int compare(Interval i1, Interval i2) {
            return Integer.compare(i1.start, i2.start);
        }
    };
    int start = Collections.binarySearch(intervals, newInterval, comparator);
    int skip = start >= 0 ? start : -start - 1;
    int end = Collections.binarySearch(intervals.subList(skip, intervals.size()),
                                       new Interval(newInterval.end, 0),
                                       comparator);

¡Desde 80 ms hasta 4 ms! ¿Que está pasando aqui? Desafortunadamente, no tengo idea de qué tipo de pruebas ejecuta LeetCode o bajo qué entorno, pero aún así, ¿no es 20 veces demasiado?

Answer 1

Obviamente, se encuentra con la sobrecarga de inicialización por primera vez de las expresiones lambda. Como ya se mencionó en los comentarios, las clases para las expresiones lambda se generan en tiempo de ejecución en lugar de cargarse desde la ruta de clase.

Sin embargo, ser generado no es la causa de la desaceleración. Después de todo, generar una clase que tenga una estructura simple puede ser incluso más rápido que cargar los mismos bytes desde una fuente externa. Y la clase interna también debe cargarse. Pero cuando la aplicación no ha usado expresiones lambda antes, incluso el marco para generar las clases lambda tiene que cargarse (la implementación actual de Oracle usa ASM bajo el capó). Esta es la causa real de la desaceleración, carga e inicialización de una docena de clases utilizadas internamente, no la expresión lambda en sí.

Puedes verificar esto fácilmente. En su código actual que usa expresiones lambda, tiene dos expresiones idénticas (i1, i2) -> Integer.compare(i1.start, i2.start) . La implementación actual no reconoce esto (en realidad, el compilador tampoco proporciona una pista). Entonces, aquí, se generan dos instancias lambda, que tienen incluso clases diferentes. Puede refactorizar el código para tener un solo comparador, similar a su variante de clase interna:

final Comparator<? super Interval> comparator
  = (i1, i2) -> Integer.compare(i1.start, i2.start);
int start = Collections.binarySearch(intervals, newInterval, comparator);
int skip = start >= 0 ? start : -start - 1;
int end = Collections.binarySearch(intervals.subList(skip, intervals.size()),
                                   new Interval(newInterval.end, 0),
                                   comparator);

No notará ninguna diferencia de rendimiento significativa, ya que no es el número de expresiones lambda lo que importa, sino solo la carga de clases y la inicialización del marco, que ocurre exactamente una vez.

Incluso puede maximizarlo insertando expresiones lambda adicionales como

final Comparator<? super Interval> comparator1
    = (i1, i2) -> Integer.compare(i1.start, i2.start);
final Comparator<? super Interval> comparator2
    = (i1, i2) -> Integer.compare(i1.start, i2.start);
final Comparator<? super Interval> comparator3
    = (i1, i2) -> Integer.compare(i1.start, i2.start);
final Comparator<? super Interval> comparator4
    = (i1, i2) -> Integer.compare(i1.start, i2.start);
final Comparator<? super Interval> comparator5
    = (i1, i2) -> Integer.compare(i1.start, i2.start);

sin ver ninguna desaceleración. Es realmente la sobrecarga inicial de la primera expresión lambda de todo el tiempo de ejecución que estás notando aquí. Dado que Leetcode en sí mismo aparentemente no usa expresiones lambda antes de ingresar su código, cuyo tiempo de ejecución se mide, esta sobrecarga se agrega a su tiempo de ejecución aquí.

Consulte también "¿Cómo se compilarán las funciones lambda de Java?" Y "¿Una expresión lambda crea un objeto en el montón cada vez que se ejecuta?"