MyWASM is an extension of MyPL. It has a grammar that's similar to MyPL's but it compiles into WASM rather than having its own interpreter. And rather than leaking memory all over the place, MyWASM has a C-like memory management. MyWASM also has its own LSP extension for VSCode.
Make sure you have bun installed. Then after cloning this repository, run make install to install all the required packages. Then run make build to build the executable. The executable then can be called to compile and run MyWASM programs. Alternatively, the executables for x86 linux and Windows can be found here
MyWASM emits WAT code which is then optimized using binaryen -- the same optimizer used by Emscripten. To generate the following graph the code in ./benchmark was executed. For binaryen, the O4 flag was passed, and for gcc the O3 flag was used.
Note: The unsafe-array flag skips checking out-of-bounds access and null checking, which is similar to how arrays in C work.
The system used to run these benchmarks:
(#tables-of-contents)
- 1. Basics
- 2. Memory Management
- 3. Struct
- 4. Arrays
- 5. Strings
- 6. Imports and Namespaces
Wasm, for now, uses 32-bit memory addressing, so a 32 bit integer (i32) is used for sizes of structs, strings, and arrays. However, this would need to change in the future since there’s a proposal to add 64-bit memory indexes to WebAssembly: https://github.com/WebAssembly/memory64
There are two types of built-in functions in MyWASM:
Functions that are implemented in WASM itself:
Signature: string itos(int num)
Converts an i32 value to a string.
Signature: double itod(int num)
Converts an i32 value to f64. This is implemented using f64.convert_i32_s.
Signature: string itos(double num)
Converts an f64 value to a string.
Signature: int dtoi(double num)
Converts an f64 value to i32. This is implemented using i32.trunc_f64_s.
Signature: double stod(string str)
Converts a string to an f64 value.
Signature: int stoi(string str)
Converts a string to an i32 value. First the string is converted to f64 using stod, and then it is casted to i32.
Signature:
int length(string str)
int length(array <any_type> arr)
The length of arrays are stored at arr[-1], where arr is the pointer to the array. So all length does is read arr[-1] and return the value. Since, as mentioned before, sizes are 32-bit integers, reading -1 index means 4 bits to the left, irrespective of the type of array. Strings are just arrays of i32 values, so the same function can be used without having to implement anything special for it.
Signature: string get(int index, string str)
Returns the character at the ith index of a string. Since strings are just arrays of integers, all we need to do is str[i] and return the value.
Signature: int string_ini(int size)
Initializes a string and returns the pointer to it.
Signature: int string_ini_assign(int str_ptr, int index, int value)
Takes in the string pointer and the index, and assigns it the given value.
Note: there are other built-in functions that are used solely for internal usage, and hence have not been documented here.
Functions that need to be implemented by the host language due to technical limitations.
Signature: void print(string str)
WASM does not support basic I/O, so print needs to be implemented by the host language. When print is called, the pointer to the string is passed, which should then be used to print the string. When print is used with non-string values, then the value is casted to a string using the appropriate function mentioned in 1.2.1
Signature: string input()
The host language must take in the input from the user, then call string_ini to initiate the string, and then call string_ini_assign for each character of the string. Then it must return the pointer to the string that was returned from string_ini.
Signature: int allocate_memory(int requestedSize)
Refer to 2.2
Signature: void deallocate_memory(int index, int size)
Refer to 2.2
Signature: void sleep(int ms)
Sleeps for ms milliseconds
Signature: void random()
Returns a random f64 between 0 (inclusive) and 1 (exclusive)
WASM has native support for ints: i32.
WASM has native support for doubles: f64.
WASM does not support int8, and neither does it support int16 (WebAssembly/design#85), so i32 are used to store bool.
The way strings are implemented is rather complex to fit in this section, so refer to section 5.
Note: Since pointers are ints, i32 is used for arrays, structs and strings.
WASM has no concept of scope other than local variables in functions. This is problematic since variables can be declared in other blocks other than functions like if, while, and for. On top of that, WASM’s local variables must be declared right at the top of the functions. This means that we need to keep track of all local variables in all the local scopes. Another thing we need to consider is that local variables can have the same names, so we need to transform them in a way that they retain their original meaning. This is done in MyWASM in the following manner:
Number the current scope by its name. For example, if we have encountered 5 if statements in the current scope, then name the current scope as “if_6”. Then all the variables encountered in that if’s scope will have the prefix “if_6”. Let’s consider a concrete case:
Original code:
function void main() {
int a = 10;
if(true) {
int a = 20;
if(true) {
int a = 30;
}
} else {
int a = 40;
if(true) {
int a = 50;
} else {
int a = 60;
}
}
}
Transformed code:
function void main() {
int a = 10;
if (true) {
int if1_a = 20;
if (true) {
int if1_if2_a = 30;
}
}
else {
int else1_a = 40;
if (true) {
int else1_if3_a = 50;
}
else {
int else1_else2_a = 60;
}
}
}
I could have used WASM’s instructions for garbage collection, essentially giving me an option to not have to implement any kind of memory management. However, the GC proposal (https://github.com/WebAssembly/gc) is really new and it was hard to find a compiler that would allow compiling WebAssembly Text (WAT) to its binary format. And as far as I know, stable versions of most WASM runtimes don’t even support the GC opcodes yet. So, I decided to implement my own memory management, which was way more fun than using native opcodes.
Since WASM has access to linear memory, MyWASM manages memory in the following manner:
allocate_memory(int n): This function takes in a single i32 value, and returns the offset of the memory in a way that n bits from that offset can be used.
deallocate_memory(int index, int size): This deallocates size bits starting from offset index.
A variable called global_offset which keeps track of where memory allocation may begin; the key word being may because having the ability to deallocate memory means that an offset lesser than global_offset may be available for allocation.
NOTE: These functions need to be implemented by the host language that’s running the WASM runtime, rather than in WASM itself. This is because of one fundamental problem: keeping track of deallocated bits needs allocating memory, which inturn means deallocating that memory, which means we need to allocate memory to keep track of those bits, which means we need to deallocate memory… I think the problem is pretty obvious here.
If size bits from the offset index have to be deallocated, the memory manager keeps track that size bits are available. This is done using an AVL tree, where the keys are the size available, and the value of a particular key is a queue-like data structure which keeps track of at what offsets are size bits available.
When size bits are requested, the smallest size greater than or equal to size is grabbed from the AVL tree, and the first value of the respective queue is dequeued. If the dequeued value is equal to size then it is returned. If it is not, then the excess bits are added back to the AVL tree. If all sizes in the AVL tree are lesser than the requested size, then global_offset is used to allocate the memory.
Since WASM does not have an explicit null value, the 0th index of the linear memory is used as null. This means that global_offset begins with the default value of 4. The first 4 bytes of the linear memory must always be 0. It is important to note here that global_offset may not always begin at 4 due to string pooling. Refer to 5.2.2 and 6.1 to know more.
When a struct is initiated, its total size is calculated and that information is used to allocate the struct. For example, consider the following struct:
struct Config {
double start;
double end;
int step;
}
Its total size is (8 + 8 + 4) = 20 bits. However, we need to track how big the struct is, so we allocate the first 4 bytes to store the struct’s length. So, we allocate 20 + 4 bits in total. If the struct was initialized like new Config(1.0, 2.0, 5) then the linear memory will look like:
When a particular needs to be read, all we need to do is add the appropriate byte offset to the struct’s pointer. For example, consider the following code:
Values are assigned in a similar way; the cumulative is calculated and then the value is assigned.
The length that was stored right before the struct’s pointer is used to deallocate it. For example, consider the struct defined in the previous section Config, when delete a; is called, the 4 bytes before a are read to find how many bits need to be deallocated, then deallocate_memory is called with the appropriate offset and size. The length of the struct is deallocated along with the struct.
Since null’s value is 0, we can detect when we try reading anything from null. For example, consider the following code:
Struct a {
int b;
}
function void main() {
a instance = null;
print(a.b);
}
Value of a would be 0, which means it is null. Thus when calculating the offset of the fieldname b we can check that the offset of the struct isn’t 0. If it is, we can safely assume that a is null and throw an error using WASM’s unreachable.
Arrays are stored in a similar fashion as structs; the length is stored in the 4 bytes before the pointer of the array. However, there’s one important distinction: the length is not the number of bits the arrays take, but rather the number of elements it has. For example, new int[10] would store the length as 10 and not as 40.
There are four base types, and they are either 4-bytes or 8-bytes. And since pointers are also 4-bytes, we only need arrays containing 4-bytes values or 8-bytes values.
The length of the array, and the size of its value (either i32 or i64) are used to delete the array.
Similar to how we detect that structs are null, we can use the same technique for arrays. Before accessing the ith element, we can check whether the offset of the array pointer is 0 or not. If it is, we can throw an error.
Strings are stored using a struct:
struct String {
array int value;
int length;
String next;
bool pooled;
}
value is the actual data that gets stored -- each index refers to an individual character. This is different from other programming languages to make the implementation more intuitive and less complex.
length is the length of the array in value. Since the strings are immutable, we can store the length in the struct, making the lookup faster and simpler.
next is used to store the String that's been concated to an instance of a String. MyWASM does not support string concatenation using +. Refer to 5.4 to learn more.
pooled is true if the String is an instance of a pooled string. This information is needed when a string needs to be deleted.
String literals are stored using WASM’s data section.
If MyWASM were to assign assign each character for string literals, then that’d mean for a string that’s considerably long, it’d take multiple opcodes to assign each character. Hence, it’s more efficient to use WASM’s data section. Also, optimizing the code would take considerably longer.
Note: for very long strings, it can take binaryen more than 5 seconds to optimize the code!
The string is converted to binary during compilation. It is iterated, and each character is converted to a hex bytestring of length 8. It is highly important to note that WASM is little-endian, and thus the bytestring must be in little-endian as well.
The bytestring in the data_section is copied to WASM’s linear memory. Thus, it means that global_offset must be incremented to reflect this. The offset of a particular string literal is stored by the compiler and reused whenever the string literal is referenced. Since MyWASM supports imports, we also need to consider other files’ global_offset. Refer to 6.1 to know more.
Since strings are a base type, and at the same time pointers, passing them to functions, and assigning them to other variables can get pretty unintuitive really quickly. One option is to pass the pointer to the string, and the other is to copy the string each time it’s referenced.
In my opinion, the latter option is more intuitive than the former. However, the major downside of copying the string is that it is more prone to memory leaks. This is because whenever a string is assigned or passed to a function, they must be deleted using the delete keyword. Consider the following code:
string a = “hello world”;
string b = a;
some_function(b);
delete b;
delete a;
void some_function(string str) {
.
.
delete str;
}
When a is assigned to b, a is actually getting copied to a new string, which is then getting assigned to b. Similarly, when b is passed to some_function, it is getting copied, and then the pointer to the new string is getting passed to it.
Note: if pooled is set to false then the array stored in value is copied as well. And when it is true, only the reference to the value is copied.
Strings cannot be concatenated using the "+" operator. There's a specific function for it called string_append that takes in two strings, and appends the second argument to the first one. The way the second argument is appened is that it copies the second String's struct, and assigns it to first's String's next property.
Other than the problem mentioned in 5.3, string concatenation is probably what makes strings trickier than other base types. At first, I considered not supporting string concatenation at all, since it was really easy to leak memory. For example, consider the following code:
string a = “hello”;
string_append(a, " world")
Here, the pointer to the String "world" is lost, and hence memory is leaked. The best way to do this would have been:
string a = "hello;
string b = " world";
string_append(a, b);
delete b;
This is not ideal. But it's probably the better option here since it can make string concatenation for pooled strings super fast. For example, let's say we have a string of length 1,000 that has been pooled already. Rather than copying the whole string to concatenate another string to it, we just need to copy the struct attached to it, which mean we just need to copy 16 bytes.
When a String is deleted, the array stored in value is deleted only if pooled is set to false. This is because another instance of a string may refer to the same string, deleting the original array would mess things up.
Namespaces are implemented using a similar technique mentioned in 1.4. Prefixes are used to differentiate between different namespaces’ functions and structs.
To import a file and give it a namespace, we just need to write the following code:
import “File.mypl” as Namespace;
Then the functions and structs can be accessed using the scope operator (::):
namespace::some_function(10);
namespace::some_struct a = new namespace::some_struact(null);
Since string pooling changes the global_offset, we need to add the calculated global_offsets of all the imported files and then add them up, and then use that value as the new global_offset.