Question about Glulx search opcodes and I7 tables

When I repeat through a table in Inform 7 in order to search the table for a particular row, does the code eventually compile to the relatively speedy Glulx search opcodes? I have a slow table, and am trying to give it a shot in the arm.

Would there be any benefit to me using the opcodes directly in an I6 inclusion specifically for this one table? I’m reading this of course: eblong.com/zarf/glulx/glulx-spec_2.html#s.16

A quick test indicates that no, the I7 compiler is not generating those opcodes for table searches.

It looks like the table structure is too complicated to use them in the general case. My test was an example from the manual:

	choose row with a name of "Victoria" in the Table of Recent Monarchs;

The I6 routine in question is TableRowCorr(), and it has a couple of variant code paths to handle the case where you’re searching for a blank entry, and the case where you’re searching a column of block-allocated (as opposed to scalar) values. That’s too fancy to do with @linearsearch.

If the I7 compiler were willing to split this up into several routines, and call the appropriate one based on call-specific knowledge, it could implement some of them using @linearsearch. (But then, splitting them up like that would produce faster code even without @linearsearch. There would be fewer “if” tests per interation. The tradeoff is more ROM usage, which could be bad for Z-code games.)

For your specific case, it may well be worth doing this, if the column you’re searching on is a scalar (i.e., not indexed text or a list or some other fancy new type). If you can ensure that the column is sorted, then you can use @binarysearch which will be slightly better.

But this is only relevant if you really are spending a lot of time searching the table. How many rows, and how many times per turn do you hit it?

Ah, perfect. I’m working with something like command history a la TADS, so the table length is “infinite”. But it starts out blank, and fills up in row order so it’d never come across a blank entry, so there’s promise of faster ways of doing search. I long ago replaced its stored action column with 4 separate object (& action name) columns for performance reasons. A couple of other columns are bitfields: known-by, for example.

It’s chronologically sorted of course, but since turn count = row#, @binarysearch isn’t useful to me. Alas. Searches on the table range from 0 to 3+ per turn.

Thanks zarf, I’ll work on this. Now I just gotta figure out some specifics. I don’t know any column would be particularly well-suited to being the first to search on. Maybe the noun’s column? Maybe use a new column for a hash of some sort? Some of the rows will have wildcards for entries – such as my someone-word object – which should match anyone. Hrm.

(I think the only possible thing more useful to me was a @linersearch that, instead of taking one key value and testing for equality, it would take two values for ANDing: a care/don’t-care bitmask, and a must-be-1 bitmask, which test each entry with “if ((entry & care-dont-care) == must-be-1), decide on matches.” (With that, I’d create a hash column that has some bits from column 1, some bits from column 2, etc.))

Anyway, even plain ol’ @linearsearch should be noticeably faster than even the tightest I6 loop.

w00t! Not even my old Mac bats an eye at searching down 70 rows across 5 columns, three times over in a single turn. You’d think I had the collated answer hard-coded to an Instead rule. :smiley: Here’s the relevant magic bit:

Include (-
Global quickloopSearchFor; 
Global quickloopStartAddress;
Global quickloopRowsLeft;
Global quickloopReturnValue;
-) after "Definitions.i6t".


To repeat through (tab - table name) until ([the next blank] row - number) with (tc - a word value of kind K valued table column) as (val - K) begin -- end: 
(-	{-require-ctvs} 
	ct_0 = {tab};
	ct_1 = -1;
	quickloopSearchFor = {val}; 
	quickloopStartAddress = ({tab})-->(TableFindCol({tab}, {tc}, true)) + (COL_HSIZE * WORDSIZE); 
	quickloopRowsLeft = {row};
	quickloopReturnValue = -1;
	while (1) {
		@linearsearch quickloopSearchFor WORDSIZE quickloopStartAddress WORDSIZE quickloopRowsLeft 0 4 quickloopReturnValue;
		quickloopReturnValue++;
		if (quickloopReturnValue == 0) break;
		ct_1 = ct_1 + quickloopReturnValue;     ! set the chosen row for I7
		quickloopStartAddress = quickloopStartAddress + (WORDSIZE * quickloopReturnValue);  ! set start point for next iteration
		quickloopRowsLeft = quickloopRowsLeft - quickloopReturnValue;  ! decrease #/rows left to check
!-).    [ ...and comment out the auto-generated opening brace ]

Thanks for the pointers, zarf. Took me an hour before I remembered that tables are stored in column-major order rather than row-major, but after watching my WIP zip through a green Skein, the hours I toiled were totally worth it. The code even ends in a winky-smiley, complete with beauty mark.

Thanks again.

EDIT: added the “of kind K” restrictions on the parameters, added comment in the parameter to clarify the expected row#, and removed the unneeded {-zero…} macro command. The loop assumes all filled rows are consecutive.

It would be worth it for most Glulx games, which aren’t shy about using big tables. But it basically begs for having a Tables.i6t specifically for Glulx, with slightly different to-phrases in the Standard Rules exposing them. Since the 6E builds of Inform allow type specifications like “word value valued table column” and the like, just as my above loop does, to-phrases could differentiate between the scalar and block types invisibly.

Blank entries aren’t actually a problem. All blank entries use a particular unlikely value for their value – on Glulx that value is the memorable 0xDEADCE11 – so you can safely use @linearsearch to zip right past it, as the chances of your real data just happening to have that same value are close to nil. (And even then, a do…until loop wrapped around the opcode to ensure non-blankness solves that edge case neatly.)

Only real snafu I see for speed is how tables are arranged in Inform. The opcodes are created with row-major arrays in mind. Inform uses column-major ordering though, because Inform is typesafe and a single column is all of one type. But if Tables.i6t were rewritten for Glulx speed, and put into row-major ordering, then yet more speed could be gained because – correct me if I’m wrong – the key (“searched for”) value used in @linearsearch and such can check more than one scalar at a time. Meaning, it could check more than one column at a time.

Has anyone tried writing such a thing? I think Jesse or some other RAIF denizen mentioned wanting such a thing, but surely those of you more familiar with Glulx opcodes and I6 coding would’ve tackled this before an I7-head like me even knew such opcodes existed.

Searching for a blank entry is a special case in the code. If you think it can be deleted, go tell Graham :slight_smile:

I’ve adapted Ron’s presentation of @linearsearch above to adapt the TableRowCorr() routine. It seems to work for some seeks on number-typed columns, but not for others.

[code]Include (-
Global seekStartAddress;
Global seekRows;
-) after “Definitions.i6t”.

To select a/the/-- row with (TC - a word value valued table column) of (W - a word value) in/from (T - table name):
(- {-require-ctvs}
ct_0 = {T};
ct_1 = -1;
seekStartAddress = ({T})–>(TableFindCol({T}, {TC}, true)) + (COL_HSIZE * WORDSIZE);
seekRows = TableRows({T});
@linearsearch {W} WORDSIZE seekStartAddress WORDSIZE seekRows 0 4 ct_1;
if (ct_1 < 1) return RunTimeProblem(RTP_TABLE_NOCORR, {T});
-).[/code]

Can anyone see what I’ve done wrong?

Thanks!

–Erik

It’s 1:30 pm, and I just woke up.

I’m pretty sure there was a reason I aliased variables rather than using {w} and such directly on @linearsearch’s line. You might want to try that.

Also, why I forgot to include “of kind K” and such in the parameters I don’t remember, but that should probably be there.

Awesome. :slight_smile:

But seriously guys, you’re scaring the newbies (and some of the old bees). Maybe no one wants to look snooty by putting “(Advanced)” in the title of their post, but it’s shorter than "super - advanced crap that you’ll never need to know or understand for that matter, but when the people on this thread figure it out it will probably make your life easier in unseen ways (or SACtYNN2KoU4tMBWtPotTFIOIWPMU’rLEiUW for short). :wink:

Are we seriously scaring newbies? Who?

Really, this is what subject lines are for.

(Also I have not looked at this question and might not have a chance before PAX. Sorry.)

Thanks, Ron. Neither of these seem to do much, unfortunately. I’ll keep at it…

–Erik

You may want to copy my above repeat loop into your code and create your Select line in I7 from that – it would be used as a phrase but is a value-returning function in the I6. Once you get that working, you can look at the generated I6 and whittle down from there.

If you truly can’t get it to go, I can roll up my sleeves…

(The bit with the “of kind K” is just protection for client code; it wasn’t intended to fix anything within the phrase.)

Hm, I should indeed try looking at the generated I6–I could tell that the phrase can return a value (the run-time error function is returned), but I assumed that the primary intent was not to return anything, but instead to set ct_0 and ct_1.

My memory is that your code didn’t work in my little experiment either, for some reason, but I just tested it bare and it worked nicely. I haven’t had a lot of time to work on this, but I’ll give it some more attention tonight if I can.

Thanks!

–Erik

EDITED TO ADD: And my code seems to work too, when tested bare. (By which I mean in a separate, simplified project; I’m using the Port Royal 4 example.) So I need to approach this differently. I’m not sure how; the functionality of my “select a row” phrase (or your repeat phrase forced to stop after the first found entry) should be identical to the TableRowCorr() routine called by the library’s “choose a row” phrase. Here’s the code that appears to be working:

[code]Include (-
Global seekStartAddress;
Global seekRows;
Global seekVal;
-) after “Definitions.i6t”.

To select a/the/-- row with (TC - a word value valued table column) of (W - a word value) in/from (T - table name):
(- {-require-ctvs}
ct_0 = {T};
ct_1 = -1;
seekStartAddress = ({T})–>(TableFindCol({T}, {TC}, true)) + (COL_HSIZE * WORDSIZE);
seekRows = TableRows({T});
seekVal = {W};
@linearsearch seekVal WORDSIZE seekStartAddress WORDSIZE seekRows 0 4 ct_1;
if (ct_1 < 1) return RunTimeProblem(RTP_TABLE_NOCORR, {T});
-).[/code]

It’s different from the code posted upthread in just one respect: the addition of seekVal; having a bare {W} in the @linearsearch produced a compiler error in my test project, but not my actual WIP. Odd! Anyway, this points me in the right direction…

Well I hadn’t had any trouble with the loop in my WIP as far as I know, but I’m interested of course if you find problems with it. If you can find a test case that breaks it then please post it & I’ll try to fix.

Ron, what is the number of rows that is intended to be passed into your function? I assume that it is the total number of rows in the table. I assume this because I’ve not been able to get it to work correctly any value other than the total number of rows, and I ask because there is definitely a problem with the code: some kind of misaddressing, apparently based on the number of rows in the table, can cause searches to fail. I haven’t been able to identify the precise parameters yet, but since I’m leaving tomorrow morning for a week that will have no Inform in it, I thought I’d post this while what I have discovered is fresh in my skull.

Both your code and mine (which is based on your code, but with the number of rows supplied by the TableRows() function) fail on the code below, but only if you remove the “with 2 blank rows” from the table definition. Even without the 2 blank rows, the linearsearch functions will work on the first two rows of the table, but fail to return the third row. The number of columns in the table doesn’t appear to make any difference (I’ve tested this table with 2 and 3 columns).

[code]
Include (-
Global seekStartAddress;
Global seekRows;
Global seekVal;
Global seekReturnValue;
-) after “Definitions.i6t”.

To select a/the/-- row with (TC - a word value valued table column) of (W - a word value) in/from (T - table name):
(- {-require-ctvs}
ct_0 = {T};
ct_1 = -1;
seekRows = TableRows({T});
!print "rows: ", seekRows, "; value: ", {W}, ". ";
seekStartAddress = ({T})–>(TableFindCol({T}, {TC}, true)) + (COL_HSIZE * WORDSIZE);
seekVal = {W};
@linearsearch seekVal WORDSIZE seekStartAddress WORDSIZE seekRows 0 4 ct_1;
if (ct_1 < 1) return RunTimeProblem(RTP_TABLE_NOCORR, {T});
-).

Include (-
Global quickloopSearchFor;
Global quickloopStartAddress;
Global quickloopRowsLeft;
Global quickloopReturnValue;
-) after “Definitions.i6t”.

To repeat through (tab - table name) until (row - number) with (tc - a word value valued table column) as (val - a word value) begin – end:
(- {-require-ctvs} ! {-zero-counter:reviewHistoryCol}
ct_0 = {tab};
!print "rows: ", {row}, "; value: ", {val}, ". ";
ct_1 = -1;
quickloopSearchFor = {val};
quickloopStartAddress = ({tab})–>(TableFindCol({tab}, {tc}, true)) + (COL_HSIZE * WORDSIZE);
quickloopRowsLeft = {row};
quickloopReturnValue = -1;
while (1) {
@linearsearch quickloopSearchFor WORDSIZE quickloopStartAddress WORDSIZE quickloopRowsLeft 0 4 quickloopReturnValue;
quickloopReturnValue++;
if (quickloopReturnValue == 0) break;
ct_1 = ct_1 + quickloopReturnValue; ! set the chosen row for I7
quickloopStartAddress = quickloopStartAddress + (WORDSIZE * quickloopReturnValue); ! set start point for next iteration
quickloopRowsLeft = quickloopRowsLeft - quickloopReturnValue; ! decrease #/rows left to check
!-).

When play begins:
say “Rows: [number of rows in the Table of Smiles].”;
select row with a smile number of 2 in the Table of Smiles;
say “smile 2 is [key entry] by the lights of the new ‘select…’ phrase.”;
repeat through the Table of Smiles until (the number of rows in the Table of Smiles) with smile number as 2:
say “smile 2 is [key entry] by the lights of the new ‘repeat…’ phrase.”

There is a room.

Table of Smiles
smile number key
0 “: )”
1 “; )”
2 “:->”
with 2 blank rows[***Remove these blank rows to see lookup fail][/code]

My little WIP has another table that seems to work when it is declared empty with 99 blank rows, but not if declared with 100 blank rows; again, much of the table is searched correctly, but data near the bottom (the last two filled rows) is not found.

If I get a chance tonight, I’ll try taking a look at the actually I6 array content and see how it matches up with the seek addresses…

Thanks,
Erik

The number of filled rows. Though it should still work with all rows, IIRC; I added that only as an optimization step. Unless an entry just happens to have the same value that flags a blank, which is exceedingly rare, it should still work.

Sometimes the very first row is blank if the type of columns appears under the header row, but that would only lose you one row off the bottom.

I’ll poke around with this example today.

Hm. Using filled rows I get even more miserable outcomes–failure in most test cases…

–Erik

My bad, I never meant to put the phrases “the number of filled rows in the table of…” into that phrase, because it finds the answer by looping through the table and counting, which kills any speed gain by using @linearsearch to begin with.

I had a variable, the next blank history row, which went into that spot. And like its name implies, it points to the first blank row, not the last filled row. Hence there’s an off-by-1 error in your just-posted test case. I believe you can fix your select by using seekRows = TableRows({T}) + 1;

EDIT TO ADD: I fixed my original loop sample on page 1 of this thread to make its assumptions more clear, including the “of kind K” parameter check.

Great, thanks for the clarification. It looks like to search a table completely, though, you need n + 1, not just n. In other words, this table:

Table of Smiles smile number key 0 ": )" 1 "; )" 2 ":->"

…has 3 rows, but your phrase needs to have 4 passed into it in order to find data in the final row:

repeat through the Table of Smiles until 4 with smile number as 2:

I’ll test this in my WIP when I get a chance, hopefully tonight. I do remember hardcoding n + 1 rows into my main table and still having problems. But that table also has a types header row, which may mean that it needs to be n + 2. (My filled rows should always be consecutive, and I have no blank columns, so those at least shouldn’t be issues, at least not for this application.)

–Erik

Edited to add little this note, acknowledging that you added the n + 1 thing to your last post before I put up this reply…

Great, n + 2 seems to fix everything, and provides a nice speed boost, to boot!

Thanks, Ron!

–Erik