intfiction.org

The Interactive Fiction Community Forum
It is currently Sat Aug 18, 2018 3:39 am

All times are UTC - 6 hours [ DST ]




Post new topic Reply to topic  [ 49 posts ]  Go to page 1, 2, 3, 4, 5  Next
Author Message
PostPosted: Mon Sep 26, 2011 10:27 am 
Offline

Joined: Sat May 29, 2010 3:08 am
Posts: 14
So, I'm currently working with a partner to bring the second work of modern IF to the Kindle, and we're having a problem with performance. In itself this is nothing new; I had to hack the accelerated opcodes into King of Shreds and Patches and spend hours optimizing the Java code at the interpreter level to get that game running at acceptable speed. Problem is, even those optimizations just aren't quite enough for this project. With nothing left to optimize on the interpreter, I'm thrown back to the Inform library.

One thing we've noticed is that our "After deciding the scope of the player" rules sometimes fire dozens of times in a single turn. I suspect this to be a symptom rather than a cause. Is the game really looping through every object to determine scope that frequently every time it parses a command? If so, it seems to scream out for optimization -- if nothing else, just build a list of applicable objects the first time through, and refer to that for the remainder of the parsing algorithm.

But then the Inform parser is a ridiculously complicated beast, and I'd prefer to hack on it as little as possible. Some of the brighter lights around these parts did quite a bit of Inform 7 profiling in years recently passed. I know this is damnably vague, but I'm just wondering if anyone can, say, point me to what THEY would look to first if they really needed to get some more speed out of Inform 7. Are there any other functions that spring to mind as good candidates for new accelerated opcodes? Any areas of parsing or world-modeling that are known to be bottlenecks?

Again, sorry for the vagueness of all this. Advice or ideas (even if similarly vague) would be greatly appreciated.


Top
 Profile Send private message  
Reply with quote  
PostPosted: Mon Sep 26, 2011 10:58 am 
Offline

Joined: Sat Jan 23, 2010 4:56 pm
Posts: 5714
Back through Inform 6, if someone's game was running slow, the first question to ask was "Are you doing too much work in add_to_scope?"

The parser doesn't loop through every object in the game when it's doing that. It only loops through objects in the location, which is pretty efficient *unless* you've added a large class of objects to scope -- or are doing an expensive test to *decide* what to add to scope. (The classic blunder is logic like "add X to scope if Y is/is not in scope", which triggers recursive scope tests.)

All that aside, it's worth using the profiling features of Glulxe (you'll probably have to recompile the interpreter with profiling on) to see what's eating the lion's share of the time. Just because a function is called "dozens of times" doesn't mean it's the long pole. (At the bottom level of the code, I6 property-reading functions are called *thousands* of times per turn. They're the ones I concentrated on for acceleration. But a bottom-level approach can only go so far.)


Top
 Profile Send private message  
Reply with quote  
PostPosted: Mon Sep 26, 2011 3:31 pm 
Offline

Joined: Mon Jun 09, 2008 8:58 pm
Posts: 765
Location: Seattle
Capmikee just posted an extension called Scope Caching which sounds like it might be useful to you.

In other news, I'm rewriting that parser in Inform 7 so we can see how the magic happens. AFAICT the add_to_scope thing isn't used in Inform 7, though I'm not finished yet so could be wrong.

_________________
Blog at Gamasutra :: Programmer's Guide to Inform 7 :: Seattle I-F


Top
 Profile Send private message  
Reply with quote  
PostPosted: Mon Sep 26, 2011 11:22 pm 
Offline
User avatar

Joined: Fri Apr 11, 2008 11:05 pm
Posts: 747
Location: Denver, Colorado
JimmyMaher wrote:
So, I'm currently working with a partner to bring the second work of modern IF to the Kindle [...]


I've no skills to assist you with your technical challenges; just want to throw in a note of applause for you facing them.

_________________
Games, Fonts, and Font-Toys For Gamers - http://www.cumberlandgames.com


Top
 Profile  
Reply with quote  
PostPosted: Tue Sep 27, 2011 6:35 am 
Offline

Joined: Sat May 29, 2010 3:08 am
Posts: 14
Thanks for the suggestions!

I'm afraid that the scope algorithms don't seem to be the source of the problem. Implementing Scope Caching yields no appreciable improvement.

So, I took Zarf's advice and made a profiling build of Glulxe. It turns out the most expensive function is ProcessRulebook. No surprise there, I suppose. But that's a... daunting one to try to implement as an accelerated function.

I did, however, find a few more modest candidates for acceleration. BlkSize in Flex.it6 seems particularly juicy. It's a bottom-level function, with no calls to anyone else. Also, it seems to get called a whole lot during the "insert" command that is particularly slow. I'm going to start with implementing it as an accelerated opcode, and go from there.


Top
 Profile Send private message  
Reply with quote  
PostPosted: Tue Sep 27, 2011 11:16 am 
Offline

Joined: Sat Jan 23, 2010 4:56 pm
Posts: 5714
It's worth looking at what functions *call* those low-level functions. If a particular path to BlkSize is a majority of the usage, you may be able to find a way to do the same thing without using the same low-level facility.

Like I said, accelerated opcodes only go so far. You're a lot smarter than the compiler is.


Top
 Profile Send private message  
Reply with quote  
PostPosted: Wed Sep 28, 2011 10:02 am 
Offline

Joined: Fri Jul 16, 2010 2:09 pm
Posts: 2164
JimmyMaher wrote:
I'm afraid that the scope algorithms don't seem to be the source of the problem. Implementing Scope Caching yields no appreciable improvement.

Although it can be used to prevent the infinite recursion Zarf described, Scope Caching has no accelerating effect on builtin code. It's primarily useful to speed up visibility tests that you need to perform in your own source.

e.g.:
Code:
Repeat with item running through not marked visible things:

could be considerably faster than:
Code:
Repeat with item running through not visible things:


Last edited by capmikee on Wed Sep 28, 2011 10:05 am, edited 1 time in total.

Top
 Profile Send private message  
Reply with quote  
PostPosted: Wed Sep 28, 2011 10:04 am 
Offline

Joined: Fri Jul 16, 2010 2:09 pm
Posts: 2164
I will follow this with interest, though. I'm using Juhana's Parchment-Transcript tool to collect testing data for my WIP, and I hate that my testers have to wait so long for Parchment - sometimes even for seemingly innocuous commands.


Top
 Profile Send private message  
Reply with quote  
PostPosted: Fri Sep 30, 2011 3:15 am 
Offline

Joined: Sat May 29, 2010 3:08 am
Posts: 14
So, I've implemented BlkSize and WhetherProvides as accelerated functions, with some modest improvements. Along the way, though, I've learned something I find pretty interesting.

The slowest command by far is "put." Something like "put hat in chest" could take upwards of 17 seconds on the Kindle (down from almost 30 without acceleration; never say I'm not making progress ;)). And some investigation has revealed that it's all in the parsing phase.

"Put" is a really complicated verb for the parser to deal with, because it can mean so many things. "Put hat in chest" parses to the Insert action; "Put hat on table" parses to Put On; "Put on hat" parses to Wear; "Put down hat" parses to Drop; etc. In addition, there are different ways to phrase each variation: "Put on hat" vs. "Put hat on", etc. There are 19 separate syntax lines for "Put" in the game I'm working with, many of them quite complicated with prepositions and indirect objects. As it happens, "Put x in x" (leading to Insert, and one of the most common constructions of "Put") is near the end of that group. The parser apparently loops through the syntax lines until it finds a match, and then quits. Thus the Wear variation, which comes at the beginning of the list, parses almost instantly, while Insert takes forever.

My first thought was to ask whether I could optimize the syntax lists, placing the most commonly used near the front. I went so far as to declare "the command 'put' as something new," then add back in all the "Understand" lines from the library in what I judged to be a better order. This accomplishes nothing, however. The compiler apparently makes it own decisions about the proper order, placing the simplest syntax lines first and working up to the more complicated. With a command like "put," this is a recipe for inefficiency in many cases -- the complicated constructions already take much longer to parse, and then to put them at the end of the collection... A useful addition to future versions of Inform 7 might be some way to prioritize certain "Understand" lines as commonly used or having priority.

But given the situation as it is, it seems there are a few options for improving performance. One (kludgy) one is to try to help the game out by catching problematic inputs at the interpreter level and changing them to something the game can process more efficiently. Say, define "place" as a synonym for the Insert version of "put" (only), then substitute where appropriate in the interpreter. Besides being ugly, this is of course also problematic in that it requires us to do a substantial amount of parsing in the interpreter -- exactly the job the parser in the game is supposed to be doing.

Another is to cut down on the number of syntax lines we define for problematic verbs like "put." Since this also means cutting down on the number of possible inputs we understand from the player, it's also not ideal.

The last solution is just to fix the damn parser, find some way to make it faster. But man, is it a complicated and opaque piece of code. I think a logical first step is to set up some performance logging in the parser itself, to try to figure out where it's spending the majority of its time. Then we could perhaps target just that section(s) for optimization -- maybe even an accelerated function if it seems manageable. I suspect that there's some sort of Inform 7 hook in there that is causing a massive slowdown, as the Inform 6 parser never had these problems. I just don't know where or what it might be.

Or maybe we learn something important from Ron's ongoing reconstruction of the parser. That would be nice...


Top
 Profile Send private message  
Reply with quote  
PostPosted: Fri Sep 30, 2011 9:08 am 
Offline

Joined: Fri Jul 16, 2010 2:09 pm
Posts: 2164
Once again, I suspect that calculating scope is the problem. I am pretty sure that scope is recalculated for every single grammar line. This is reasonable, because the action in the grammar line (and maybe the direct object too) can affect rules in the Deciding the Scope of Something activity. But it seems like there must be a way to make it more efficient.

You have a number of After Deciding the Scope of Something rules, don't you? Do you perhaps have some Understand by a relation rules too? I think those affect scope calculations as well.


Top
 Profile Send private message  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 49 posts ]  Go to page 1, 2, 3, 4, 5  Next

All times are UTC - 6 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 8 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group