如何高效实现大量定时器？

Question

我正在用C++编写一个程序，可以拥有数十万个对象，每个对象都有一个“过期时间”，即如果对象在一定时间内不活动，则应该将其删除。许多对象非常频繁地变为活动状态，而且新对象也会相当快地创建出来。

我一直在犹豫如何处理。我一直在阅读Asio计时器的相关内容，但我不确定它们是否能够满足我的需求，以及如何使用它们。我有两种方法：

1.我可以为每个对象设置一个到期时间，并在对象执行某些操作时重置它。这意味着我将拥有数十万个定时器。

2.我可以建立一些计时器队列，例如30秒到期时间的30个计时器。第一个计时器是为剩余寿命30秒的对象而设的。如果它们不活动超过1秒钟，则它们被移动到剩余寿命为29秒的对象的计时器队列中，以此类推。最后一个队列中的对象如果不活动超过1秒钟就会被删除。任何变为活动状态的对象都会回到第一个队列。

第二种方法听起来更有效率，但它真的吗？如果Asio可以高效地处理大量的计时器，第二种方法可能会浪费我的很多精力。我该怎么做？或者有更好的方法吗？

注：在效率方面，我认为这里指的是更好的CPU利用率。内存使用是次要问题。

- Elektito

---

我刚刚编辑了我的答案，因为我误读了你的方法1。 - merlin2011

我简直不敢相信这些答案.. 唯一正确的答案是: 进行性能分析! - akaltar

Answer 1

我会创建一个队列，按照剩余过期时间对对象进行排序。如果过期时间频繁出现，我会使用链表；否则使用数组，因为在列表内查找某个元素更快（但是，如果你将下一个和前一个对象的引用保存在对象本身而不是节点中，则无关紧要）。

现在，您只需要为具有最低到期时间的对象设置单个定时器。

当此计时器运行完毕时，请删除队列开头的对象并准备下一个对象的计时器。

- user1476710

---

我认为你正在寻找的数据结构是一个priority_queue。 - merlin2011

许多对象经常变得活跃。在我看来，你的方法会导致很多开销，因为每次一个对象变得活跃时，我都必须将它移动到队列中。虽然，我承认当使用许多计时器时，Asio可能正是这样做的。在那种情况下，也许我最好使用它们。 - Elektito

@merlin2011 我明白了。遗憾的是，我的STL知识不够全面，感谢你指出来！ - user1476710

@Elektito 我认为这取决于具体实现。如果您将使用链表中对象的节点，则移动不应该太困难。特别是如果您使用一些间隔保持对节点的引用（这将导致几乎二分搜索）...（顺便说一句，我不知道Asio的工作原理）。 - user1476710

常常发生这样的情况，即这些超时具有共同的间隔时间，例如，服务器在客户端没有通信时会超时。使用 delta-queue 方法是可以的，因为新条目将进入队列的末尾。 - Martin James

如果需要重置超时时间，您可以在队列末尾添加一个副本，并在原始条目中设置“已删除”标志，以便计时器/线程/任何其他内容在其“到达”时忽略并删除它。这样可以避免一直洗牌队列。 - Martin James

Answer 2

制作数字的属性列表并为计时器提供逻辑。这是实现计时器最有效的方式，因为它消耗的内存较少。

- BECOOL

Answer 3

我会选择第一种方法，并加上一个小技巧，即只有在尝试执行操作且截止日期已过期时才删除对象。这种方法更容易实现，因为它是惰性的，也就是说，在必须使用对象时才会评估计时器（也就是在尝试使用对象时）。

如果你考虑效率，无论何时删除对象所需的工作量都应该是相同的。

保存截止日期时间的内存大约为每个截止日期8字节，这等于64位系统上指针的大小（适用于第二种方法）。

第一种方法的唯一风险是，如果不经常使用对象，则可能会一次积累许多对象。您可以通过定期扫描和删除对象来缓解这种情况。只要对象不会太快地积累，您就可以相对较少地进行扫描。

- merlin2011

---

许多对象经常变得活跃，而且新对象也非常快速地被创建。 - Elektito

@Elektito，如果在你的系统中实现这种方法足够容易，我会先实施、测试并切换到更复杂的方法，以防你无法快速删除对象来跟上对象创建的步伐。 - merlin2011

@Elektito，如果你需要进行主动删除，那么Laethnes的回答是一个不错的选择。 - merlin2011

请问您所说的“主动删除”具体是什么意思？ - Elektito

@elektito，我的意思是有一个线程或函数定期运行，唤醒并删除东西，而不仅在过期时删除。 - merlin2011

@elektito，使用主动删除，因为主程序在过期后从未接触过它，所以没有对象永远存在的风险。 - merlin2011

Answer 4

如果您需要不断创建新对象并删除旧对象，则考虑使用对象池，在程序启动时创建一堆对象。如果用完了，可以动态增加对象的数量。每次增加一定百分比（10% - 25%）而不是逐个增加。如果一个对象不再需要，则将其返回到对象池中。如果内存是一个问题，可以考虑使用算法来删除对象池中的对象。例如，它可以每5或10分钟删除未使用的75%的对象。

要实现这个功能，可以考虑使用可用对象池列表和正在使用的列表。您的对象应该有一个初始化方法，可以调用它来初始化现有对象。调用参数应该与构造函数非常相似。至于容器本身，您可能想尝试使用向量和链表，并查看哪个更快。如果您的应用程序需要搜索对象，则std::map或std::unordered_map将是更好的选择。当计时器唤醒时，可以使用迭代器遍历整个正在使用的列表。

关于计时器，你认为哪种方式更快 - 让500,000个计时器每秒唤醒并执行某些操作，还是只有一个计时器每秒唤醒一次，然后遍历500,000个对象列表以查看是否应将对象返回到对象池中？我认为使用一个计时器更有效率。如果这500,000个计时器现在或将来在Windows上运行，我也会非常担心。我知道一些旧的Windows操作系统肯定会崩溃。计时器应该多久唤醒一次？尝试在1到5秒之间的值进行实验。这将是内存消耗与较长唤醒时间相对于较短唤醒时间的CPU限制之间的权衡。

你的第二种方法听起来像一些垃圾收集器所做的事情。Microsoft's .NET garbage collector被组织成几代，短寿命对象进入第零代，长寿命对象进入第一代，最长寿命对象进入第二代。

如果进行多线程，则考虑每个线程使用一个对象池。每个对象池都将有自己的计时器。

- Bob Bryan