WebAssembly-Call Performance-Analysis Benchmark Suite

README.md

A Microbenchmark Suite for WebAssembly Function Calls

This collection of files constitute the code that was used to evaluate the performance of WebAssembly and related systems as presented in the Oct. 11 '22 WebAssembly CG Meeting so that interested parties may replicate the results on their own machines. They essentially comprise many slight variations on how to implement the same high-level program, varying the backend target, the low-level implementation strategy and degree of optimization, and the compilation and linking configuration. As such, although technically this is a suite of microbenchmarks, it is the performance of these variations relative to each other that is primarily interesting.

WebAssembly (and JavaScript)

The *.wat files provide the hand-written WebAssembly code for the various configurations.

The whole-*.wat files implement the program as a single module.

• whole-vtable.wat is arguably the "straighforward" implementation of the benchmark. Class methods are implemented by using call_indirect with the index computed by adding the method's offset within the vtable to the object's class's index within the funcref table.
• whole-switch.wat instead implements class methods by making a direct call to a function that br_tables on the object's class identifier, branching to the respective class's implementation of the method.
• whole-unguarded.wat exploits whole-program reasoning to eliminate all br_tables. In the case of isNil, the method can instead be implemented by comparing object's class identifier with the identifier for Nil. In the other cases, the respective method is only ever called on instances of Cons.
• whole-optimal.wat forgoes function calls and branches therein entirely by completely inlining whole-unguarded.wat, providing the "optimal" solution that serves as a baseline that can be used on all WebAssembly engines.

The list-*.wat and sort-*.wat files implement the program as two separate modules (the producer of the list versus the consumer of the list), which are then linked during instantiation.

• list-direct-switch and sort-direct.wat is the obvious splitting of whole-switch.wat.
• list-direct-unguarded.wat is sort-direct.wat are the obvious splitting of whole-unguarded.wat.
• list-vtable.wat and sort-vtable-constant.wat is the obvious splitting of whole-vtable.way.
• list-vtable.wat and sort-vtable-extern.wat furthermore incorporates the fact that often the v-table offsets of code consuming a class are not known until link time, using imported globals rather than fixed i32.const to compute the offsets for call_indirect.

The WebAssembly numbers presented were generated by opening sort.html in the respective browsers, selecting the corresponding benchmark, clicking Run (reloading the page between runs), and selecting the median value (rounded to 10ms). sort.html was itself generated by executing make html, which inserts the base64 string encodings of the respective wat benchmarks, as well as the JavaScript implementation in Sort.js. One can also execute make wasm to generate the respective wasm files, and/or make b64 to generate the B64 files with their respective base64 string encodings. The Test button in sort.html can be used to check their correctness by comparing the output with expected-output.txt.

Native

The *.c and *.h files provide the native analogs to the above WebAssembly files.

The whole-*.c files are analogous to the corresponding whole-*.wat files. They were compiled with gcc -O1.

The list-direct-*.c/sort-direct.c (and list-direct.h) files are analagous to the corresponding list-direct-*.wat/sort-direct.wat files. The list-vtable-*.c/sort-vtable-*.c (and list-vtable-*.h) files are analagous to the corresponding list-vtable.wat/sort-vtable-*.wat files. They were compiled to separate object files with gcc -O1 -fno-lto and then linked with gcc -fno-lto.

One can also compile them using make native. One can run them without arguments to collect times, or one can run them with --test and compare the output with expected-output.txt to check their correctness. Alternatively, one can use wasm run-native and wasm test-native to respectively (compile and) collect times or check correctness of all the native benchmarks.

Java

The Sort.java file implements the program in Java using interfaces rather than (abstract) classes. One can compile this file using javac Sort.java and then run it (or check its correctness) using java Sort (or java Sort --test). Alternatively, one can use wasm java, wasm run-java, and wasm test-java.

Miscellaneous

Use make all to generate sort.html and all *.wasm, *.B64, *.class, and executable files. Use make clean to remove these files (including the pregenerated sort.html included with this bundle), as well as intermediately generated sort.html.bkp and *.o files that might have left if an earlier make was interrupted.

Acknowledgements

Thanks to Derek Schuff (@dschuff) and Petr Penzin (@penzn) for reviewing the code to confirm that the comparisons are fair!

expected-output.txt

unsorted
389181
5522775
11911463
1959233
17
sorted
17
389181
1959233
5522775
11911463

list-direct-switch.c

#include<stdlib.h>
#include<printf.h>
#include"list-direct.h"

typedef struct Nil Nil;
struct Nil {
    Node base;
};

Node* newNil() {
    Nil* nil = malloc(sizeof(Nil));
    nil->base.class = NIL;
    return &nil->base;
}

typedef struct Cons Cons;
struct Cons {
    Node base;
    unsigned int element;
    Node* next;
};

Node* newCons(unsigned int element, Node* next) {
    Cons* cons = malloc(sizeof(Cons));
    cons->base.class = CONS;
    cons->element = element;
    cons->next = next;
    return &cons->base;
}

unsigned int IsNil(Node* this) {
    switch (this->class) {
    case NIL:
        return 1;
    case CONS:
        return 0;
    default:
        exit(-1);
        return 0;
    }
}
const IsNilFunc isNil = IsNil;
unsigned int GetElement(Node* this) {
    switch (this->class) {
    case NIL:
        exit(-1);
        return 0;
    case CONS:
        return ((Cons*)this)->element;
    default:
        exit(-1);
        return 0;
    }
}
const GetElementFunc getElement = GetElement;
void SetElement(Node* this, unsigned int element) {
    switch (this->class) {
    case NIL:
        exit(-1);
        return;
    case CONS:
        ((Cons*)this)->element = element;
        return;
    default:
        exit(-1);
        return;
    }
}
const SetElementFunc setElement = SetElement;
Node* GetNext(Node* this) {
    switch (this->class) {
    case NIL:
        exit(-1);
        return 0;
    case CONS:
        return ((Cons*)this)->next;
    default:
        exit(-1);
        return 0;
    }
}
const GetNextFunc getNext = GetNext;
void print(Node* this) {
    switch (this->class) {
    case NIL:
        return;
    case CONS:
        printf("%d\n", ((Cons*)this)->element);
        Node* next = ((Cons*)this)->next;
        print(next);
        return;
    default:
        exit(-1);
        return;
    }
}
void freeNode(Node* this) {
    Node* next;
    switch (this->class) {
    case NIL:
        free(this);
        return;
    case CONS:
        next = ((Cons*)this)->next;
        freeNode(next);
        free(this);
        return;
    default:
        exit(-1);
        return;
    }
}

list-direct-switch.wat

(module
  (func $log (import "console" "log") (param $element i32))
  
  (memory (export "memory") 2 2)
  (global $unallocated (mut i32) (i32.const 0))
  
  (func (export "reset")
    (global.set $unallocated (i32.const 0))
  )
  
  (func $newNil (export "newNil") (result i32) (local $address i32)
    (local.set $address (global.get $unallocated))
    (i32.store (local.get $address) (i32.const 0))
    (global.set $unallocated (i32.add (local.get $address) (i32.const 4)))
    (return (local.get $address))
  )
  
  (func $newCons (export "newCons") (param $element i32) (param $next i32) (result i32) (local $address i32)
    (local.set $address (global.get $unallocated))
    (i32.store (local.get $address) (i32.const 1))
    (i32.store offset=4 (local.get $address) (local.get $element))
    (i32.store offset=8 (local.get $address) (local.get $next))
    (global.set $unallocated (i32.add (local.get $address) (i32.const 12)))
    (return (local.get $address))
  )
  
  (func $isNil (export "isNil") (param $this i32) (result i32)
    (block $Nil
      (block $Cons
        (block $Unreachable
          (br_table $Nil $Cons $Unreachable (i32.load (local.get $this)))
        )
        unreachable
      )
      (return (i32.const 0))
    )
    (return (i32.const 1))
  )
  
  (func $getElement (export "getElement") (param $this i32) (result i32)
    (block $Nil
      (block $Cons
        (block $Unreachable
          (br_table $Nil $Cons $Unreachable (i32.load (local.get $this)))
        )
        unreachable
      )
      (return (i32.load offset=4 (local.get $this)))
    )
    unreachable
  )
  
  (func $getNext (export "getNext") (param $this i32) (result i32)
    (block $Nil
      (block $Cons
        (block $Unreachable
          (br_table $Nil $Cons $Unreachable (i32.load (local.get $this)))
        )
        unreachable
      )
      (return (i32.load offset=8 (local.get $this)))
    )
    unreachable
  )
  
  (func $setElement (export "setElement") (param $this i32) (param $element i32)
    (block $Nil
      (block $Cons
        (block $Unreachable
          (br_table $Nil $Cons $Unreachable (i32.load (local.get $this)))
        )
        unreachable
      )
      (i32.store offset=4 (local.get $this) (local.get $element))
      return
    )
    unreachable
  )
  
  (func $print (export "print") (param $this i32)
    (block $Nil
      (block $Cons
        (block $Unreachable
          (br_table $Nil $Cons $Unreachable (i32.load (local.get $this)))
        )
        unreachable
      )
      (call $log (i32.load offset=4 (local.get $this)))
      (call $print (i32.load offset=8 (local.get $this)))
      return
    )
    return
  )
)

list-direct-unguarded.c

#include<stdlib.h>
#include<printf.h>
#include<time.h>
#include"list-direct.h"

typedef struct Nil Nil;
struct Nil {
    Node base;
};

Node* newNil() {
    Nil* nil = malloc(sizeof(Nil));
    nil->base.class = NIL;
    return &nil->base;
}

typedef struct Cons Cons;
struct Cons {
    Node base;
    unsigned int element;
    Node* next;
};

Node* newCons(unsigned int element, Node* next) {
    Cons* cons = malloc(sizeof(Cons));
    cons->base.class = CONS;
    cons->element = element;
    cons->next = next;
    return &cons->base;
}

unsigned int IsNil(Node* this) {
    return this->class == NIL;
}
const IsNilFunc isNil = IsNil;
unsigned int GetElement(Node* this) {
    return ((Cons*)this)->element;
}
const GetElementFunc getElement = GetElement;
void SetElement(Node* this, unsigned int element) {
    ((Cons*)this)->element = element;
}
const SetElementFunc setElement = SetElement;
Node* GetNext(Node* this) {
    return ((Cons*)this)->next;
}
const GetNextFunc getNext = GetNext;
void print(Node* this) {
    switch (this->class) {
    case NIL:
        return;
    case CONS:
        printf("%d\n", ((Cons*)this)->element);
        Node* next = ((Cons*)this)->next;
        print(next);
        return;
    default:
        exit(-1);
        return;
    }
}
void freeNode(Node* this) {
    Node* next;
    switch (this->class) {
    case NIL:
        free(this);
        return;
    case CONS:
        next = ((Cons*)this)->next;
        freeNode(next);
        free(this);
        return;
    default:
        exit(-1);
        return;
    }
}

list-direct-unguarded.wat

(module
  (func $log (import "console" "log") (param $element i32))
  
  (memory (export "memory") 2 2)
  (global $unallocated (mut i32) (i32.const 0))
  
  (func (export "reset")
    (global.set $unallocated (i32.const 0))
  )
  
  (func $newNil (export "newNil") (result i32) (local $address i32)
    (local.set $address (global.get $unallocated))
    (i32.store (local.get $address) (i32.const 0))
    (global.set $unallocated (i32.add (local.get $address) (i32.const 4)))
    (return (local.get $address))
  )
  
  (func $newCons (export "newCons") (param $element i32) (param $next i32) (result i32) (local $address i32)
    (local.set $address (global.get $unallocated))
    (i32.store (local.get $address) (i32.const 1))
    (i32.store offset=4 (local.get $address) (local.get $element))
    (i32.store offset=8 (local.get $address) (local.get $next))
    (global.set $unallocated (i32.add (local.get $address) (i32.const 12)))
    (return (local.get $address))
  )
  
  (func $isNil (export "isNil") (param $this i32) (result i32)
    (return (i32.eq (i32.const 0) (i32.load (local.get $this))))
  )
  
  (func $getElement (export "getElement") (param $this i32) (result i32)
    (return (i32.load offset=4 (local.get $this)))
  )
  
  (func $getNext (export "getNext") (param $this i32) (result i32)
    (return (i32.load offset=8 (local.get $this)))
  )
  
  (func $setElement (export "setElement") (param $this i32) (param $element i32)
    (i32.store offset=4 (local.get $this) (local.get $element))
  )
  
  (func $print (export "print") (param $this i32)
    (block $Nil
      (block $Cons
        (block $Unreachable
          (br_table $Nil $Cons $Unreachable (i32.load (local.get $this)))
        )
        unreachable
      )
      (call $log (i32.load offset=4 (local.get $this)))
      (call $print (i32.load offset=8 (local.get $this)))
      return
    )
    return
  )
)

list-direct.h

typedef struct Node Node;
typedef struct NodeVTable NodeVTable;

#define NIL 0
#define CONS 1

typedef struct Node Node;
struct Node {
    unsigned int class;
};

Node* newNil();
Node* newCons(unsigned int element, Node* next);

typedef unsigned int (*IsNilFunc)(Node*);
typedef unsigned int (*GetElementFunc)(Node*);
typedef void (*SetElementFunc)(Node*, unsigned int);
typedef Node* (*GetNextFunc)(Node*);
typedef void (*PrintFunc)(Node*);
typedef void (*FreeFunc)(Node*);

extern const IsNilFunc isNil;
extern const GetElementFunc getElement;
extern const SetElementFunc setElement;
extern const GetNextFunc getNext;
void print(Node* this);
void freeNode(Node* this);

list-vtable-constant.c

#include<stdlib.h>
#include<printf.h>
#include"list-vtable-constant.h"

typedef struct Nil Nil;
struct Nil {
    Node base;
};

unsigned int isNilNil(Node* this) {
    return 1;
}
unsigned int getElementNil(Node* this) {
    exit(-1);
    return 0;
}
void setElementNil(Node* this, unsigned int element) {
    exit(-1);
}
Node* getNextNil(Node* this) {
    exit(-1);
    return NULL;
}
void printNil(Node* this) {
}
void freeNil(Node* this) {
    free(this);
}

struct NodeVTable nilvtable = {
    .isNil = isNilNil,
    .getElement = getElementNil,
    .setElement = setElementNil,
    .getNext = getNextNil,
    .print = printNil,
    .free = freeNil
};

Node* newNil() {
    Nil* nil = malloc(sizeof(Nil));
    nil->base.vtable = &nilvtable;
    return &nil->base;
}

typedef struct Cons Cons;
struct Cons {
    Node base;
    unsigned int element;
    Node* next;
};

unsigned int isNilCons(Node* this) {
    return 0;
}
unsigned int getElementCons(Node* this) {
    return ((Cons*)this)->element;
}
void setElementCons(Node* this, unsigned int element) {
    ((Cons*)this)->element = element;
}
Node* getNextCons(Node* this) {
    return ((Cons*)this)->next;
}
void printCons(Node* this) {
    printf("%d\n", ((Cons*)this)->element);
    Node* next = ((Cons*)this)->next;
    next->vtable->print(next);
}
void freeCons(Node* this) {
    Node* next = ((Cons*)this)->next;
    next->vtable->free(next);
    free(this);
}

struct NodeVTable consvtable = {
    .isNil = isNilCons,
    .getElement = getElementCons,
    .setElement = setElementCons,
    .getNext = getNextCons,
    .print = printCons,
    .free = freeCons
};

Node* newCons(unsigned int element, Node* next) {
    Cons* cons = malloc(sizeof(Cons));
    cons->base.vtable = &consvtable;
    cons->element = element;
    cons->next = next;
    return &cons->base;
}

list-vtable-constant.h

#include<stdlib.h>
#include<printf.h>
#include<time.h>

typedef struct Node Node;
typedef struct NodeVTable NodeVTable;

struct Node {
    NodeVTable* vtable;
};

typedef unsigned int (*IsNilFunc)(Node*);
typedef unsigned int (*GetElementFunc)(Node*);
typedef void (*SetElementFunc)(Node*, unsigned int);
typedef Node* (*GetNextFunc)(Node*);
typedef void (*PrintFunc)(Node*);
typedef void (*FreeFunc)(Node*);

struct NodeVTable {
    IsNilFunc isNil;
    GetElementFunc getElement;
    SetElementFunc setElement;
    GetNextFunc getNext;
    PrintFunc print;
    FreeFunc free;
};

Node* newNil();
Node* newCons(unsigned int element, Node* next);

list-vtable-extern.c

#include<stdlib.h>
#include<printf.h>
#include"list-vtable-extern.h"

typedef struct NodeVTable NodeVTable;

typedef unsigned int (*IsNilFunc)(Node*);
typedef unsigned int (*GetElementFunc)(Node*);
typedef void (*SetElementFunc)(Node*, unsigned int);
typedef Node* (*GetNextFunc)(Node*);
typedef void (*PrintFunc)(Node*);
typedef void (*FreeFunc)(Node*);

struct NodeVTable {
    IsNilFunc isNil;
    GetElementFunc getElement;
    SetElementFunc setElement;
    GetNextFunc getNext;
    PrintFunc print;
    FreeFunc free;
};

const size_t isNilOffset = offsetof(NodeVTable, isNil);
const size_t getElementOffset = offsetof(NodeVTable, getElement);
const size_t setElementOffset = offsetof(NodeVTable, setElement);
const size_t getNextOffset = offsetof(NodeVTable, getNext);
const size_t printOffset = offsetof(NodeVTable, print);
const size_t freeOffset = offsetof(NodeVTable, free);

typedef struct Nil Nil;
struct Nil {
    Node base;
};

unsigned int isNilNil(Node* this) {
    return 1;
}
unsigned int getElementNil(Node* this) {
    exit(-1);
    return 0;
}
void setElementNil(Node* this, unsigned int element) {
    exit(-1);
}
Node* getNextNil(Node* this) {
    exit(-1);
    return NULL;
}
void printNil(Node* this) {
}
void freeNil(Node* this) {
    free(this);
}

struct NodeVTable nilvtable = {
    .isNil = isNilNil,
    .getElement = getElementNil,
    .setElement = setElementNil,
    .getNext = getNextNil,
    .print = printNil,
    .free = freeNil
};

Node* newNil() {
    Nil* nil = malloc(sizeof(Nil));
    nil->base.vtable = (char*)&nilvtable;
    return &nil->base;
}

typedef struct Cons Cons;
struct Cons {
    Node base;
    unsigned int element;
    Node* next;
};

unsigned int isNilCons(Node* this) {
    return 0;
}
unsigned int getElementCons(Node* this) {
    return ((Cons*)this)->element;
}
void setElementCons(Node* this, unsigned int element) {
    ((Cons*)this)->element = element;
}
Node* getNextCons(Node* this) {
    return ((Cons*)this)->next;
}
void printCons(Node* this) {
    printf("%d\n", ((Cons*)this)->element);
    Node* next = ((Cons*)this)->next;
    (*PrintAddress(next->vtable))(next);
}
void freeCons(Node* this) {
    Node* next = ((Cons*)this)->next;
    (*FreeAddress(next->vtable))(next);
    free(this);
}

struct NodeVTable consvtable = {
    .isNil = isNilCons,
    .getElement = getElementCons,
    .setElement = setElementCons,
    .getNext = getNextCons,
    .print = printCons,
    .free = freeCons
};

Node* newCons(unsigned int element, Node* next) {
    Cons* cons = malloc(sizeof(Cons));
    cons->base.vtable = (char*)&consvtable;
    cons->element = element;
    cons->next = next;
    return &cons->base;
}

list-vtable-extern.h

#include<stddef.h>

typedef struct Node Node;

struct Node {
    char* vtable;
};

typedef unsigned int (*IsNilFunc)(Node*);
typedef unsigned int (*GetElementFunc)(Node*);
typedef void (*SetElementFunc)(Node*, unsigned int);
typedef Node* (*GetNextFunc)(Node*);
typedef void (*PrintFunc)(Node*);
typedef void (*FreeFunc)(Node*);

Node* newNil();

Node* newCons(unsigned int element, Node* next);

extern const size_t isNilOffset;
extern const size_t getElementOffset;
extern const size_t setElementOffset;
extern const size_t getNextOffset;
extern const size_t printOffset;
extern const size_t freeOffset;

#define IsNilAddress(vtable) (IsNilFunc*)(((char*)vtable)+isNilOffset)
#define GetElementAddress(vtable) (GetElementFunc*)(((char*)vtable)+getElementOffset)
#define SetElementAddress(vtable) (SetElementFunc*)(((char*)vtable)+setElementOffset)
#define GetNextAddress(vtable) (GetNextFunc*)(((char*)vtable)+getNextOffset)
#define PrintAddress(vtable) (PrintFunc*)(((char*)vtable)+printOffset)
#define FreeAddress(vtable) (FreeFunc*)(((char*)vtable)+freeOffset)

list-vtable.wat

(module
  (func $log (import "console" "log") (param $element i32))
  (global $isNilOffset (export"isNilOffset") i32 (i32.const 0))
  (global $getElementOffset (export "getElementOffset") i32 (i32.const 1))
  (global $setElementOffset (export "setElementOffset") i32 (i32.const 2))
  (global $getNextOffset (export "getNextOffset") i32 (i32.const 3))
  (global $printOffset (export "printOffset") i32 (i32.const 4))
  
  (memory (export "memory") 2 2)
  (global $unallocated (mut i32) (i32.const 0))
  (table $vtable (export "vtable") funcref (elem $isNil_Nil $getElement_Nil $setElement_Nil $getNext_Nil $print_Nil $isNil_Cons $getElement_Cons $setElement_Cons $getNext_Cons $print_Cons))

  (func (export "reset")
    (global.set $unallocated (i32.const 0))
  )
  
  (func $newNil (export "newNil") (result i32) (local $address i32)
    (local.set $address (global.get $unallocated))
    (i32.store (local.get $address) (i32.const 0))
    (global.set $unallocated (i32.add (local.get $address) (i32.const 4)))
    (return (local.get $address))
  )
  
  (func $newCons (export "newCons") (param $element i32) (param $next i32) (result i32) (local $address i32)
    (local.set $address (global.get $unallocated))
    (i32.store (local.get $address) (i32.const 5))
    (i32.store offset=4 (local.get $address) (local.get $element))
    (i32.store offset=8 (local.get $address) (local.get $next))
    (global.set $unallocated (i32.add (local.get $address) (i32.const 12)))
    (return (local.get $address))
  )
  
  (func $isNil_Nil (param $this i32) (result i32)
    (return (i32.const 1))
  )
  (func $isNil_Cons (param $this i32) (result i32)
    (return (i32.const 0))
  )
  
  (func $getElement_Nil (param $this i32) (result i32)
    unreachable
  )
  (func $getElement_Cons (param $this i32) (result i32)
    (return (i32.load offset=4 (local.get $this)))
  )
  
  (func $getNext_Nil (param $this i32) (result i32)
    unreachable
  )
  (func $getNext_Cons (param $this i32) (result i32)
    (return (i32.load offset=8 (local.get $this)))
    unreachable
  )
  
  (func $setElement_Nil (param $this i32) (param $element i32)
    unreachable
  )
  (func $setElement_Cons (param $this i32) (param $element i32)
    (i32.store offset=4 (local.get $this) (local.get $element))
    return
  )
  
  (func $print_Nil (param $this i32)
    return
  )
  (func $print_Cons (param $this i32)
    (call $log (i32.load offset=4 (local.get $this)))
    (call $print (i32.load offset=8 (local.get $this)))
    return
  )
  (func $print (export "print") (param $this i32)
    (call_indirect $vtable (param i32) (local.get $this) (i32.add (global.get $printOffset) (i32.load (local.get $this))))
  )
)

Makefile

CC=gcc
OPT=-O1
NATIVE=whole-optimal whole-unguarded whole-switch whole-vtable separate-direct-unguarded separate-direct-switch separate-vtable-constant separate-vtable-extern
WAT2WASM=wat2wasm --output=-
BASE64=openssl base64 -A
WASM=whole-optimal whole-unguarded whole-switch whole-vtable list-direct-unguarded list-direct-switch sort-direct list-vtable sort-vtable-constant sort-vtable-extern
JAVAC=javac
JAVA=java

.PHONY: run-native test-native native wasm b64 html run-java test-java java all clean

run-native: native
	@for exe in $(NATIVE); do \
		echo $$exe; \
		./$$exe; \
	done

test-native: expected-output.txt native
	@for exe in $(NATIVE); do \
		echo $$exe '--test | diff expected-output.txt -'; \
		./$$exe --test | diff expected-output.txt -; \
	done

native: $(NATIVE)

whole-%: whole-%.c
	$(CC) $(OPT) -o $@ $@.c

separate-direct-%: list-direct-%.o sort-direct.o
	$(CC) -fno-lto -o $@ list-direct-$*.o sort-direct.o

list-direct-%.o: list-direct-%.c list-direct.h
	$(CC) $(OPT) -fno-lto -c list-direct-$*.c

.INTERMEDIATE: sort-direct.o

sort-direct.o: sort-direct.c list-direct.h
	$(CC) $(OPT) -fno-lto -c sort-direct.c

separate-vtable-%: list-vtable-%.o sort-vtable-%.o
	$(CC) -fno-lto -o $@ list-vtable-$*.o sort-vtable-$*.o

list-vtable-%.o: list-vtable-%.c list-vtable-%.h
	$(CC) $(OPT) -fno-lto -c list-vtable-$*.c

sort-vtable-%.o: sort-vtable-%.c list-vtable-%.h
	$(CC) $(OPT) -fno-lto -c sort-vtable-$*.c

wasm: $(WASM:=.wasm)

%.wasm: %.wat
	$(WAT2WASM) $*.wat > $@

b64: $(WASM:=.B64)

%.B64: %.wat
	$(WAT2WASM) $*.wat | $(BASE64) > $*.B64

define NEWLINE


endef

html: sort.html

sort.html: sort-template.html Sort.js $(WASM:=.wat)
	sed -e '/instantiateJavascript();/{r Sort.js' -e 'd' -e '}' sort-template.html > sort.html
	$(foreach WASM,$(WASM),sed -i .bkp -e "s|$(subst -,\-,$(WASM))\-base64|$$($(WAT2WASM) $(WASM).wat | $(BASE64))|g" sort.html${NEWLINE})
	rm -f sort.html.bkp

run-java: java
	$(JAVA) Sort

test-java: expected-output.txt java
	$(JAVA) Sort --test | diff expected-output.txt -

java: Sort.class

Sort.class: Sort.java
	$(JAVAC) Sort.java

all: native wasm b64 html java

clean:
	rm -f $(NATIVE) *.o sort.html sort.html.bkp *.class *.B64 *.wasm

sort-direct.c

#include<stdlib.h>
#include<printf.h>
#include<time.h>
#include"list-direct.h"

void sort(Node* head) {
    while (!isNil(head)) {
        unsigned int element = getElement(head);
        Node* old = head;
        Node* node = getNext(old);
        while (!isNil(node)) {
            unsigned int value = getElement(node);
            if (value < element) {
                setElement(node, element);
                setElement(old, value);
                old = node;
            }
            node = getNext(node);
        }
        if (old == head) {
            head = getNext(head);
        }
    }
}

void perform(unsigned int show, unsigned int time, unsigned int size) {
    Node* list = newNil();
    unsigned long element =  17;
    for (unsigned int i = 0; i < size; i++) {
        list = newCons((unsigned int)element, list);
        element = (element * 115249) % 16777213;
    }
    if (show) {
        printf("unsorted\n");
        print(list);
    }
    clock_t start = clock();
    sort(list);
    clock_t end = clock();
    double seconds = ((double)(end - start))/CLOCKS_PER_SEC;
    if (time)
        printf("%f\n", seconds * 1000);
    if (show) {
        printf("sorted\n");
        print(list);
    }
    freeNode(list);
}

int main(int argc, char* argv[]) {
    unsigned int test = argc > 1;
    unsigned int show = test;
    unsigned int time = !test;
    unsigned int size = test ? 5 : 10000;
    for (unsigned int count = test ? 1 : 5; count != 0; count--)
        perform(show, time, size);
    return 0;
}

sort-direct.wat

(module
  (memory (import "list" "memory") 1)
  
  (func $isNil (import "list" "isNil") (param $this i32) (result i32))
  (func $getElement (import "list" "getElement") (param $this i32) (result i32))
  (func $getNext (import "list" "getNext") (param $this i32) (result i32))
  (func $setElement (import "list" "setElement") (param $this i32) (param $element i32))
  
  (func $sort (export "sort") (param $head i32) (local $element i32) (local $old i32) (local $node i32) (local $value i32)
    (loop $while_head
      (if (call $isNil (local.get $head))
        (return)
      )
      (local.set $element (call $getElement (local.get $head)))
      (local.set $old (local.get $head))
      (local.set $node (call $getNext (local.get $old)))
      (loop $while_node
        (if (call $isNil (local.get $node))
          (then
            (if (i32.eq (local.get $old) (local.get $head))
              (local.set $head (call $getNext (local.get $head)))
            )
            (br $while_head)
          )
        )
        (local.set $value (call $getElement (local.get $node)))
        (if (i32.lt_u (local.get $value) (local.get $element))
          (then
            (call $setElement (local.get $node) (local.get $element))
            (call $setElement (local.get $old) (local.get $value))
            (local.set $old (local.get $node))
          )
        )
        (local.set $node (call $getNext (local.get $node)))
        (br $while_node)
      )
    )
  )
)

sort-template.html

<!DOCTYPE html>
<html>
    <script>
        const base64 = {
            whole: {
                optimal: "whole-optimal-base64",
                unguarded: "whole-unguarded-base64",
                switch: "whole-switch-base64",
                vtable: "whole-vtable-base64"
            },
            separate: {
                direct: {
                    list: {
                        unguarded: "list-direct-unguarded-base64",
                        switch: "list-direct-switch-base64"
                    },
                    sort: "sort-direct-base64"
                },
                vtable: {
                    list: "list-vtable-base64",
                    sort: {
                        constant: "sort-vtable-constant-base64",
                        extern: "sort-vtable-extern-base64"
                    }
                }
            },
        }

        function base64ToArrayBuffer(base64) {
            var binary_string = window.atob(base64);
            var len = binary_string.length;
            var bytes = new Uint8Array(len);
            for (var i = 0; i < len; i++) {
                bytes[i] = binary_string.charCodeAt(i);
            }
            return bytes.buffer;
        }
        function log(text) {
            document.getElementById("console").innerHTML += text + "</br>";
        }
        function clearConsole() {
            document.getElementById("console").innerHTML = "";
        }

        const instances = {}

        function instantiateWhole(wasm_base64) {
            return WebAssembly.instantiate(base64ToArrayBuffer(wasm_base64),
                                           {console: {log: log}}
                                          ).then((wasm) => {
                const { newNil: newNil, newCons: newCons, print: print, reset: reset, sort: sort } = wasm.instance.exports;
                return { newNil: newNil, newCons: newCons, print: print, reset: reset, sort: sort };
            });
        }

        function instantiateSeparateDirect(list_base64, sort_base64) {
            return WebAssembly.instantiate(base64ToArrayBuffer(list_base64),
                                        {console: {log: log}}
                                        ).then((list_wasm) => {
                const { newNil: newNil, newCons: newCons, print: print, reset: reset, memory: memory,
                        isNil: isNil, getElement: getElement, setElement: setElement, getNext: getNext
                    } = list_wasm.instance.exports;
                return WebAssembly.instantiate(base64ToArrayBuffer(sort_base64),
                                            {list: {memory: memory, isNil: isNil, getElement: getElement, setElement: setElement, getNext: getNext}}
                                            ).then((sort_wasm) => {
                    const { sort: sort } = sort_wasm.instance.exports;
                    return { newNil: newNil, newCons: newCons, print: print, reset: reset, sort: sort };
                });
            });
        }

        function instantiateSeparateVtable(list_base64, sort_base64) {
            return WebAssembly.instantiate(base64ToArrayBuffer(list_base64),
                                           {console: {log: log}}
                                          ).then((list_wasm) => {
                const { newNil: newNil, newCons: newCons, print: print, reset: reset, memory: memory, vtable: vtable,
                        isNilOffset: isNilOffset, getElementOffset: getElementOffset, setElementOffset: setElementOffset, getNextOffset: getNextOffset
                      } = list_wasm.instance.exports;
                return WebAssembly.instantiate(base64ToArrayBuffer(sort_base64),
                                               {list: {memory: memory, vtable: vtable, isNil: isNilOffset, getElement: getElementOffset, setElement: setElementOffset, getNext: getNextOffset}}
                                              ).then((sort_wasm) => {
                    const { sort: sort } = sort_wasm.instance.exports;
                    return { newNil: newNil, newCons: newCons, print: print, reset: reset, sort: sort };
                });
            });
        }

        function instantiateJavascript() {
            instantiateJavascript();
        }

        const instantiators = {
            wholeOptimal: () => instantiateWhole(base64.whole.optimal),
            wholeUnguarded: () => instantiateWhole(base64.whole.unguarded),
            wholeSwitch: () => instantiateWhole(base64.whole.switch),
            wholeVtable: () => instantiateWhole(base64.whole.vtable),
            separateDirectUnguarded: () => instantiateSeparateDirect(base64.separate.direct.list.unguarded, base64.separate.direct.sort),
            separateDirectSwitch: () => instantiateSeparateDirect(base64.separate.direct.list.switch, base64.separate.direct.sort),
            separateVtableConstant: () => instantiateSeparateVtable(base64.separate.vtable.list, base64.separate.vtable.sort.constant),
            separateVtableExtern: () => instantiateSeparateVtable(base64.separate.vtable.list, base64.separate.vtable.sort.extern),
            javascript: instantiateJavascript,
        };

        function runEvaluation() {
            const selector = document.getElementById("selection");
            const name = selector.options[selector.selectedIndex].innerHTML;
            const selection = selector.value;
            if (selection in instances) {
                log(name + " already instantiated");
            } else {
                log("instantiating " + name);
                instances[selection] = instantiators[selection]();
            }

            instances[selection].then((sorter) => {
                log("starting " + name);

                const { newNil: newNil, newCons: newCons, print: print, reset: reset, sort: sort } = sorter;

                times = 5;

                function runOnce() {
                    size = 10000;

                    reset();
                    list = newNil();
                    element = 17;
                    for (i = 0; i < size; i++) {
                        list = newCons(element, list);
                        element = (element * 115249) % 16777213;
                    }
                    start = performance.now();
                    sort(list);
                    log(performance.now() - start);

                    if (--times > 0)
                        window.setTimeout(runOnce, 0);
                    else {
                        log(name + " done");
                        log("");
                    }
                }

                window.setTimeout(runOnce, 0);
            });
        }

        function checkCorrectness() {
            const selector = document.getElementById("selection");
            const name = selector.options[selector.selectedIndex].innerHTML;
            const selection = selector.value;
            if (selection in instances) {
                log(name + " already instantiated");
            } else {
                log("instantiating " + name);
                instances[selection] = instantiators[selection]();
            }

            instances[selection].then((sorter) => {
                log("starting " + name);

                const { newNil: newNil, newCons: newCons, print: print, reset: reset, sort: sort } = sorter;

                size = 5;

                reset();
                list = newNil();
                element = 17;
                for (i = 0; i < size; i++) {
                    list = newCons(element, list);
                    element = (element * 115249) % 16777213;
                }
                log("unsorted");
                print(list);
                log("sorted");
                sort(list);
                print(list);
                log(name + " done");
                log("");
            });
        }
    </script>
    <body>

        <h1>WebAssembly Performance</h1>
        <select id="selection">
            <option value="wholeOptimal">whole-optimal: Fully Inlined without Tests</option>
            <option value="wholeUnguarded">whole-unguarded: Direct Calls without Tests</option>
            <option value="wholeSwitch">whole-switch: Direct Calls using Switch Tables</option>
            <option value="wholeVtable">whole-vtable: Indirect Calls</option>
            <option value="separateDirectUnguarded">separate-direct-unguarded: Separately Compiled using Direct Calls without Tests</option>
            <option value="separateDirectSwitch">separate-direct-switch: Separately Compiled using Direct Calls using Switch Tables</option>
            <option value="separateVtableConstant">separate-vtable-constant: Separately Compiled using Indirect Calls at Predetermined Method Offsets</option>
            <option value="separateVtableExtern">separate-vtable-extern: Separately Compiled using Indirect Calls at Imported Method Offsets</option>
            <option value="javascript">JavaScript Classes using only Methods</option>
        </select>
        <input type="button" value="Run" onclick="runEvaluation()"/>
        <input type="button" value="Test" onclick="checkCorrectness()"/>
        <input type="button" value="Clear" onclick="clearConsole()"/>
        <p id="console"></p>

    </body>
</html>

sort-vtable-constant.c

#include<stdlib.h>
#include<printf.h>
#include<time.h>
#include"list-vtable-constant.h"

void sort(Node* head) {
    while (!head->vtable->isNil(head)) {
        unsigned int element = head->vtable->getElement(head);
        Node* old = head;
        Node* node = old->vtable->getNext(old);
        while (!node->vtable->isNil(node)) {
            unsigned int value = node->vtable->getElement(node);
            if (value < element) {
                node->vtable->setElement(node, element);
                old->vtable->setElement(old, value);
                old = node;
            }
            node = node->vtable->getNext(node);
        }
        if (old == head) {
            head = head->vtable->getNext(head);
        }
    }
}

void perform(unsigned int show, unsigned int time, unsigned int size) {
    Node* list = newNil();
    unsigned long element =  17;
    for (unsigned int i = 0; i < size; i++) {
        list = newCons((unsigned int)element, list);
        element = (element * 115249) % 16777213;
    }
    if (show) {
        printf("unsorted\n");
        list->vtable->print(list);
    }
    clock_t start = clock();
    sort(list);
    clock_t end = clock();
    double seconds = ((double)(end - start))/CLOCKS_PER_SEC;
    if (time)
        printf("%f\n", seconds * 1000);
    if (show) {
        printf("sorted\n");
        list->vtable->print(list);
    }
    list->vtable->free(list);
}

int main(int argc, char* argv[]) {
    unsigned int test = argc > 1;
    unsigned int show = test;
    unsigned int time = !test;
    unsigned int size = test ? 5 : 10000;
    for (unsigned int count = test ? 1 : 5; count != 0; count--)
        perform(show, time, size);
    return 0;
}

sort-vtable-constant.wat

(module
  (memory (import "list" "memory") 1)
  (table $vtable (import "list" "vtable") 0 funcref)
  
  (func $sort (export "sort") (param $head i32) (local $element i32) (local $old i32) (local $node i32) (local $value i32)
    (loop $while_head
      (if (call_indirect $vtable (param i32) (result i32) (local.get $head) (i32.load (local.get $head)))
        (return)
      )
      (local.set $element (call_indirect $vtable (param i32) (result i32) (local.get $head) (i32.add (i32.const 1) (i32.load (local.get $head)))))
      (local.set $old (local.get $head))
      (local.set $node (call_indirect $vtable (param i32) (result i32) (local.get $old) (i32.add (i32.const 3) (i32.load (local.get $old)))))
      (loop $while_node
        (if (call_indirect $vtable (param i32) (result i32) (local.get $node) (i32.load (local.get $node)))
          (then
            (if (i32.eq (local.get $old) (local.get $head))
              (local.set $head (call_indirect $vtable (param i32) (result i32) (local.get $head) (i32.add (i32.const 3) (i32.load (local.get $head)))))
            )
            (br $while_head)
          )
        )
        (local.set $value (call_indirect $vtable (param i32) (result i32) (local.get $node) (i32.add (i32.const 1) (i32.load (local.get $node)))))
        (if (i32.lt_u (local.get $value) (local.get $element))
          (then
            (call_indirect $vtable (param i32 i32) (local.get $node) (local.get $element) (i32.add (i32.const 2) (i32.load (local.get $node))))
            (call_indirect $vtable (param i32 i32) (local.get $old) (local.get $value) (i32.add (i32.const 2) (i32.load (local.get $old))))
            (local.set $old (local.get $node))
          )
        )
        (local.set $node (call_indirect $vtable (param i32) (result i32) (local.get $node) (i32.add (i32.const 3) (i32.load (local.get $node)))))
        (br $while_node)
      )
    )
  )
)

sort-vtable-extern.c

#include<stdlib.h>
#include<printf.h>
#include<time.h>
#include"list-vtable-extern.h"

void sort(Node* head) {
  while (!(*IsNilAddress(head->vtable))(head)) {
    unsigned int element = (*GetElementAddress(head->vtable))(head);
    Node* old = head;
    Node* node = (*GetNextAddress(old->vtable))(old);
    while (!(*IsNilAddress(node->vtable))(node)) {
      unsigned int value = (*GetElementAddress(node->vtable))(node);
      if (value < element) {
        (*SetElementAddress(node->vtable))(node, element);
        (*SetElementAddress(old->vtable))(old, value);
        old = node;
      }
      node = (*GetNextAddress(node->vtable))(node);
    }
    if (old == head) {
      head = (*GetNextAddress(head->vtable))(head);
    }
  }
}

void perform(unsigned int show, unsigned int time, unsigned int size) {
    Node* list = newNil();
    unsigned long element =  17;
    for (unsigned int i = 0; i < size; i++) {
        list = newCons((unsigned int)element, list);
        element = (element * 115249) % 16777213;
    }
    if (show) {
        printf("unsorted\n");
        (*PrintAddress(list->vtable))(list);
    }
    clock_t start = clock();
    sort(list);
    clock_t end = clock();
    double seconds = ((double)(end - start))/CLOCKS_PER_SEC;
    if (time)
        printf("%f\n", seconds * 1000);
    if (show) {
        printf("sorted\n");
        (*PrintAddress(list->vtable))(list);
    }
    (*FreeAddress(list->vtable))(list);
}

int main(int argc, char* argv[]) {
    unsigned int test = argc > 1;
    unsigned int show = test;
    unsigned int time = !test;
    unsigned int size = test ? 5 : 10000;
    for (unsigned int count = test ? 1 : 5; count != 0; count--)
        perform(show, time, size);
    return 0;
}

sort-vtable-extern.wat

(module
  (global $isNilOffset (import "list" "isNil") i32)
  (global $getElementOffset (import "list" "getElement") i32)
  (global $setElementOffset (import "list" "setElement") i32)
  (global $getNextOffset (import "list" "getNext") i32)
  
  (memory (import "list" "memory") 1)
  (table $vtable (import "list" "vtable") 0 funcref)
  
  (func $sort (export "sort") (param $head i32) (local $element i32) (local $old i32) (local $node i32) (local $value i32)
    (loop $while_head
      (if (call_indirect $vtable (param i32) (result i32) (local.get $head) (i32.add (global.get $isNilOffset) (i32.load (local.get $head))))
        (return)
      )
      (local.set $element (call_indirect $vtable (param i32) (result i32) (local.get $head) (i32.add (global.get $getElementOffset) (i32.load (local.get $head)))))
      (local.set $old (local.get $head))
      (local.set $node (call_indirect $vtable (param i32) (result i32) (local.get $old) (i32.add (global.get $getNextOffset) (i32.load (local.get $old)))))
      (loop $while_node
        (if (call_indirect $vtable (param i32) (result i32) (local.get $node) (i32.add (global.get $isNilOffset) (i32.load (local.get $node))))
          (then
            (if (i32.eq (local.get $old) (local.get $head))
              (local.set $head (call_indirect $vtable (param i32) (result i32) (local.get $head) (i32.add (global.get $getNextOffset) (i32.load (local.get $head)))))
            )
            (br $while_head)
          )
        )
        (local.set $value (call_indirect $vtable (param i32) (result i32) (local.get $node) (i32.add (global.get $getElementOffset) (i32.load (local.get $node)))))
        (if (i32.lt_u (local.get $value) (local.get $element))
          (then
            (call_indirect $vtable (param i32 i32) (local.get $node) (local.get $element) (i32.add (global.get $setElementOffset) (i32.load (local.get $node))))
            (call_indirect $vtable (param i32 i32) (local.get $old) (local.get $value) (i32.add (global.get $setElementOffset) (i32.load (local.get $old))))
            (local.set $old (local.get $node))
          )
        )
        (local.set $node (call_indirect $vtable (param i32) (result i32) (local.get $node) (i32.add (global.get $getNextOffset) (i32.load (local.get $node)))))
        (br $while_node)
      )
    )
  )
)

sort.html

<!DOCTYPE html>
<html>
    <script>
        const base64 = {
            whole: {
                optimal: "AGFzbQEAAAABEgRgAX8AYAAAYAABf2ACf38BfwIPAQdjb25zb2xlA2xvZwAAAwYFAQIDAAAFBAEBAgIGBgF/AUEACwcrBQVyZXNldAABBm5ld05pbAACB25ld0NvbnMAAwVwcmludAAEBHNvcnQABQrgAQUGAEEAJAALGQEBfyMAIQAgAEEANgIAIABBBGokACAADwsnAQF/IwAhAiACQQE2AgAgAiAANgIEIAIgATYCCCACQQxqJAAgAg8LJgACQAJAAkAgACgCAA4CAgEACwALIAAoAgQQACAAKAIIEAQPCw8LbgEEfwNAQQAgACgCAEYEQA8LIAAoAgQhASAAIQIgAigCCCEDA0BBACADKAIARgRAIAIgAEYEQCAAKAIIIQALDAILIAMoAgQhBCAEIAFJBEAgAyABNgIEIAIgBDYCBCADIQILIAMoAgghAwwACwsL",
                unguarded: "AGFzbQEAAAABHAZgAX8AYAAAYAABf2ACf38Bf2ABfwF/YAJ/fwACDwEHY29uc29sZQNsb2cAAAMKCQECAwQEBAUAAAUEAQECAgYGAX8BQQALBysFBXJlc2V0AAEGbmV3TmlsAAIHbmV3Q29ucwADBXByaW50AAgEc29ydAAJCvkBCQYAQQAkAAsZAQF/IwAhACAAQQA2AgAgAEEEaiQAIAAPCycBAX8jACECIAJBATYCACACIAA2AgQgAiABNgIIIAJBDGokACACDwsLAEEAIAAoAgBGDwsIACAAKAIEDwsIACAAKAIIDwsJACAAIAE2AgQLJgACQAJAAkAgACgCAA4CAgEACwALIAAoAgQQACAAKAIIEAgPCw8LXwEEfwNAIAAQBARADwsgABAFIQEgACECIAIQBiEDA0AgAxAEBEAgAiAARgRAIAAQBiEACwwCCyADEAUhBCAEIAFJBEAgAyABEAcgAiAEEAcgAyECCyADEAYhAwwACwsL",
                switch: "AGFzbQEAAAABHAZgAX8AYAAAYAABf2ACf38Bf2ABfwF/YAJ/fwACDwEHY29uc29sZQNsb2cAAAMKCQECAwQEBAUAAAUEAQECAgYGAX8BQQALBysFBXJlc2V0AAEGbmV3TmlsAAIHbmV3Q29ucwADBXByaW50AAgEc29ydAAJCsoCCQYAQQAkAAsZAQF/IwAhACAAQQA2AgAgAEEEaiQAIAAPCycBAX8jACECIAJBATYCACACIAA2AgQgAiABNgIIIAJBDGokACACDwscAAJAAkACQCAAKAIADgICAQALAAtBAA8LQQEPCx0AAkACQAJAIAAoAgAOAgIBAAsACyAAKAIEDwsACx0AAkACQAJAIAAoAgAOAgIBAAsACyAAKAIIDwsACx8AAkACQAJAIAAoAgAOAgIBAAsACyAAIAE2AgQPCwALJgACQAJAAkAgACgCAA4CAgEACwALIAAoAgQQACAAKAIIEAgPCw8LXwEEfwNAIAAQBARADwsgABAFIQEgACECIAIQBiEDA0AgAxAEBEAgAiAARgRAIAAQBiEACwwCCyADEAUhBCAEIAFJBEAgAyABEAcgAiAEEAcgAyECCyADEAYhAwwACwsL",
                vtable: "AGFzbQEAAAABHAZgAX8AYAAAYAABf2ACf38Bf2ABfwF/YAJ/fwACDwEHY29uc29sZQNsb2cAAAMQDwECAwQEBAQEBAUFAAAAAAQFAXABCgoFBAEBAgIGBgF/AUEACwcrBQVyZXNldAABBm5ld05pbAACB25ld0NvbnMAAwVwcmludAAOBHNvcnQADwkQAQBBAAsKBAYKCAwFBwsJDQrSAg8GAEEAJAALGQEBfyMAIQAgAEEANgIAIABBBGokACAADwsnAQF/IwAhAiACQQU2AgAgAiAANgIEIAIgATYCCCACQQxqJAAgAg8LBQBBAQ8LBQBBAA8LAwAACwgAIAAoAgQPCwMAAAsJACAAKAIIDwALAwAACwoAIAAgATYCBA8LAwAPCxEAIAAoAgQQACAAKAIIEA4PCw8AIABBBCAAKAIAahEAAAuqAQEEfwNAIAAgACgCABEEAARADwsgAEEBIAAoAgBqEQQAIQEgACECIAJBAyACKAIAahEEACEDA0AgAyADKAIAEQQABEAgAiAARgRAIABBAyAAKAIAahEEACEACwwCCyADQQEgAygCAGoRBAAhBCAEIAFJBEAgAyABQQIgAygCAGoRBQAgAiAEQQIgAigCAGoRBQAgAyECCyADQQMgAygCAGoRBAAhAwwACwsL"
            },
            separate: {
                direct: {
                    list: {
                        unguarded: "AGFzbQEAAAABHAZgAX8AYAAAYAABf2ACf38Bf2ABfwF/YAJ/fwACDwEHY29uc29sZQNsb2cAAAMJCAECAwQEBAUABQQBAQICBgYBfwFBAAsHWQkGbWVtb3J5AgAFcmVzZXQAAQZuZXdOaWwAAgduZXdDb25zAAMFaXNOaWwABApnZXRFbGVtZW50AAUHZ2V0TmV4dAAGCnNldEVsZW1lbnQABwVwcmludAAICpkBCAYAQQAkAAsZAQF/IwAhACAAQQA2AgAgAEEEaiQAIAAPCycBAX8jACECIAJBATYCACACIAA2AgQgAiABNgIIIAJBDGokACACDwsLAEEAIAAoAgBGDwsIACAAKAIEDwsIACAAKAIIDwsJACAAIAE2AgQLJgACQAJAAkAgACgCAA4CAgEACwALIAAoAgQQACAAKAIIEAgPCw8L",
                        switch: "AGFzbQEAAAABHAZgAX8AYAAAYAABf2ACf38Bf2ABfwF/YAJ/fwACDwEHY29uc29sZQNsb2cAAAMJCAECAwQEBAUABQQBAQICBgYBfwFBAAsHWQkGbWVtb3J5AgAFcmVzZXQAAQZuZXdOaWwAAgduZXdDb25zAAMFaXNOaWwABApnZXRFbGVtZW50AAUHZ2V0TmV4dAAGCnNldEVsZW1lbnQABwVwcmludAAICuoBCAYAQQAkAAsZAQF/IwAhACAAQQA2AgAgAEEEaiQAIAAPCycBAX8jACECIAJBATYCACACIAA2AgQgAiABNgIIIAJBDGokACACDwscAAJAAkACQCAAKAIADgICAQALAAtBAA8LQQEPCx0AAkACQAJAIAAoAgAOAgIBAAsACyAAKAIEDwsACx0AAkACQAJAIAAoAgAOAgIBAAsACyAAKAIIDwsACx8AAkACQAJAIAAoAgAOAgIBAAsACyAAIAE2AgQPCwALJgACQAJAAkAgACgCAA4CAgEACwALIAAoAgQQACAAKAIIEAgPCw8L"
                    },
                    sort: "AGFzbQEAAAABDwNgAX8Bf2ACf38AYAF/AAJQBQRsaXN0Bm1lbW9yeQIAAQRsaXN0BWlzTmlsAAAEbGlzdApnZXRFbGVtZW50AAAEbGlzdAdnZXROZXh0AAAEbGlzdApzZXRFbGVtZW50AAEDAgECBwgBBHNvcnQABAphAV8BBH8DQCAAEAAEQA8LIAAQASEBIAAhAiACEAIhAwNAIAMQAARAIAIgAEYEQCAAEAIhAAsMAgsgAxABIQQgBCABSQRAIAMgARADIAIgBBADIAMhAgsgAxACIQMMAAsLCw=="
                },
                vtable: {
                    list: "AGFzbQEAAAABHAZgAX8AYAAAYAABf2ACf38Bf2ABfwF/YAJ/fwACDwEHY29uc29sZQNsb2cAAAMPDgECAwQEBAQEBAUFAAAABAUBcAEKCgUEAQECAgYfBn8AQQALfwBBAQt/AEECC38AQQMLfwBBBAt/AUEACweIAQsLaXNOaWxPZmZzZXQDABBnZXRFbGVtZW50T2Zmc2V0AwEQc2V0RWxlbWVudE9mZnNldAMCDWdldE5leHRPZmZzZXQDAwtwcmludE9mZnNldAMEBm1lbW9yeQIABnZ0YWJsZQEABXJlc2V0AAEGbmV3TmlsAAIHbmV3Q29ucwADBXByaW50AA4JEAEAQQALCgQGCggMBQcLCQ0KpgEOBgBBACQFCxkBAX8jBSEAIABBADYCACAAQQRqJAUgAA8LJwEBfyMFIQIgAkEFNgIAIAIgADYCBCACIAE2AgggAkEMaiQFIAIPCwUAQQEPCwUAQQAPCwMAAAsIACAAKAIEDwsDAAALCQAgACgCCA8ACwMAAAsKACAAIAE2AgQPCwMADwsRACAAKAIEEAAgACgCCBAODwsPACAAIwQgACgCAGoRAAAL",
                    sort: {
                        constant: "AGFzbQEAAAABDwNgAX8AYAF/AX9gAn9/AAIgAgRsaXN0Bm1lbW9yeQIAAQRsaXN0BnZ0YWJsZQFwAAADAgEABwgBBHNvcnQAAAqtAQGqAQEEfwNAIAAgACgCABEBAARADwsgAEEBIAAoAgBqEQEAIQEgACECIAJBAyACKAIAahEBACEDA0AgAyADKAIAEQEABEAgAiAARgRAIABBAyAAKAIAahEBACEACwwCCyADQQEgAygCAGoRAQAhBCAEIAFJBEAgAyABQQIgAygCAGoRAgAgAiAEQQIgAigCAGoRAgAgAyECCyADQQMgAygCAGoRAQAhAwwACwsL",
                        extern: "AGFzbQEAAAABDwNgAX8AYAF/AX9gAn9/AAJkBgRsaXN0BWlzTmlsA38ABGxpc3QKZ2V0RWxlbWVudAN/AARsaXN0CnNldEVsZW1lbnQDfwAEbGlzdAdnZXROZXh0A38ABGxpc3QGbWVtb3J5AgABBGxpc3QGdnRhYmxlAXAAAAMCAQAHCAEEc29ydAAACrMBAbABAQR/A0AgACMAIAAoAgBqEQEABEAPCyAAIwEgACgCAGoRAQAhASAAIQIgAiMDIAIoAgBqEQEAIQMDQCADIwAgAygCAGoRAQAEQCACIABGBEAgACMDIAAoAgBqEQEAIQALDAILIAMjASADKAIAahEBACEEIAQgAUkEQCADIAEjAiADKAIAahECACACIAQjAiACKAIAahECACADIQILIAMjAyADKAIAahEBACEDDAALCws="
                    }
                }
            },
        }

        function base64ToArrayBuffer(base64) {
            var binary_string = window.atob(base64);
            var len = binary_string.length;
            var bytes = new Uint8Array(len);
            for (var i = 0; i < len; i++) {
                bytes[i] = binary_string.charCodeAt(i);
            }
            return bytes.buffer;
        }
        function log(text) {
            document.getElementById("console").innerHTML += text + "</br>";
        }
        function clearConsole() {
            document.getElementById("console").innerHTML = "";
        }

        const instances = {}

        function instantiateWhole(wasm_base64) {
            return WebAssembly.instantiate(base64ToArrayBuffer(wasm_base64),
                                           {console: {log: log}}
                                          ).then((wasm) => {
                const { newNil: newNil, newCons: newCons, print: print, reset: reset, sort: sort } = wasm.instance.exports;
                return { newNil: newNil, newCons: newCons, print: print, reset: reset, sort: sort };
            });
        }

        function instantiateSeparateDirect(list_base64, sort_base64) {
            return WebAssembly.instantiate(base64ToArrayBuffer(list_base64),
                                        {console: {log: log}}
                                        ).then((list_wasm) => {
                const { newNil: newNil, newCons: newCons, print: print, reset: reset, memory: memory,
                        isNil: isNil, getElement: getElement, setElement: setElement, getNext: getNext
                    } = list_wasm.instance.exports;
                return WebAssembly.instantiate(base64ToArrayBuffer(sort_base64),
                                            {list: {memory: memory, isNil: isNil, getElement: getElement, setElement: setElement, getNext: getNext}}
                                            ).then((sort_wasm) => {
                    const { sort: sort } = sort_wasm.instance.exports;
                    return { newNil: newNil, newCons: newCons, print: print, reset: reset, sort: sort };
                });
            });
        }

        function instantiateSeparateVtable(list_base64, sort_base64) {
            return WebAssembly.instantiate(base64ToArrayBuffer(list_base64),
                                           {console: {log: log}}
                                          ).then((list_wasm) => {
                const { newNil: newNil, newCons: newCons, print: print, reset: reset, memory: memory, vtable: vtable,
                        isNilOffset: isNilOffset, getElementOffset: getElementOffset, setElementOffset: setElementOffset, getNextOffset: getNextOffset
                      } = list_wasm.instance.exports;
                return WebAssembly.instantiate(base64ToArrayBuffer(sort_base64),
                                               {list: {memory: memory, vtable: vtable, isNil: isNilOffset, getElement: getElementOffset, setElement: setElementOffset, getNext: getNextOffset}}
                                              ).then((sort_wasm) => {
                    const { sort: sort } = sort_wasm.instance.exports;
                    return { newNil: newNil, newCons: newCons, print: print, reset: reset, sort: sort };
                });
            });
        }

        function instantiateJavascript() {
class Node {
  //isNil()
  //getElement() : Int16
  //setElement(Int16)
  //getNext() : Node
  //print()
}

class Nil extends Node {
  isNil() { return true; }
  print() { }
}

class Cons extends Node {
  element;
  next;
  constructor(element, next) { super(); this.element = element; this.next = next; }
  isNil() { return false; }
  getElement() { return this.element; }
  setElement(element) { this.element = element; }
  getNext() { return this.next; }
  print() { log(this.element); this.next.print(); }
}

function sort(head) {
  while (!head.isNil()) {
    element = head.getElement();
    old = head;
    node = old.getNext();
    while (!node.isNil()) {
      value = node.getElement();
      if (value < element) {
        node.setElement(element);
        old.setElement(value);
        old = node;
      }
      node = node.getNext();
    }
    if (old === head) {
      head = head.getNext();
    }
  }
}
function newNil() { return new Nil(); }
function newCons(element, next) { return new Cons(element, next); }
function print(node) { node.print(); }
function reset() {}

return Promise.resolve({ newNil: newNil, newCons: newCons, print: print, reset: reset, sort: sort });
        }

        const instantiators = {
            wholeOptimal: () => instantiateWhole(base64.whole.optimal),
            wholeUnguarded: () => instantiateWhole(base64.whole.unguarded),
            wholeSwitch: () => instantiateWhole(base64.whole.switch),
            wholeVtable: () => instantiateWhole(base64.whole.vtable),
            separateDirectUnguarded: () => instantiateSeparateDirect(base64.separate.direct.list.unguarded, base64.separate.direct.sort),
            separateDirectSwitch: () => instantiateSeparateDirect(base64.separate.direct.list.switch, base64.separate.direct.sort),
            separateVtableConstant: () => instantiateSeparateVtable(base64.separate.vtable.list, base64.separate.vtable.sort.constant),
            separateVtableExtern: () => instantiateSeparateVtable(base64.separate.vtable.list, base64.separate.vtable.sort.extern),
            javascript: instantiateJavascript,
        };

        function runEvaluation() {
            const selector = document.getElementById("selection");
            const name = selector.options[selector.selectedIndex].innerHTML;
            const selection = selector.value;
            if (selection in instances) {
                log(name + " already instantiated");
            } else {
                log("instantiating " + name);
                instances[selection] = instantiators[selection]();
            }

            instances[selection].then((sorter) => {
                log("starting " + name);

                const { newNil: newNil, newCons: newCons, print: print, reset: reset, sort: sort } = sorter;

                times = 5;

                function runOnce() {
                    size = 10000;

                    reset();
                    list = newNil();
                    element = 17;
                    for (i = 0; i < size; i++) {
                        list = newCons(element, list);
                        element = (element * 115249) % 16777213;
                    }
                    start = performance.now();
                    sort(list);
                    log(performance.now() - start);

                    if (--times > 0)
                        window.setTimeout(runOnce, 0);
                    else {
                        log(name + " done");
                        log("");
                    }
                }

                window.setTimeout(runOnce, 0);
            });
        }

        function checkCorrectness() {
            const selector = document.getElementById("selection");
            const name = selector.options[selector.selectedIndex].innerHTML;
            const selection = selector.value;
            if (selection in instances) {
                log(name + " already instantiated");
            } else {
                log("instantiating " + name);
                instances[selection] = instantiators[selection]();
            }

            instances[selection].then((sorter) => {
                log("starting " + name);

                const { newNil: newNil, newCons: newCons, print: print, reset: reset, sort: sort } = sorter;

                size = 5;

                reset();
                list = newNil();
                element = 17;
                for (i = 0; i < size; i++) {
                    list = newCons(element, list);
                    element = (element * 115249) % 16777213;
                }
                log("unsorted");
                print(list);
                log("sorted");
                sort(list);
                print(list);
                log(name + " done");
                log("");
            });
        }
    </script>
    <body>

        <h1>WebAssembly Performance</h1>
        <select id="selection">
            <option value="wholeOptimal">whole-optimal: Fully Inlined without Tests</option>
            <option value="wholeUnguarded">whole-unguarded: Direct Calls without Tests</option>
            <option value="wholeSwitch">whole-switch: Direct Calls using Switch Tables</option>
            <option value="wholeVtable">whole-vtable: Indirect Calls</option>
            <option value="separateDirectUnguarded">separate-direct-unguarded: Separately Compiled using Direct Calls without Tests</option>
            <option value="separateDirectSwitch">separate-direct-switch: Separately Compiled using Direct Calls using Switch Tables</option>
            <option value="separateVtableConstant">separate-vtable-constant: Separately Compiled using Indirect Calls at Predetermined Method Offsets</option>
            <option value="separateVtableExtern">separate-vtable-extern: Separately Compiled using Indirect Calls at Imported Method Offsets</option>
            <option value="javascript">JavaScript Classes using only Methods</option>
        </select>
        <input type="button" value="Run" onclick="runEvaluation()"/>
        <input type="button" value="Test" onclick="checkCorrectness()"/>
        <input type="button" value="Clear" onclick="clearConsole()"/>
        <p id="console"></p>

    </body>
</html>

Sort.java

interface Node {
    boolean isNil();
    int getElement();
    void setElement(int element);
    Node getNext();
    void print();
}

class Nil implements Node {
    public Nil() { }

    public boolean isNil() { return true; }
    public int getElement() { throw new UnsupportedOperationException(); }
    public void setElement(int element) { throw new UnsupportedOperationException(); }
    public Node getNext() { throw new UnsupportedOperationException(); }
    public void print() { }
}

class Cons implements Node {
    private int element;
    private Node next;
    public Cons(int element, Node next) { this.element = element; this.next = next; }

    public boolean isNil() { return false; }
    public int getElement() { return element; }
    public void setElement(int element) { this.element = element; }
    public Node getNext() { return next; }
    public void print() { System.out.println(element); next.print(); }
}

public class Sort {
    static Node newNil() { return new Nil(); }
    static Node newCons(long element, Node next) { return new Cons((int)element, next); }

    public static void sort(Node head) {
        while (!head.isNil()) {
            int element = head.getElement();
            Node old = head;
            Node node = old.getNext();
            while (!node.isNil()) {
                int value = node.getElement();
                if (value < element) {
                    node.setElement(element);
                    old.setElement(value);
                    old = node;
                }
                node = node.getNext();
            }
            if (old == head) {
                head = head.getNext();
            }
        }
    }

    public static void main(String[] args) {
        boolean test = args.length > 0;
        boolean show = test;
        boolean time = !test;
        int size = test ? 5 : 10000;

        for (int count = test ? 1 : 5; count > 0; count--) {
            Node list = newNil();
            long element = 17;
            for (int i = 0; i < size; i++) {
                list = newCons(element, list);
                element = (element * 115249) % 16777213;
            }
            if (show) {
                System.out.println("unsorted");
                list.print();
            }
            long start = System.currentTimeMillis();
            sort(list);
            if (time)
                System.out.println(System.currentTimeMillis() - start);
            if (show) {
                System.out.println("sorted");
                list.print();
            }
        }
    }
}

Sort.js

class Node {
  //isNil()
  //getElement() : Int16
  //setElement(Int16)
  //getNext() : Node
  //print()
}

class Nil extends Node {
  isNil() { return true; }
  print() { }
}

class Cons extends Node {
  element;
  next;
  constructor(element, next) { super(); this.element = element; this.next = next; }
  isNil() { return false; }
  getElement() { return this.element; }
  setElement(element) { this.element = element; }
  getNext() { return this.next; }
  print() { log(this.element); this.next.print(); }
}

function sort(head) {
  while (!head.isNil()) {
    element = head.getElement();
    old = head;
    node = old.getNext();
    while (!node.isNil()) {
      value = node.getElement();
      if (value < element) {
        node.setElement(element);
        old.setElement(value);
        old = node;
      }
      node = node.getNext();
    }
    if (old === head) {
      head = head.getNext();
    }
  }
}
function newNil() { return new Nil(); }
function newCons(element, next) { return new Cons(element, next); }
function print(node) { node.print(); }
function reset() {}

return Promise.resolve({ newNil: newNil, newCons: newCons, print: print, reset: reset, sort: sort });

whole-optimal.c

#include<stdlib.h>
#include<printf.h>
#include<time.h>

typedef struct Node Node;

#define NIL 0
#define CONS 1

typedef struct Node Node;
struct Node {
    unsigned int class;
};

typedef struct Nil Nil;
struct Nil {
    Node base;
};

Node* newNil() {
    Nil* nil = malloc(sizeof(Nil));
    nil->base.class = NIL;
    return &nil->base;
}

typedef struct Cons Cons;
struct Cons {
    Node base;
    unsigned int element;
    Node* next;
};

Node* newCons(unsigned int element, Node* next) {
    Cons* cons = malloc(sizeof(Cons));
    cons->base.class = CONS;
    cons->element = element;
    cons->next = next;
    return &cons->base;
}

void print(Node* this) {
    switch (this->class) {
    case NIL:
        return;
    case CONS:
        printf("%d\n", ((Cons*)this)->element);
        Node* next = ((Cons*)this)->next;
        print(next);
        return;
    default:
        exit(-1);
        return;
    }
}
void freeNode(Node* this) {
    Node* next;
    switch (this->class) {
    case NIL:
        free(this);
        return;
    case CONS:
        next = ((Cons*)this)->next;
        freeNode(next);
        free(this);
        return;
    default:
        exit(-1);
        return;
    }
}

void sort(Node* head) {
    while (head->class != NIL) {
        Cons* old = (Cons*)head;
        unsigned int element = old->element;
        Node* node = old->next;
        while (node->class != NIL) {
            Cons* cons = (Cons*)node;
            unsigned int value = cons->element;
            if (value < element) {
                cons->element = element;
                old->element = value;
                old = cons;
            }
            node = cons->next;
        }
        if (head == (Node*)old) {
            head = old->next;
        }
    }
}

void perform(unsigned int show, unsigned int time, unsigned int size) {
    Node* list = newNil();
    unsigned long element =  17;
    for (unsigned int i = 0; i < size; i++) {
        list = newCons((unsigned int)element, list);
        element = (element * 115249) % 16777213;
    }
    if (show) {
        printf("unsorted\n");
        print(list);
    }
    clock_t start = clock();
    sort(list);
    clock_t end = clock();
    double seconds = ((double)(end - start))/CLOCKS_PER_SEC;
    if (time)
        printf("%f\n", seconds * 1000);
    if (show) {
        printf("sorted\n");
        print(list);
    }
    freeNode(list);
}

int main(int argc, char* argv[]) {
    unsigned int test = argc > 1;
    unsigned int show = test;
    unsigned int time = !test;
    unsigned int size = test ? 5 : 10000;
    for (unsigned int count = test ? 1 : 5; count != 0; count--)
        perform(show, time, size);
    return 0;
}

whole-optimal.wat

(module
  (func $log (import "console" "log") (param $element i32))
  
  (memory 2 2)
  (global $unallocated (mut i32) (i32.const 0))
  
  (func (export "reset")
    (global.set $unallocated (i32.const 0))
  )
  
  (func $newNil (export "newNil") (result i32) (local $address i32)
    (local.set $address (global.get $unallocated))
    (i32.store (local.get $address) (i32.const 0))
    (global.set $unallocated (i32.add (local.get $address) (i32.const 4)))
    (return (local.get $address))
  )
  
  (func $newCons (export "newCons") (param $element i32) (param $next i32) (result i32) (local $address i32)
    (local.set $address (global.get $unallocated))
    (i32.store (local.get $address) (i32.const 1))
    (i32.store offset=4 (local.get $address) (local.get $element))
    (i32.store offset=8 (local.get $address) (local.get $next))
    (global.set $unallocated (i32.add (local.get $address) (i32.const 12)))
    (return (local.get $address))
  )
  
  (func $print (export "print") (param $this i32)
    (block $Nil
      (block $Cons
        (block $Unreachable
          (br_table $Nil $Cons $Unreachable (i32.load (local.get $this)))
        )
        unreachable
      )
      (call $log (i32.load offset=4 (local.get $this)))
      (call $print (i32.load offset=8 (local.get $this)))
      return
    )
    return
  )
  
  (func $sort (export "sort") (param $head i32) (local $element i32) (local $old i32) (local $node i32) (local $value i32)
    (loop $while_head
      (if (i32.eq (i32.const 0) (i32.load (local.get $head)))
        (return)
      )
      (local.set $element (i32.load offset=4 (local.get $head)))
      (local.set $old (local.get $head))
      (local.set $node (i32.load offset=8 (local.get $old)))
      (loop $while_node
        (if (i32.eq (i32.const 0) (i32.load (local.get $node)))
          (then
            (if (i32.eq (local.get $old) (local.get $head))
              (local.set $head (i32.load offset=8 (local.get $head)))
            )
            (br $while_head)
          )
        )
        (local.set $value (i32.load offset=4 (local.get $node)))
        (if (i32.lt_u (local.get $value) (local.get $element))
          (then
            (i32.store offset=4 (local.get $node) (local.get $element))
            (i32.store offset=4 (local.get $old) (local.get $value))
            (local.set $old (local.get $node))
          )
        )
        (local.set $node (i32.load offset=8 (local.get $node)))
        (br $while_node)
      )
    )
  )
)

whole-switch.c

#include<stdlib.h>
#include<printf.h>
#include<time.h>

typedef struct Node Node;
typedef struct NodeVTable NodeVTable;

#define NIL 0
#define CONS 1

typedef struct Node Node;
struct Node {
    unsigned int class;
};

typedef struct Nil Nil;
struct Nil {
    Node base;
};

Node* newNil() {
    Nil* nil = malloc(sizeof(Nil));
    nil->base.class = NIL;
    return &nil->base;
}

typedef struct Cons Cons;
struct Cons {
    Node base;
    unsigned int element;
    Node* next;
};

Node* newCons(unsigned int element, Node* next) {
    Cons* cons = malloc(sizeof(Cons));
    cons->base.class = CONS;
    cons->element = element;
    cons->next = next;
    return &cons->base;
}

unsigned int isNil(Node* this) {
    switch (this->class) {
    case NIL:
        return 1;
    case CONS:
        return 0;
    default:
        exit(-1);
        return 0;
    }
}
unsigned int getElement(Node* this) {
    switch (this->class) {
    case NIL:
        exit(-1);
        return 0;
    case CONS:
        return ((Cons*)this)->element;
    default:
        exit(-1);
        return 0;
    }
}
void setElement(Node* this, unsigned int element) {
    switch (this->class) {
    case NIL:
        exit(-1);
        return;
    case CONS:
        ((Cons*)this)->element = element;
        return;
    default:
        exit(-1);
        return;
    }
}
Node* getNext(Node* this) {
    switch (this->class) {
    case NIL:
        exit(-1);
        return 0;
    case CONS:
        return ((Cons*)this)->next;
    default:
        exit(-1);
        return 0;
    }
}
void print(Node* this) {
    switch (this->class) {
    case NIL:
        return;
    case CONS:
        printf("%d\n", ((Cons*)this)->element);
        Node* next = ((Cons*)this)->next;
        print(next);
        return;
    default:
        exit(-1);
        return;
    }
}
void freeNode(Node* this) {
    Node* next;
    switch (this->class) {
    case NIL:
        free(this);
        return;
    case CONS:
        next = ((Cons*)this)->next;
        freeNode(next);
        free(this);
        return;
    default:
        exit(-1);
        return;
    }
}

void sort(Node* head) {
  while (!isNil(head)) {
    unsigned int element = getElement(head);
    Node* old = head;
    Node* node = getNext(old);
    while (!isNil(node)) {
      unsigned int value = getElement(node);
      if (value < element) {
        setElement(node, element);
        setElement(old, value);
        old = node;
      }
      node = getNext(node);
    }
    if (old == head) {
      head = getNext(head);
    }
  }
}

void perform(unsigned int show, unsigned int time, unsigned int size) {
    Node* list = newNil();
    unsigned long element =  17;
    for (unsigned int i = 0; i < size; i++) {
        list = newCons((unsigned int)element, list);
        element = (element * 115249) % 16777213;
    }
    if (show) {
        printf("unsorted\n");
        print(list);
    }
    clock_t start = clock();
    sort(list);
    clock_t end = clock();
    double seconds = ((double)(end - start))/CLOCKS_PER_SEC;
    if (time)
        printf("%f\n", seconds * 1000);
    if (show) {
        printf("sorted\n");
        print(list);
    }
    freeNode(list);
}

int main(int argc, char* argv[]) {
    unsigned int test = argc > 1;
    unsigned int show = test;
    unsigned int time = !test;
    unsigned int size = test ? 5 : 10000;
    for (unsigned int count = test ? 1 : 5; count != 0; count--)
        perform(show, time, size);
    return 0;
}

whole-switch.wat

(module
  (func $log (import "console" "log") (param $element i32))
  
  (memory 2 2)
  (global $unallocated (mut i32) (i32.const 0))
  
  (func (export "reset")
    (global.set $unallocated (i32.const 0))
  )
  
  (func $newNil (export "newNil") (result i32) (local $address i32)
    (local.set $address (global.get $unallocated))
    (i32.store (local.get $address) (i32.const 0))
    (global.set $unallocated (i32.add (local.get $address) (i32.const 4)))
    (return (local.get $address))
  )
  
  (func $newCons (export "newCons") (param $element i32) (param $next i32) (result i32) (local $address i32)
    (local.set $address (global.get $unallocated))
    (i32.store (local.get $address) (i32.const 1))
    (i32.store offset=4 (local.get $address) (local.get $element))
    (i32.store offset=8 (local.get $address) (local.get $next))
    (global.set $unallocated (i32.add (local.get $address) (i32.const 12)))
    (return (local.get $address))
  )
  
  (func $isNil (param $this i32) (result i32)
    (block $Nil
      (block $Cons
        (block $Unreachable
          (br_table $Nil $Cons $Unreachable (i32.load (local.get $this)))
        )
        unreachable
      )
      (return (i32.const 0))
    )
    (return (i32.const 1))
  )
  
  (func $getElement (param $this i32) (result i32)
    (block $Nil
      (block $Cons
        (block $Unreachable
          (br_table $Nil $Cons $Unreachable (i32.load (local.get $this)))
        )
        unreachable
      )
      (return (i32.load offset=4 (local.get $this)))
    )
    unreachable
  )
  
  (func $getNext (param $this i32) (result i32)
    (block $Nil
      (block $Cons
        (block $Unreachable
          (br_table $Nil $Cons $Unreachable (i32.load (local.get $this)))
        )
        unreachable
      )
      (return (i32.load offset=8 (local.get $this)))
    )
    unreachable
  )
  
  (func $setElement (param $this i32) (param $element i32)
    (block $Nil
      (block $Cons
        (block $Unreachable
          (br_table $Nil $Cons $Unreachable (i32.load (local.get $this)))
        )
        unreachable
      )
      (i32.store offset=4 (local.get $this) (local.get $element))
      return
    )
    unreachable
  )
  
  (func $print (export "print") (param $this i32)
    (block $Nil
      (block $Cons
        (block $Unreachable
          (br_table $Nil $Cons $Unreachable (i32.load (local.get $this)))
        )
        unreachable
      )
      (call $log (i32.load offset=4 (local.get $this)))
      (call $print (i32.load offset=8 (local.get $this)))
      return
    )
    return
  )
  
  (func $sort (export "sort") (param $head i32) (local $element i32) (local $old i32) (local $node i32) (local $value i32)
    (loop $while_head
      (if (call $isNil (local.get $head))
        (return)
      )
      (local.set $element (call $getElement (local.get $head)))
      (local.set $old (local.get $head))
      (local.set $node (call $getNext (local.get $old)))
      (loop $while_node
        (if (call $isNil (local.get $node))
          (then
            (if (i32.eq (local.get $old) (local.get $head))
              (local.set $head (call $getNext (local.get $head)))
            )
            (br $while_head)
          )
        )
        (local.set $value (call $getElement (local.get $node)))
        (if (i32.lt_u (local.get $value) (local.get $element))
          (then
            (call $setElement (local.get $node) (local.get $element))
            (call $setElement (local.get $old) (local.get $value))
            (local.set $old (local.get $node))
          )
        )
        (local.set $node (call $getNext (local.get $node)))
        (br $while_node)
      )
    )
  )
)

whole-unguarded.c

#include<stdlib.h>
#include<printf.h>
#include<time.h>

typedef struct Node Node;
typedef struct NodeVTable NodeVTable;

#define NIL 0
#define CONS 1

typedef struct Node Node;
struct Node {
    unsigned int class;
};

typedef struct Nil Nil;
struct Nil {
    Node base;
};

Node* newNil() {
    Nil* nil = malloc(sizeof(Nil));
    nil->base.class = NIL;
    return &nil->base;
}

typedef struct Cons Cons;
struct Cons {
    Node base;
    unsigned int element;
    Node* next;
};

Node* newCons(unsigned int element, Node* next) {
    Cons* cons = malloc(sizeof(Cons));
    cons->base.class = CONS;
    cons->element = element;
    cons->next = next;
    return &cons->base;
}

unsigned int isNil(Node* this) {
    return this->class == NIL;
}
unsigned int getElement(Node* this) {
    return ((Cons*)this)->element;
}
void setElement(Node* this, unsigned int element) {
    ((Cons*)this)->element = element;
}
Node* getNext(Node* this) {
    return ((Cons*)this)->next;
}
void print(Node* this) {
    switch (this->class) {
    case NIL:
        return;
    case CONS:
        printf("%d\n", ((Cons*)this)->element);
        Node* next = ((Cons*)this)->next;
        print(next);
        return;
    default:
        exit(-1);
        return;
    }
}
void freeNode(Node* this) {
    Node* next;
    switch (this->class) {
    case NIL:
        free(this);
        return;
    case CONS:
        next = ((Cons*)this)->next;
        freeNode(next);
        free(this);
        return;
    default:
        exit(-1);
        return;
    }
}

void sort(Node* head) {
  while (!isNil(head)) {
    unsigned int element = getElement(head);
    Node* old = head;
    Node* node = getNext(old);
    while (!isNil(node)) {
      unsigned int value = getElement(node);
      if (value < element) {
        setElement(node, element);
        setElement(old, value);
        old = node;
      }
      node = getNext(node);
    }
    if (old == head) {
      head = getNext(head);
    }
  }
}

void perform(unsigned int show, unsigned int time, unsigned int size) {
    Node* list = newNil();
    unsigned long element =  17;
    for (unsigned int i = 0; i < size; i++) {
        list = newCons((unsigned int)element, list);
        element = (element * 115249) % 16777213;
    }
    if (show) {
        printf("unsorted\n");
        print(list);
    }
    clock_t start = clock();
    sort(list);
    clock_t end = clock();
    double seconds = ((double)(end - start))/CLOCKS_PER_SEC;
    if (time)
        printf("%f\n", seconds * 1000);
    if (show) {
        printf("sorted\n");
        print(list);
    }
    freeNode(list);
}

int main(int argc, char* argv[]) {
    unsigned int test = argc > 1;
    unsigned int show = test;
    unsigned int time = !test;
    unsigned int size = test ? 5 : 10000;
    for (unsigned int count = test ? 1 : 5; count != 0; count--)
        perform(show, time, size);
    return 0;
}

whole-unguarded.wat

(module
  (func $log (import "console" "log") (param $element i32))
  
  (memory 2 2)
  (global $unallocated (mut i32) (i32.const 0))
  
  (func (export "reset")
    (global.set $unallocated (i32.const 0))
  )
  
  (func $newNil (export "newNil") (result i32) (local $address i32)
    (local.set $address (global.get $unallocated))
    (i32.store (local.get $address) (i32.const 0))
    (global.set $unallocated (i32.add (local.get $address) (i32.const 4)))
    (return (local.get $address))
  )
  
  (func $newCons (export "newCons") (param $element i32) (param $next i32) (result i32) (local $address i32)
    (local.set $address (global.get $unallocated))
    (i32.store (local.get $address) (i32.const 1))
    (i32.store offset=4 (local.get $address) (local.get $element))
    (i32.store offset=8 (local.get $address) (local.get $next))
    (global.set $unallocated (i32.add (local.get $address) (i32.const 12)))
    (return (local.get $address))
  )
  
  (func $isNil (param $this i32) (result i32)
    (return (i32.eq (i32.const 0) (i32.load (local.get $this))))
  )
  
  (func $getElement (param $this i32) (result i32)
    (return (i32.load offset=4 (local.get $this)))
  )
  
  (func $getNext (param $this i32) (result i32)
    (return (i32.load offset=8 (local.get $this)))
  )
  
  (func $setElement (param $this i32) (param $element i32)
    (i32.store offset=4 (local.get $this) (local.get $element))
  )
  
  (func $print (export "print") (param $this i32)
    (block $Nil
      (block $Cons
        (block $Unreachable
          (br_table $Nil $Cons $Unreachable (i32.load (local.get $this)))
        )
        unreachable
      )
      (call $log (i32.load offset=4 (local.get $this)))
      (call $print (i32.load offset=8 (local.get $this)))
      return
    )
    return
  )
  
  (func $sort (export "sort") (param $head i32) (local $element i32) (local $old i32) (local $node i32) (local $value i32)
    (loop $while_head
      (if (call $isNil (local.get $head))
        (return)
      )
      (local.set $element (call $getElement (local.get $head)))
      (local.set $old (local.get $head))
      (local.set $node (call $getNext (local.get $old)))
      (loop $while_node
        (if (call $isNil (local.get $node))
          (then
            (if (i32.eq (local.get $old) (local.get $head))
              (local.set $head (call $getNext (local.get $head)))
            )
            (br $while_head)
          )
        )
        (local.set $value (call $getElement (local.get $node)))
        (if (i32.lt_u (local.get $value) (local.get $element))
          (then
            (call $setElement (local.get $node) (local.get $element))
            (call $setElement (local.get $old) (local.get $value))
            (local.set $old (local.get $node))
          )
        )
        (local.set $node (call $getNext (local.get $node)))
        (br $while_node)
      )
    )
  )
)

whole-vtable.c

#include<stdlib.h>
#include<printf.h>
#include<time.h>

typedef struct Node Node;
typedef struct NodeVTable NodeVTable;

struct Node {
    NodeVTable* vtable;
};

typedef unsigned int (*IsNilFunc)(Node*);
typedef unsigned int (*GetElementFunc)(Node*);
typedef void (*SetElementFunc)(Node*, unsigned int);
typedef Node* (*GetNextFunc)(Node*);
typedef void (*PrintFunc)(Node*);
typedef void (*FreeFunc)(Node*);

struct NodeVTable {
    IsNilFunc isNil;
    GetElementFunc getElement;
    SetElementFunc setElement;
    GetNextFunc getNext;
    PrintFunc print;
    FreeFunc free;
};

typedef struct Nil Nil;
struct Nil {
    Node base;
};

unsigned int isNilNil(Node* this) {
    return 1;
}
unsigned int getElementNil(Node* this) {
    exit(-1);
    return 0;
}
void setElementNil(Node* this, unsigned int element) {
    exit(-1);
}
Node* getNextNil(Node* this) {
    exit(-1);
    return NULL;
}
void printNil(Node* this) {
}
void freeNil(Node* this) {
    free(this);
}

struct NodeVTable nilvtable = {
    .isNil = isNilNil,
    .getElement = getElementNil,
    .setElement = setElementNil,
    .getNext = getNextNil,
    .print = printNil,
    .free = freeNil
};

Node* newNil() {
    Nil* nil = malloc(sizeof(Nil));
    nil->base.vtable = &nilvtable;
    return &nil->base;
}

typedef struct Cons Cons;
struct Cons {
    Node base;
    unsigned int element;
    Node* next;
};

unsigned int isNilCons(Node* this) {
    return 0;
}
unsigned int getElementCons(Node* this) {
    return ((Cons*)this)->element;
}
void setElementCons(Node* this, unsigned int element) {
    ((Cons*)this)->element = element;
}
Node* getNextCons(Node* this) {
    return ((Cons*)this)->next;
}
void printCons(Node* this) {
    printf("%d\n", ((Cons*)this)->element);
    Node* next = ((Cons*)this)->next;
    next->vtable->print(next);
}
void freeCons(Node* this) {
    Node* next = ((Cons*)this)->next;
    next->vtable->free(next);
    free(this);
}

struct NodeVTable consvtable = {
    .isNil = isNilCons,
    .getElement = getElementCons,
    .setElement = setElementCons,
    .getNext = getNextCons,
    .print = printCons,
    .free = freeCons
};

Node* newCons(unsigned int element, Node* next) {
    Cons* cons = malloc(sizeof(Cons));
    cons->base.vtable = &consvtable;
    cons->element = element;
    cons->next = next;
    return &cons->base;
}

void sort(Node* head) {
  while (!head->vtable->isNil(head)) {
    unsigned int element = head->vtable->getElement(head);
    Node* old = head;
    Node* node = old->vtable->getNext(old);
    while (!node->vtable->isNil(node)) {
      unsigned int value = node->vtable->getElement(node);
      if (value < element) {
        node->vtable->setElement(node, element);
        old->vtable->setElement(old, value);
        old = node;
      }
      node = node->vtable->getNext(node);
    }
    if (old == head) {
      head = head->vtable->getNext(head);
    }
  }
}

void perform(unsigned int show, unsigned int time, unsigned int size) {
    Node* list = newNil();
    unsigned long element =  17;
    for (unsigned int i = 0; i < size; i++) {
        list = newCons((unsigned int)element, list);
        element = (element * 115249) % 16777213;
    }
    if (show) {
        printf("unsorted\n");
        list->vtable->print(list);
    }
    clock_t start = clock();
    sort(list);
    clock_t end = clock();
    double seconds = ((double)(end - start))/CLOCKS_PER_SEC;
    if (time)
        printf("%f\n", seconds * 1000);
    if (show) {
        printf("sorted\n");
        list->vtable->print(list);
    }
    list->vtable->free(list);
}

int main(int argc, char* argv[]) {
    unsigned int test = argc > 1;
    unsigned int show = test;
    unsigned int time = !test;
    unsigned int size = test ? 5 : 10000;
    for (unsigned int count = test ? 1 : 5; count != 0; count--)
        perform(show, time, size);
    return 0;
}

whole-vtable.wat

(module
  (func $log (import "console" "log") (param $element i32))
  
  (memory 2 2)
  (global $unallocated (mut i32) (i32.const 0))
  (table $vtable funcref (elem $isNil_Nil $getElement_Nil $setElement_Nil $getNext_Nil $print_Nil $isNil_Cons $getElement_Cons $setElement_Cons $getNext_Cons $print_Cons))
 
  (func (export "reset")
    (global.set $unallocated (i32.const 0))
  )
  
  (func $newNil (export "newNil") (result i32) (local $address i32)
    (local.set $address (global.get $unallocated))
    (i32.store (local.get $address) (i32.const 0))
    (global.set $unallocated (i32.add (local.get $address) (i32.const 4)))
    (return (local.get $address))
  )
  
  (func $newCons (export "newCons") (param $element i32) (param $next i32) (result i32) (local $address i32)
    (local.set $address (global.get $unallocated))
    (i32.store (local.get $address) (i32.const 5))
    (i32.store offset=4 (local.get $address) (local.get $element))
    (i32.store offset=8 (local.get $address) (local.get $next))
    (global.set $unallocated (i32.add (local.get $address) (i32.const 12)))
    (return (local.get $address))
  )
  
  (func $isNil_Nil (param $this i32) (result i32)
    (return (i32.const 1))
  )
  (func $isNil_Cons (param $this i32) (result i32)
    (return (i32.const 0))
  )
  
  (func $getElement_Nil (param $this i32) (result i32)
    unreachable
  )
  (func $getElement_Cons (param $this i32) (result i32)
    (return (i32.load offset=4 (local.get $this)))
  )
  
  (func $getNext_Nil (param $this i32) (result i32)
    unreachable
  )
  (func $getNext_Cons (param $this i32) (result i32)
    (return (i32.load offset=8 (local.get $this)))
    unreachable
  )
  
  (func $setElement_Nil (param $this i32) (param $element i32)
    unreachable
  )
  (func $setElement_Cons (param $this i32) (param $element i32)
    (i32.store offset=4 (local.get $this) (local.get $element))
    return
  )
  
  (func $print_Nil (param $this i32)
    return
  )
  (func $print_Cons (param $this i32)
    (call $log (i32.load offset=4 (local.get $this)))
    (call $print (i32.load offset=8 (local.get $this)))
    return
  )
  (func $print (export "print") (param $this i32)
    (call_indirect $vtable (param i32) (local.get $this) (i32.add (i32.const 4) (i32.load (local.get $this))))
  )
  
  (func $sort (export "sort") (param $head i32) (local $element i32) (local $old i32) (local $node i32) (local $value i32)
    (loop $while_head
      (if (call_indirect $vtable (param i32) (result i32) (local.get $head) (i32.load (local.get $head)))
        (return)
      )
      (local.set $element (call_indirect $vtable (param i32) (result i32) (local.get $head) (i32.add (i32.const 1) (i32.load (local.get $head)))))
      (local.set $old (local.get $head))
      (local.set $node (call_indirect $vtable (param i32) (result i32) (local.get $old) (i32.add (i32.const 3) (i32.load (local.get $old)))))
      (loop $while_node
        (if (call_indirect $vtable (param i32) (result i32) (local.get $node) (i32.load (local.get $node)))
          (then
            (if (i32.eq (local.get $old) (local.get $head))
              (local.set $head (call_indirect $vtable (param i32) (result i32) (local.get $head) (i32.add (i32.const 3) (i32.load (local.get $head)))))
            )
            (br $while_head)
          )
        )
        (local.set $value (call_indirect $vtable (param i32) (result i32) (local.get $node) (i32.add (i32.const 1) (i32.load (local.get $node)))))
        (if (i32.lt_u (local.get $value) (local.get $element))
          (then
            (call_indirect $vtable (param i32 i32) (local.get $node) (local.get $element) (i32.add (i32.const 2) (i32.load (local.get $node))))
            (call_indirect $vtable (param i32 i32) (local.get $old) (local.get $value) (i32.add (i32.const 2) (i32.load (local.get $old))))
            (local.set $old (local.get $node))
          )
        )
        (local.set $node (call_indirect $vtable (param i32) (result i32) (local.get $node) (i32.add (i32.const 3) (i32.load (local.get $node)))))
        (br $while_node)
      )
    )
  )
)