对象定向、数据定向、缓存污染和缓存明显性



在常规的面向对象实践中,稀有对象并不是具有多个不相关的成员属性。当处理对象时,在不同的过程中进行处理并不罕见,这些过程针对对象属性的不同部分。

在这方面,创建对象集合的典型方法似乎不是很有效。考虑到计算机访问内存的方式和缓存线的平均大小,缓存内存很有可能被不需要的东西填满,但恰好是相邻的,所以它最终浪费了缓存的容量,并增加了执行的停滞和延迟。

更糟糕的是,在没有内存池和自定义分配器的情况下,使用多态性和动态分配对象的做法。在这种情况下,不仅缓存中充满了不需要的数据,而且由于动态内存分配使用的任意地址,预取器也无法正常工作。

拯救之道是回到OOP之前的时代,选择面向数据,这似乎是开发性能关键型应用程序、操作系统等的首选。但为什么不使用两者的混合版本呢?有点像面向数据的对象编程?

在那漫长的序曲之后,让我们进入手头的问题。我没有一个足够大的项目来测试这个概念的效率,所以社区的理论专业知识非常受欢迎。

对象不存储自己的数据成员,而是只存储对集合的引用,在集合中,它们的数据成员按顺序存储在自己的容器中,并且它们的成员方法从这些容器返回数据,这样,不需要的数据最终到达CPU的几率应该会降低,而在不久的将来需要的数据的几率会增加。逻辑假设是,这种方法将提高预取器的效率、缓存命中率和使用效率,还将减少自动和手动并行化中的延迟。

你觉得怎么样?

后期编辑:如果我们考虑到结构和类填充,应用"数据定向模式"可能会更有益,如果"模型"有一个char和一个int数据成员,以OOP方式,它将被填充,这只会进一步污染缓存,但面向数据的存储模式可以顺序存储所有char和所有int,而不会浪费任何空间和缓存。

首先,很好的幻灯片演示。好吧,正如我所理解的,你的问题与刚才的陈述大不相同。变量随机存储在主内存中,甚至对象属性也是如此。如果你试图将内存分配给连续的数据结构,你的数据结构的大小将受到主内存中最大的"气泡"的限制,否则它就不会是纯连续的。也许你有这样的想法:

class MyClass
{
public:
MyClass()
{
m_dataMembers = new GenericObject[DATA_MEMBERS_AMOUNT];
//initialize array values...
}
int getMyVar()
{
return (int)m_dataMembers[MY_VAR_INDEX];
}
//others functions...
private:
GenericObject* m_dataMembers;
}

这样,你会遇到一些问题。首先,您将需要一个通用对象类来存储任何类型的变量。然后,您需要知道每个变量在数据结构中的位置,然后您需要知道数据结构中每个变量的类型,以便在getter中正确转换。他在演示中实际做的是减少类的大小,使用引用,使其更好地适合缓存页面,并减少缓存中的使用,而不是主内存中的使用。我希望我没有误解你。

我认为,如果在非常精细的细粒度对象级别(如抽象的IPixel接口)使用多态性,那么对象级别的多态性本身就很昂贵。在这种情况下,从效率的角度来看,围绕IPixel依赖关系的视频处理软件将非常糟糕,因为它没有优化的喘息空间。除了每个像素的动态调度成本外,即使这里需要的虚拟指针也可能比整个像素本身大,从而使内存使用量增加一倍或三倍。此外,我们不能再以超越单个像素的方式处理像素表示,而且,最可怕的是,图像中的相邻像素甚至可能在内存中无法连续表示。

同时,IImage可以提供足够的优化空间,因为图像对像素的集合/容器进行建模,并且仍然具有足够的灵活性(例如:每个像素格式都有不同的具体图像表示)。现在,每个图像的动态调度很便宜,并且虚拟指针的大小对于整个图像来说可以忽略不计。我们还可以探索如何以一次有效处理多个像素的方式来表达像素。所以我认为,和你一样,这是一个以适当的粗糙度设计对象的问题,这通常意味着事物的集合,以减少所有的开销和优化的障碍。

对象不是存储自己的数据成员,而是仅存储对集合的引用,其中集合的数据成员按顺序存储在各自的容器中,并且其成员方法从这些容器返回数据,这样应该减少最终到达CPU的不需要的数据,并且在不久的"未来"需要的数据的可能性增加了。

我喜欢这个想法,但如果你对多态上下文做得太过分,你可以重新使用自定义内存分配器和排序基指针。我经常发现这种设计的用途是在需要聚合单个元素以提高效率的情况下提高使用单个元素的便利性(一种情况是使用SoA表示将其放入容器中,另一种情况我将在下面介绍)。

多态的情况不一定有那么大的好处,因为固有的问题在于一次一个地处理粒度事物的非齐次。为了恢复效率,我们必须恢复关键回路的均匀性。

非齐次临界循环

Orc继承CreatureHuman继承CreatureElf继承Elves为例,但人类、兽人和精灵有不同的大小/字段、不同的对齐要求和不同的vtables。在这种情况下,当客户端代码想要处理它们的非同质列表时,这些列表存储了指向如下生物的多态基指针:

for each creature in creatures:
creature.do_something();

与此相反,这将牺牲多态性:

for each orc in orcs:
orc.do_something();
for each human in humans:
humans.do_something();
for each elf in elves:
elves.do_something();

如果我们每次引入一种新型生物时都需要在很多地方这样做,这将是一个真正的PITA扩展。。。

那么,如果我们想保持多态解,但仍然以非均匀的方式一次处理每个生物,那么无论每个生物是否只是存储一个指向容器的后向指针,我们最终都会失去时间和空间位置。我们失去了vtable的时间局部性,因为我们可能在一次迭代中访问一个vtable,然后在下一次迭代访问另一个vtable。这里的内存访问模式也可能是随机和偶发的,导致空间局部性的丢失,因此我们最终会出现大量缓存未命中。

因此,在这种情况下,如果您想要继承和多态性,我的解决方案是在容器级别进行抽象:Orcs继承CreaturesHumans继承CreaturesElves继承了Creatures。当客户端想要表达对特定生物执行的操作时,这会将一些额外的复杂性转移到客户端代码中,但现在上面的顺序循环可以这样写:

for each creatures in creature_types:
creatures.do_something();

在第一次迭代中,这可能会对整个兽人列表(可能就像存储在阵列中的一百万个兽人)产生影响。现在,该列表中的所有兽人都可以连续存储,我们正在将同质功能应用于该列表中所有兽人。在这种情况下,在不改变设计的情况下,我们有大量的喘息空间需要优化。

我们仍然有一个利用多态性的非同质循环,但现在它非常便宜,因为我们只为整个生物容器支付开销,而不是为每一个单独的生物支付开销。处理单个生物的循环现在是同质的。这类似于使用抽象IImage来提亮一组图像(一组像素容器),而不是一次对一个实现IPixel的抽象像素对象进行提亮。

齐次循环和表示

因此,这将繁重的关键循环从一次处理来自各地的各种不同数据的非同质循环转移到处理连续存储的同质数据的同质循环。

这是我对界面设计的一个总体策略。如果它倾向于以难以优化的方式产生热点,那么我认为的固有问题是接口的设计过于精细(Creature,而不是Creatures)。

因此,如果希望利用OOP,我认为这就是解决这个问题的方法。我认为你的设计思想可能有用的地方是简化客户端代码必须表达仅适用于一个特定生物的操作的情况,在这一点上,他们可以通过某种指向容器的代理对象工作,并可能存储指向特定条目的索引或指针,如引用抽象CCD_ 25容器之一中的特定条目的CCD_。

最新更新