intfiction.org

The Interactive Fiction Community Forum
It is currently Sun Nov 18, 2018 11:06 pm

All times are UTC - 6 hours [ DST ]




Post new topic Reply to topic  [ 21 posts ]  Go to page 1, 2, 3  Next
Author Message
 Post subject: [I7] Table lookup speed
PostPosted: Fri Sep 14, 2018 8:59 am 
Offline
User avatar

Joined: Sun Nov 22, 2009 12:58 pm
Posts: 796
Location: Malmö, Sweden
I've been playing around with a small project that gets its data from 256 rows in a table. Accessing that data is... not slow, but there's a barely perceptible delay. I don't want that; it's bound to be worse when I pile on rules and daemons.

So I thought I'd subdivide the (sorted) giant table into a tree structure and then do a binary search. The idea seemed solid. I built it to access by number (called x), and got the game to load the giant table, chunk it into 32 equal-sized tables on the leaf-nodes, and then I recursively let the max-x values bubble up the tree in (fixed-size) tables (basically, top node table has 2 subtables, which each have 2 subtables, etc, each looking something like this:

Code:
Table of Top-Node
max-x   table-name
102   Table of Sub-node a
230   Table of Sub-node b

Table of Sub-node a
max-x   table-name
63   Table of Sub-node a a
102   Table of Sub-node a b

Table of Sub-node b
max-x   table-name
160   Table of Sub-node b a
230   Table of Sub-node b b
.

While finished code does run, I still sensed a small but perceptible delay in the built-in i7 terp (which has always been slow as molasses on my end, but still). So I guess what I'm asking is, am I just reinventing something I7 does under the hood already, or could this method help reduce lag to a useful degree?

_________________
~Björn Paulsen


Top
 Profile Send private message  
Reply with quote  
PostPosted: Fri Sep 14, 2018 10:18 am 
Offline

Joined: Sat Jan 23, 2010 4:56 pm
Posts: 5804
I7 does not do that under the hood. Table searches are simple linear loops.

However, a loop of 256 values isn't *that* bad. Consider the possibility that some rule elsewhere in your code is doing something expensive.

If you can figure out how to run a profiling interpreter, that may be helpful. Unfortunately this is a pain in the ass, both to do (https://github.com/erkyrath/glulxe/blob ... analyze.py) and to understand the output.


Top
 Profile Send private message  
Reply with quote  
PostPosted: Fri Sep 14, 2018 10:35 am 
Offline
User avatar

Joined: Sun Nov 22, 2009 12:58 pm
Posts: 796
Location: Malmö, Sweden
Ah. No, this is a fresh project just to test out the code. It does nothing but lookups and one numeric comparison per element in one When Play Begins rule. And yeah, there's also about eight square root operations in there, but even without them it still lags noticeably.

Guess I'll try super-large iterations and stick a timer in there, see what happens.

_________________
~Björn Paulsen


Top
 Profile Send private message  
Reply with quote  
PostPosted: Fri Sep 14, 2018 1:25 pm 
Offline

Joined: Fri Oct 18, 2013 10:13 am
Posts: 2664
Location: The Midwest
If the table is sorted, there are some shiny Glulx tricks you can use to have the interpreter do a more efficient search. I'm not sure if I7 uses any of them for table searches at present.

_________________
Daniel Stelzer


Top
 Profile Send private message  
Reply with quote  
PostPosted: Fri Sep 14, 2018 2:27 pm 
Offline

Joined: Sat Jan 23, 2010 4:56 pm
Posts: 5804
All simple linear loops, I promise.


Top
 Profile Send private message  
Reply with quote  
PostPosted: Fri Sep 14, 2018 6:27 pm 
Offline
User avatar

Joined: Wed Oct 14, 2009 4:02 am
Posts: 2546
Each column is stored in a separate array so it would be possible to use @linearsearch (no sorting required). Probably wouldn't be too hard to make an extension to do that. If anyone wants to try, look for the TableRowCorr function and the others around it.

Once change that would make a big performance difference would be to make Inform use Glulx's malloc instead of its own heap implementation. Every call to BlkValueRead and BlkValueWrite is orders of magnitude slower than it would be compared to reading and writing to a malloc'd block of memory.


Top
 Profile Send private message  
Reply with quote  
PostPosted: Fri Sep 14, 2018 6:51 pm 
Offline

Joined: Sat Jan 23, 2010 4:56 pm
Posts: 5804
Glulx's malloc is pretty shoddily implemented, mind you. It's shoddily implemented in C (or JS), rather than in I6 code, which is indeed an improvement, but I always wince when I think about it...

I still think that a perceptible slowdown when dealing with a 256-element table is not caused by searching the table. Sorting the table, maybe, if that's a thing which is happening.


Top
 Profile Send private message  
Reply with quote  
PostPosted: Fri Sep 14, 2018 6:52 pm 
Offline

Joined: Fri Oct 18, 2013 10:13 am
Posts: 2664
Location: The Midwest
Exactly, and if it's sorted anyway, you could use @binarysearch (though for 256 elements the difference should be imperceptible).

How much work would be involved in switching out BlkValue* for @malloc and @free? I.e. how deeply entrenched are they?

And zarf is of course correct, a linear search through 256 elements shouldn't be causing a delay.

_________________
Daniel Stelzer


Top
 Profile Send private message  
Reply with quote  
PostPosted: Fri Sep 14, 2018 7:24 pm 
Offline
User avatar

Joined: Wed Oct 14, 2009 4:02 am
Posts: 2546
Zarf, that's an implementation detail though, right? Just as there are multiple C malloc implementations, it would be possible to improve the ones in Glulxe, Git, and Quixe. But even without improvements, letting the terp handle it would be so much more performant than the the BlkValue functions.

Draconis, it might be possible to do in an extension. But it would be close to a thousand replacements.


Top
 Profile Send private message  
Reply with quote  
PostPosted: Sat Sep 15, 2018 3:06 pm 
Offline

Joined: Tue Mar 09, 2010 2:34 pm
Posts: 5405
Location: Burlington, VT
This is a shot in the dark, but would it be more efficient to use the table to define a kind of value and then look up things according to the kind of value? So instead of choosing a row with a foo value of bar and then getting the baz entry, you would define bar as one of many different foos and then look up the baz property that bar has. I don't know if there are any circumstances in which that is quicker.

Also, instead of doing square-root operations, is it possible to work with the square of the value? When I was doing grid distance in Terminator, instead of determining the distance from (3, 3) to (4, 5) as sqrt((4 - 3)^2 + (5 - 3)^2) and then comparing that to 3, I would determine the squared distance to be (4 - 3)^2 + (5 - 3)^2 and compare that to 9. Just another shot in the dark if you're using square roots, you might be able to avoid floating point arithmetic that way.


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

All times are UTC - 6 hours [ DST ]


Who is online

Users browsing this forum: Google [Bot] and 17 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