ID:103894
 
Keywords: programming
In response to a request from Divine Traveller, I have recently reviewed a library provided by Flick, called F_Damage. Some of you may be using it in your games currently. It is essentially a very small library, that provides you with a means of showing a number above some player / enemies head temporarily, a kind of hit marker for damage taken or healing.

It's a nice little library in itself, providing a good little battle effect that's quite tried and trusted among more professional development circles for RPGs and some strategies. The issue Divine Traveller seemed to note is that as part of it's processing, it creates a new icon, coloured according to your requirement. This he believed was a computationally expensive process, and not being cached, contributed to making F_Damage computationally expensive in kind. While I can't say for sure, it appears he isn't alone in this view.

Taking their experience in these matters at face value, I set about lessening the computational strain of this otherwise pleasant effect, that I would encourage others to consider as a possible means of visual feedback to players. At Divine Traveller and Lummox JR's recommendation, some caching of this created icon was in order. At this point I would like you to spend a few minutes having a little think about this issue. How would you cache this custom coloured icon, so it can be re-used in subsequent calls when appropriate.

My starting point was to assess the user, and their likely requirements, from a common sense stand-point. The users of F_Damage are likely to be RPG / Action type developers. F_Damage does provide the option to customise the colour of the damage icons shown with any old colour you like.

However, these developers are probably only going to display a few different colours, to represent a limited set of concepts. Too many different colours, and their users will get confused (magenta numbers ... what does that signify again??). Now I don't know what the colours will be, but I know there will probably only be a few different ones.

The other main observation is that F_Damage will probably be called with fair frequency. It won't be insane like hundreds of calls per second, but damage in those sorts of games is a core mechanic.

This translates into some potentially useful properties for our caching. We will have a fairly limited range of values to cache which will be hit fairly frequently.

Our aims for the cache are thus:
  • Optimal or sub-optimal performance, which is brought about by high cache hit success rates. - Cache misses cost time to build the icon again.
  • No changes to the F_Damage interface, minimal intrusion on other people's environment. - It's a library, already currently in use. Fiddling with the interface or intruding on their environment means people are less likely to move over to using the new version.

Now onto the solution.

The cache itself is fairly simple. I suspect a number of you will have chosen something like ... an associative list? Makes sense, mapping a colour string to the appropriately coloured icon. This scales very well to large numbers of cached entries, as it happens. I didn't do this.

Some of the more observant of you will have noticed this list needs pruning. If you just keep adding entries, you have an effective memory leak in the case where outliers exist. Outliers would be the odd call with a quirky colour, possibly randomly generated, that isn't used often.

Perhaps to solve this you kept a record of when the entry was last used, maybe in a datum with the entry itself, and spawn()ed a persistent loop that sleep()s for a long while, and checks the cache periodically for unused entries? I didn't do this.

Here's why:
  • The associative list just wasn't needed. It's not a bad idea, but it's not essential either. We know that the number of entries we probably need to store is small, so we don't have to use the associative list's "rapid lookup" properties to be quick. It's preferable to use them, but if we have some other more pressing design issue, we don't need to.
  • The persistent loop cleanup is well suited to large caches that need infrequent pruning, but incurs a bit of a penalty by virtue of being up to the soft scheduler to decide when it runs, along with everything else the soft scheduler has to do with a game. We have a small cache, and frequent (but not too frequent) pruning would keep it small.


And here's the solution I chose:
Cache
var/list/entries = new()

get(var/key)
var/result = null
for(var/CacheEntry/C in entries)
if (C.key == key)
result = C.hit()
else
C.miss()
return result

put(var/key, var/value)
var/CacheEntry/C = new(key, value, 10)
entries.Add(C)

CacheEntry
var
key
value
timer

New(var/key, var/value, var/timer = 10)
src.key = key
src.value = value
src.timer = timer

proc
hit()
timer = 10
return value

miss()
timer--
if (timer == 0)
del(src)


The pruning is done by virtue of F_Damage being called frequently, as cache misses decrease the entry's timer until it hits 0, then the entry deletes itself and the cache icon is cleaned up.

The "rapid lookup" property of an associative list wasn't used, to allow the entry to clean itself up without having to know of the existence of the parent Cache object. The performance difference on a small cache is negligable, but allows good encapsulation of the CacheEntry, and Cache simply takes care of insertion and cache lookup.

The value of 10 for the timer is examplary, but happens to work quite well for F_Damage. It acts as an informal limit on the cache size, you can't really store more items than that number, as entries will expire. If a hit is not met in 10 calls, then it's not used frequently enough, and evicted. In discussion with Divine Traveller, we decided ~5 entries are likely to be commonly used, and they would probably survive this timer process okay. If eviction proved too aggressive, you'd simply increase this number.

Some will note "performance issues" with this design, such as the need to inspect all entries to find a match and maintain the timer mechanism, every call. To which I'd fully agree, but note they don't matter because the expected use scenario mitigates them and by design this issue cannot grow out of hand. The goals dictate the alternative (a persistent loop) was not desirable.

It is goals that should drive your design at all times. Not just a matter of "what am I doing", but "why am I doing it" and "what is important". A design that doesn't obey a small and clear set of goals at all times is prone to failure.

People usually don't like restricting their goals to a small number. We all want our code to be flexible as hell, super efficient in both performance and memory use and elegant. However in trying all of these, people suffer "frameworkism", where-by their code fails to meet it's original objective, because by design it was meant to meet not just a few goals, but all goals, and by consequence in implementation meets none of the goals.

The ability to discern key goals before starting a design is the programmer's greatest aid to clarity and effective software, in my opinion. Just thought I'd share why.
oh ok
Zaole wrote:
oh ok

Pretty much my response as well.
I don't think I understand this.

Are you creating a single icon that contains the number "123" and caching that? Or are you creating icons for each number ("1", "2", and "3") and caching those three icons? Are you limiting the size of the cache to 10 icons? If so, why?

It sounds like you learned about memory and page replacement algorithms so you want to implement a sophisticated cache when a simpler cache would work better.

I would let the user decide when icons should or shouldn't be cached. If you have a spell effect that generates numbers that are randomly colored, don't cache them (because generating that same color again is unlikely). When you generate numbers in your standard damage or healing color, do cache them.
Forum_account wrote:
I don't think I understand this.

Are you creating a single icon that contains the number "123" and caching that? Or are you creating icons for each number ("1", "2", and "3") and caching those three icons? Are you limiting the size of the cache to 10 icons? If so, why?

It sounds like you learned about memory and page replacement algorithms so you want to implement a sophisticated cache when a simpler cache would work better.

I would let the user decide when icons should or shouldn't be cached. If you have a spell effect that generates numbers that are randomly colored, don't cache them (because generating that same color again is unlikely). When you generate numbers in your standard damage or healing color, do cache them.

F_Damage isn't my library as it happens (and as I noted at the top of the article). It contains a single icon file, with states for 0, 1, 2, 3 etc. Each of those is an animation state, as it happens, but library users can replace the icon file so long as they keep the icon file structure going (which I suspect would actually be tricky to do with some artisti flair).

The algorithm colors that icon file by blending it, then adds a number of overlays using that icon file, setting the state according to the digit in question and offseting the overlay as appropriate. The API only provides a means to colour the whole "string" of overlays, not individual digits. The end result is a list of overlays with appropriate offsets that are added "as one" to look like a continuous number to the player.

You can look at the library in it's currently used form by following the link I put in the article, here it is again for convenience: http://www.byond.com/developer/Flick/F_Damage

The update was simply to improve the performance of the library, with no changes to the API, so the update could just be "dropped in" by existing library users.

There are many overlays (which aren't cached), but ultimately only one icon, which is duplicated when blended to a given colour. It's those blended icons that are being cached, as deemed by DT and Lummox that this was some form of bottleneck. Whether it is or not, I'm not going to discuss (I suspect it's not).

The cache I would say is actually dirt simple, and while I did learn about memory and page replacement algorithms some years ago, this solution wasn't especially inspired by that learning.

Importantly (and I can't really stress this enough), a key goal of the activity was the API must not change. No change to the proc signatures, and no extra procs should need to be called to opt in this caching, and most hopefully no undesirable behavioural changes.

This means the cache needs to be self-pruning in some regard, so the caching process is transparent to the library user. I think given that goal, I couldn't really have made it much simpler than the already fairly dumb and simple solution I settled on. However I'm open to alternative implementations here.
So you're caching the whole set of numbers by color? Meaning that you'd be able to cache all numbers in up to 10 different colors?

You can change the proc's signature without changing the API:
proc/F_damage(atom/Target, value, color = "#ff0000", cache = 1)


Existing calls to F_damage won't have a 4th parameter so they'll cache icons by default, but you do give users the ability to specify when an icon doesn't need to be cached. You don't need to do this, but it is possible to make changes like this and keep the API backwards compatible.
Forum_account wrote:
So you're caching the whole set of numbers by color? Meaning that you'd be able to cache all numbers in up to 10 different colors?

You can change the proc's signature without changing the API:
> proc/F_damage(atom/Target, value, color = "#ff0000", cache = 1)
>

Existing calls to F_damage won't have a 4th parameter so they'll cache icons by default, but you do give users the ability to specify when an icon doesn't need to be cached. You don't need to do this, but it is possible to make changes like this and keep the API backwards compatible.

As you see in the icon file in the library, it's one icon object with all the digits as icon states in it. I cache coloured versions of that icon object.

As for the cache option, I could do that, but I still require the self-pruning function. The "pain-free" upgrade a developer takes with this update, where-by they don't update any of their code, would have all icons cached, frequent and infrequent alike. While I do consider it unlikely for lots of random infrequent colours to be used, their possibility is something the cache needs to take into account to avoid a growing cache problem.

I can't assume the developer will do the sensible thing and update their code to turn off caching where appropriate for them, because I've sold the update as having no API changes and being a drop-in replacement. It's not a drop-in replacement if they drop in the update and then need to review their code to adjust for the new implementation.

The self-pruning function provides that catch-all, with reasonable performance for all users. Constant cache misses are tantamount to the existing implementation where icons are generated each time, as that's the bulk cost of a cache miss.

Given this property, and the meeting of a no API change / drop-in replacement goal as a result of that design, it seems my settled solution is ideal for this case.
I can't assume the developer will do the sensible thing and update their code to turn off caching where appropriate for them

You also can't assume that what you're doing for them is the sensible thing =)

Now that I understand what you're doing it does make more sense but I'd still give the users more control over the process. Just because you want a drop-in solution doesn't mean that people are against having more control and wouldn't update their code to utilize new features.
I'm still a fan of coming up with what colors you are going to use and pre-generating everything you need for them. You don't need millions of colors, players won't see any difference between millions of pairs of them. Just pick the colors you want.
I realize that Stephen001's goal was to extend F_Damage, but I do agree that there are better ways to handle this. It might be nice to have a fixed up F_Damage library for legacy games but we can make a better system. I'd prefer to not generate icons at runtime unless it was completely necessary. If you know what colors you'll need just make the .dmi for the icons of that color.

This is also why it would be nice to have more control over the cache. You could, when the game starts up, generate icons of the colors you'll know that you need (telling F_Damage to cache them) then all calls to F_Damage that occur in the game will not cache the icons. None of these calls need to cache icons because the important icons were already cached and all other icons are not important enough to cache.
Interesting read. I had actually planned, at some point (possibly never), to make an add-on for my data structures library that would utilize the features of splay trees to create a caching system, seeing as how their structure is fairly optimized for caches.
Forum_account wrote:
I realize that Stephen001's goal was to extend F_Damage, but I do agree that there are better ways to handle this. It might be nice to have a fixed up F_Damage library for legacy games but we can make a better system. I'd prefer to not generate icons at runtime unless it was completely necessary. If you know what colors you'll need just make the .dmi for the icons of that color.

This is also why it would be nice to have more control over the cache. You could, when the game starts up, generate icons of the colors you'll know that you need (telling F_Damage to cache them) then all calls to F_Damage that occur in the game will not cache the icons. None of these calls need to cache icons because the important icons were already cached and all other icons are not important enough to cache.

You are of course welcome to make such a system. This is outside of the remitt of my blog post. Frankly the API exposed by F_damage has oddities as it is, beyond a lack of exposed controls of it's algorithm.

The rationale with the F_Damage update comes primarily from it's existing developer base, who tend to be fairly inert when it comes to non-user facing features. Functionally F_Damage meets their needs "well enough" for them to have adopted it, and have little cause to drive towards a new API. They pick a colour, then just F_damage() away as they please, nice and easy. Free to move onto other areas.

These users also make up a good portion of the developer readership of BYOND Anime, who I wanted to demonstrate some rationale to along with advertising this coming improvement.
Forum_account wrote:
I can't assume the developer will do the sensible thing and update their code to turn off caching where appropriate for them

You also can't assume that what you're doing for them is the sensible thing =)

I don't need to, in the worst-case (full cache misses, 100% of the time) the update performs about the same as the current version, and has no functional change from their perspective (bugs aside, which are a testing and validation matter). By about the same, I mean the profiler can't measure the difference accurately.

The cache implementation I chose only stands to improve the situation for them, with minimal effort on their part.

Now that I understand what you're doing it does make more sense but I'd still give the users more control over the process. Just because you want a drop-in solution doesn't mean that people are against having more control and wouldn't update their code to utilize new features.

Okay, but I'm not going to do that.