Qué cola de bloqueo de Java es más eficiente para escenarios de consumidor único de un solo productor

Question

Estoy trabajando en un sistema Java estándar con requisitos críticos de temporización para mis productores (1/100s de asuntos de ms).

Tengo un productor colocando cosas en una cola de bloqueo, y un solo consumidor más tarde recogiendo esas cosas y volcándolas en un archivo. El consumidor bloquea cuando los datos no están disponibles.

Obviamente, la cola de bloqueo es la interfaz adecuada, pero ¿qué implementación real debo elegir si quiero minimizar el costo para el productor? Quiero jugar lo menos posible en cosas como bloquear y asignar cuando estoy poniendo cosas en la cola, y no me importa si el consumidor tiene que esperar mucho más tiempo o trabajar mucho más duro.

¿Existe una implementación que puede ser más rápida porque solo tengo un solo consumidor y un único productor?

Answer 1

Bueno, realmente no hay demasiadas opciones. Déjame ir a través de la listed subclasses:

DelayQueue, LinkedBlockingDeque, PriorityBlockingQueue y SynchronousQueue todos estamos hechos para casos especiales que requieren una funcionalidad adicional; no tienen sentido en este escenario.

Eso deja solo ArrayBlockingQueue y LinkedBlockingQueue. Si sabe cómo saber si necesita ArrayList o LinkedList, probablemente pueda contestar esta usted mismo.

Tenga en cuenta que en LinkedBlockingQueue, "los nodos vinculados se crean dinámicamente en cada inserción"; esto puede tender a empujarlo hacia ArrayBlockingQueue.

Answer 2

Si los requisitos de tiempo son tan ajustados, probablemente necesite realizar una evaluación comparativa exhaustiva en exactamente el mismo hardware para determinar el mejor ajuste.

Si tuviera que adivinar, iría con ArrayBlockingQueue porque las colecciones basadas en arreglos tienden a tener una buena localidad de referencia.

Answer 3

LinkedBlockingQueue tendrá un costo de inserción O (1) a menos que haya un retraso en la asignación de la memoria. Un muy grande ArrayBlockingQueue tendrá un costo de inserción O (1) a menos que el sistema esté bloqueado debido a una recolección de basura; sin embargo, bloqueará el inserto cuando esté en capacidad.

Incluso con la recolección de basura simultánea no estoy seguro de si debe escribir un sistema en tiempo real en un lenguaje administrado.

Answer 4

ArrayBlockingQueue probablemente sea más rápido ya que no es necesario crear nodos de enlace en la inserción. Sin embargo, tenga en cuenta que ArrayBlockingQueue tiene una longitud fija, si desea que su cola crezca arbitrariamente grande (al menos en Integer.MAX_INT) tendrá que usar un LinkedBlockingQueue (a menos que desee asignar una matriz de elementos Integer.MAX_INT) .

Answer 5

Estoy de acuerdo con la observación de Andrew Duffy de que la implementación de un sistema tan limitado en Java puede ser un error. De todos modos, suponiendo que esté casado con la JVM, y no espera que esta cola se ejecute por completo (es decir, el consumidor pueda manejar la carga), creo que lo mejor sería una implementación personalizada, similar a una ArrayBlockingQueue pero recortado/optimizado para el escenario de productor único/consumidor. En particular, me gusta la idea de girar en el lado del productor para esperar espacio, en lugar de bloquear.

Me referí a la java.sources concurrente como guía, y redactó este algoritmo ...

Me parece bastante bueno, pero no está probado y puede que no sea más rápido en la práctica (probablemente no revolucionario, pero lo inventé yo mismo: -) Me divertí mucho con eso, de todos modos ... ¿Puedes encontrar un defecto?

Pseudocódigo:

private final ReentrantLock takeLock = new ReentrantLock(); 
private final Condition notEmpty = takeLock.newCondition(); 
private final E[] buffer; 
private int head = 0 
private int tail = 0; 

public void put(E e) { 
    if (e == null) throw NullPointerException(); 

    while (buffer[tail] != null) { 
    // spin, wait for space... hurry up, consumer! 
    // open Q: would a tight/empty loop be superior here? 
    Thread.sleep(1); 
    } 

    buffer[tail] = e; 
    tail = (tail + 1) % buffer.length; 

    if (count.getAndIncrement() == 0) { 
    sync(takeLock) { // this is pseudocode -- should be lock/try/finally/unlock 
     notEmpty.signal(); 
    } 
    } 
} 

public E take() { 
    sync(takeLock) { 
    while (count.get() == 0) notEmpty.await(); 
    } 
    E item = buffer[head]; 
    buffer[head] = null; 
    count.decrement(); 
    head = (head + 1) % buffer.length; 

    return item; 
} 

Answer 6

Puede escribir un sistema sensible latencia en Java, pero hay que tener cuidado con las asignaciones de memoria, la información que pasa entre los hilos y de bloqueo. Debe escribir algunas pruebas simples para ver cuánto tiempo cuestan estas cosas en su servidor. (Varían según el sistema operativo y la arquitectura de memoria)

Si hace esto, puede obtener tiempos estables para operaciones de hasta el 99.99% del tiempo. Esto no es correcto en tiempo real, pero puede ser lo suficientemente cerca. En un sistema de comercio, usar Java en lugar de C puede costar £ 100/d, sin embargo, el costo de desarrollar en C/C++ en lugar de Java es probable que sea mucho más alto que esto. p.ej. en términos de la flexibilidad que nos brinda y la cantidad de errores que guarda.

Puede acercarse bastante a la misma cantidad de fluctuación que vería en un programa C haciendo lo mismo. Algunos lo llaman Java "C-like".

Desafortunadamente, se tarda unos 8 microsegundos en pasar un objeto entre subprocesos en Java a través de ArrayBlockingQueue en los servidores en los que trabajo y le sugiero que pruebe esto en sus servidores. Una prueba simple es pasar el System.nanoTime() entre los hilos y ver cuánto tiempo lleva.

ArrayBlockingQueue tiene una "característica" donde se crea un objeto en cada elemento agregado (aunque no hay muchas buenas razones para hacerlo) Así que si encuentra una implementación estándar que no hace esto, hágamelo saber .

Answer 7

Puede examinar el uso de LinkedTransferQueue, que implementa "Cola dual con holgura" y es bueno para combinar Productores y Consumidores. véase el siguiente para más detalles Java 7 TransferQueue, Dual Synchronous Queues (.pdf) y LinkedTransferQueue source