c++ - Diseño de algoritmos que requieren espacio de scratch

algorithm boost

Question

La biblioteca estándar de C ++ separa las estructuras de datos de los algoritmos, como con std::sort :

template< class RandomAccessIterator >
void sort( RandomAccessIterator first, RandomAccessIterator last );

Me gustaría mantener la separación de los algoritmos y las estructuras de datos cuando los algoritmos requieren un espacio de trabajo intermedio.

Con este objetivo en mente, quería implementar un algoritmo de imagen que requiera un espacio intermedio entre la imagen de entrada y de salida. Uno podría asignar el espacio de scratch necesario en la llamada de función, sin embargo, debido al tamaño y la frecuencia de estas llamadas con imágenes de tamaño idéntico, degradaría gravemente el rendimiento. Esto hace que sea mucho más difícil separar la estructura de datos del algoritmo.

Una posible forma de lograr esto es la siguiente:

// Algorithm function
template<typename InputImageView, typename OutputImageView, typename ScratchView>
void algorithm(
  InputImageView inputImageView, 
  OutputImageView outputImageView, 
  ScratchView scratchView
);

// Algorithm class with scratch space
template<typename DataStructure>
class Algorithm {
public:
  template<typename InputImageView,typename OutputImageView>
  void operator()(
  InputImageView inputImageView, 
  OutputImageView outputImageView
  ){
    m_scratch.resize(inputImageView.size());
    algorithm(inputImageView,outputImageView,makeView(m_scratch));
  }

private:
  DataStructure m_scratch;
}

¿Es lo anterior un algoritmo efectivo + un diseño de espacio de borrador a seguir, o hay una mejor manera?

Nota al margen: estoy usando la librería boost::gil

Answer 1

Como mencionaste, esta pregunta realmente puede considerarse como ir más allá de las imágenes en el espacio de scratch. De hecho, lo he encontrado en muchas formas diferentes (secciones de memoria, matrices escritas, hilos, conexiones de red, ...).

Entonces, lo que terminé haciendo fue escribirme un " BufferPool " genérico. Es una clase que administra cualquier forma de objeto de búfer, ya sea una matriz de bytes, alguna otra pieza de memoria o (en su caso) una imagen asignada. He prestado esta idea de la ThreadPool .

Es una clase bastante simple que mantiene un grupo de objetos de Buffer desde los que puede acquire un búfer cuando lo necesite y release al grupo cuando haya terminado con él. La función de acquire verificará si hay un búfer en el grupo disponible, y si no, creará uno nuevo. Si hay uno en el grupo, se reset el Buffer , es decir, se borrará para que se comporte de forma idéntica a uno recién creado.

Luego tengo un par de instancias estáticas de este BufferPool , una para cada tipo de Buffer diferente que uso: una para matrices de byte , una para matrices de caracteres, ... (Estoy codificando en Java, en caso de que se lo esté preguntando ... . :) Luego uso estas instancias estáticas en todas las funciones de biblioteca que estoy escribiendo. Esto me permite que, por ejemplo, mis funciones de criptografía puedan compartir arrays de bytes con mis funciones de aplanamiento binario, o cualquier otro código en mi aplicación. De esta manera, obtengo la máxima reutilización de estos objetos y me ha dado un gran aumento de rendimiento en muchos casos.

En C ++, es posible que pueda implementar este esquema de uso en todas partes de manera muy elegante al escribir un asignador personalizado para las estructuras de datos que necesita basándose en esta técnica de agrupación (Gracias a Andrew por señalar esto; vea los comentarios).

Una cosa que hice para mi búfer de matriz de bytes es que la función de acquire aceptará un parámetro minimumLength que especifica el tamaño mínimo del búfer que necesito. Entonces solo devolverá una matriz de bytes de al menos esta longitud del grupo, o creará uno nuevo, si el grupo está vacío o solo tiene imágenes más pequeñas. Podría utilizar el mismo enfoque con su búfer de imagen. Deje que la función de acquire acepte los parámetros minWidth y minWidth y luego devuelva una imagen de al menos estas dimensiones del conjunto, o cree una con exactamente estas dimensiones. Entonces podría hacer que la función de reset solo borre la sección (0, 0) a ( minWidth , minWidth ) de la imagen, si es que incluso la necesita borrada.

La única característica que decidí no preocuparme en mi código, pero es posible que desee considerar dependiendo de cuánto tiempo se ejecutará su aplicación y cuántos tamaños de imagen diferentes procesará es si desea limitar el tamaño del búfer de alguna manera. y libere imágenes en caché para reducir el uso de memoria de su aplicación.

A modo de ejemplo, aquí está el código que uso para mi ByteArrayPool :

public class ByteArrayPool {

    private static final Map<Integer, Stack<byte[]>> POOL = new HashMap<Integer, Stack<byte[]>>();

    /**
     * Returns a <code>byte[]</code> of the given length from the pool after clearing
     * it with 0''s, if one is available. Otherwise returns a fresh <code>byte[]</code>
     * of the given length.
     * 
     * @param length the length of the <code>byte[]</code>
     * @return a fresh or zero''d buffer object
     */
    public static byte[] acquire(int length) {
        Stack<byte[]> stack = POOL.get(length);
        if (stack==null) {
            if (CompileFlags.DEBUG) System.out.println("Creating new byte[] pool of lenth "+length);
            return new byte[length];
        }
        if (stack.empty()) return new byte[length];
        byte[] result = stack.pop();
        Arrays.fill(result, (byte) 0);
        return result;
    }

    /**
     * Returns a <code>byte[]</code> of the given length from the pool after optionally clearing
     * it with 0''s, if one is available. Otherwise returns a fresh <code>byte[]</code>
     * of the given length.<br/>
     * <br/>
     * If the initialized state of the needed <code>byte[]</code> is irrelevant, calling this
     * method with <code>zero</code> set to <code>false</code> leads to the best performance.
     * 
     * @param length the length of the <code>byte[]</code>
     * @param zero T - initialize a reused array to 0
     * @return a fresh or optionally zero''d buffer object
     */
    public static byte[] acquire(int length, boolean zero) {
        Stack<byte[]> stack = POOL.get(length);
        if (stack==null) {
            if (CompileFlags.DEBUG) System.out.println("Creating new byte[] pool of lenth "+length);
            return new byte[length];
        }
        if (stack.empty()) return new byte[length];
        byte[] result = stack.pop();
        if (zero) Arrays.fill(result, (byte) 0);
        return result;
    }

    /**
     * Returns a <code>byte[]</code> of the given length from the pool after setting all
     * of its entries to the given <code>initializationValue</code>, if one is available.
     * Otherwise returns a fresh <code>byte[]</code> of the given length, which is also
     * initialized to the given <code>initializationValue</code>.<br/>
     * <br/>
     * For performance reasons, do not use this method with <code>initializationValue</code>
     * set to <code>0</code>. Use <code>acquire(<i>length</i>)</code> instead.
     * 
     * @param length the length of the <code>byte[]</code>
     * @param initializationValue the
     * @return a fresh or zero''d buffer object
     */
    public static byte[] acquire(int length, byte initializationValue) {
        Stack<byte[]> stack = POOL.get(length);
        if (stack==null) {
            if (CompileFlags.DEBUG) System.out.println("Creating new byte[] pool of lenth "+length);
            byte[] result = new byte[length];
            Arrays.fill(result, initializationValue);
            return result;
        }
        if (stack.empty()) {
            byte[] result = new byte[length];
            Arrays.fill(result, initializationValue);
            return result;
        }
        byte[] result = stack.pop();
        Arrays.fill(result, initializationValue);
        return result;
    }

    /**
     * Puts the given <code>byte[]</code> back into the <code>ByteArrayPool</code>
     * for future reuse.
     * 
     * @param buffer the <code>byte[]</code> to return to the pool
     */
    public static byte[] release(byte[] buffer) {
        Stack<byte[]> stack = POOL.get(buffer.length);
        if (stack==null) {
            stack = new Stack<byte[]>();
            POOL.put(buffer.length, stack);
        }
        stack.push(buffer);
        return buffer;
    }
}

Y luego, en el resto de mi código donde necesito los byte[] , uso algo como:

byte[] buffer = ByteArrayPool.acquire(65536, false);
try {
    // Do something requiring a byte[] of length 65536 or longer
} finally {
    ByteArrayPool.release(buffer);
}

Tenga en cuenta cómo agregué 3 funciones de acquire diferentes que me permiten especificar qué tan "limpio" necesito que sea el búfer que estoy solicitando. Por ejemplo, si estoy sobrescribiéndolo todo, no es necesario perder tiempo en ponerlo a cero primero.

Answer 2

Creo que en tal caso, tendría el algoritmo que le permitiría pasar (una referencia o un puntero a) una estructura para el espacio de borrador, y dar a ese argumento un valor predeterminado. De esta manera, el usuario puede llamar a la función sin pasar una estructura cuando / si el tiempo adicional para asignar la estructura no es un problema, pero puede pasar uno si (por ejemplo) construye una tubería de procesamiento que puede beneficiarse de la reutilización del mismo espacio repetidamente .

Answer 3

El diseño que presenta su pregunta inicial utilizando resize() no es eficiente, ya que el cambio de tamaño puede requerir no solo la asignación, sino que también copiará el contenido existente de la asignación anterior a la nueva. También requerirá la asignación y el llenado del nuevo espacio antes de desasignar el anterior, lo que aumenta el uso máximo de memoria máximo.

Es preferible proporcionar alguna forma para que el código del cliente calcule el tamaño de la estructura que se debe proporcionar como espacio de borrador y luego afirmar que el espacio de reutilización pasado satisface las necesidades de la rutina de la biblioteca al momento de ingresar. El cálculo podría ser otro método de la clase de algoritmo, o la asignación / fábrica para el objeto de espacio reutilizable podría tomar argumentos adecuadamente representativos (tamaño / forma correctos, o los tamaños mismos) y devolver un objeto de espacio reutilizable adecuado y reutilizable.

El algoritmo de trabajo no debería tener que "manipular" el espacio desde cero para que sea adecuado una vez que se le haya pedido que lo use, ya que la manipulación puede ser costosa.

Answer 4

Si utiliza un objeto de función, puede llevar el estado que necesite.

Dos algoritmos útiles son transform y accumulate .

transform puede tomar un objeto de función para realizar la transformación en cada objeto en la secuencia:

class TransformerWithScratchSpace {
public:
    Target operator()(const Source& source);
};

vector<Source> sources;
vector<Target> targets;
targets.reserve(sources.size());

transform(sources.begin(), sources.end(),
          back_inserter<Target>(targets),
          TransformerWithScratchSpace());

accumulate puede tomar un objeto de función que acumula todos los objetos en sí mismo. El resultado es el objeto acumulado. El acumulador en sí no tiene que producir nada.

class Accumulator {
public:
    Accumulator& operator+()(const Source& source);
};

vector<Source> sources;

Accumulator accumulated = accumulate(sources.begin(), sources.end(),
                                     Accumulator());