Sunday, November 14, 2010

Programming : Cached Interface Requests

Problem
When writing interfaces for tools I commonly need to display a POD (Piece of Data) that is complex and needs a decent bit of preprocessing time.  
One example is a pull down constraint list containing every string in a game.  This could be thousands of data points which must be sorted for quick browsing.  In addition, users invariably expect a slower custom numeric sorting (where text10 comes after text9).
 
(Rule: Once you show users something is possible, they come to expect it.)
I should point out my language of choice for tools is C#.  This may differ elsewhere, but it lets my company prototype and develop internal applications quickly.  Sadly, Microsoft's GUI tools don't seem to have been updated in the past ten years, forcing you to purchase or write your own, but I'll save my whining on that topic.
We don't want to presort every possible query but we can't have the interface take seconds or minutes to draw every time.  How to solve this?

Ignorance
Ignore the problem and wait for it to occur.  It's easy to make elaborate systems to solve problems that don't (yet) exist.  This is actually a good idea if you don't anticipate users will have large enough data sets, although you should be aware of the potential issue.
You may need to take into account the availability of people to update the software, however.  We have long periods of time where our programmers are shuffled onto other things, making it unlikely tools will be updated in a timely manner.
The idea of ripping away queries and making it generalized didn't come until very late in the process and I feel silly for not realizing it then.  Ignorance is bliss, after all, until it bites you.


Quick and Dirty
Make enough assumptions about the query and it's pretty easy to deal with.  Your data container (presumably a list of elements) could contain a PresortedList.  This would be null and populated when the first request came in.  This gets complicated if you can have queries with parameters as you have to store the parameters, toss out old results, etc.  Not very forward thinking but that was my first solution.

Memoization
Create a struct for your search query.  Here's a sample:
QueryStruct { sorted : b; numericsort : b; regexPattern : string; ... }
Structs (or tuples) are a great way of making things more maintainable.   Functions can pass structs instead of long parameter sets.  Classes can later be wrapped around those functions and own the struct.  And so on.
My query cache is a List with records that look like:
QueryCacheRecord { QueryStruct query; List<T> dataList; }
I include the template for ambiguity of your data type, but this is obviously pseudocode.  The idea is to scan through the cache and find a matching QueryStruct.  If one exists, return the dataList.  If one is not found, perform the Query and add it to the cache.
Externally, you have the interface:
List<T> DoQuery( QueryStruct query );
DoQuery would automatically perform queries as necessary and return caches when possible.
Memory is cheap, but not free, so when your cache grows to a predetermined size, old queries will need to be removed.  The easiest way would be to sort the queries as you go along, moving hits on cached queries to the bottom of the list.  Then, you remove the oldest ones first.  A more intelligent system would weight this based on query size or other metrics.
This approach makes the caching invisible to the calling code.  You could further generalize the caching implementation into a reusable component.

Sideline: Lazy Data
If you have a set of pre-defined queries you could construct a class like:
LazyClass {
    LazyClass(QueryStruct query) {
    T mData;
    QueryStruct mQuery;
    public T get( return mData == NULL ? generate(query) | mData );
}
LazyClass wraps a data object T that potentially exists.  It is only constructed when you access it through get() and then cached for the future.
Note: The generate function could be implemented as a delegate (or similar) and QueryStruct could be a second templated value, making it a completely generic lazy pattern.

Saturday, November 6, 2010

Career : Working on Unpopular Projects

The current project that I'm on is a real stinker.  Seriously.  A handful of coworkers have already confided in me that they originally didn't want to be on it.  Passionately.  I felt the same way when I was told I'd be on it.
There's nothing wrong with the project, really.  It isn't flashy or exciting.  It caters to an audience that isn't the developers.  It is sarcastically cheerful.  Amazingly it isn't overscoped, has a good budget, decent timelines, and so on.  It just... isn't what people want to work on.
I bring it up because it's turned out to be one of the best projects I've been on in a long time.  I can relax, work on developing all kinds of new tech, write documentation, and even play manager and organize.  We don't even have to crunch, really.  Let me tell you, though.  I hated the idea of working on it for a whole day.  That's how long it took me to think about it another way and realize that I could have a golden ticket to sit down and really work on new technology (and systems) in peaceful isolation.
Paradoxically a day later I found another programmer assigned to me confided the same thing.  I confided my own results, but he persisted in wanting to transfer to a more interesting project.  This seemed unfortunate, so I proceeded to tell him enthusiastically about all my ideas for developing new broad, then-theoretical (to me) systems that will happen to facilitate the project.
Skepticism remained.  Our last project was particular brutal and we were still tired.  So I changed tactics.  This time I told him, basically:  If it's your decision to transfer, just remember that you probably will be transferring into another round of crunching like the one we just went through.  You'll probably get what you wish for.  An interesting project that is really popular and therefore very tiring.
Surprisingly, I was right.  In the 'fires of hell' ratings, our project is the ugly stepchild everyone forgets about because it's going pretty swimmingly.  This despite being cursed by disease and a few car crashes.  I've had time to read a dozen books and my other programmer has had time to work on his own career goals.  Plus, I can actually take some time to mentor and (gasp) review code.
We're unpopular.  But I can't say that I mind.

Intro


Harken ye back to tymes of oolde!  Sooth was wrought in lyon's grove and...  Okay, enough of that.
That's just not how to start a programming blog.  So where do we begin?
I'm a game programmer, historically speaking.  From the monochrome glare of the Apple II I typed in games from magazines and shifted to making my own.  Years were spent unproductively (according to my teachers) poking at calculators, frantic times trying to have a go at shareware, and admittedly I wasted half a decade (at least) with no firm direction but a lot of wheel spinning.
One of the interesting things about managing programmers is that you slowly start to see the fence you created around yourself.  Expanding theirs has a lot to do with mentoring.  Expanding your own is probably the other 90%.  Why?  Your knowledge base may be too small and as you grow yours, it spreads to others.
It is all too easy to believe that working on your project (and putting in overtime) is the best plan.  Doing that will likely make you an expert at completing that project.  You're lucky if it teaches you anything else and even more lucky if you receive real training.  That's a good path to become obsolete / irrelevant (and burned out).
So, I am redoubling my own journey through software development.  Perhaps you'd like to come along?  Hopefully I will bring light to a few dark caverns along the way and find some treasure.  Note, however we let chanceOfFindingBalrogs = (%) (*) 10 10.