LOS Cache Prototype Idea

[image]

I wanted to throw this idea around as it can potentially save a lot of cpu on all the line of sight checks we do all the time. Rough calculations in velketor (using #aggrozone to put all mobs on me) show that under load I can save roughly up to 30% cpu usage. Idle was harder to calculate (takes time for the cpu to level out) but I did notice about up to a 10% cpu usage difference. Obviously this will change depending on what you set the millisecond value to (shorter at more cpu versus longer at less).

This adds two rules:

by default it is off, you will have to enable it:
RULE_BOOL ( Performance, LOSCacheEnabled, false )

Second the default cache entry value for now is kind of high, but for testing purposes it has been shown that cache entries stay alive long enough to be re-used, and if both npc/player don't move it saves additional calculations. However this does create a period that moving back and forth between a wall may be a bit inconsistent and in the end this value should probably be reduced.
RULE_INT ( Performance, LOSCacheEntryMS, 3000 )


Pretty much what we do is get a LOS entry, put it into a map. When we CheckLOS again we see if the time at adding the entry + Performance:LOSCacheEntryMS against the current time, if current time is higher we automatically purge. If the entry is still 'new enough' we can check and see if their location is the same (just X,Y check for now, also thought maybe adding a precision here). If the location is the same for both mobs we cache the entry for the additional Performance:LOSCacheEntryMS.

I also added some info to #checklos just for testing. It will display if there is a cached entry between Client->Mob or Mob->Client. Secondly it will track the hits (keep in mind that when we call the cache function it counts as a hit, the #checklos adds an additional hit for Client->Mob).

Here is the code against the latest SVN:

Index: common/ruletypes.h
===================================================================
--- common/ruletypes.h	(revision 2231)
+++ common/ruletypes.h	(working copy)
@@ -480,6 +480,14 @@
 RULE_REAL ( EQStream, RetransmitTimeoutMult, 3.0 ) // multiplier applied to rtt stats to generate a retransmit timeout value
 RULE_BOOL ( EQStream, RetransmitAckedPackets, true ) // should we restransmit packets that were already acked?
 RULE_CATEGORY_END()
+
+// Image: Features that are not required but may help improve performance
+RULE_CATEGORY ( Performance )
+RULE_BOOL ( Performance, LOSCacheEnabled, false )
+// The millisecond value is important to be above the time it would take for AI process or something else to trigger CheckLOS.
+// If you have too low of value, say 250ms, the cached entry will most likely be expired before it can be re-used.
+RULE_INT ( Performance, LOSCacheEntryMS, 3000 )
+RULE_CATEGORY_END()
 
 #undef RULE_CATEGORY
 #undef RULE_INT
Index: zone/aggro.cpp
===================================================================
--- zone/aggro.cpp	(revision 2231)
+++ zone/aggro.cpp	(working copy)
@@ -1002,12 +1002,86 @@
 }
 
 
+// Image (10/14/2012): Added LOSEntry as a cache to slow down the attempts against los on the same mob in a short time frame
+bool Mob::FindLosCacheEntry(Mob* other, bool& inLOS, int32& hits)
+{
+	if ( other == NULL || !RuleB(Performance,LOSCacheEnabled) )
+		return false;
+
+	std::map<int16, LOSEntry>::iterator iter = m_LOSCache.find(other->GetID());
+	if ( iter != m_LOSCache.end() )
+	{
+		LOSEntry ent = (LOSEntry)iter->second;
+		if ( ent.entry != NULL && ent.entry == other ) // this means the entry is valid and we have the right mob
+		{
+			if ( Timer::GetCurrentTime() < ent.lastChecked )
+			{
+				// Update the entry with the new hits, here we could essentially 'increase' the cache too
+				LOSEntry newEnt;
+				newEnt.entry = other;
+				newEnt.isLOS = ent.isLOS;
+				newEnt.hits = ent.hits + 1;
+
+				// if this is true then we already have an entry that is at the same location, save it for another period of time
+				if ( ent.lastX == other->GetX() &&
+					ent.lastY == other->GetY() &&
+					ent.ourLastX == GetX() &&
+					ent.ourLastY == GetY() )
+					newEnt.lastChecked = Timer::GetCurrentTime() + RuleI(Performance, LOSCacheEntryMS);
+				else
+					newEnt.lastChecked = ent.lastChecked;
+				
+				newEnt.lastX = other->GetX();
+				newEnt.lastY = other->GetY();
+				newEnt.lastZ = other->GetZ();
+				newEnt.ourLastX = GetX();
+				newEnt.ourLastY = GetY();
+				newEnt.ourLastZ = GetZ();
+				m_LOSCache[other->GetID()] = newEnt;
+
+				inLOS = ent.isLOS;
+				hits = ent.hits;
+				return true;
+			}
+		}
+	}
+
+	return false;
+}
+
 //Father Nitwit's LOS code
 bool Mob::CheckLosFN(Mob* other) {
 	bool Result = false;
 
+	if ( other == this )
+		return true;
+	
+	int32 hits = 0;
+
+	// Image (10/14/2012): Added LOSEntry as a cache to slow down the attempts against los on the same mob in a short time frame
+	if ( FindLosCacheEntry( other, Result, hits) )
+		return Result;
+
 	if(other)
+	{
 		Result = CheckLosFN(other->GetX(), other->GetY(), other->GetZ(), other->GetSize());
+		
+		if ( RuleB(Performance,LOSCacheEnabled) )
+		{
+			LOSEntry newEnt;
+			newEnt.entry = other;
+			newEnt.isLOS = Result;
+			newEnt.lastChecked = Timer::GetCurrentTime() + RuleI(Performance, LOSCacheEntryMS);
+			newEnt.hits = 1;
+			newEnt.lastX = other->GetX();
+			newEnt.lastY = other->GetY();
+			newEnt.lastZ = other->GetZ();
+			newEnt.ourLastX = GetX();
+			newEnt.ourLastY = GetY();
+			newEnt.ourLastZ = GetZ();
+			m_LOSCache[other->GetID()] = newEnt;
+		}
+	}
 
 	return Result;
 }
Index: zone/command.cpp
===================================================================
--- zone/command.cpp	(revision 2231)
+++ zone/command.cpp	(working copy)
@@ -6723,7 +6723,13 @@
 {
 	if(c->GetTarget())
 	{
-//		if(c->CheckLos(c->GetTarget()))
+		bool los = false;
+		int32 hits = 0;
+		if ( c->FindLosCacheEntry(c->GetTarget(), los, hits) )
+			c->Message(12,"(Client->Mob) Cached entry exists with mob. LOSVisibleStatus: %i.  CacheEntryHits: %i.", los, hits);
+		if ( c->GetTarget()->FindLosCacheEntry(c, los, hits) )
+			c->Message(12,"(Mob->Client) Cached entry exists ON mob. LOSVisibleStatus: %i.  CacheEntryHits: %i.", los, hits);
+
 		if(c->CheckLosFN(c->GetTarget()))
 			c->Message(0, "You have LOS to %s", c->GetTarget()->GetName());
 		else
Index: zone/mob.h
===================================================================
--- zone/mob.h	(revision 2231)
+++ zone/mob.h	(working copy)
@@ -466,6 +466,23 @@
 class EGNode;
 class MobFearState;
 
+// Image (10/14/2012): Added LOSEntry as a cache to slow down the attempts against los on the same mob in a short time frame
+struct LOSEntry {
+	Mob* entry;
+	bool isLOS;
+	int32 lastChecked; // Timer::GetCurrentTime entry to compare
+	int32 hits; // times the entry was hit in the timeframe of the cache
+	// target last location
+	float lastX;
+	float lastY;
+	float lastZ;
+
+	// our last location when we got this entry
+	float ourLastX;
+	float ourLastY;
+	float ourLastZ;
+};
+
 class Mob : public Entity {
 public:
 bool logpos;
@@ -646,6 +663,9 @@
 	inline bool SeeInvisibleUndead() const { return see_invis_undead; } 
 	inline bool SeeHide() const { return see_hide; }
 	inline bool SeeImprovedHide() const { return see_improved_hide; }
+	
+	// Image (10/14/2012): Added LOSEntry as a cache to slow down the attempts against los on the same mob in a short time frame
+	bool FindLosCacheEntry(Mob* other, bool& inLOS, int32& hits);
 
 	bool CheckLos(Mob* other);
 	bool CheckLosFN(Mob* other);
@@ -1256,6 +1276,9 @@
 
 	std::vector<std::string> RampageArray;
 	std::map<std::string, std::string> m_EntityVariables;
+	
+	// Image (10/14/2012): Added LOSEntry as a cache to slow down the attempts against los on the same mob in a short time frame
+	std::map<int16, LOSEntry> m_LOSCache;
 
 	sint16 SkillDmgTaken_Mod[HIGHEST_SKILL+2];
 	sint16 Vulnerability_Mod[HIGHEST_RESIST+2];

Just example of spamming #checklos:

http://imgur.com/iBKUm

[lerxst2112]

LOSEntry ent = (LOSEntry)iter->second;

You shouldn't need to cast iter->second to LOSEntry, types are not lost when objects are stored in a map.

You should also use a reference here as it avoids a copy, and then use the reference to update the values stored in the object rather than creating a new one and copying it over the existing one.

[image]

I'll take those under consideration thanks. I typecast just to make it look cleaner frankly, but I agree with the update.

[image]

This is a bit cleaner.. The performance seems about the same, it may matter if the zones have 1000+ npc's.

Index: common/ruletypes.h
===================================================================
--- common/ruletypes.h	(revision 2231)
+++ common/ruletypes.h	(working copy)
@@ -480,6 +480,14 @@
 RULE_REAL ( EQStream, RetransmitTimeoutMult, 3.0 ) // multiplier applied to rtt stats to generate a retransmit timeout value
 RULE_BOOL ( EQStream, RetransmitAckedPackets, true ) // should we restransmit packets that were already acked?
 RULE_CATEGORY_END()
+
+// Image: Features that are not required but may help improve performance
+RULE_CATEGORY ( Performance )
+RULE_BOOL ( Performance, LOSCacheEnabled, false )
+// The millisecond value is important to be above the time it would take for AI process or something else to trigger CheckLOS.
+// If you have too low of value, say 250ms, the cached entry will most likely be expired before it can be re-used.
+RULE_INT ( Performance, LOSCacheEntryMS, 3000 )
+RULE_CATEGORY_END()
 
 #undef RULE_CATEGORY
 #undef RULE_INT
Index: zone/aggro.cpp
===================================================================
--- zone/aggro.cpp	(revision 2231)
+++ zone/aggro.cpp	(working copy)
@@ -1002,12 +1002,71 @@
 }
 
 
+// Image (10/14/2012): Added LOSEntry as a cache to slow down the attempts against los on the same mob in a short time frame
+bool Mob::FindLosCacheEntry(Mob* other, bool& inLOS, int32& hits)
+{
+	if ( other == NULL || !RuleB(Performance,LOSCacheEnabled) )
+		return false;
+
+	std::map<int16, LOSEntry>::iterator iter = m_LOSCache.find(other->GetID());
+	if ( iter != m_LOSCache.end() )
+	{
+		if ( iter->second.entry == other ) // this means the entry is valid and we have the right mob
+		{
+			if ( Timer::GetCurrentTime() < iter->second.lastChecked )
+			{
+				// Update the entry with the new hits, here we could essentially 'increase' the cache too
+				iter->second.hits += 1;
+				// if this is true then we already have an entry that is at the same location, save it for another period of time
+				if ( iter->second.lastX == other->GetX() &&
+					iter->second.lastY == other->GetY() &&
+					iter->second.ourLastX == GetX() &&
+					iter->second.ourLastY == GetY() )
+					iter->second.lastChecked = Timer::GetCurrentTime() + RuleI(Performance, LOSCacheEntryMS);
+
+				inLOS = iter->second.isLOS;
+				hits = iter->second.hits;
+				return true;
+			}
+		}
+	}
+
+	return false;
+}
+
 //Father Nitwit's LOS code
 bool Mob::CheckLosFN(Mob* other) {
 	bool Result = false;
 
+	if ( other == this )
+		return true;
+	
+	int32 hits = 0;
+
+	// Image (10/14/2012): Added LOSEntry as a cache to slow down the attempts against los on the same mob in a short time frame
+	if ( FindLosCacheEntry( other, Result, hits) )
+		return Result;
+
 	if(other)
+	{
 		Result = CheckLosFN(other->GetX(), other->GetY(), other->GetZ(), other->GetSize());
+		
+		if ( RuleB(Performance,LOSCacheEnabled) )
+		{
+			LOSEntry newEnt;
+			newEnt.entry = other;
+			newEnt.isLOS = Result;
+			newEnt.lastChecked = Timer::GetCurrentTime() + RuleI(Performance, LOSCacheEntryMS);
+			newEnt.hits = 1;
+			newEnt.lastX = other->GetX();
+			newEnt.lastY = other->GetY();
+			newEnt.lastZ = other->GetZ();
+			newEnt.ourLastX = GetX();
+			newEnt.ourLastY = GetY();
+			newEnt.ourLastZ = GetZ();
+			m_LOSCache[other->GetID()] = newEnt;
+		}
+	}
 
 	return Result;
 }
Index: zone/command.cpp
===================================================================
--- zone/command.cpp	(revision 2231)
+++ zone/command.cpp	(working copy)
@@ -6723,7 +6723,13 @@
 {
 	if(c->GetTarget())
 	{
-//		if(c->CheckLos(c->GetTarget()))
+		bool los = false;
+		int32 hits = 0;
+		if ( c->FindLosCacheEntry(c->GetTarget(), los, hits) )
+			c->Message(12,"(Client->Mob) Cached entry exists with mob. LOSVisibleStatus: %i.  CacheEntryHits: %i.", los, hits);
+		if ( c->GetTarget()->FindLosCacheEntry(c, los, hits) )
+			c->Message(12,"(Mob->Client) Cached entry exists ON mob. LOSVisibleStatus: %i.  CacheEntryHits: %i.", los, hits);
+
 		if(c->CheckLosFN(c->GetTarget()))
 			c->Message(0, "You have LOS to %s", c->GetTarget()->GetName());
 		else
Index: zone/mob.h
===================================================================
--- zone/mob.h	(revision 2231)
+++ zone/mob.h	(working copy)
@@ -466,6 +466,23 @@
 class EGNode;
 class MobFearState;
 
+// Image (10/14/2012): Added LOSEntry as a cache to slow down the attempts against los on the same mob in a short time frame
+struct LOSEntry {
+	Mob* entry;
+	bool isLOS;
+	int32 lastChecked; // Timer::GetCurrentTime entry to compare
+	int32 hits; // times the entry was hit in the timeframe of the cache
+	// target last location
+	float lastX;
+	float lastY;
+	float lastZ;
+
+	// our last location when we got this entry
+	float ourLastX;
+	float ourLastY;
+	float ourLastZ;
+};
+
 class Mob : public Entity {
 public:
 bool logpos;
@@ -646,6 +663,9 @@
 	inline bool SeeInvisibleUndead() const { return see_invis_undead; } 
 	inline bool SeeHide() const { return see_hide; }
 	inline bool SeeImprovedHide() const { return see_improved_hide; }
+	
+	// Image (10/14/2012): Added LOSEntry as a cache to slow down the attempts against los on the same mob in a short time frame
+	bool FindLosCacheEntry(Mob* other, bool& inLOS, int32& hits);
 
 	bool CheckLos(Mob* other);
 	bool CheckLosFN(Mob* other);
@@ -1256,6 +1276,9 @@
 
 	std::vector<std::string> RampageArray;
 	std::map<std::string, std::string> m_EntityVariables;
+	
+	// Image (10/14/2012): Added LOSEntry as a cache to slow down the attempts against los on the same mob in a short time frame
+	std::map<int16, LOSEntry> m_LOSCache;
 
 	sint16 SkillDmgTaken_Mod[HIGHEST_SKILL+2];
 	sint16 Vulnerability_Mod[HIGHEST_RESIST+2];

[lerxst2112]

I think the cache is a good idea, especially if there are many los checks being performed without the mobs moving, and as you've seen in your tests it does seem to be a performance win.

The only concern I have is that I don't see anything ever being removed from the cache. It'll get cleaned up in the destructor when a mob dies, but any other mob with entries pointing to the now destroyed mob won't go away.

Do mobs regularly perform los checks on each other? I suppose the worry is that in a zone where many mobs are killed over and over but there are some that are never killed, then those caches would continue to grow over time as the entries that point to the dead mobs accumulate.

The only way I can see to keep that from happening would be to tell every other mob to remove any entries pointing to a mob that is being destroyed from their cache. That would mean a potentially costly operation whenever a mob dies. An alternative could be to have a scheduled task on each that dumped entries that were very old, but then that will cause a periodic cpu spike if they all do it at the same time.

Have you seen memory usage creeping up over time if you kill some mobs but not all of them? It might be worth logging out the size of each cache periodically for debugging purposes and see if they just grow forever on any mobs with long lifetimes.

[image]

this CheckLosFN is called for quite a few things including aggro, friendly faction (mobs), spell casting, auto attack, etc. It would be possible to build it over time but difficult to consume large amounts of memory.

As you mentioned it would seem costly for a cleanup and I don't think that you would see the accumulation (we try to start re-using id's once we get up to 1500 in the Entity class).

If anything -- it becoming a problem id say just every 5 minutes or something clear the map (dont bother checking the cache entries just flush it).