设计需要临时存储空间的算法

16

C++标准库将数据结构和算法分开,例如使用std::sort:

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

我希望在算法需要中间临时空间时,仍然能够保持算法和数据结构的分离。

考虑到这一目标,我想要实现一个需要在输入和输出图像之间使用中间临时空间的图像算法。虽然可以在函数调用中分配所需的临时空间,但由于使用相同大小的图像进行多次调用,这将严重降低性能。这使得从算法中分离数据结构变得更加困难。

实现这一目标的一种可能方法如下:

// 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;
}

上述算法和临时空间设计是否有效,或者有更好的方法?

顺便提一句:我正在使用boost::gil库。


1
通常的方法是为算法提供一个通用数据结构的接口,而不指定该数据结构的实现方式。例如,如果您的算法需要一个队列,请传入具有push()pop()peek()函数的IQueue;实际的实现可以是链表、堆或其他任何数据结构。 - BlueRaja - Danny Pflughoeft
2
至少在C语言中,更常见的是有一个“itch”函数告诉你需要传递多大的刮擦空间,但依赖于调整大小的函数看起来也可以。 - Marc Glisse
什么是临时空间? - AlexWien
@AlexWien 在计算或算法中使用的临时内存,不属于输入或结果的一部分。也许有更好的词或描述吗? - Andrew Hundt
我认为从语义上讲,Scratch空间是算法的一部分,而不是数据结构。 - salezica
4个回答

3

我认为在这种情况下,我会让算法允许您传递(引用或指针)一个结构体作为临时空间,并给该参数设置默认值。这样用户可以在不需要分配结构体的额外时间时调用函数,但是如果正在构建可以从反复重用相同空间中受益的处理管道,他们可以传递一个结构体。


我相信我问题中的设计示例遵循了您在答案中提倡的设计,对吗? - Andrew Hundt
@AndrewHundt:是的,看起来你添加的内容实现了我所描述的。 - Jerry Coffin

2
如果使用函数对象,你可以携带任何需要的状态。
两个有用的算法是transform和accumulate。
transform可以采用函数对象对序列中的每个对象执行转换: transform
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" 可以接受一个函数对象,将所有的对象累加到其中。结果是累加后的对象。累加器本身不必产生任何东西。
class Accumulator {
public:
    Accumulator& operator+()(const Source& source);
};

vector<Source> sources;

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

问题在于你不知道转换中当前元素的位置,那么你如何访问缓存的值呢?也就是说,对于任何正在操作的N个值,在中间步骤也有N个值被存储,因此在每一步变换中都需要知道中间缓存中的位置。也许我错过了什么? - Andrew Hundt
这个想法是你有一批图像并希望对每个图像应用相同的转换,而不必为每个图像重新分配一个临时空间;你可以重复使用这个临时空间。你是在谈论对一张图片应用多个转换吗? - Peter Wood
实际上,对于单个图像执行多个变换以及处理多个图像。但是,并非所有图像都同时可用。想象一下,从网络摄像头中获取每个图像并对其运行多个变换。 - Andrew Hundt
对于每个图像,您想要生成一个输出图像还是多个图像?变换是否始终相同?您是否想要组合使用相同的临时空间的变换管道? - Peter Wood
是的,我正在组合一系列的转换操作,并且这些转换操作始终相同。对于每个输入图像,在管道的不同步骤中会产生一个或多个输出图像,然后将这些中间结果组合成最终结果。这个管道会在每个输入图像到达时运行一次,因此只需要分配一次中间图像,这样效率更高。 - Andrew Hundt

1
正如你所提到的,这个问题实际上可以被看作远远超出了scratch空间中的图像。我实际上在许多不同形式中遇到过这个问题(内存部分、类型化数组、线程、网络连接等)。
所以我最终写了一个通用的"BufferPool"。它是一个管理任何形式的缓冲区对象的类,无论是字节数组、其他一些内存片段,还是(在您的情况下)已分配的图像。我从ThreadPool借鉴了这个想法。
这是一个相当简单的类,它维护一个Buffer对象池,您可以在需要时acquire一个缓冲区,并在使用完后将其release回池中。acquire函数将检查是否有可用的缓冲区在池中,如果没有,将创建一个新的。如果池中有一个缓冲区,它将resetBuffer,即清除它,使其行为与新创建的缓冲区相同。
我有几个静态实例的这个BufferPool,每种不同类型的缓冲区使用一个:一个用于字节数组,一个用于字符数组,...(我在Java中编码,如果你想知道的话... :) 然后我在我编写的所有库函数中使用这些静态实例。例如,这使我的加密函数可以与我的二进制平坦化函数共享字节数组或应用程序中的任何其他代码。这样,我可以最大限度地重用这些对象,并在许多情况下给我带来了主要性能提升。

在C++中,您可以通过编写基于此池技术的数据结构的自定义分配器来非常优雅地实现此处处使用方案(感谢Andrew指出;请参见评论)。

我为字节数组缓冲区做的一件事是,acquire函数将接受一个minimumLength参数,指定我所需的缓冲区的最小大小。如果池中只有较小的图像或者池为空,它将仅返回至少具有此长度的字节数组,或创建一个新的字节数组。您可以使用相同的方法来处理您的图像缓冲区。让acquire函数接受minWidthminHeight参数,然后从池中返回至少具有这些尺寸的图像,或创建一个恰好具有这些尺寸的图像。然后,如果您需要清除它,您可以让reset函数仅清除图像的(0, 0)到(minWidth, minHeight)部分。

我在我的代码中决定不担心的一个功能,但您可能要考虑根据您的应用程序运行时间和要处理的不同图像大小的数量是否希望限制缓冲区大小,并释放缓存图像以减少应用程序的内存使用。

这里只是一个示例,这是我用于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;
    }
}

然后,在我需要 byte[] 的所有代码中,我使用类似以下的内容:

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

注意,我添加了3个不同的acquire函数,使我能够指定我请求的缓冲区需要多么“干净”。例如,如果我总是覆盖它,那么没有必要浪费时间先清零它。

这种方式与为您的使用情况编写自定义分配器相比如何更高效?我猜编写Java中的自定义分配器可能并不像在C++中那样简单,因为Java是垃圾收集的。 - Andrew Hundt
@AndrewHundt 我对C++并不是很熟悉,所以我不知道自定义分配器的概念。我认为这并不比自定义分配器更有效率,相反,我会说这可能是实现自定义分配器的一种方式。在你的情况下,我建议你这样做! ;) 让我知道我是否正确理解了这个概念,以及这是否有意义。然后我可以在我的答案中具体提到“自定义分配器”关键字。 - Markus A.
是的,对于像这样特定用例的C++性能改进来说,自定义分配器确实是有意义的。从您和其他回答中看来,我在原始问题中提出的设计是一个好的设计,此外为特定用例和性能优化定制分配器也是有意义的。请记住,原始问题更多地与设计相关,而不是性能,尽管性能很重要。这里是关于C ++中分配器的描述:http://en.cppreference.com/w/cpp/concept/Allocator - Andrew Hundt
@AndrewHundt:感谢您提供的参考!这是一个非常有趣的概念。我更新了我的答案,包括这个想法。我想知道Java是否有类似的东西...很有趣,我想当涉及编码时,我还是有点老派。对我来说,性能问题几乎总是在很大程度上决定设计,除非它真正影响可维护性。回到80386风靡一时的时候,没有太多空间用于“概念上清晰和可维护”的编码,而今天这种编码方式迫使每个人都购买最新的硬件才能运行扫雷游戏而不掉帧!;) - Markus A.

1
你的初始问题使用 resize() 的设计并不高效,因为调整大小可能不仅需要分配,还需要将现有内容从旧分配复制到新分配。它还需要在释放旧空间之前分配和填充新空间,增加最大峰值内存使用量。
更好的方法是提供某种方式让客户端代码计算必须提供多大的结构作为临时空间,然后断言传递的临时空间在进入库例程时满足其需求。计算可以是算法类的另一种方法,或者是临时空间对象的分配/工厂可以采用适当代表性的参数(正确的大小/形状或大小本身),并返回一个合适且可重复使用的临时空间对象。
一旦被要求使用,工作算法就不应该以任何方式“操作”临时空间,因为这种操作很可能是昂贵的。

如果工作的尺寸集很小,可以为每个尺寸创建单独的算法对象。如果没有,那么resize()肯定是低效的。然而,如果需要对象的大小来执行算法,则处理临时对象会很困难。也许有一种我没有想到的方法可以轻松分配更大的尺寸并仅使用其中的一部分? - Andrew Hundt
算法为什么要依赖于临时对象的大小,除了它足够大之外?临时对象应该只包含足够的空间,以便算法根据其需要进行分配。 - Phil Miller
如果一个对象正在被使用,你可能只能用单个分配来表示单个大小。例如,在不同大小的图像上访问begin()和end()可能需要更改对象的大小。在我的情况下,大小不会改变,所以这不是一个问题,但对于更一般的问题,它确实适用。 - Andrew Hundt

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接