From 817d10634f54631004dc0ac9bee04e22fe4b46b6 Mon Sep 17 00:00:00 2001
From: Daniel Schadt <kingdread@gmx.de>
Date: Thu, 18 Nov 2021 19:44:06 +0100
Subject: speed up Log::agent_by_addr
We know that the way we construct the Log, the agents are always sorted
by their address. This invariant cannot be broken, as the only way to
construct a Log is in evtclib itself, and there is no way to obtain a
mutable view on the agent vector or change the address of an agent.
Since Log::agent_by_addr is used by other functions, this speedup (even
if it is small) can show in a lot of different places.
Note that if we change the interface of Log in the future to allow
creating logs from different sources that processing::process, we need
to make sure we adjust this function.
---
src/lib.rs | 9 ++++++++-
1 file changed, 8 insertions(+), 1 deletion(-)
diff --git a/src/lib.rs b/src/lib.rs
index ccf6692..53107ff 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -138,6 +138,8 @@ pub enum EvtcError {
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Debug, Clone)]
pub struct Log {
+ // evtclib assumes that the agents in this vector are sorted by their address. This information
+ // is used to speed up the agent_by_addr search.
agents: Vec<Agent>,
events: Vec<Event>,
boss_id: u16,
@@ -152,7 +154,12 @@ impl Log {
/// Return an agent based on its address.
pub fn agent_by_addr(&self, addr: u64) -> Option<&Agent> {
- self.agents.iter().find(|a| a.addr() == addr)
+ // We know that the agents are sorted because processing::process puts them like that. We
+ // can use the same trick here to achieve a faster agent searching:
+ self.agents
+ .binary_search_by_key(&addr, Agent::addr)
+ .ok()
+ .map(|i| &self.agents[i])
}
/// Return an agent based on the instance ID.
--
cgit v1.2.3