提问人：sbi 提问时间：6/28/2013 最后编辑：sbi 更新时间：1/22/2015 访问量：364
选择任何一个环路作为外环路有什么优势吗？
Is there an advantage in choosing either loop as an outer loop?
问：
我正在扩展现有的日志记录库。它是一个具有两个侧面的系统：前端是任务将其日志消息写入其中的位置，后端是应用程序可以插入侦听器的地方，侦听器将这些消息转发到不同的接收器。后端曾经是一个硬连线侦听器，我现在正在扩展它以提高灵活性。该代码专门用于嵌入式设备，其中高性能（以每毫秒转发的字节数来衡量）是一个非常重要的设计和实现目标。
出于性能原因，消息是缓冲的，转发是在后台任务中完成的。该任务从队列中获取一大块消息，将它们全部格式化，然后通过注册的函数将它们传递给侦听器。这些侦听器将筛选消息，并且只会将通过筛选条件的消息写入其接收器。
鉴于此，我最终拥有通知函数（侦听器）来发送消息，这是一个相当经典的问题。现在我有两种可能性：我可以遍历消息，然后遍历将消息传递给每个消息的通知函数。NMN*M
for(m in formatted_messages)
for(n in notification_functions)
n(m);
void n(message)
{
if( filter(message) )
write(message);
}
或者我可以遍历所有通知函数，并一次将我拥有的所有消息传递给它们：
for(n in notification_functions)
n(formatted_messages);
void n(messages)
{
for(m in messages)
if( filter(m) )
write(m);
}
关于哪种设计更有可能允许每个时间片处理更多消息，是否有任何基本考虑因素？（请注意，这个问题如何确定侦听器的接口。这不是一个微优化问题，而是一个关于如何进行不影响性能的设计的问题。我只能在很久以后进行测量，然后重新设计侦听器界面将成本高昂。
我已经做了一些考虑：
- 这些侦听器需要在某处写入消息，这相当昂贵，因此函数调用本身在性能方面可能不太重要。
- 在 95% 的情况下，只有一个侦听器。
答：
9赞
Reed Copsey
6/28/2013
#1
关于哪种设计更有可能允许每个时间片处理更多消息，是否有任何基本考虑因素？
一般来说，主要考虑因素通常归结为两件主要事情。
如果其中一个循环正在循环可能具有良好内存局部性的对象（例如循环访问值数组），则将该部分保留在内部循环中可能会将对象保留在 CPU 缓存中，并提高性能。
如果您计划尝试并行化操作，则在外层循环中保留“较大”（就计数而言）集合可以有效地并行化外层循环，并且不会导致线程过度订阅等。在外部级别并行化算法通常更简单、更干净，因此，如果以后有可能的话，在外部循环处设计具有潜在更大的并行工作“块”的循环可以简化这一点。
这些侦听器需要在某处写入消息，这相当昂贵，因此函数调用本身在性能方面可能不太重要。
这可能会完全否定将一个循环移出另一个循环的任何好处。
在 95% 的情况下，只有一个侦听器。
如果是这种情况，我可能会将侦听器循环放在外部范围，除非您计划并行化此操作。鉴于这将在嵌入式设备上的后台线程中运行，并行化是不可能的，因此将侦听器循环作为外部循环应该会减少整体指令计数（它实际上变成了 M 个操作的循环，而不是单个操作的 M 个循环）。
评论
0赞
sbi
6/28/2013
回复#1：“对象”主要是字符串加上一些元数据（、、时间戳等），但我目前的方法是在后台任务中将它们转换为字符串（“格式化”），而不是在侦听器中单独转换。所以基本上“对象”是普通的字符缓冲区（通常在 0.1-1kB 之间）。您如何看待 char 缓冲区的位置？回复 #2：并行化难道不需要我将消息转发到并行工作任务吗——这正是我目前遇到的问题？__FILE____LINE__MN
0赞
Reed Copsey
6/28/2013
@sbi 如果它们是字符缓冲区，则不会有太多的局部性。基本上，如果有任何大的东西，或者使用指针（甚至在内部），图形局部性就会消失。如果字符缓冲区的大小是恒定的，并且存储在数组中，则可能存在局部性，但同样，在这种情况下，侦听器正在执行 IO 的事实可能意味着在这种情况下它真的无关紧要。
0赞
tmyklebu
6/28/2013
#2
没有任何“根本”原因可以解释为什么一个设计比另一个更好。根据库的使用方式，可能会有一些非常小的速度差异。我个人更愿意先迭代侦听器，然后再迭代消息。
我猜处理程序的主体通常非常快。您可能希望将侦听器作为外部循环进行迭代，以便重复调用相同的代码。像间接呼叫预测这样的东西会更好地工作。当然，您最终会更糟糕地使用数据缓存，但希望每个消息缓冲区都足够小，可以轻松放入 L1。
为什么不让听众也接受一个，让他们做自己的迭代呢？它们可以做任何有益的缓冲，并且最后只做一次昂贵的写入。const vector<message> &
评论
0赞
sbi
6/28/2013
无论我在哪里写或，那么这可能是一个缓冲区。（不过我没有使用。每个缓冲区为 1k，但通常消息使用 <0.1k。如果通过“处理程序主体”来指代侦听器，那么，不，考虑到需求，他们并不是真的很快。写入内部闪存的速度非常慢（~100ms），以至于我们使用 NVRAM 作为现金，并从那里将另一个后台任务复制到闪存......messagesformatted_messagesstd::vectorstd::string
2赞
Mats Petersson
6/28/2013
#3
因此，这里将有几个因素：
缓存中的消息之间的距离有多近，它们占用了多少空间？如果它们相对较小（几千字节或更少）并且靠得很近（例如，在执行大量其他内存分配的系统中，不是间隔几秒钟分配内存的链表）。
如果它们很接近，而且很小，那么我相信第二种选择更有效，因为消息将被预取/缓存在一起，其中调用所有侦听器和过滤器函数（也假设有很多函数，而不是一个、两个或三个）可能会导致更多“缓存抛出”以前的消息。当然，这也取决于侦听器和过滤器函数的实际复杂程度。他们做了多少工作？如果每个函数都做了相当多的工作，那么你执行它的顺序可能并不那么重要，因为它只是边缘的。n
评论
0赞
tmyklebu
6/28/2013
分支目标预测器似乎讨厌从同一指令调用许多不同的函数时。但是，是的，正如您所指出的，在良好的数据缓存使用率和充分利用 CPU 之间需要权衡。
0赞
sbi
6/28/2013
Messages are cut off at 1k, but 99.9% of them are 0.1k max anyway. They are stored in dynamically allocated buffers (1k each) that (usually) are not freed, but recycled. I could write an allocator that allocates a hole chunk of those buffers to improve their locality, but since in the frontend they're consumed by parallel threads, they end up scrambled anyway, which screws their locality, so I don't think this would buy me much. As I wrote, usually (99%) it's one function, and more then two should be extremely rare. (Of course, it could be users use it in unpredicted ways.)
5赞
David Rodríguez - dribeas
6/28/2013
#4
The order of the loops will probably have much less of an advantage than the change in the signature of the listener (note that whichever loop is outside, the listener could maintain the first interface, i.e. both loops can be in the caller).
The natural advantage of the second interface (i.e. sending a sequence of messages to each listener) is that you enable possible grouping on the implementation of the listener. For example, if writing to a device, the listener can pack multiple messages into a single , while if the interface takes a single message, then either the listener caches (which has a memory and cpu cost) or needs to perform multiple one per call.writewrites
评论
0赞
sbi
6/28/2013
Coalescing message write operations in the listeners is a very important consideration I hadn't thought of. Thanks for making this observation!
评论
N*M