选择哪个循环作为外层循环有什么优势吗？

Question

我正在扩展一个现有的日志库(logging library)。它是一个有两个方面的系统: 前端是任务将其日志消息写入的地方，后端是应用程序可以插入侦听器(forward those messages to different sinks)的地方。后端过去只有一个硬连线的监听器，我现在正在扩展它以实现灵活性。该代码将被专门用于嵌入式设备，其中高性能（以每毫秒转发的字节数衡量）是非常重要的设计和实现目标。

出于性能原因，消息被缓冲，并且在后台任务中进行转发。该任务从队列中获取一块消息，所有格式化后将它们传递给已注册的函数通过侦听器。这些侦听器会过滤(filter)消息，并且只会将通过筛选条件的消息写入到其汇流处。

鉴于此，我最终需要向N个通知函数(侦听器)发送M条消息，这是一个相当经典的N*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％只会有一个侦听器。

- sbi

---

有些东西告诉我，将循环选择为外部循环（即首先循环函数，然后再循环消息）可能会更有效率，但也许这只是错误的直觉，你甚至不应该听我的建议。 - user529758

您可以将发送到同一监听器的多个消息组合在一起吗？ - Mysticial

第一种方法是M*N，但第二种方法对我来说更像是N。这可能吗？ - StackedCrooked

@StackedCrooked 第二个是 N*M。 - user529758

公平有多重要？第一种方法将消息均匀地传递给所有听众。而第二种方法在召唤听众之间留下更长的间隔。 - StackedCrooked

Answer 1

有没有一些基本的考虑因素，可以使设计更容易处理更多的消息？

一般来说，这主要取决于两个关键因素：

1. 如果您的循环正在循环可能具有良好内存局部性的对象（例如循环遍历值数组），将该部分保留在内部循环中可能会使对象保留在CPU缓存中，从而提高性能。

2. 如果您计划尝试并行化操作，将“较大”（按数量计算）的集合保留在外部循环中，可以有效地并行化外部循环，并不会过度订阅线程等。通常更容易在外层级别上并行化算法，因此，如果以后可能存在这种情况，则设计循环时应将潜在的较大并行“块”放在外部循环中，以简化操作。

这些侦听器需要在某个地方写入消息，这是相当昂贵的，因此单独的函数调用可能在性能方面并不重要。

这可能会完全抵消将一个循环移至另一个循环的所有好处。

在95％的情况下，只会有一个侦听器。

如果是这种情况，我可能会将侦听器循环放在外部作用域中，除非您计划并行化此操作。鉴于这将在嵌入式设备的后台线程中运行，因此并行化是不太可能的，因此使侦听器循环成为外部循环应该会减少总指令数（它实际上变成了M个操作的循环，而不是M个循环执行单个操作）。

- Reed Copsey

---

Re #1：这些“对象”主要是字符串加上一些元数据（__FILE__，__LINE__，时间戳等），但我的当前方法是在后台任务中将它们转换为字符串（“格式化”）一次，而不是在侦听器中单独处理。因此，基本上，“对象”是普通的字符缓冲区（通常在0.1-1kB之间）。您认为字符缓冲区的局部性如何？Re #2：并行化不需要我将M条消息转发到N个并行工作任务中吗？这正是我目前遇到的问题，不是吗？ - sbi

如果它们是字符缓冲区，那么它们很可能没有太多的本地性。基本上，如果有任何东西要么很大，要么使用指针（即使在内部），则本地性都将被忽略。如果字符缓冲区是固定大小并存储在数组中，则可能存在本地性，但再次，在这种情况下，侦听器正在执行IO操作的事实可能意味着这实际上并不重要。 - Reed Copsey

Answer 2

循环的顺序可能比监听器签名的更改优势小得多（请注意，无论哪个循环在外部，监听器都可以保持第一个接口，即两个循环都可以在调用者中）。

第二个接口的自然优势（即向每个监听器发送一系列消息）是您可以在监听器的实现上启用可能的分组。例如，如果要写入设备，则监听器可以将多个消息打包到单个write中，而如果接口接受单个消息，则监听器需要缓存（这具有内存和CPU成本）或需要执行多个writes。

- David Rodríguez - dribeas

---

在监听器中合并消息写操作是一个非常重要的考虑因素，我之前没有想到过。感谢您提出这个观察！ - sbi

Answer 3

因此，这里有几个因素需要考虑：

缓存中的消息彼此之间有多接近，占用了多少空间？如果它们相对较小（几千字节或更少）且彼此相邻（例如，在进行大量其他内存分配的系统中，不是分配了几秒钟的链接列表）。

如果它们非常接近且很小，则我认为第二个选项更有效，因为消息将被预取/缓存在一起，而调用所有n个侦听器和过滤器函数（还假设有许多函数，而不是一个、两个或三个）可能会导致更多先前消息的“缓存抛出”。当然，这也取决于侦听器和过滤器函数实际上有多复杂。它们要做多少工作？如果每个函数都要做很多工作，那么做的顺序可能并不重要，因为它只会是微不足道的。

- Mats Petersson

---

分支目标预测器似乎不喜欢从同一指令中调用许多不同的函数。但是，正如您所指出的，良好的数据缓存使用和充分利用您的CPU之间存在权衡。 - tmyklebu

消息在1k处被截断，但99.9%的消息最多只有0.1k。它们存储在动态分配的缓冲区（每个1k）中，通常不会被释放，而是被回收利用。我可以编写一个分配器来分配这些缓冲区的整个块以改善它们的局部性，但由于在前端它们被并行线程消耗，它们最终还是会乱掉，这会破坏它们的局部性，所以我认为这不会带来太大的好处。正如我所写的，通常（99%）只涉及一个函数，涉及两个以上的情况应该极为罕见。（当然，用户可以使用它们以不可预测的方式。） - sbi

Answer 4

没有什么“根本”原因可以证明哪种设计比另一种更好。根据库的使用方式，可能会有一些非常小的速度差异。我个人更喜欢先迭代监听器，然后再迭代消息。

我猜处理程序主体通常非常快。你可能希望将监听器作为外部循环迭代，这样你就可以重复调用相同的代码。这样间接调用预测等内容会更有效。当然，你最终会使数据缓存的使用变得更糟糕，但希望每个消息缓冲区都足够小，可以轻松地适应L1缓存。

为什么不让监听器也接受一个const vector<message> &，并让它们自己进行迭代呢？他们可以执行任何有益的缓冲操作，并仅在最后执行单个昂贵的写入操作。

- tmyklebu

---

无论我写了 messages 还是 formatted_messages，它们都可能是缓冲区的 std::vector。（虽然我没有使用 std::string。）每个缓冲区为 1k，但通常消息使用 <0.1k。如果你所说的“处理程序体”指的是监听器，那么不，它们并不真的快，考虑到要求。对于这个问题，将数据写入内部闪存非常慢（约100毫秒），因此我们使用 NVRAM 作为缓存，并有另一个后台任务从那里复制到闪存中... - sbi