Mapa informático: cálculo de valor por adelantado

Question

Tengo un computing map (con) que estoy utilizando para almacenar en caché los resultados de un cálculo costoso.

Ahora tengo una situación en la que sé que es probable que se busque una clave en particular en los próximos segundos. Esa clave también es más costosa de computar que la mayoría.

Me gustaría calcular el valor por adelantado, en un subproceso de prioridad mínima, de modo que cuando el valor sea finalmente solicitado, ya estará en la memoria caché, mejorando el tiempo de respuesta.

¿Qué es una buena manera de hacer esto de tal manera que:

1. tengo control sobre el hilo (en concreto su prioridad) en el que se realiza el cálculo.
2. Se evita el trabajo duplicado, es decir, el cálculo solo se realiza una vez. Si la tarea de cálculo ya se está ejecutando, el hilo llamante espera esa tarea en lugar de calcular el valor nuevamente (FutureTask implementa esto. Con los mapas informáticos de Guava esto es cierto si solo llama al get pero no si lo mezcla con llamadas al put).
3. El método "calcular el valor por adelantado" es asíncrono e idempotente. Si un cálculo ya está en curso, debe regresar inmediatamente sin esperar a que termine el cálculo.
4. Evite la inversión de prioridad, p. si un subproceso de alta prioridad solicita el valor mientras que un subproceso de prioridad media está haciendo algo que no está relacionado pero la tarea de cómputo está en cola en un subproceso de baja prioridad, el subproceso de alta prioridad no debe faltar. Quizás esto podría lograrse aumentando temporalmente la prioridad de los hilos informáticos y/o ejecutando el cálculo en el hilo de llamada.

¿Cómo podría coordinarse esto entre todos los hilos implicados?

---

Otros detalles
Los cálculos en mi solicitud son operaciones de filtrado de imágenes, lo que significa que están limitados por CPU. Estas operaciones incluyen transformaciones afines (que oscilan entre 50 μs y 1 ms) y convoluciones (hasta 10 ms). Por supuesto, la efectividad de las distintas prioridades de subprocesos depende de la capacidad del sistema operativo para adelantarse a las tareas más grandes.

Answer 1

Puede organizar la ejecución "una sola vez" de la computación en segundo plano utilizando un Futuro con ComputedMap. El futuro representa la tarea que calcula el valor. El futuro es creado por ComputedMap y, al mismo tiempo, pasó a ExecutorService para la ejecución en segundo plano. El ejecutor se puede configurar con su propia implementación ThreadFactory que crea subprocesos de baja prioridad, p.

class LowPriorityThreadFactory implements ThreadFactory 
{ 
    public Thread newThread(Runnable r) { 
    Tread t = new Thread(r); 
    t.setPriority(MIN_PRIORITY); 
    return t; 
    } 
} 

Cuando se necesita el valor, el hilo de alta prioridad, entonces va a buscar el futuro en el mapa, y llama al método get() para recuperar el resultado, esperando a que se puede calcular si es necesario. Para evitar priority inversion se agrega algo de código adicional para la tarea:

class HandlePriorityInversionTask extends FutureTask<ResultType> 
{ 
    Integer priority; // non null if set 
    Integer originalPriority; 
    Thread thread; 
    public ResultType get() { 
     if (!isDone()) 
     setPriority(Thread.currentThread().getPriority()); 
     return super.get(); 
    } 
    public void run() { 
     synchronized (this) { 
     thread = Thread.currentThread(); 
     originalPriority = thread.getPriority(); 
     if (priority!=null) setPriority(priority); 
     } 
     super.run(); 
    } 
    protected synchronized void done() { 
     if (originalPriority!=null) setPriority(originalPriority); 
     thread = null; 
    } 

    void synchronized setPriority(int priority) { 
     this.priority = Integer.valueOf(priority); 
     if (thread!=null) 
      thread.setPriority(priority); 
    } 
} 

Este se encarga de elevar la prioridad de la tarea a la prioridad del subproceso de llamada get() si la tarea no se ha completado, y devuelve la prioridad a la original cuando la tarea se completa, normalmente o de otra manera. (Para mantenerlo breve, el código no comprueba si la prioridad es mayor, pero eso es fácil de agregar.)

Cuando la tarea de alta prioridad llama a get(), es posible que el futuro aún no haya comenzado a ejecutarse. Puede que tengas la tentación de evitar esto estableciendo un límite superior grande en el número de subprocesos utilizados por el servicio del ejecutor, pero puede ser una mala idea, ya que cada subproceso se puede ejecutar con alta prioridad, consumiendo tanta CPU como sea posible antes el SO lo desconecta El grupo probablemente debería tener el mismo tamaño que el número de subprocesos de hardware, p. dimensione el grupo al Runtime.availableProcessors(). Si la tarea no ha comenzado a ejecutarse, en lugar de esperar a que el ejecutor la programe (que es una forma de inversión de prioridad, dado que su subproceso de alta prioridad está esperando que se completen los subprocesos de baja prioridad), puede optar por cancelarlo el ejecutor actual y vuelva a enviarlo a un ejecutor que ejecuta solo subprocesos de alta prioridad.

Answer 2

Una forma común de coordinar este tipo de situaciones es tener un mapa cuyos valores sean objetos FutureTask. Entonces, robando como ejemplo algún código que escribí de un servidor web mío, la idea esencial es que para un parámetro dado, vemos si ya hay un FutureTask (lo que significa que el cálculo con ese parámetro ya ha sido programado), y si es así lo esperamos. En este ejemplo, que de otro modo la Lista de las operaciones de búsqueda, pero que se podría hacer en otro lugar con una llamada independiente si era deseable:

private final ConcurrentMap<WordLookupJob, Future<CharSequence>> cache = ... 

    private Future<CharSequence> getOrScheduleLookup(final WordLookupJob word) { 
    Future<CharSequence> f = cache.get(word); 
    if (f == null) { 
     Callable<CharSequence> ex = new Callable<CharSequence>() { 
     public CharSequence call() throws Exception { 
      return doCalculation(word); 
     } 
     }; 
     Future<CharSequence> ft = executor.submit(ex); 
     f = cache.putIfAbsent(word, ft); 
     if (f != null) { 
     // somebody slipped in with the same word -- cancel the 
     // lookup we've just started and return the previous one 
     ft.cancel(true); 
     } else { 
     f = ft; 
     } 
    } 
    return f; 
    } 

en términos de prioridades de los hilos: Me pregunto si esto va a lograr lo que creo que sí? No entiendo muy bien su punto sobre elevar la prioridad de la búsqueda por encima del hilo de espera: si el hilo está esperando, está esperando, cualesquiera que sean las prioridades relativas de otros hilos ... (Es posible que desee echar un vistazo a algunos artículos que he escrito en thread priorities y thread scheduling, pero para abreviar, no estoy seguro de que cambiar la prioridad necesariamente le compre lo que está esperando.)

Answer 3

Sospecho que se dirige hacia abajo camino equivocado al enfocarse en las prioridades de la secuencia.Por lo general, los datos que contiene una caché son caros de computar debido a la E/S (datos de falta de memoria) frente a la CPU vinculada (cálculo lógico). Si está captando previamente para adivinar la acción futura de un usuario, como mirar correos electrónicos no leídos, entonces me indica que su trabajo probablemente esté vinculado a E/S. Esto significa que mientras no se produzca la inanición de subprocesos (que los planificadores no permiten), jugar juegos con prioridad de subprocesos no ofrecerá una gran mejora en el rendimiento.

Si el costo es una llamada de E/S, el hilo de fondo se bloquea esperando a que lleguen los datos y procesando los datos que deberían ser bastante baratos (por ejemplo, deserialización). Como el cambio en la prioridad de subprocesos no ofrecerá mucha aceleración, realizar el trabajo asincrónicamente en el subproceso de subprocesos en segundo plano debería ser suficiente. Si la penalización por falta de caché es demasiado alta, el uso de varias capas de almacenamiento en memoria caché tiende a ayudar a reducir aún más la latencia percibida por el usuario.

Answer 4

Como alternativa a las prioridades de subprocesos, puede realizar una tarea de baja prioridad solo si no hay tareas de alta prioridad en progreso. Aquí está una manera simple de hacer que:

AtomicInteger highPriorityCount = new AtomicInteger(); 

void highPriorityTask() { 
    highPriorityCount.incrementAndGet(); 
    try { 
    highPriorityImpl(); 
    } finally { 
    highPriorityCount.decrementAndGet(); 
    } 
} 

void lowPriorityTask() { 
    if (highPriorityCount.get() == 0) { 
    lowPriorityImpl(); 
    } 
} 

En el caso de uso, tanto Impl() métodos llamarían get() en el mapa de computación, highPriorityImpl() en el mismo hilo y lowPriorityImpl() en un hilo diferente .

Puede escribir una versión más sofisticada que difiera las tareas de baja prioridad hasta que se completen las tareas de alta prioridad y limite el número de tareas concurrentes de baja prioridad.