List representation in WASM

[poorna2152]

Using the array type described in the gc proposal to represent the lists.

• https://github.com/WebAssembly/gc/blob/main/proposals/gc/Overview.md#arrays

Sample

import ballerina/io;

public function main() {
    io:println([1, 2, 3]); // @output [1,2,3]
}

Procedure:

• Define new array type which can set of store anyref values: (type $any_list (array (mut anyref)))

• Create a variable of the above mentioned type with the length of the array. First parameter is the length of the array: (array.new_default_with_rtt $any_list (i32.const 3) (rtt.canon $any_list)))

• Set the values of the array. (array.set $any_list (local.get $3) (i32.const 0) (local.get $0))

• Call println function with the array reference. (call $println (local.get $3))

• println checks the type of the reference passed to it using the get_type function exported from the wasm module.

• If the reference is of type array then println uses the exported function len from the wasm module to get the length of the array.

• Loop over the length of the array get each element by passing the array reference and index to the array_get function exported from the wasm module.

• Print the values.

(module
  (type $BoxedInt (struct (field $val i64))) 
  (type $any_list (array (mut anyref)))
  (import "console" "log" (func $println (param anyref))) 
  (export "main" (func $main)) 
  (export "tagged_to_int" (func $tagged_to_int)) 
  (export "get_type" (func $get_type)) 
  (export "len" (func $len)) 
  (export "array_get" (func $array_get)) 
  (func $main 
    (local $0 anyref) 
    (local $1 anyref) 
    (local $2 anyref)
    (local $3 (ref null $any_list))
    (block 
      (local.set $0
        (call $int_to_tagged
          (i64.const 1)))
      (local.set $1
        (call $int_to_tagged
          (i64.const 2)))
      (local.set $2
        (call $int_to_tagged
          (i64.const 3)))
      (local.set $3
        (array.new_default_with_rtt $any_list (i32.const 3) (rtt.canon $any_list)))
      (array.set 
        $any_list 
        (local.get $3) 
        (i32.const 0) 
        (local.get $0))
      (array.set 
        $any_list 
        (local.get $3)
        (i32.const 1)
        (local.get $1))
      (array.set 
        $any_list 
        (local.get $3)
        (i32.const 2)
        (local.get $2))
      (call $println 
        (local.get $3)) 
      (return)))
  (func $int_to_tagged (param $0 i64) (result anyref) 
    (return 
      (struct.new_with_rtt $BoxedInt 
        (local.get $0) 
        (rtt.canon $BoxedInt))))
  (func $tagged_to_int (param $0 anyref) (result i64) 
    (return 
      (struct.get $BoxedInt $val 
        (ref.cast 
          (ref.as_data 
            (local.get $0)) 
          (rtt.canon $BoxedInt)))))
  (func $len (param $0 anyref) (result i32)
    (array.len 
      $any_list
      (ref.cast
        (ref.as_data 
          (local.get $0)) 
        (rtt.canon $any_list))))
  (func $array_get (param $0 anyref) (param $1 i32) (result anyref)
    (array.get 
      $any_list  
      (ref.cast
        (ref.as_data 
          (local.get $0)) 
        (rtt.canon $any_list)) 
      (local.get $1)))
  (func $get_type (param $0 anyref) (result i32) 
    (if 
      (ref.is_i31 
        (local.get $0)) 
      (return 
        (i32.const 1)) 
      (if 
        (ref.is_null 
          (local.get $0)) 
        (return 
          (i32.const 2))
        (return
          (i32.const 0))))))

[poorna2152]

Using this method doesn't allow us to push content to an array because array length is predefined. What can be done?

1. Preallocate more space than needed.
2. Create a new array when pushing to an array.

[manuranga]

Option 2 is the way to go, look at array in C runtime. we do the same there.

[manuranga]

Another option is to wrap javascript array shall we give that a try.

[poorna2152]

Array provides gc support in wasm. If we use C or Js wouldn't it remove that advantage

[manuranga]

1) Not to use C, look at the algorithm we use to grow an array and replicate it in wasm. 2) JS should get GC shouldn't it? I am not sure how it happens when ref escapes to wasm land.

[poorna2152]

If we are to create a new array when pushing to an array. Then we change the reference of the array. Then the following program fails.

import ballerina/io;
public function main() {
    any[] v = [0];
    any[] y = v;
    io:println(v === y); // @output true
    v.push(0);
    io:println(v === y); // @output true
}

The expected output should be true, true. But the output we get is true, false because when pushing reference gets changed.

[manuranga]

I think I didn't make myself clear enough in above 1. You will need to create a fixed length array and warp it with a another GC-able structure such as struct and return that. Provide a function that will accept an element and a wrapper (let's call this a list) and insert to the inner array. It should grow the inner array by some factor if it runs out, look at the ballerina runtime C code to get the exact starting length and factor.

[poorna2152]

Current implementation: Using a struct to represent a list.

(type $List (struct (field $arr (mut (ref $AnyList))) (field $len (mut i64)))) 
(type $AnyList (array (mut eqref))) 

• Length of the list: Actual number of elements stored in the list.
• Capacity of the list: Number of elements that can be stored in the list.
• Struct has two fields $arr: which stores the array and the $len: which stores the length of the array.
• List is created with a minimum capacity 4.
• List has a maximum capacity of 2^32. (This is due to a constraint in wasm)
• When the length equals to the capacity, capacity of the length is increased by 1.5 as done in nBallerina