Add host functions and/or guest utilities to deal with nested VecObjects

[salaheldinsoliman]

Add host functions and/or guest utilities to deal with nested VecObjects

Introduction

In this discussion, I will explain the differences in how Solidity and Soroban deal with arrays (both memory and storage).

Then, I will explain which approaches Solang(A Solidity compiler to Soroban) explored to support memory and storage arrays, and the issues encountered along the way.

Finally, I will lay out my proposed solutions, which may involve adding host functions that manipulate or read VecObjects.

Background

Arrays: Solidity vs. Soroban dialect

• Passing an array as a function parameter: In Solidity, when a memory array is passed as a function parameter, its bytes are ABI-encoded. The compiler allocates memory, decodes the array, and copies it into memory.
  In Soroban, arrays are most often passed to public functions as VecObjects. The host provides functions to read and mutate the VecObject. At this stage, no copying to linear memory is needed.

• Reading/mutating an array in memory: In Solidity, if the array is in memory, reading or mutating it involves pointer calculations and mload/mstore.
  In Soroban (if the developer created a new VecObject and did not use alloc), reading/mutating VecObjects involves host function calls (vec_get, vec_set, etc.). The same concept applies after storing the VecObject handle in the ledger as well.

• Storing a memory array in the ledger: In Solidity, copying a memory array to the ledger involves an O(n) loop, where each element is stored separately, each with a separate SSTORE (the opcode for storing a value).
  In Soroban, the guest can store an entire VecObject in the ledger via a single call to the put_contract_data host function.

With the above concepts in mind, let's discuss the implications for nested Solidity arrays.

Implications for nested arrays

A Solidity developer would expect the cost (and mechanics) of setting an element in a nested Solidity array to be as follows:

1. Random access in a storage array costs D * index calculations + D * load/store, where D is the number of dimensions.
2. Copying a memory array to storage is O(n), where n is the number of elements.

In Soroban, however, random access of an element in a nested VecObject involves:

// define an empty 2D vector to use as default
let empty_2d_vec: Vec<Vec<u64>> = vec![&env, Vec::new(&env)];

// get a nested vector from storage
let mut nums = env
    .storage()
    .instance()
    .get(&MULTI_DIM_VEC)
    .unwrap_or(empty_2d_vec);

// first, get the first inner vector
let mut inner_vec = nums.get(0).unwrap();

// then, set its element 0 to 1
inner_vec.set(0, 1u64);

// now, set the updated inner vector back to the outer vector
nums.set(0, inner_vec);

// finally, store the updated outer vector back to storage
env.storage().instance().set(&MULTI_DIM_VEC, &nums);

Meanwhile, copying a nested VecObject to storage is O(1) (a single call to put_contract_data).

In Solang, we do not try to forcefully mimic Solidity's memory and storage layout for supported targets. Instead, we support the syntax and explain how things work under the hood on the target VM compared to Solidity.

This leaves Solang with a few options when dealing with arrays in memory and storage.

Possible routes to support storage and memory arrays in Solidity, and open questions/issues with each one

Route 1: Deal with VecObjects as-is, but request extra host functions from the Stellar core team

The first route is to deal with VecObjects as-is. Solang would not copy anything to the guest linear memory by default; it would translate array access (storage or memory) to vec_get/vec_set. Of course, it must be made clear to developers that the array is not literally in memory—only its handle is.

The issue with that approach is that Solidity syntax makes nested arrays appealing (whether in memory or storage). On the other hand, accessing an element in a nested VecObject would require crossing the host <=> guest boundary multiple times, which is more costly than a Solidity developer would expect.

Solang already supports alloc in linear memory, but I would argue that Soroban would not encourage developers to rely on that most of the time.

What I'm proposing is the host function vec_get_in / vec_set_in:

{
  "export": "...",
  "name": "vec_get_in",
  "args": [
    {
      "name": "v",
      "type": "VecObject"
    },
    {
      "name": "indices",
      "type": "VecObject"
    }
  ],
  "return": "Val",
  "docs": "Returns the element at the ordered `indices` of the vector. Traps if any index is out of bounds, or if the vector's depth does not match the indices length."
}

I would also argue that having this host function would simplify nested VecObject access in the Rust contracts SDK as well:)

Route 2: Mimic Solidity by unpacking a received VecObject into linear memory

In this route, a Solidity memory array would literally exist in the guest linear memory (not in the host) via vec_unpack_to_linear_memory. Storing the array in the ledger would be done by storing each element separately in storage, the Solidity way.

The overhead would be unpacking into memory and decoding the values, which is already expected in Solidity. However, the same issue remains: how can we unpack a nested VecObject into linear memory without doing lots of work in the guest?

Therefore, this route would require an implementation such as deep_vec_unpack_to_linear_memory, which handles nested VecObjects.

Summary

I'm more inclined to follow Route 1. Although it strays away from Solidity's memory and storage layout for vectors, it makes full use of Soroban's VM design. What do you think? Are there other routes to explore?

[leighmcculloch]

The host functions seem reasonable to me, but I think to really weigh up the cost benefit, some hard numbers are needed for how bad in terms of resource costs the status quo is.

For a double nested Vec, the cost is a couple host functions which does not seem significant, it's an N multiplier on cost were N is small I believe.