Esta publicación continúa la discusión de las mejoras de rendimiento que podrían hacerse realidad si no fuera por los diferentes peros. La parte anterior sobre StringBuilder está aquí .
Aquí observamos varias "mejoras" rechazadas debido a la falta de comprensión de las sutilezas de la especificación del lenguaje, los casos de esquina no obvios y otras razones. Vamos!
Cuando nada presagia problemas
Creo que cada uno de nosotros trabajó con los métodos Collections.emptySet() / Collections.emptyList() . Estos son métodos muy útiles que le permiten devolver una colección inmutable vacía sin crear un nuevo objeto. Mirando dentro de la clase EmptyList veremos esto:
private static class EmptyList<E> { public Iterator<E> iterator() { return emptyIterator(); } public Object[] toArray() { return new Object[0]; } }
¿Ves un fuerte potencial de mejora? El método EmptyList.iterator() devuelve un iterador vacío de la presencia, ¿por qué no hacer la misma finta con sus oídos para la matriz devuelta por el método toArray() ?
En otras palabras, el método siempre debe devolver una nueva matriz.
Dirás: "¡Él es inmutable! ¿Qué puede salir mal?"
Solo expertos experimentados pueden responder esta pregunta:
- ¿Quién es responsable?
- Expertos responsables Paul Sandoz y Tagir Valeev
La respuesta de los expertos.http://mail.openjdk.java.net/pipermail/core-libs-dev/2017-September/049171.html
También tenga en cuenta que esto cambia el comportamiento visible. E. g. alguien podría sincronizarse en el objeto de matriz devuelto por la llamada a Array, por lo que este cambio podría causar un intercambio de bloqueo no deseado.
Una vez que sugerí una mejora similar: devolver EMPTY_LIST de Arrays.asList () cuando la matriz suministrada tiene una longitud cero. Se rechazó con la misma razón [1].
http://mail.openjdk.java.net/pipermail/core-libs-dev/2015-September/035197.html
Por cierto, probablemente sea razonable que Arrays.asList compruebe la longitud de la matriz como:
public static <T> List<T> asList(T... a) { if(a.length == 0) return Collections.emptyList(); return new ArrayList<>(a); }
Suena razonable, ¿verdad? ¿Por qué crear una nueva lista para una matriz vacía si puede tomar una lista preparada de forma gratuita?
Hay una razón para no hacer esto. Por el momento, Arrays.asList no especifica restricciones en la identidad de la Lista devuelta. Agregar la microoptimización cambiará eso. Es un caso marginal y un caso de uso cuestionable también, pero teniendo en cuenta que dejaría las cosas conservadoramente como están.
Esta afirmación probablemente te causará desconcierto:
E. g. alguien podría sincronizarse en el objeto de matriz devuelto por la llamada a Array, por lo que este cambio podría causar un intercambio de bloqueo no deseado.
Dirá: "¿Quién en su sano juicio se sincronizará en la matriz (!) Devuelto (!!!) de la colección!?"
No parece muy creíble, pero el lenguaje brinda esa oportunidad, lo que significa que existe la posibilidad de que cierto usuario haga esto (o incluso que ya lo haya hecho). Luego, el cambio propuesto cambiará en el mejor de los casos el comportamiento del código y, en el peor de los casos, provocará un colapso en la sincronización (vaya más tarde, agárrelo). El riesgo es tan injustificado y la ganancia esperada es tan insignificante que es mejor dejar todo como está.
En general, la capacidad de sincronizar cualquier objeto, kmk, fue un error de los desarrolladores del lenguaje. En primer lugar, el encabezado de cada objeto contiene una estructura responsable de la sincronización, y en segundo lugar, nos encontramos en la situación descrita anteriormente cuando un objeto aparentemente inmutable no puede devolverse varias veces, ya que puede sincronizarse en él.
La moraleja de esta fábula es esta: la especificación y la compatibilidad con versiones anteriores son vacas sagradas de Java. Ni siquiera intentes invadirlos: el guardia dispara sin previo aviso.
Intentando, intentando ...
Hay varias clases basadas en matrices en el JDK a la vez, y todas ellas implementan los métodos List.indexOf() y List.lastIndexOf() :
- java.util.ArrayList
- java.util.Arrays $ ArrayList
- java.util.Vector
- java.util.concurrent.CopyOnWriteArrayList
El código de estos métodos en estas clases se repite casi uno a uno. Muchas aplicaciones y marcos también ofrecen sus soluciones para el mismo problema:
Como resultado, tenemos un código perdido que debe compilarse (a veces a veces varias veces), que tiene lugar en ReserverCodeCache, que debe probarse y que simplemente va de clase en clase casi sin cambios.
Los desarrolladores, a su vez, son muy aficionados a escribir algo como
int i = Arrays.asList(array).indexOf(obj);
Me gustaría introducir métodos de utilidad generalizados en el JDK y usarlos en todas partes, como se sugiere . El parche es tan simple como dos centavos:
1) las implementaciones de List.indexOf() y List.lastIndexOf() mueven a java.util.Arrays
2) en su lugar, se Arrays.indexOf() y Arrays.lastIndexOf() , respectivamente
Parece que lo que podría salir mal? El beneficio de este enfoque es [aparentemente] obvio. Pero el artículo trata sobre fracasos, así que piense qué podría salir mal.
- ¿Quién es responsable?
- Expertos responsables Martin Buchholz y Paul Sandoz
En mi humilde opinión, un poco tenso, pero no obstanteMartin Buchholz:
Sergey, estoy manteniendo todas esas clases de colección, y en ocasiones también he querido tener métodos indexOf en Array.java. Pero:
Las matrices generalmente se desaconsejan. Cualquier método estático nuevo en matrices (o, donde realmente las quiero, en el objeto matriz ¡Requiere un cambio de lenguaje java!) Encontrará resistencia.
Nos hemos arrepentido de admitir nulos en colecciones, por lo que las nuevas clases de colección como ArrayDeque no los admiten.
Otra variante que los usuarios pueden desear es qué tipo de comparación de igualdad usar.
Hemos lamentado tener ArrayList con un índice de inicio basado en cero; hubiera sido mejor tener el comportamiento de matriz circular de ArrayDeque desde el primer día.
El código para buscar segmentos de matriz es muy pequeño, por lo que no está ahorrando mucho. Es fácil cometer un error off-by-one, pero eso también es cierto para una API de arrays.
Paul Sandoz:
No iría tan lejos como para decir que las matrices están desalentadas, lo giraría positivamente como "usar con cuidado", ya que son espinosas, por ejemplo, siempre mutables. Sin duda podrían mejorarse. Me encantaría ver que las matrices implementan una matriz común En esta interfaz, podríamos avanzar un poco después de los sedimentos de los tipos de valor.
Sin embargo, cualquier nueva adición a Arrays se enfrentaría con cierta resistencia, al menos por mí :-) Nunca agrega solo uno o dos métodos, muchos otros también quieren venir (todas las primitivas más las variantes de rango). Por lo tanto, cualquier característica nueva debe ser lo suficientemente beneficiosa y, en este caso, no creo que los beneficios sean lo suficientemente fuertes (como una posible presión de caché de código de reducción).
Paul
Correspondencia: http://mail.openjdk.java.net/pipermail/core-libs-dev/2018-March/051968.html
La moraleja de esta fábula es la siguiente: su ingenioso parche puede ser sacrificado para su revisión simplemente porque no verá ningún valor especial en él. Bueno, sí, hay un código duplicado, pero no molesta a nadie, así que déjalo vivir.
¿Mejoras para ArrayList? Los tengo
Ciclomotor el parche no es mío, solo lo publicaré para que lo pienses. La propuesta en sí fue expresada aquí , y se ve muy atractiva. Véalo usted mismo:
A simple vista, la propuesta es muy, muy lógica. Puede medir el rendimiento utilizando un punto de referencia simple:
@State(Scope.Benchmark) public class ArrayListBenchmark { @State(Scope.Benchmark) public static class Data { @Param({"10", "100", "1000", "10000"}) public int size; ArrayList<Integer> arrayRandom = new ArrayList<Integer>(size); @Setup(Level.Invocation) public void initArrayList() { Random rand = new Random(); rand.setSeed(System.currentTimeMillis());
Resumen:
Benchmark (size) Mode Cnt Score Error Units construct_new_array_list 10 thrpt 25 388.212 ± 23.110 ops/s construct_new_array_list 100 thrpt 25 90.208 ± 7.995 ops/s construct_new_array_list 1000 thrpt 25 23.289 ± 1.687 ops/s construct_new_array_list 10000 thrpt 25 7.659 ± 0.560 ops/s construct_new_array_list 10 thrpt 25 562.678 ± 37.370 ops/s construct_new_array_list 100 thrpt 25 119.791 ± 13.232 ops/s construct_new_array_list 1000 thrpt 25 33.811 ± 3.812 ops/s construct_new_array_list 10000 thrpt 25 10.889 ± 0.564 ops/s
Nada mal para un cambio tan simple. Lo principal es que parece que no hay trampa. Honestamente cree una matriz, honestamente copie los datos y no se olvide del tamaño. ¡Ahora definitivamente deben aceptar el parche!
Pero ahí estabaMartin Buchholz:
No hay duda de que podemos optimizar el caso de ArrayList -> ArrayList, pero ¿qué pasa con todas las otras implementaciones de Collection? ArrayDeque y CopyOnWriteArrayList vienen a la mente.
ArrayList es una clase popular para hacer copias de Colecciones. ¿Dónde te detienes?
Una subclase patológica de ArrayList podría decidir no almacenar elementos en la matriz de respaldo, con la consiguiente rotura.
La solución bendecida al problema de copia de la lista es probablemente List.copyOf https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/List.html#copyOf(java .util.Collection ) que podría hacer la optimización que espera.
Alan Bateman
ArrayList no es final, por lo que es posible que alguien lo haya extendido para usar algo que no sea elementData. Puede ser más seguro usar la identidad de clase en lugar de la instancia de.
Nada me prohíbe desasociarme de ArrayList y almacenar datos en una lista vinculada. Luego, c instanceof ArrayList devolverá la verdad, llegaremos al área de copia y caeremos con seguridad.
La moraleja de esta fábula es la siguiente: un posible cambio en el comportamiento puede ser la causa del fracaso. En otras palabras, uno debe tener en cuenta la probabilidad de incluso el cambio más absurdo, si lo permite el lenguaje. Y sí, podría haber funcionado si ArrayList hubiera declarado final desde el principio.
Especificación de nuevo
Mientras depuraba mi aplicación, accidentalmente caí en las entrañas de Spring y encontré el siguiente código :
Afortunadamente, al entrar en java.lang.reflect.Constructor.getParameterTypes() desplacé el código un poco más abajo y encontré uno hermoso:
@Override public Class<?>[] getParameterTypes() { return parameterTypes.clone(); } public int getParameterCount() { return parameterTypes.length; }
Ya ves, si? Si necesitamos averiguar el número de argumentos de constructor / método, simplemente llame a java.lang.reflect.Method.getParameterCount() y no copie la matriz. Comprueba si el juego vale la pena en el caso más simple, en el que el método no tiene parámetros:
@State(Scope.Thread) @BenchmarkMode(Mode.AverageTime) @OutputTimeUnit(TimeUnit.NANOSECONDS) public class MethodToStringBenchmark { private Method method; @Setup public void setup() throws Exception { method = getClass().getMethod("toString"); } @Benchmark public int getParameterCount() { return method.getParameterCount(); } @Benchmark public int getParameterTypes() { return method.getParameterTypes().length; } }
En mi máquina y con JDK 11 resulta así:
Benchmark Mode Cnt Score Error Units getParameterCount avgt 25 2,528 ± 0,085 ns/op getParameterCount:·gc.alloc.rate avgt 25 ≈ 10⁻⁴ MB/sec getParameterCount:·gc.alloc.rate.norm avgt 25 ≈ 10⁻⁷ B/op getParameterCount:·gc.count avgt 25 ≈ 0 counts getParameterTypes avgt 25 7,299 ± 0,410 ns/op getParameterTypes:·gc.alloc.rate avgt 25 1999,454 ± 89,929 MB/sec getParameterTypes:·gc.alloc.rate.norm avgt 25 16,000 ± 0,001 B/op getParameterTypes:·gc.churn.G1_Eden_Space avgt 25 2003,360 ± 91,537 MB/sec getParameterTypes:·gc.churn.G1_Eden_Space.norm avgt 25 16,030 ± 0,045 B/op getParameterTypes:·gc.churn.G1_Old_Gen avgt 25 0,004 ± 0,001 MB/sec getParameterTypes:·gc.churn.G1_Old_Gen.norm avgt 25 ≈ 10⁻⁵ B/op getParameterTypes:·gc.count avgt 25 2380,000 counts getParameterTypes:·gc.time avgt 25 1325,000 ms
¿Qué podemos hacer al respecto? Podemos buscar el uso del antipatrón Method.getParameterTypes().length en el JDK (al menos en java.base ) y reemplazarlo donde tenga sentido:
java.lang.invoke.MethodHandleProxies
java.util.concurrent.ForkJoinTask
java.lang.reflect.Executable
sun.reflect.annotation.AnnotationType
El parche fue enviado junto con una carta de presentación .
De repente, resultó que durante varios años ha habido una tarea similar, e incluso se han preparado cambios para ello. Los comentarios señalaron un aumento de rendimiento bastante decente para cambios tan simples. Sin embargo, tanto ellos como mi parche están limpios hasta ahora y permanecen inmóviles. Por qué Probablemente porque los desarrolladores están demasiado ocupados con cosas más necesarias y estúpidamente no lo tienen en sus manos.
La moraleja de esta fábula es la siguiente: sus ingeniosos cambios pueden congelarse simplemente debido a la falta de trabajadores.
¡Pero este no es el final! Durante la discusión sobre la racionalidad del reemplazo descrito en otros proyectos, los camaradas más experimentados presentaron una contrapropuesta: tal vez no debería hacer el reemplazo de Method.getParameterTypes().length -> Method.getParameterCount() con sus manos, ¿pero confiar esto al compilador? ¿Es esto posible y será "legal"?
Intentemos verificar usando la prueba:
@Test void arrayClone() { final Object[] objects = new Object[3]; objects[0] = "azaza"; objects[1] = 365; objects[2] = 9876L; final Object[] clone = objects.clone(); assertEquals(objects.length, clone.length); assertSame(objects[0], clone[0]); assertSame(objects[1], clone[1]); assertSame(objects[2], clone[2]); }
que pasa y que muestra que si la matriz clonada no abandona el alcance, se puede eliminar, porque el acceso a cualquier elemento desde sus celdas o el campo de length se puede obtener del original.
¿Puede el JDK hacer esto? Comprobamos:
@State(Scope.Thread) @BenchmarkMode(Mode.AverageTime) @OutputTimeUnit(TimeUnit.NANOSECONDS) public class ArrayAllocationEliminationBenchmark { private int length = 10; @Benchmark public int baseline() { return new int[length].length; } @Benchmark public int baselineClone() { return new int[length].clone().length; } }
Salida para JDK 13:
Benchmark Mode Cnt Score Error Units baseline avgt 50 6,135 ± 0,140 ns/op baseline:·gc.alloc.rate.norm avgt 50 56,000 ± 0,001 B/op clone avgt 50 18,359 ± 0,619 ns/op clone:·gc.alloc.rate.norm avgt 50 112,000 ± 0,001 B/op
Resulta que openjdk no sabe cómo lanzar una new int[length] , a diferencia del Grial , jeje:
Benchmark Mode Cnt Score Error Units baseline avgt 25 2,470 ± 0,156 ns/op baseline:·gc.alloc.rate.norm avgt 25 0,005 ± 0,008 B/op lone avgt 25 13,086 ± 1,059 ns/op lone:·gc.alloc.rate.norm avgt 25 112,113 ± 0,115 B/op
Resulta que puedes ajustar un poco el compilador de optimización de OpenJDK para que pueda hacer lo que el Grial puede hacer. Dado que no solo todos pueden obtener un anuncio positivo en el código VM y presentar algo significativo, me limité a una carta en la que expresé mis observaciones.
Resultó, y hay varias sutilezas. Vladimir Ivanov indica que:
Teniendo en cuenta que no hay forma de aumentar / reducir las matrices Java,
La transformación "cloned_array.length => original_array.length" es correcta
independientemente de si la variante clonada escapa o no.
Además, la transformación ya está ahí:
http://hg.openjdk.java.net/jdk/jdk/file/tip/src/hotspot/share/opto/memnode.cpp#l2388
No he examinado los puntos de referencia que mencionaste, pero parece que
cloned_array.length access no es la razón por la cual la matriz clonada sigue siendo
ahi
En cuanto a sus otras ideas, redirige los accesos desde la instancia clonada a
el original es problemático (en el caso general) ya que el compilador tiene que demostrar
no hubo cambios en ambas versiones y los accesos indexados lo hacen incluso
más duro Y los puntos seguros también causan problemas (para la rematerialización).
Pero estoy de acuerdo en que sería bueno cubrir (al menos) casos simples de
copia defensiva
Es decir, golpear un clon parece ser posible, y no particularmente difícil. Pero con la conversión
int len = new int[arrayLength].length;
->
int len = arrayLength;
surgen dificultades :
No eliminamos las asignaciones de matriz que no tienen una longitud conocida
porque pueden causar una excepción NegativeArraySize. En este caso nosotros
Sin embargo, debería poder demostrar que la longitud es positiva.
De todos modos, tengo un parche casi terminado que reemplaza la matriz no utilizada
asignaciones con un guardia adecuado.
En otras palabras, no puede simplemente tomar y descartar la creación de una matriz, porque de acuerdo con la especificación, la ejecución debe arrojar una NegativeArraySizeException y no hay nada que podamos hacer al respecto:
@Test void arrayWithNwgativeSize() { int length = 0; try { int newLen = -3; length = new Object[newLen].length;
¿Por qué pudo el Grial? Creo que la razón es que el valor del campo de length en el punto de referencia anterior fue constante y siempre igual a 10, lo que permitió al analizador concluir que no es necesario verificar un valor negativo, lo que significa que se puede eliminar junto con la creación de la matriz en sí. Correcto en los comentarios si cometí un error.
Eso es todo por hoy :) Agregue sus ejemplos en los comentarios, lo entenderemos.