[dev] SCI: selector mystery

[pipper]

Hi,
I'm in the process of making the SCI engine more palatable for an 030 Amiga on OS3.
One function that shows up during profiling is Object::locateVarSelector().
It basically walks the list of _baseVar in a linear fashion until it finds 'Selector slc' in there (or not).

In order to accelerate that lookup I made it so that _baseVar is basically sorted for the selector ID.
This way I can do a binary search on the array, bringing theoverall cost of this function down by ca. 50%
https://github.com/mheyer32/scummvm-ami ... 509ad8cbbb

The code I have works for SQ1, but somehow subtlety breaks SQV during start of the game already:

Code: Select all

[2019-01-30 21:54:39] Access violation reading : 252 + 2 > 236 (abs: 2683 + 2 > 2667)!

From outside of the Object class, there should be no observable difference in behavior to prior
the change (when _variables and _baseVars were in 1:1 sync), but _something_ must have changed.

I have only a vague idea of what selectors are - I thought them to be sort of a symbolic identifier, like a unique variable name.
I started printing the selector Ids that Object::init() observes when starting up.
And to my surprise the same selector Id can be multiple times in the list:

This is an example of the order in which Object::init() puts selectors into _baseVars:

Code: Select all

[2019-01-30 21:54:38] inserting baseVar 0, slc 0 
[2019-01-30 21:54:38] inserting baseVar 1, slc 12 
[2019-01-30 21:54:38] inserting baseVar 2, slc 0 
[2019-01-30 21:54:38] inserting baseVar 3, slc 32768 
[2019-01-30 21:54:38] inserting baseVar 4, slc 54 
[2019-01-30 21:54:38] inserting baseVar 5, slc 0 
[2019-01-30 21:54:38] inserting baseVar 6, slc 0 
[2019-01-30 21:54:38] inserting baseVar 7, slc 0 
[2019-01-30 21:54:38] inserting baseVar 8, slc 0 
[2019-01-30 21:54:38] inserting baseVar 9, slc 127 
[2019-01-30 21:54:38] inserting baseVar 10, slc 0 
[2019-01-30 21:54:38] inserting baseVar 11, slc 1 
[2019-01-30 21:54:38] inserting baseVar 12, slc 0 
[2019-01-30 21:54:38] inserting baseVar 13, slc 0 
[2019-01-30 21:54:38] inserting baseVar 14, slc 0 
[2019-01-30 21:54:38] inserting baseVar 15, slc 0 
[2019-01-30 21:54:38] inserting baseVar 16, slc 0 
[2019-01-30 21:54:38] inserting baseVar 17, slc 0 
[2019-01-30 21:54:38] inserting baseVar 18, slc 0 
[2019-01-30 21:54:38] inserting baseVar 19, slc 0 
[2019-01-30 21:54:38] inserting baseVar 20, slc 0 
[2019-01-30 21:54:38] inserting baseVar 21, slc 28499 
[2019-01-30 21:54:38] inserting baseVar 22, slc 28277 
[2019-01-30 21:54:38] inserting baseVar 23, slc 100  

This is the _baseVars array when using insert() into a SortedArray. propIdx is pointing back to its original variable index.

Code: Select all

[2019-01-30 21:54:38] baseVar 0, propIdx 2, slc 0 
[2019-01-30 21:54:38] baseVar 1, propIdx 6, slc 0 
[2019-01-30 21:54:38] baseVar 2, propIdx 5, slc 0 
[2019-01-30 21:54:38] baseVar 3, propIdx 7, slc 0 
[2019-01-30 21:54:38] baseVar 4, propIdx 8, slc 0 
[2019-01-30 21:54:38] baseVar 5, propIdx 10, slc 0 
[2019-01-30 21:54:38] baseVar 6, propIdx 13, slc 0 
[2019-01-30 21:54:38] baseVar 7, propIdx 15, slc 0 
[2019-01-30 21:54:38] baseVar 8, propIdx 17, slc 0 
[2019-01-30 21:54:38] baseVar 9, propIdx 19, slc 0 
[2019-01-30 21:54:38] baseVar 10, propIdx 20, slc 0 
[2019-01-30 21:54:38] baseVar 11, propIdx 18, slc 0 
[2019-01-30 21:54:38] baseVar 12, propIdx 16, slc 0 
[2019-01-30 21:54:38] baseVar 13, propIdx 14, slc 0 
[2019-01-30 21:54:38] baseVar 14, propIdx 12, slc 0 
[2019-01-30 21:54:38] baseVar 15, propIdx 0, slc 0 
[2019-01-30 21:54:38] baseVar 16, propIdx 11, slc 1 
[2019-01-30 21:54:38] baseVar 17, propIdx 1, slc 12 
[2019-01-30 21:54:38] baseVar 18, propIdx 4, slc 54 
[2019-01-30 21:54:38] baseVar 19, propIdx 23, slc 100 
[2019-01-30 21:54:38] baseVar 20, propIdx 9, slc 127 
[2019-01-30 21:54:38] baseVar 21, propIdx 22, slc 28277 
[2019-01-30 21:54:38] baseVar 22, propIdx 21, slc 28499 
[2019-01-30 21:54:38] baseVar 23, propIdx 3, slc 32768 

Now as you may have noticed, selector 0 appears multiple times in there, pointing back to different original property indices.
(Other objects have multiple selectors, too - even of the same value != 0)

But what does it mean to have the same selector multiple times, pointing to a different property each time?

The only observable difference I could imagine is, if someone is trying to lookup selector 0, the original
linear search would have brought up index '0' as it is the first hit _baseVar with selector 0.
The binary search will likely cough up any other of the original _baseVars with selector 0, but likely not 0.


I'd appreciate, if someone could enlighten me on what exactly selectors are (the Wiki is too vague about them) and to what rules
they must adhere.
Other ideas on how to accelerate the selector lookup in general are greatly appreciated, too.
Sci::lookupSelector() is eating up 10% of the runtime alone on this old machine

[OmerMor]

I can't answer your question, but you can try the following:

1. Try to figure how Sierra implemented this, in their interpreter. The source can be found here: https://github.com/OmerMor/SCI16
2. Ask in the SCI Programming forums: http://sciprogramming.com/community/index.php. It has many SCI experts there who could help you.

[pipper]

The question has become moot. There was a very subtle bug in the refactoring that affected only the SCI_LATE_1_1 games and resulted in corrupted baseVar selectors (thus the multiple entries).

But thanks for the pointers!