java - taylor - Error de orden de encuentro al ordenar un flujo paralelo

serie de taylor analisis numerico

Question

Tengo una clase de Record :

public class Record implements Comparable<Record>
{
   private String myCategory1;
   private int    myCategory2;
   private String myCategory3;
   private String myCategory4;
   private int    myValue1;
   private double myValue2;

   public Record(String category1, int category2, String category3, String category4,
      int value1, double value2)
   {
      myCategory1 = category1;
      myCategory2 = category2;
      myCategory3 = category3;
      myCategory4 = category4;
      myValue1 = value1;
      myValue2 = value2;
   }

   // Getters here
}

Creo una gran lista de muchos discos. Solo los valores segundo y quinto, i / 10000 e i , se usan más adelante, por parte de los getCategory2() y getValue1() respectivamente.

List<Record> list = new ArrayList<>();
for (int i = 0; i < 115000; i++)
{
    list.add(new Record("A", i / 10000, "B", "C", i, (double) i / 100 + 1));
}

Tenga en cuenta que los primeros 10,000 registros tienen una category2 de 0 , luego los siguientes 10,000 tienen 1 , etc., mientras que los valores de value1 son 0-114999 secuencialmente.

Creo una Stream que es parallel y sorted .

Stream<Record> stream = list.stream()
   .parallel()
   .sorted(
       //(r1, r2) -> Integer.compare(r1.getCategory2(), r2.getCategory2())
   )
   //.parallel()
;

Tengo un ForkJoinPool que mantiene 8 hilos, que es el número de núcleos que tengo en mi PC.

ForkJoinPool pool = new ForkJoinPool(8);

Utilizo el truco descrito aquí para enviar una tarea de procesamiento de secuencias a mi propia ForkJoinPool lugar de la ForkJoinPool común .

List<Record> output = pool.submit(() ->
    stream.collect(Collectors.toList()
)).get();

Esperaba que la operación sorted paralelo respetara el orden de encuentro de la secuencia y que fuera una ordenación estable , porque el Spliterator devuelto por ArrayList está ORDERED .

Sin embargo, el código simple que imprime los elementos de la output resultante de la List en orden muestra que no es así.

for (Record record : output)
{
     System.out.println(record.getValue1());
}

Salida, condensada:

0
1
2
3
...
69996
69997
69998
69999
71875  // discontinuity!
71876
71877
71878
...
79058
79059
79060
79061
70000  // discontinuity!
70001
70002
70003
...
71871
71872
71873
71874
79062  // discontinuity!
79063
79064
79065
79066
...
114996
114997
114998
114999

El size() de output es 115000 , y todos los elementos parecen estar allí, solo que en un orden ligeramente diferente.

Así que escribí un código de verificación para ver si el sort era estable. Si es estable, entonces todos los valores de value1 deben permanecer en orden. Este código verifica el pedido, imprimiendo cualquier discrepancia.

int prev = -1;
boolean verified = true;
for (Record record : output)
{
    int curr = record.getValue1();
    if (prev != -1)
    {
        if (prev + 1 != curr)
        {
            System.out.println("Warning: " + prev + " followed by " + curr + "!");
            verified = false;
        }
    }
    prev = curr;
}
System.out.println("Verified: " + verified);

Salida:

Warning: 69999 followed by 71875!
Warning: 79061 followed by 70000!
Warning: 71874 followed by 79062!
Warning: 99999 followed by 100625!
Warning: 107811 followed by 100000!
Warning: 100624 followed by 107812!
Verified: false

Esta condición persiste si hago cualquiera de lo siguiente:

• Reemplace el ForkJoinPool con un ThreadPoolExecutor .

  ThreadPoolExecutor pool = new ThreadPoolExecutor(8, 8, 0, TimeUnit.SECONDS, new ArrayBlockingQueue<>(10));

• Utilice el ForkJoinPool común procesando el Stream directamente.

  List<Record> output = stream.collect(Collectors.toList());

• Llamada parallel() después de que llame sorted .

  Stream<Record> stream = list.stream().sorted().parallel();

• Llame a parallelStream() lugar de stream().parallel() .

  Stream<Record> stream = list.parallelStream().sorted();

• Ordenar utilizando un Comparator . Tenga en cuenta que este criterio de clasificación es diferente al orden "natural" que definí para la interfaz Comparable , aunque comenzando con los resultados en orden desde el principio, el resultado debería ser el mismo.

  Stream<Record> stream = list.stream().parallel().sorted(
      (r1, r2) -> Integer.compare(r1.getCategory2(), r2.getCategory2())
  );

Solo puedo obtener esto para conservar el orden de encuentro si no hago una de las siguientes Stream en el Stream :

• No llames parallel() .
• No llame a ninguna sobrecarga de sorted .

Curiosamente, el parallel() sin ordenamiento conservó el orden.

En los dos casos anteriores, la salida es:

Verified: true

Mi versión de Java es 1.8.0_05. Esta anomalía también ocurre en Ideone , que parece estar ejecutando Java 8u25.

Actualizar

He actualizado mi JDK a la última versión en este momento, 1.8.0_45, y el problema no ha cambiado.

Pregunta

¿Está el orden de grabación en la List resultante ( output ) fuera de orden porque la ordenación de alguna manera no es estable, porque la orden de encuentro no se conserva, o alguna otra razón?

¿Cómo puedo asegurarme de que el orden de encuentro se conserve cuando creo una secuencia paralela y la clasifico?

Answer 1

Parece que Arrays.parallelSort no es estable en algunas circunstancias. Bien descrito. La ordenación paralela del flujo se implementa en términos de Arrays.parallelSort , por lo que también afecta a los flujos. Aquí hay un ejemplo simplificado:

public class StableSortBug {
    static final int SIZE = 50_000;

    static class Record implements Comparable<Record> {
        final int sortVal;
        final int seqNum;

        Record(int i1, int i2) { sortVal = i1; seqNum = i2; }

        @Override
        public int compareTo(Record other) {
            return Integer.compare(this.sortVal, other.sortVal);
        }
    }

    static Record[] genArray() {
        Record[] array = new Record[SIZE];
        Arrays.setAll(array, i -> new Record(i / 10_000, i));
        return array;
    }

    static boolean verify(Record[] array) {
        return IntStream.range(1, array.length)
                        .allMatch(i -> array[i-1].seqNum + 1 == array[i].seqNum);
    }

    public static void main(String[] args) {
        Record[] array = genArray();
        System.out.println(verify(array));
        Arrays.sort(array);
        System.out.println(verify(array));
        Arrays.parallelSort(array);
        System.out.println(verify(array));
    }
}

En mi máquina (2 hilos x 2 hilos) esto imprime lo siguiente:

true
true
false

Por supuesto, se supone que se imprime true tres veces. Esto está en las compilaciones de desarrollo JDK 9 actuales. No me sorprendería si ocurriera en todos los lanzamientos de JDK 8 hasta ahora, dado lo que has intentado. Curiosamente, reducir el tamaño o el divisor cambiará el comportamiento. Un tamaño de 20,000 y un divisor de 10,000 es estable, y un tamaño de 50,000 y un divisor de 1,000 también es estable. Parece que el problema tiene que ver con una serie de valores suficientemente grande que compara el tamaño de división igual al paralelo.

El problema de OpenJDK JDK-8076446 cubre este error.