The problem:
Currently, in the integration tests we are comparing decoded memory and execution traces of Nethermind Cairo-VM with the Starkware Cairo-VM implemented in Python. When we try to run the following Cairo0 programs as examples in Nethermind VM and Starkware VM with layout small, we can notice the differences in decoded memory traces, which are prompted by the integration tests.

%builtins range_check
from starkware.cairo.common.math import assert_le_felt

func main{range_check_ptr: felt}() {
    assert_le_felt(1, 2);
    assert_le_felt(-2, -1);
    assert_le_felt(2, -1);
    return ();
}


%builtins ecdsa
from starkware.cairo.common.cairo_builtins import SignatureBuiltin
from starkware.cairo.common.signature import verify_ecdsa_signature

func main{ecdsa_ptr: SignatureBuiltin*}() {
    verify_ecdsa_signature(
        2718,
        1735102664668487605176656616876767369909409133946409161569774794110049207117,
        3086480810278599376317923499561306189851900463386393948998357832163236918254,
        598673427589502599949712887611119751108407514580626464031881322743364689811,
    );
    return ();
}

After conducting some digging in the code of both VMs, I noticed, that the segments offsets, which are significant in memory relocation differ between the VMs. When running the following program:

%builtins range_check
from starkware.cairo.common.find_element import find_element
from starkware.cairo.common.alloc import alloc

func main{range_check_ptr}() -> () {
    alloc_locals;
    let (local array_ptr: felt*) = alloc();
    assert array_ptr[0] = 1;

    let (element_ptr: felt*) = find_element(
        array_ptr=array_ptr, elm_size=1, n_elms=1, key=1
    );
    assert [element_ptr] = 1;

    return ();
}


We will notice, that the segments offsets for relocation look like this:

1. Nethermind VM: [1 65 108 110 111]
2. Python VM: {0: 1, 1: 65, 2: 108, 3: 108, 4: 1644, 5: 2156, 6: 2172}

Eventhough the sizes of the segments look like this:

1. Nethermind VM (with builtin runner names):

segment 0 64 no builtin
segment 1 43 no builtin
segment 2 2 range_check
segment 3 1 no builtin

2. Python VM: (0, 64), (1, 43), (2, 0), (3, 0), (4, 2), (5, 0), (6, 1)], builtin runners keys: {'output_builtin', 'pedersen_builtin', 'range_check_builtin', 'ecdsa_builtin'}

Since the addresses during relocation are transformed into felts, by adding the address offset to the segment base (offset), this should indeed cause the differences in the values of relocated addresses. The differences in the relocated addresses values look like this:

During decoding the memory in Nethermind VM, we take the highest memory address as length of the memory. As one can see in the example, the highest memory addresses are not the same, thus the effect of decoded memory filled with nills.
From this short analysis, the difference in the memory traces is caused by two problems:

1. In our integration tests we support only two builtins layouts, "small" (pedersen, range_check, ecdsa) and "plain" (default, no builtins) for running the python-vm. Starkware Cairo VM supports different layouts, with different builtins sets. They are all specified here. As presented in the examples before, all the segments for the builtins, specified in the Python VM layout get allocated, and their segments offsets are calculated as well, even when those segments are empty. In Nethermind VM we include the builtins specified in the builtins field of the compiled program json. This might cause differences in the memory traces, as some segments from given layout might not be present in the builtins field, which will affect the segments offsets. To conclude with a question, should we support layout flags as well?
2. In Python VM the proposed solution for calculating the final segments offsets for relocation is Finalization. This method produces the relocation offsets for program segment, execution segments and builtins segments. The builtins segments offsets are calculated using this method, which utilize informations about builtin like: ratio (ratio between number of steps and the number of builtins instances), instances_per_component (the number of invocations being handled in each call to the corresponding component), as well as information about the runtime (current step). Currently in Nethermind VM we use the actual sizes of the segments during relocation, for builtins segments as well. This difference in size of the memory traces and the values of relocated addresses is caused mostly by that.