intfiction.org

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:

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

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.

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

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

All simple linear loops, I promise.

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.

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.

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

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.

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.