SCMD_LOADSPOFFS inefficient code (script interpreter)

[ghost]

As noted by @rofl0r earlier, SCMD_LOADSPOFFS implementation became very inefficient in comparison to the original script VM.

Original code: https://github.com/adventuregamestudio/ags/blob/legacy/Common/csrun.cpp#L1499

New code is implemented as ccInstance::GetStackPtrOffsetRw function:

ags/Engine/script/cc_instance.cpp

Lines 2261 to 2278 in 5adc343

	RuntimeScriptValue ccInstance::GetStackPtrOffsetRw(int32_t rw_offset)
	{
	int32_t total_off = 0;
	RuntimeScriptValue *stack_entry = registers[SREG_SP].RValue;
	while (total_off < rw_offset && stack_entry >= &stack[0])
	{
	stack_entry--;
	total_off += stack_entry->Size;
	}
	CC_ERROR_IF_RETVAL(total_off < rw_offset, RuntimeScriptValue, "accessing address before stack's head");
	RuntimeScriptValue stack_ptr;
	stack_ptr.SetStackPtr(stack_entry);
	stack_ptr.IValue += total_off - rw_offset; // possibly offset to the mid-array
	// Could be accessing array element, so state error only if stack entry does not refer to data array
	CC_ERROR_IF_RETVAL((total_off > rw_offset) && (stack_entry->Type != kScValData), RuntimeScriptValue,
	"stack offset backward: trying to access stack data inside stack entry, stack corrupted?")
	return stack_ptr;
	}

as you may notice, instead of simply "jumping" into requested address the new code parses the stack checking it entry by entry until accumulating necessary offset.

TBH I don't remember all details now, but I think the main reason for this function was that old stack was implemented as a plain sequence of bytes, while the new stack is implemented as an array of RuntimeScriptValue objects, which in turn may contain pointers to larger data (such as arrays) allocated separately. The new code also stores separate Ptr as an address of the object's "head" and extra offset in IValue.
You may also notice the "64-bit" fix in the legacy branch which did similar thing and maybe which I used as a reference too.

Given the above, I am not sure if it's easy to optimize this particular operation without changing some fundamental principles of how new interpreter works.

[ericoporto]

@ivan-mogilko the lines from the original comment apparently changed now, but is this still true?

[ivan-mogilko]

@ivan-mogilko the lines from the original comment apparently changed now, but is this still true?

It become somewhat faster only because the assertions are now done in debug mode, but the suboptimal algorithm still persists.

EDIT: fixed the code reference.

The original scummvm port used a hashmap there, where the key was the offset of each variable, but I found that it's incorrect, because compiler may instruct to jump in the middle of a local struct or array too.

In theory one could try using a map or sorted vector, and lower bound function (iirc), but idk if that would really be faster than a loop (may not be faster unless there's a big number of local variables).

[ericoporto]

Looked up the history a bit, the following part of jjsat commit here
jjsat@22221b6#diff-4db3d150dec6fcd9180c42130e5d06d6f11649403d1a1d46700564785284e0dbR1456-R1481

We see that load.sp.offs was used to load the value of the stack pointer (SP) with an offset, moving the stack pointer up or down.

But then, after the commit, it changed from

case SCMD_LOADSPOFFS:
  inst->registers[SREG_MAR] = inst->registers[SREG_SP] - arg1;

to

case SCMD_LOADSPOFFS:

  // 64 bit: Rewrite offset so that it doesn't point inside a variable
  original_sp_diff = arg1;
  new_sp_diff = 0;
  sp_index = inst->stackSizeIndex - 1;

  while (original_sp_diff > 0)
  {
    if (inst->stackSizes[sp_index] == -1)
    {
      original_sp_diff -= 4;
      new_sp_diff += sizeof(long);//inst->stackSizes[sp_index];
      sp_index--;
    }
    else
    {
      original_sp_diff -= inst->stackSizes[sp_index];
      new_sp_diff += inst->stackSizes[sp_index];
      sp_index--;
    }
  }

  if (sp_index < -1)
    cc_error("Stack offset cannot be rewritten. Stack corrupted?");

  inst->registers[SREG_MAR] = inst->registers[SREG_SP] - new_sp_diff;

This was the intermediary change for 64-bit compatibility - before RuntimeVariables.