java - programas - for anidado netbeans

Bucles anidados Java 8 con secuencias y rendimiento

Question

Para practicar las secuencias de Java 8 intenté convertir el siguiente ciclo anidado en la API de la secuencia de Java 8. Calcula la mayor suma de dígitos de a ^ b (a, b <100) y toma ~ 0.135s en mi Core i5 760.

public static int digitSum(BigInteger x)
{
int sum = 0;
for(char c: x.toString().toCharArray()) {sum+=Integer.valueOf(c+"");}
return sum;
}
@Test public void solve()
{
int max = 0;
for(int i=1;i<100;i++)
for(int j=1;j<100;j++)
max = Math.max(max,digitSum(BigInteger.valueOf(i).pow(j)));
System.out.println(max);
}

Mi solución, que esperaba ser más rápida debido al paralelismo, en realidad tomó 0.25s (0.19s sin el parallel() ):

int max = IntStream.range(1,100).parallel()
.map(i -> IntStream.range(1, 100)
.map(j->digitSum(BigInteger.valueOf(i).pow(j)))
.max().getAsInt()).max().getAsInt();

Mis preguntas

• ¿Hice la conversión correcta o hay una mejor manera de convertir bucles anidados para cálculos de flujo?
• ¿Por qué la variante de la corriente es mucho más lenta que la anterior?
• ¿Por qué la instrucción parallel () aumentó el tiempo de 0.19s a 0.25s?

Sé que microbenchmarks son frágiles y el paralelismo solo vale la pena para grandes problemas, pero para una CPU, incluso 0.1s es una eternidad, ¿verdad?

Actualizar

Medí con el marco de Junit 4 en Eclipse Kepler (muestra el tiempo necesario para ejecutar una prueba).

Mis resultados para a, b <1000 en vez de 100:

• ciclo tradicional 186s
• flujo secuencial 193s
• flujo paralelo 55s

Actualización 2 Sustitución de sum+=Integer.valueOf(c+""); con sum+= c - ''0''; (¡gracias Peter!) afeitó 10 segundos enteros del método paralelo, llevándolo a 45s. ¡No esperaba un gran impacto en el rendimiento!

Además, reducir el paralelismo con la cantidad de núcleos de CPU (4 en mi caso) no hizo mucho, ya que redujo el tiempo solo a 44.8s (sí, agrega a y b = 0, pero creo que esto no afectará el rendimiento mucho):

int max = IntStream.range(0, 3).parallel().
.map(m -> IntStream.range(0,250)
.map(i -> IntStream.range(1, 1000)
.map(j->.digitSum(BigInteger.valueOf(250*m+i).pow(j)))
.max().getAsInt()).max().getAsInt()).max().getAsInt();

Answer 1

El problema que tienes es que estás buscando un código subóptimo. Cuando tiene un código que puede estar muy optimizado, depende mucho de si la JVM es lo suficientemente inteligente como para optimizar su código. Los bucles han existido por mucho más tiempo y se entienden mejor.

Una gran diferencia en su código de bucle, es que el conjunto de trabajo es muy pequeño. Solo está considerando una suma máxima de dígitos por vez. Esto significa que el código es amigable con la caché y que tiene objetos de muy corta duración. En el caso de stream () está creando colecciones para las cuales hay más en el conjunto de trabajo en cualquier momento, usando más caché, con más sobrecarga. Yo esperaría que tus tiempos de GC sean más largos y / o más frecuentes también.

¿Por qué la variante de la corriente es mucho más lenta que la anterior?

Los bucles están bastante bien optimizados desde que se desarrolló Java. Se pueden asignar de manera muy eficiente al hardware. Los flujos son bastante nuevos y no están tan optimizados.

¿Por qué la instrucción parallel () aumentó el tiempo de 0.19s a 0.25s?

Lo más probable es que tenga un cuello de botella en un recurso compartido. Usted crea bastantes basura, pero esto suele ser bastante concurrente. Usar más hilos, solo garantiza que tendrá más sobrecarga, no garantiza que pueda aprovechar la potencia de CPU adicional que tiene.

Answer 2

He creado un micro benchmark rápido y sucio basado en tu código. Los resultados son:

loop: 3192
lambda: 3140
lambda paralelo: 868

Entonces, el ciclo y lambda son equivalentes y la secuencia paralela mejora significativamente el rendimiento. Sospecho que sus resultados no son confiables debido a su metodología de evaluación comparativa.

public static void main(String[] args) {
int sum = 0;
//warmup
for (int i = 0; i < 100; i++) {
solve();
solveLambda();
solveLambdaParallel();
}
{
long start = System.nanoTime();
for (int i = 0; i < 100; i++) {
sum += solve();
}
long end = System.nanoTime();
System.out.println("loop: " + (end - start) / 1_000_000);
}
{
long start = System.nanoTime();
for (int i = 0; i < 100; i++) {
sum += solveLambda();
}
long end = System.nanoTime();
System.out.println("lambda: " + (end - start) / 1_000_000);
}
{
long start = System.nanoTime();
for (int i = 0; i < 100; i++) {
sum += solveLambdaParallel();
}
long end = System.nanoTime();
System.out.println("lambda parallel : " + (end - start) / 1_000_000);
}
System.out.println(sum);
}
public static int digitSum(BigInteger x) {
int sum = 0;
for (char c : x.toString().toCharArray()) {
sum += Integer.valueOf(c + "");
}
return sum;
}
public static int solve() {
int max = 0;
for (int i = 1; i < 100; i++) {
for (int j = 1; j < 100; j++) {
max = Math.max(max, digitSum(BigInteger.valueOf(i).pow(j)));
}
}
return max;
}
public static int solveLambda() {
return IntStream.range(1, 100)
.map(i -> IntStream.range(1, 100).map(j -> digitSum(BigInteger.valueOf(i).pow(j))).max().getAsInt())
.max().getAsInt();
}
public static int solveLambdaParallel() {
return IntStream.range(1, 100)
.parallel()
.map(i -> IntStream.range(1, 100).map(j -> digitSum(BigInteger.valueOf(i).pow(j))).max().getAsInt())
.max().getAsInt();
}

También lo he ejecutado con jmh, que es más confiable que las pruebas manuales. Los resultados son consistentes con los anteriores (micro segundos por llamada):

Benchmark Mode Mean Units
c.a.p.SO21968918.solve avgt 32367.592 us/op
c.a.p.SO21968918.solveLambda avgt 31423.123 us/op
c.a.p.SO21968918.solveLambdaParallel avgt 8125.600 us/op