Skip to content

Instantly share code, notes, and snippets.

@surma

surma/.gitignore Secret

Last active Jul 15, 2022
Embed
What would you like to do?
package-lock.json
*.wasm
*.wat
node_modules
target
Cargo.lock
v8.log
results.csv

This is a benchmark comparing JavaScript libraries with a port to AssemblyScript. AssemblyScript is a TypeScript-like language that compiles to WebAssembly, so the process of porting consisted merely of adding some type annotation and type casts (see diff -y blur.js blur.ts).

Running

You need v8 or d8. If you don’t have it, install jsvu:

$ npm i -g jsvu

The also need Rust nightly as well as Emscripten.

To run the actual benchmark and generate results.csv:

$ npm i
$ ./run_benchmark.sh
const numWarmupDefault = 5;
const numIterationsDefault = 50;
export async function benchmark({
before = () => {},
run = () => {},
after = () => {},
numIterations = numIterationsDefault,
numWarmup = numWarmupDefault,
} = {}) {
const results = [];
for (let i = 0; i < numWarmup; i++) {
const context = {};
await before.call(context);
await run.call(context);
await after.call(context);
}
for (let i = 0; i < numIterations; i++) {
const context = {};
await before.call(context);
const start = Date.now();
await run.call(context);
results.push(Date.now() - start);
await after.call(context);
}
return results;
}
// Binary heap implementation from:
// http://eloquentjavascript.net/appendix2.html
export class BinaryHeap {
constructor(scoreFunction) {
this.content = [];
this.scoreFunction = scoreFunction;
}
push(element) {
// Add the new element to the end of the array.
this.content.push(element);
// Allow it to bubble up.
this.bubbleUp(this.content.length - 1);
}
pop() {
// Store the first element so we can return it later.
var result = this.content[0];
// Get the element at the end of the array.
var end = this.content.pop();
// If there are any elements left, put the end element at the
// start, and let it sink down.
if (this.content.length > 0) {
this.content[0] = end;
this.sinkDown(0);
}
return result;
}
peek() {
return this.content[0];
}
remove(node) {
var len = this.content.length;
// To remove a value, we must search through the array to find
// it.
for (var i = 0; i < len; i++) {
if (this.content[i] == node) {
// When it is found, the process seen in 'pop' is repeated
// to fill up the hole.
var end = this.content.pop();
if (i != len - 1) {
this.content[i] = end;
if (this.scoreFunction(end) < this.scoreFunction(node))
this.bubbleUp(i);
else this.sinkDown(i);
}
return;
}
}
throw new Error("Node not found.");
}
size() {
return this.content.length;
}
bubbleUp(n) {
// Fetch the element that has to be moved.
var element = this.content[n];
// When at 0, an element can not go up any further.
while (n > 0) {
// Compute the parent element's index, and fetch it.
var parentN = Math.floor((n + 1) / 2) - 1,
parent = this.content[parentN];
// Swap the elements if the parent is greater.
if (this.scoreFunction(element) < this.scoreFunction(parent)) {
this.content[parentN] = element;
this.content[n] = parent;
// Update 'n' to continue at the new position.
n = parentN;
}
// Found a parent that is less, no need to move it further.
else {
break;
}
}
}
sinkDown(n) {
// Look up the target element and its score.
var length = this.content.length,
element = this.content[n],
elemScore = this.scoreFunction(element);
while (true) {
// Compute the indices of the child elements.
var child2N = (n + 1) * 2,
child1N = child2N - 1;
// This is used to store the new position of the element,
// if any.
var swap = null;
// If the first child exists (is inside the array)...
if (child1N < length) {
// Look it up and compute its score.
var child1 = this.content[child1N],
child1Score = this.scoreFunction(child1);
// If the score is less than our element's, we need to swap.
if (child1Score < elemScore) swap = child1N;
}
// Do the same checks for the other child.
if (child2N < length) {
var child2 = this.content[child2N],
child2Score = this.scoreFunction(child2);
if (child2Score < (swap == null ? elemScore : child1Score)) {
swap = child2N;
}
}
// If the element needs to be moved, swap it, and continue.
if (swap != null) {
this.content[n] = this.content[swap];
this.content[swap] = element;
n = swap;
}
// Otherwise, we are done.
else {
break;
}
}
}
}
#![feature(option_result_unwrap_unchecked)]
#[cfg(feature = "idiomatic")]
mod binaryheap_idiomatic;
#[cfg(feature = "idiomatic")]
use binaryheap_idiomatic as bhimpl;
#[cfg(feature = "optimized")]
mod binaryheap_optimized;
#[cfg(feature = "optimized")]
use binaryheap_optimized as bhimpl;
#[no_mangle]
pub fn init() {
bhimpl::init();
}
#[no_mangle]
pub fn push(v: f32) {
bhimpl::push(v)
}
#[no_mangle]
pub fn pop() -> f32 {
bhimpl::pop()
}
#[no_mangle]
pub fn size() -> usize {
bhimpl::size()
}
#[no_mangle]
pub fn peek() -> f32 {
bhimpl::peek()
}
import { benchmark } from "./bench.js";
const ascModule = new WebAssembly.Module(readbuffer(arguments[0]));
const results = await benchmark({
async before() {
this.instance = new WebAssembly.Instance(ascModule, {
env: {
abort(msgPtr, fileNamePtr, lineNumber) {
throw Error("AAARGH");
},
},
});
this.instance.exports.init();
},
async run() {
for (let i = 0; i < 1000000; i++) {
this.instance.exports.push(Math.random());
}
let last = Number.NEGATIVE_INFINITY;
while (this.instance.exports.size() > 0) {
const current = this.instance.exports.pop();
if (current < last) {
console.log(`current=${current}, last=${last}`);
throw Error(`Invalid ordering! Left: ${this.instance.exports.size()}`);
}
last = current;
}
},
numWarmup: 0,
});
console.log(results);
import { benchmark } from "./bench.js";
load("binaryheap_idiomatic_cpp.js");
Module.onRuntimeInitialized = async () => {
const results = await benchmark({
async before() {
this.instance = Module;
this.instance.init();
},
async run() {
for (let i = 0; i < 1000000; i++) {
this.instance.push(Math.random());
}
let last = Number.NEGATIVE_INFINITY;
while (this.instance.size() > 0) {
const current = this.instance.pop();
if (current < last) {
console.log(`current=${current}, last=${last}`);
throw Error(
`Invalid ordering! Left: ${this.instance.exports.size()}`
);
}
last = current;
}
},
numWarmup: 0,
});
console.log(results);
};
// Binary heap implementation from:
// http://eloquentjavascript.net/appendix2.html
class MyArray<T> {
data: StaticArray<T>;
length: i32 = 0;
[key: number]: T;
constructor(capacity: u32 = 10) {
this.data = new StaticArray<T>(capacity);
}
@inline
capacity(): i32 {
return this.data.length;
}
push(value: T): void {
// If we have reached capacity, create a new underlying array with
// double the capacity.
if (this.length == this.capacity()) {
const newData = new StaticArray<T>(this.capacity() * 2);
memory.copy(
changetype<usize>(newData),
changetype<usize>(this.data),
this.length * sizeof<T>()
);
this.data = newData;
}
this.data[this.length] = value;
this.length++;
}
pop(): T {
if (this.length <= 0) {
throw new Error("Popping empty MyArray");
}
this.length -= 1;
return this.data[<i32>this.length];
}
@operator("[]") private __get(index: i32): T {
// No bounds check because lol
return unchecked(this[index]);
}
@operator("[]=") private __set(index: i32, value: T): void {
// No bounds check because lol
unchecked((this[index] = value));
}
// Unchecked get
@unsafe @operator("{}") private __uget(index: i32): T {
return load<T>(changetype<usize>(this.data) + <usize>index * sizeof<T>());
}
// Unchecked set
@unsafe @operator("{}=") private __uset(index: i32, value: T): void {
store<T>(changetype<usize>(this.data) + <usize>index * sizeof<T>(), value);
}
}
type ScoreFunction<T> = (v: T) => f32;
class BinaryHeap<T> {
content: MyArray<T> = new MyArray<T>(10);
push(element: T): void {
// Add the new element to the end of the array.
this.content.push(element);
// Allow it to bubble up.
this.bubbleUp(<i32>this.content.length - 1);
}
pop(): T {
if (this.content.length <= 0) {
throw new Error("Can't pop an empty heap");
}
// Store the first element so we can return it later.
const result = unchecked(this.content[0]);
// Get the element at the end of the array.
const end = this.content.pop();
// If there are any elements left, put the end element at the
// start, and let it sink down.
if (this.content.length > 0) {
unchecked((this.content[0] = end));
this.sinkDown(0);
}
return result;
}
peek(): T {
if (this.content.length <= 0) {
throw new Error("Can't peek an empty heap");
}
return unchecked(this.content[0]);
}
remove(node: T): void {
if (this.content.length <= 0) {
throw new Error("Can't remove from an empty heap");
}
const len = this.content.length;
// To remove a value, we must search through the array to find
// it.
for (let i = 0; i < len; i++) {
if (unchecked(this.content[i]) == node) {
// When it is found, the process seen in 'pop' is repeated
// to fill up the hole.
const end = this.content.pop();
if (i != len - 1) {
unchecked((this.content[i] = end));
if (end < node) this.bubbleUp(i);
else this.sinkDown(i);
}
return;
}
}
throw new Error("Node not found.");
}
size(): u32 {
return this.content.length;
}
bubbleUp(n: u32): void {
// Fetch the element that has to be moved.
const element = unchecked(this.content[n]);
// When at 0, an element can not go up any further.
while (n > 0) {
// Compute the parent element's index, and fetch it.
const parentN = <i32>Math.floor((n + 1) / 2) - 1,
parent = unchecked(this.content[parentN]);
// Swap the elements if the parent is greater.
if (element < parent) {
unchecked((this.content[parentN] = element));
unchecked((this.content[n] = parent));
// Update 'n' to continue at the new position.
n = parentN;
}
// Found a parent that is less, no need to move it further.
else {
break;
}
}
}
sinkDown(n: u32): void {
// Look up the target element and its score.
const length = this.content.length,
element = unchecked(this.content[n]),
elemScore = element;
while (true) {
// Compute the indices of the child elements.
const child2N: i32 = (n + 1) * 2,
child1N: i32 = child2N - 1;
// This is used to store the new position of the element,
// if any.
let swap: i32 = -1;
let child1: T, child1Score: f32, child2: T, child2Score: f32;
// If the first child exists (is inside the array)...
if (child1N < length) {
// Look it up and compute its score.
child1 = unchecked(this.content[child1N]);
child1Score = child1;
// If the score is less than our element's, we need to swap.
if (child1Score < elemScore) swap = child1N;
}
// Do the same checks for the other child.
if (child2N < length) {
child2 = unchecked(this.content[child2N]);
child2Score = child2;
if (child2Score < (swap == -1 ? elemScore : child1Score)) {
swap = child2N;
}
}
// If the element needs to be moved, swap it, and continue.
if (swap != -1) {
unchecked((this.content[n] = unchecked(this.content[swap])));
unchecked((this.content[swap] = element));
n = swap;
}
// Otherwise, we are done.
else {
break;
}
}
}
}
let heapInstance: BinaryHeap<f32>;
export function init(): void {
heapInstance = new BinaryHeap();
}
export function push(v: f32): void {
heapInstance.push(v);
}
export function pop(): f32 {
return heapInstance.pop();
}
export function size(): u32 {
return heapInstance.size();
}
export function peek(): f32 {
return heapInstance.peek();
}
#include "emscripten.h"
#include "emscripten/bind.h"
#include <cstdint>
#include <optional>
#include <utility>
#include <vector>
using namespace emscripten;
class BinaryHeap {
public:
BinaryHeap() : data() {}
void push(float v) {
this->data.push_back(v);
this->bubble_up(this->data.size() - 1);
}
float peek() { return this->data[0]; }
float pop() {
float result = this->data[0];
float end = this->data.back();
this->data.pop_back();
if (this->data.size() > 1) {
this->data[0] = end;
this->sink_down(0);
}
return result;
}
uint32_t size() { return this->data.size(); }
private:
std::vector<float> data;
void bubble_up(uint32_t n) {
float element = this->data[n];
while (n > 0) {
uint32_t parent_n =
static_cast<uint32_t>(floor((static_cast<float>(n) + 1) / 2 - 1));
float parent = this->data[parent_n];
if (element < parent) {
std::swap(this->data[parent_n], this->data[n]);
n = parent_n;
} else {
break;
}
}
}
void sink_down(uint32_t n) {
auto length = this->data.size();
float element = this->data[n];
while (true) {
uint32_t child2_n = (n + 1) * 2;
uint32_t child1_n = child2_n - 1;
std::optional<uint32_t> swap = {};
float child1, child2;
if (child1_n < length) {
child1 = this->data[child1_n];
if (child1 < element) {
swap = std::optional<uint32_t>(child1_n);
}
}
if (child2_n < length) {
child2 = this->data[child2_n];
if (child2 < (swap.has_value() ? child1 : element)) {
swap = std::optional<uint32_t>(child2_n);
}
}
if (swap.has_value()) {
auto swap_n = swap.value();
std::swap(this->data[n], this->data[swap_n]);
n = swap_n;
} else {
break;
}
}
}
};
thread_local BinaryHeap instance;
void init() { instance = BinaryHeap(); }
void push(float v) { instance.push(v); }
float pop() { return instance.pop(); }
uint32_t size() { return instance.size(); }
float peek() { return instance.peek(); }
EMSCRIPTEN_BINDINGS(my_module) {
function("init", &init);
function("push", &push);
function("pop", &pop);
function("size", &size);
function("peek", &peek);
}
extern crate wee_alloc;
// Use `wee_alloc` as the global allocator.
#[global_allocator]
static ALLOC: wee_alloc::WeeAlloc = wee_alloc::WeeAlloc::INIT;
type Scorer<T> = fn(&T) -> f32;
struct BinaryHeap<T> {
data: Vec<T>,
scorer: Scorer<T>,
}
struct Item {
index: usize,
score: f32,
}
impl<T> BinaryHeap<T> {
fn new(scorer: Scorer<T>) -> BinaryHeap<T> {
BinaryHeap {
data: Vec::with_capacity(10),
scorer,
}
}
fn push(&mut self, v: T) {
self.data.push(v);
self.bubble_up(self.data.len() - 1);
}
fn peek(&self) -> Option<&T> {
self.data.get(0)
}
fn pop(&mut self) -> Option<T> {
if self.data.len() == 0 {
return None;
}
let result = self.data.swap_remove(0);
if self.data.len() > 0 {
self.sink_down(0);
}
Some(result)
}
fn size(&self) -> usize {
self.data.len()
}
fn get_item(&self, n: usize) -> Option<Item> {
let item = self.data.get(n)?;
let score = (self.scorer)(item);
Some(Item { index: n, score })
}
fn bubble_up(&mut self, n: usize) {
let mut element = self.get_item(n).unwrap();
while element.index > 0 {
// Compute the parent element's index, and fetch it.
let parent_n: usize = (((element.index as f32) - 1.0) / 2.0).floor() as usize;
let parent = self.get_item(parent_n).unwrap();
// Swap the elements if the parent is greater.
if element.score < parent.score {
self.data.swap(element.index, parent.index);
element.index = parent.index;
}
// Found a parent that is less, no need to move it further.
else {
break;
}
}
}
fn sink_down(&mut self, mut n: usize) {
// Look up the target element and its score.
let length = self.data.len();
let element = self.get_item(n).unwrap();
loop {
// Compute the indices of the child elements.
let child2_n = 2 * n + 1;
let child1_n = child2_n + 1;
// This is used to store the new position of the element,
// if any.
let mut swap: Option<Item> = None;
// If the first child exists (is inside the array)...
if child1_n < length {
// Look it up and compute its score.
let child1 = self.get_item(child1_n).unwrap();
// If the score is less than our element's, we need to swap.
if child1.score < element.score {
swap = Some(child1);
}
}
// Do the same checks for the other child.
if child2_n < length {
let child2 = self.get_item(child2_n).unwrap();
if child2.score
< swap
.as_ref()
.map(|item| item.score)
.unwrap_or(element.score)
{
swap = Some(child2);
}
}
// If the element needs to be moved, swap it, and continue.
if let Some(swap) = swap {
self.data.swap(n, swap.index);
n = swap.index
}
// Otherwise, we are done.
else {
break;
}
}
}
}
static mut INSTANCE: Option<BinaryHeap<f32>> = None;
pub fn init() {
unsafe {
INSTANCE = Some(BinaryHeap::new(|v: &f32| *v));
}
}
pub fn push(v: f32) {
unsafe { INSTANCE.as_mut() }.map(|i| i.push(v));
}
pub fn pop() -> f32 {
unsafe { INSTANCE.as_mut() }
.and_then(|i| i.pop())
.unwrap_or(-1.0)
}
pub fn size() -> usize {
unsafe { INSTANCE.as_mut() }.map(|i| i.size()).unwrap_or(0)
}
pub fn peek() -> f32 {
unsafe { INSTANCE.as_mut() }
.and_then(|i| i.peek())
.cloned()
.unwrap_or(-1.0)
}
var Module=typeof Module!=="undefined"?Module:{};var moduleOverrides={};var key;for(key in Module){if(Module.hasOwnProperty(key)){moduleOverrides[key]=Module[key]}}var arguments_=[];var thisProgram="./this.program";var quit_=function(status,toThrow){throw toThrow};var ENVIRONMENT_IS_WEB=false;var ENVIRONMENT_IS_WORKER=false;var ENVIRONMENT_IS_NODE=false;var ENVIRONMENT_IS_SHELL=false;ENVIRONMENT_IS_WEB=typeof window==="object";ENVIRONMENT_IS_WORKER=typeof importScripts==="function";ENVIRONMENT_IS_NODE=typeof process==="object"&&typeof process.versions==="object"&&typeof process.versions.node==="string";ENVIRONMENT_IS_SHELL=!ENVIRONMENT_IS_WEB&&!ENVIRONMENT_IS_NODE&&!ENVIRONMENT_IS_WORKER;var scriptDirectory="";function locateFile(path){if(Module["locateFile"]){return Module["locateFile"](path,scriptDirectory)}return scriptDirectory+path}var read_,readAsync,readBinary,setWindowTitle;var nodeFS;var nodePath;if(ENVIRONMENT_IS_NODE){if(ENVIRONMENT_IS_WORKER){scriptDirectory=require("path").dirname(scriptDirectory)+"/"}else{scriptDirectory=__dirname+"/"}read_=function shell_read(filename,binary){if(!nodeFS)nodeFS=require("fs");if(!nodePath)nodePath=require("path");filename=nodePath["normalize"](filename);return nodeFS["readFileSync"](filename,binary?null:"utf8")};readBinary=function readBinary(filename){var ret=read_(filename,true);if(!ret.buffer){ret=new Uint8Array(ret)}assert(ret.buffer);return ret};if(process["argv"].length>1){thisProgram=process["argv"][1].replace(/\\/g,"/")}arguments_=process["argv"].slice(2);if(typeof module!=="undefined"){module["exports"]=Module}process["on"]("uncaughtException",function(ex){if(!(ex instanceof ExitStatus)){throw ex}});process["on"]("unhandledRejection",abort);quit_=function(status){process["exit"](status)};Module["inspect"]=function(){return"[Emscripten Module object]"}}else if(ENVIRONMENT_IS_SHELL){if(typeof read!="undefined"){read_=function shell_read(f){return read(f)}}readBinary=function readBinary(f){var data;if(typeof readbuffer==="function"){return new Uint8Array(readbuffer(f))}data=read(f,"binary");assert(typeof data==="object");return data};if(typeof scriptArgs!="undefined"){arguments_=scriptArgs}else if(typeof arguments!="undefined"){arguments_=arguments}if(typeof quit==="function"){quit_=function(status){quit(status)}}if(typeof print!=="undefined"){if(typeof console==="undefined")console={};console.log=print;console.warn=console.error=typeof printErr!=="undefined"?printErr:print}}else if(ENVIRONMENT_IS_WEB||ENVIRONMENT_IS_WORKER){if(ENVIRONMENT_IS_WORKER){scriptDirectory=self.location.href}else if(typeof document!=="undefined"&&document.currentScript){scriptDirectory=document.currentScript.src}if(scriptDirectory.indexOf("blob:")!==0){scriptDirectory=scriptDirectory.substr(0,scriptDirectory.lastIndexOf("/")+1)}else{scriptDirectory=""}{read_=function(url){var xhr=new XMLHttpRequest;xhr.open("GET",url,false);xhr.send(null);return xhr.responseText};if(ENVIRONMENT_IS_WORKER){readBinary=function(url){var xhr=new XMLHttpRequest;xhr.open("GET",url,false);xhr.responseType="arraybuffer";xhr.send(null);return new Uint8Array(xhr.response)}}readAsync=function(url,onload,onerror){var xhr=new XMLHttpRequest;xhr.open("GET",url,true);xhr.responseType="arraybuffer";xhr.onload=function(){if(xhr.status==200||xhr.status==0&&xhr.response){onload(xhr.response);return}onerror()};xhr.onerror=onerror;xhr.send(null)}}setWindowTitle=function(title){document.title=title}}else{}var out=Module["print"]||console.log.bind(console);var err=Module["printErr"]||console.warn.bind(console);for(key in moduleOverrides){if(moduleOverrides.hasOwnProperty(key)){Module[key]=moduleOverrides[key]}}moduleOverrides=null;if(Module["arguments"])arguments_=Module["arguments"];if(Module["thisProgram"])thisProgram=Module["thisProgram"];if(Module["quit"])quit_=Module["quit"];var wasmBinary;if(Module["wasmBinary"])wasmBinary=Module["wasmBinary"];var noExitRuntime=Module["noExitRuntime"]||true;if(typeof WebAssembly!=="object"){abort("no native wasm support detected")}var wasmMemory;var ABORT=false;var EXITSTATUS;function assert(condition,text){if(!condition){abort("Assertion failed: "+text)}}var UTF8Decoder=typeof TextDecoder!=="undefined"?new TextDecoder("utf8"):undefined;function UTF8ArrayToString(heap,idx,maxBytesToRead){var endIdx=idx+maxBytesToRead;var endPtr=idx;while(heap[endPtr]&&!(endPtr>=endIdx))++endPtr;if(endPtr-idx>16&&heap.subarray&&UTF8Decoder){return UTF8Decoder.decode(heap.subarray(idx,endPtr))}else{var str="";while(idx<endPtr){var u0=heap[idx++];if(!(u0&128)){str+=String.fromCharCode(u0);continue}var u1=heap[idx++]&63;if((u0&224)==192){str+=String.fromCharCode((u0&31)<<6|u1);continue}var u2=heap[idx++]&63;if((u0&240)==224){u0=(u0&15)<<12|u1<<6|u2}else{u0=(u0&7)<<18|u1<<12|u2<<6|heap[idx++]&63}if(u0<65536){str+=String.fromCharCode(u0)}else{var ch=u0-65536;str+=String.fromCharCode(55296|ch>>10,56320|ch&1023)}}}return str}function UTF8ToString(ptr,maxBytesToRead){return ptr?UTF8ArrayToString(HEAPU8,ptr,maxBytesToRead):""}function stringToUTF8Array(str,heap,outIdx,maxBytesToWrite){if(!(maxBytesToWrite>0))return 0;var startIdx=outIdx;var endIdx=outIdx+maxBytesToWrite-1;for(var i=0;i<str.length;++i){var u=str.charCodeAt(i);if(u>=55296&&u<=57343){var u1=str.charCodeAt(++i);u=65536+((u&1023)<<10)|u1&1023}if(u<=127){if(outIdx>=endIdx)break;heap[outIdx++]=u}else if(u<=2047){if(outIdx+1>=endIdx)break;heap[outIdx++]=192|u>>6;heap[outIdx++]=128|u&63}else if(u<=65535){if(outIdx+2>=endIdx)break;heap[outIdx++]=224|u>>12;heap[outIdx++]=128|u>>6&63;heap[outIdx++]=128|u&63}else{if(outIdx+3>=endIdx)break;heap[outIdx++]=240|u>>18;heap[outIdx++]=128|u>>12&63;heap[outIdx++]=128|u>>6&63;heap[outIdx++]=128|u&63}}heap[outIdx]=0;return outIdx-startIdx}function stringToUTF8(str,outPtr,maxBytesToWrite){return stringToUTF8Array(str,HEAPU8,outPtr,maxBytesToWrite)}function lengthBytesUTF8(str){var len=0;for(var i=0;i<str.length;++i){var u=str.charCodeAt(i);if(u>=55296&&u<=57343)u=65536+((u&1023)<<10)|str.charCodeAt(++i)&1023;if(u<=127)++len;else if(u<=2047)len+=2;else if(u<=65535)len+=3;else len+=4}return len}var UTF16Decoder=typeof TextDecoder!=="undefined"?new TextDecoder("utf-16le"):undefined;function UTF16ToString(ptr,maxBytesToRead){var endPtr=ptr;var idx=endPtr>>1;var maxIdx=idx+maxBytesToRead/2;while(!(idx>=maxIdx)&&HEAPU16[idx])++idx;endPtr=idx<<1;if(endPtr-ptr>32&&UTF16Decoder){return UTF16Decoder.decode(HEAPU8.subarray(ptr,endPtr))}else{var str="";for(var i=0;!(i>=maxBytesToRead/2);++i){var codeUnit=HEAP16[ptr+i*2>>1];if(codeUnit==0)break;str+=String.fromCharCode(codeUnit)}return str}}function stringToUTF16(str,outPtr,maxBytesToWrite){if(maxBytesToWrite===undefined){maxBytesToWrite=2147483647}if(maxBytesToWrite<2)return 0;maxBytesToWrite-=2;var startPtr=outPtr;var numCharsToWrite=maxBytesToWrite<str.length*2?maxBytesToWrite/2:str.length;for(var i=0;i<numCharsToWrite;++i){var codeUnit=str.charCodeAt(i);HEAP16[outPtr>>1]=codeUnit;outPtr+=2}HEAP16[outPtr>>1]=0;return outPtr-startPtr}function lengthBytesUTF16(str){return str.length*2}function UTF32ToString(ptr,maxBytesToRead){var i=0;var str="";while(!(i>=maxBytesToRead/4)){var utf32=HEAP32[ptr+i*4>>2];if(utf32==0)break;++i;if(utf32>=65536){var ch=utf32-65536;str+=String.fromCharCode(55296|ch>>10,56320|ch&1023)}else{str+=String.fromCharCode(utf32)}}return str}function stringToUTF32(str,outPtr,maxBytesToWrite){if(maxBytesToWrite===undefined){maxBytesToWrite=2147483647}if(maxBytesToWrite<4)return 0;var startPtr=outPtr;var endPtr=startPtr+maxBytesToWrite-4;for(var i=0;i<str.length;++i){var codeUnit=str.charCodeAt(i);if(codeUnit>=55296&&codeUnit<=57343){var trailSurrogate=str.charCodeAt(++i);codeUnit=65536+((codeUnit&1023)<<10)|trailSurrogate&1023}HEAP32[outPtr>>2]=codeUnit;outPtr+=4;if(outPtr+4>endPtr)break}HEAP32[outPtr>>2]=0;return outPtr-startPtr}function lengthBytesUTF32(str){var len=0;for(var i=0;i<str.length;++i){var codeUnit=str.charCodeAt(i);if(codeUnit>=55296&&codeUnit<=57343)++i;len+=4}return len}var buffer,HEAP8,HEAPU8,HEAP16,HEAPU16,HEAP32,HEAPU32,HEAPF32,HEAPF64;function updateGlobalBufferAndViews(buf){buffer=buf;Module["HEAP8"]=HEAP8=new Int8Array(buf);Module["HEAP16"]=HEAP16=new Int16Array(buf);Module["HEAP32"]=HEAP32=new Int32Array(buf);Module["HEAPU8"]=HEAPU8=new Uint8Array(buf);Module["HEAPU16"]=HEAPU16=new Uint16Array(buf);Module["HEAPU32"]=HEAPU32=new Uint32Array(buf);Module["HEAPF32"]=HEAPF32=new Float32Array(buf);Module["HEAPF64"]=HEAPF64=new Float64Array(buf)}var INITIAL_MEMORY=Module["INITIAL_MEMORY"]||16777216;var wasmTable;var __ATPRERUN__=[];var __ATINIT__=[];var __ATMAIN__=[];var __ATPOSTRUN__=[];var runtimeInitialized=false;function preRun(){if(Module["preRun"]){if(typeof Module["preRun"]=="function")Module["preRun"]=[Module["preRun"]];while(Module["preRun"].length){addOnPreRun(Module["preRun"].shift())}}callRuntimeCallbacks(__ATPRERUN__)}function initRuntime(){runtimeInitialized=true;callRuntimeCallbacks(__ATINIT__)}function preMain(){callRuntimeCallbacks(__ATMAIN__)}function postRun(){if(Module["postRun"]){if(typeof Module["postRun"]=="function")Module["postRun"]=[Module["postRun"]];while(Module["postRun"].length){addOnPostRun(Module["postRun"].shift())}}callRuntimeCallbacks(__ATPOSTRUN__)}function addOnPreRun(cb){__ATPRERUN__.unshift(cb)}function addOnInit(cb){__ATINIT__.unshift(cb)}function addOnPostRun(cb){__ATPOSTRUN__.unshift(cb)}var runDependencies=0;var runDependencyWatcher=null;var dependenciesFulfilled=null;function addRunDependency(id){runDependencies++;if(Module["monitorRunDependencies"]){Module["monitorRunDependencies"](runDependencies)}}function removeRunDependency(id){runDependencies--;if(Module["monitorRunDependencies"]){Module["monitorRunDependencies"](runDependencies)}if(runDependencies==0){if(runDependencyWatcher!==null){clearInterval(runDependencyWatcher);runDependencyWatcher=null}if(dependenciesFulfilled){var callback=dependenciesFulfilled;dependenciesFulfilled=null;callback()}}}Module["preloadedImages"]={};Module["preloadedAudios"]={};function abort(what){if(Module["onAbort"]){Module["onAbort"](what)}what+="";err(what);ABORT=true;EXITSTATUS=1;what="abort("+what+"). Build with -s ASSERTIONS=1 for more info.";var e=new WebAssembly.RuntimeError(what);throw e}function hasPrefix(str,prefix){return String.prototype.startsWith?str.startsWith(prefix):str.indexOf(prefix)===0}var dataURIPrefix="data:application/octet-stream;base64,";function isDataURI(filename){return hasPrefix(filename,dataURIPrefix)}var fileURIPrefix="file://";function isFileURI(filename){return hasPrefix(filename,fileURIPrefix)}var wasmBinaryFile="binaryheap_idiomatic_cpp.wasm";if(!isDataURI(wasmBinaryFile)){wasmBinaryFile=locateFile(wasmBinaryFile)}function getBinary(file){try{if(file==wasmBinaryFile&&wasmBinary){return new Uint8Array(wasmBinary)}if(readBinary){return readBinary(file)}else{throw"both async and sync fetching of the wasm failed"}}catch(err){abort(err)}}function getBinaryPromise(){if(!wasmBinary&&(ENVIRONMENT_IS_WEB||ENVIRONMENT_IS_WORKER)){if(typeof fetch==="function"&&!isFileURI(wasmBinaryFile)){return fetch(wasmBinaryFile,{credentials:"same-origin"}).then(function(response){if(!response["ok"]){throw"failed to load wasm binary file at '"+wasmBinaryFile+"'"}return response["arrayBuffer"]()}).catch(function(){return getBinary(wasmBinaryFile)})}else{if(readAsync){return new Promise(function(resolve,reject){readAsync(wasmBinaryFile,function(response){resolve(new Uint8Array(response))},reject)})}}}return Promise.resolve().then(function(){return getBinary(wasmBinaryFile)})}function createWasm(){var info={"a":asmLibraryArg};function receiveInstance(instance,module){var exports=instance.exports;Module["asm"]=exports;wasmMemory=Module["asm"]["p"];updateGlobalBufferAndViews(wasmMemory.buffer);wasmTable=Module["asm"]["r"];addOnInit(Module["asm"]["q"]);removeRunDependency("wasm-instantiate")}addRunDependency("wasm-instantiate");function receiveInstantiatedSource(output){receiveInstance(output["instance"])}function instantiateArrayBuffer(receiver){return getBinaryPromise().then(function(binary){var result=WebAssembly.instantiate(binary,info);return result}).then(receiver,function(reason){err("failed to asynchronously prepare wasm: "+reason);abort(reason)})}function instantiateAsync(){if(!wasmBinary&&typeof WebAssembly.instantiateStreaming==="function"&&!isDataURI(wasmBinaryFile)&&!isFileURI(wasmBinaryFile)&&typeof fetch==="function"){return fetch(wasmBinaryFile,{credentials:"same-origin"}).then(function(response){var result=WebAssembly.instantiateStreaming(response,info);return result.then(receiveInstantiatedSource,function(reason){err("wasm streaming compile failed: "+reason);err("falling back to ArrayBuffer instantiation");return instantiateArrayBuffer(receiveInstantiatedSource)})})}else{return instantiateArrayBuffer(receiveInstantiatedSource)}}if(Module["instantiateWasm"]){try{var exports=Module["instantiateWasm"](info,receiveInstance);return exports}catch(e){err("Module.instantiateWasm callback failed with error: "+e);return false}}instantiateAsync();return{}}function callRuntimeCallbacks(callbacks){while(callbacks.length>0){var callback=callbacks.shift();if(typeof callback=="function"){callback(Module);continue}var func=callback.func;if(typeof func==="number"){if(callback.arg===undefined){wasmTable.get(func)()}else{wasmTable.get(func)(callback.arg)}}else{func(callback.arg===undefined?null:callback.arg)}}}var ExceptionInfoAttrs={DESTRUCTOR_OFFSET:0,REFCOUNT_OFFSET:4,TYPE_OFFSET:8,CAUGHT_OFFSET:12,RETHROWN_OFFSET:13,SIZE:16};function ___cxa_allocate_exception(size){return _malloc(size+ExceptionInfoAttrs.SIZE)+ExceptionInfoAttrs.SIZE}function _atexit(func,arg){}function ___cxa_thread_atexit(a0,a1){return _atexit(a0,a1)}function ExceptionInfo(excPtr){this.excPtr=excPtr;this.ptr=excPtr-ExceptionInfoAttrs.SIZE;this.set_type=function(type){HEAP32[this.ptr+ExceptionInfoAttrs.TYPE_OFFSET>>2]=type};this.get_type=function(){return HEAP32[this.ptr+ExceptionInfoAttrs.TYPE_OFFSET>>2]};this.set_destructor=function(destructor){HEAP32[this.ptr+ExceptionInfoAttrs.DESTRUCTOR_OFFSET>>2]=destructor};this.get_destructor=function(){return HEAP32[this.ptr+ExceptionInfoAttrs.DESTRUCTOR_OFFSET>>2]};this.set_refcount=function(refcount){HEAP32[this.ptr+ExceptionInfoAttrs.REFCOUNT_OFFSET>>2]=refcount};this.set_caught=function(caught){caught=caught?1:0;HEAP8[this.ptr+ExceptionInfoAttrs.CAUGHT_OFFSET>>0]=caught};this.get_caught=function(){return HEAP8[this.ptr+ExceptionInfoAttrs.CAUGHT_OFFSET>>0]!=0};this.set_rethrown=function(rethrown){rethrown=rethrown?1:0;HEAP8[this.ptr+ExceptionInfoAttrs.RETHROWN_OFFSET>>0]=rethrown};this.get_rethrown=function(){return HEAP8[this.ptr+ExceptionInfoAttrs.RETHROWN_OFFSET>>0]!=0};this.init=function(type,destructor){this.set_type(type);this.set_destructor(destructor);this.set_refcount(0);this.set_caught(false);this.set_rethrown(false)};this.add_ref=function(){var value=HEAP32[this.ptr+ExceptionInfoAttrs.REFCOUNT_OFFSET>>2];HEAP32[this.ptr+ExceptionInfoAttrs.REFCOUNT_OFFSET>>2]=value+1};this.release_ref=function(){var prev=HEAP32[this.ptr+ExceptionInfoAttrs.REFCOUNT_OFFSET>>2];HEAP32[this.ptr+ExceptionInfoAttrs.REFCOUNT_OFFSET>>2]=prev-1;return prev===1}}var exceptionLast=0;var uncaughtExceptionCount=0;function ___cxa_throw(ptr,type,destructor){var info=new ExceptionInfo(ptr);info.init(type,destructor);exceptionLast=ptr;uncaughtExceptionCount++;throw ptr}function getShiftFromSize(size){switch(size){case 1:return 0;case 2:return 1;case 4:return 2;case 8:return 3;default:throw new TypeError("Unknown type size: "+size)}}function embind_init_charCodes(){var codes=new Array(256);for(var i=0;i<256;++i){codes[i]=String.fromCharCode(i)}embind_charCodes=codes}var embind_charCodes=undefined;function readLatin1String(ptr){var ret="";var c=ptr;while(HEAPU8[c]){ret+=embind_charCodes[HEAPU8[c++]]}return ret}var awaitingDependencies={};var registeredTypes={};var typeDependencies={};var char_0=48;var char_9=57;function makeLegalFunctionName(name){if(undefined===name){return"_unknown"}name=name.replace(/[^a-zA-Z0-9_]/g,"$");var f=name.charCodeAt(0);if(f>=char_0&&f<=char_9){return"_"+name}else{return name}}function createNamedFunction(name,body){name=makeLegalFunctionName(name);return new Function("body","return function "+name+"() {\n"+' "use strict";'+" return body.apply(this, arguments);\n"+"};\n")(body)}function extendError(baseErrorType,errorName){var errorClass=createNamedFunction(errorName,function(message){this.name=errorName;this.message=message;var stack=new Error(message).stack;if(stack!==undefined){this.stack=this.toString()+"\n"+stack.replace(/^Error(:[^\n]*)?\n/,"")}});errorClass.prototype=Object.create(baseErrorType.prototype);errorClass.prototype.constructor=errorClass;errorClass.prototype.toString=function(){if(this.message===undefined){return this.name}else{return this.name+": "+this.message}};return errorClass}var BindingError=undefined;function throwBindingError(message){throw new BindingError(message)}var InternalError=undefined;function throwInternalError(message){throw new InternalError(message)}function whenDependentTypesAreResolved(myTypes,dependentTypes,getTypeConverters){myTypes.forEach(function(type){typeDependencies[type]=dependentTypes});function onComplete(typeConverters){var myTypeConverters=getTypeConverters(typeConverters);if(myTypeConverters.length!==myTypes.length){throwInternalError("Mismatched type converter count")}for(var i=0;i<myTypes.length;++i){registerType(myTypes[i],myTypeConverters[i])}}var typeConverters=new Array(dependentTypes.length);var unregisteredTypes=[];var registered=0;dependentTypes.forEach(function(dt,i){if(registeredTypes.hasOwnProperty(dt)){typeConverters[i]=registeredTypes[dt]}else{unregisteredTypes.push(dt);if(!awaitingDependencies.hasOwnProperty(dt)){awaitingDependencies[dt]=[]}awaitingDependencies[dt].push(function(){typeConverters[i]=registeredTypes[dt];++registered;if(registered===unregisteredTypes.length){onComplete(typeConverters)}})}});if(0===unregisteredTypes.length){onComplete(typeConverters)}}function registerType(rawType,registeredInstance,options){options=options||{};if(!("argPackAdvance"in registeredInstance)){throw new TypeError("registerType registeredInstance requires argPackAdvance")}var name=registeredInstance.name;if(!rawType){throwBindingError('type "'+name+'" must have a positive integer typeid pointer')}if(registeredTypes.hasOwnProperty(rawType)){if(options.ignoreDuplicateRegistrations){return}else{throwBindingError("Cannot register type '"+name+"' twice")}}registeredTypes[rawType]=registeredInstance;delete typeDependencies[rawType];if(awaitingDependencies.hasOwnProperty(rawType)){var callbacks=awaitingDependencies[rawType];delete awaitingDependencies[rawType];callbacks.forEach(function(cb){cb()})}}function __embind_register_bool(rawType,name,size,trueValue,falseValue){var shift=getShiftFromSize(size);name=readLatin1String(name);registerType(rawType,{name:name,"fromWireType":function(wt){return!!wt},"toWireType":function(destructors,o){return o?trueValue:falseValue},"argPackAdvance":8,"readValueFromPointer":function(pointer){var heap;if(size===1){heap=HEAP8}else if(size===2){heap=HEAP16}else if(size===4){heap=HEAP32}else{throw new TypeError("Unknown boolean type size: "+name)}return this["fromWireType"](heap[pointer>>shift])},destructorFunction:null})}var emval_free_list=[];var emval_handle_array=[{},{value:undefined},{value:null},{value:true},{value:false}];function __emval_decref(handle){if(handle>4&&0===--emval_handle_array[handle].refcount){emval_handle_array[handle]=undefined;emval_free_list.push(handle)}}function count_emval_handles(){var count=0;for(var i=5;i<emval_handle_array.length;++i){if(emval_handle_array[i]!==undefined){++count}}return count}function get_first_emval(){for(var i=5;i<emval_handle_array.length;++i){if(emval_handle_array[i]!==undefined){return emval_handle_array[i]}}return null}function init_emval(){Module["count_emval_handles"]=count_emval_handles;Module["get_first_emval"]=get_first_emval}function __emval_register(value){switch(value){case undefined:{return 1}case null:{return 2}case true:{return 3}case false:{return 4}default:{var handle=emval_free_list.length?emval_free_list.pop():emval_handle_array.length;emval_handle_array[handle]={refcount:1,value:value};return handle}}}function simpleReadValueFromPointer(pointer){return this["fromWireType"](HEAPU32[pointer>>2])}function __embind_register_emval(rawType,name){name=readLatin1String(name);registerType(rawType,{name:name,"fromWireType":function(handle){var rv=emval_handle_array[handle].value;__emval_decref(handle);return rv},"toWireType":function(destructors,value){return __emval_register(value)},"argPackAdvance":8,"readValueFromPointer":simpleReadValueFromPointer,destructorFunction:null})}function _embind_repr(v){if(v===null){return"null"}var t=typeof v;if(t==="object"||t==="array"||t==="function"){return v.toString()}else{return""+v}}function floatReadValueFromPointer(name,shift){switch(shift){case 2:return function(pointer){return this["fromWireType"](HEAPF32[pointer>>2])};case 3:return function(pointer){return this["fromWireType"](HEAPF64[pointer>>3])};default:throw new TypeError("Unknown float type: "+name)}}function __embind_register_float(rawType,name,size){var shift=getShiftFromSize(size);name=readLatin1String(name);registerType(rawType,{name:name,"fromWireType":function(value){return value},"toWireType":function(destructors,value){if(typeof value!=="number"&&typeof value!=="boolean"){throw new TypeError('Cannot convert "'+_embind_repr(value)+'" to '+this.name)}return value},"argPackAdvance":8,"readValueFromPointer":floatReadValueFromPointer(name,shift),destructorFunction:null})}function new_(constructor,argumentList){if(!(constructor instanceof Function)){throw new TypeError("new_ called with constructor type "+typeof constructor+" which is not a function")}var dummy=createNamedFunction(constructor.name||"unknownFunctionName",function(){});dummy.prototype=constructor.prototype;var obj=new dummy;var r=constructor.apply(obj,argumentList);return r instanceof Object?r:obj}function runDestructors(destructors){while(destructors.length){var ptr=destructors.pop();var del=destructors.pop();del(ptr)}}function craftInvokerFunction(humanName,argTypes,classType,cppInvokerFunc,cppTargetFunc){var argCount=argTypes.length;if(argCount<2){throwBindingError("argTypes array size mismatch! Must at least get return value and 'this' types!")}var isClassMethodFunc=argTypes[1]!==null&&classType!==null;var needsDestructorStack=false;for(var i=1;i<argTypes.length;++i){if(argTypes[i]!==null&&argTypes[i].destructorFunction===undefined){needsDestructorStack=true;break}}var returns=argTypes[0].name!=="void";var argsList="";var argsListWired="";for(var i=0;i<argCount-2;++i){argsList+=(i!==0?", ":"")+"arg"+i;argsListWired+=(i!==0?", ":"")+"arg"+i+"Wired"}var invokerFnBody="return function "+makeLegalFunctionName(humanName)+"("+argsList+") {\n"+"if (arguments.length !== "+(argCount-2)+") {\n"+"throwBindingError('function "+humanName+" called with ' + arguments.length + ' arguments, expected "+(argCount-2)+" args!');\n"+"}\n";if(needsDestructorStack){invokerFnBody+="var destructors = [];\n"}var dtorStack=needsDestructorStack?"destructors":"null";var args1=["throwBindingError","invoker","fn","runDestructors","retType","classParam"];var args2=[throwBindingError,cppInvokerFunc,cppTargetFunc,runDestructors,argTypes[0],argTypes[1]];if(isClassMethodFunc){invokerFnBody+="var thisWired = classParam.toWireType("+dtorStack+", this);\n"}for(var i=0;i<argCount-2;++i){invokerFnBody+="var arg"+i+"Wired = argType"+i+".toWireType("+dtorStack+", arg"+i+"); // "+argTypes[i+2].name+"\n";args1.push("argType"+i);args2.push(argTypes[i+2])}if(isClassMethodFunc){argsListWired="thisWired"+(argsListWired.length>0?", ":"")+argsListWired}invokerFnBody+=(returns?"var rv = ":"")+"invoker(fn"+(argsListWired.length>0?", ":"")+argsListWired+");\n";if(needsDestructorStack){invokerFnBody+="runDestructors(destructors);\n"}else{for(var i=isClassMethodFunc?1:2;i<argTypes.length;++i){var paramName=i===1?"thisWired":"arg"+(i-2)+"Wired";if(argTypes[i].destructorFunction!==null){invokerFnBody+=paramName+"_dtor("+paramName+"); // "+argTypes[i].name+"\n";args1.push(paramName+"_dtor");args2.push(argTypes[i].destructorFunction)}}}if(returns){invokerFnBody+="var ret = retType.fromWireType(rv);\n"+"return ret;\n"}else{}invokerFnBody+="}\n";args1.push(invokerFnBody);var invokerFunction=new_(Function,args1).apply(null,args2);return invokerFunction}function ensureOverloadTable(proto,methodName,humanName){if(undefined===proto[methodName].overloadTable){var prevFunc=proto[methodName];proto[methodName]=function(){if(!proto[methodName].overloadTable.hasOwnProperty(arguments.length)){throwBindingError("Function '"+humanName+"' called with an invalid number of arguments ("+arguments.length+") - expects one of ("+proto[methodName].overloadTable+")!")}return proto[methodName].overloadTable[arguments.length].apply(this,arguments)};proto[methodName].overloadTable=[];proto[methodName].overloadTable[prevFunc.argCount]=prevFunc}}function exposePublicSymbol(name,value,numArguments){if(Module.hasOwnProperty(name)){if(undefined===numArguments||undefined!==Module[name].overloadTable&&undefined!==Module[name].overloadTable[numArguments]){throwBindingError("Cannot register public name '"+name+"' twice")}ensureOverloadTable(Module,name,name);if(Module.hasOwnProperty(numArguments)){throwBindingError("Cannot register multiple overloads of a function with the same number of arguments ("+numArguments+")!")}Module[name].overloadTable[numArguments]=value}else{Module[name]=value;if(undefined!==numArguments){Module[name].numArguments=numArguments}}}function heap32VectorToArray(count,firstElement){var array=[];for(var i=0;i<count;i++){array.push(HEAP32[(firstElement>>2)+i])}return array}function replacePublicSymbol(name,value,numArguments){if(!Module.hasOwnProperty(name)){throwInternalError("Replacing nonexistant public symbol")}if(undefined!==Module[name].overloadTable&&undefined!==numArguments){Module[name].overloadTable[numArguments]=value}else{Module[name]=value;Module[name].argCount=numArguments}}function dynCallLegacy(sig,ptr,args){var f=Module["dynCall_"+sig];return args&&args.length?f.apply(null,[ptr].concat(args)):f.call(null,ptr)}function dynCall(sig,ptr,args){if(sig.indexOf("j")!=-1){return dynCallLegacy(sig,ptr,args)}return wasmTable.get(ptr).apply(null,args)}function getDynCaller(sig,ptr){var argCache=[];return function(){argCache.length=arguments.length;for(var i=0;i<arguments.length;i++){argCache[i]=arguments[i]}return dynCall(sig,ptr,argCache)}}function embind__requireFunction(signature,rawFunction){signature=readLatin1String(signature);function makeDynCaller(){if(signature.indexOf("j")!=-1){return getDynCaller(signature,rawFunction)}return wasmTable.get(rawFunction)}var fp=makeDynCaller();if(typeof fp!=="function"){throwBindingError("unknown function pointer with signature "+signature+": "+rawFunction)}return fp}var UnboundTypeError=undefined;function getTypeName(type){var ptr=___getTypeName(type);var rv=readLatin1String(ptr);_free(ptr);return rv}function throwUnboundTypeError(message,types){var unboundTypes=[];var seen={};function visit(type){if(seen[type]){return}if(registeredTypes[type]){return}if(typeDependencies[type]){typeDependencies[type].forEach(visit);return}unboundTypes.push(type);seen[type]=true}types.forEach(visit);throw new UnboundTypeError(message+": "+unboundTypes.map(getTypeName).join([", "]))}function __embind_register_function(name,argCount,rawArgTypesAddr,signature,rawInvoker,fn){var argTypes=heap32VectorToArray(argCount,rawArgTypesAddr);name=readLatin1String(name);rawInvoker=embind__requireFunction(signature,rawInvoker);exposePublicSymbol(name,function(){throwUnboundTypeError("Cannot call "+name+" due to unbound types",argTypes)},argCount-1);whenDependentTypesAreResolved([],argTypes,function(argTypes){var invokerArgsArray=[argTypes[0],null].concat(argTypes.slice(1));replacePublicSymbol(name,craftInvokerFunction(name,invokerArgsArray,null,rawInvoker,fn),argCount-1);return[]})}function integerReadValueFromPointer(name,shift,signed){switch(shift){case 0:return signed?function readS8FromPointer(pointer){return HEAP8[pointer]}:function readU8FromPointer(pointer){return HEAPU8[pointer]};case 1:return signed?function readS16FromPointer(pointer){return HEAP16[pointer>>1]}:function readU16FromPointer(pointer){return HEAPU16[pointer>>1]};case 2:return signed?function readS32FromPointer(pointer){return HEAP32[pointer>>2]}:function readU32FromPointer(pointer){return HEAPU32[pointer>>2]};default:throw new TypeError("Unknown integer type: "+name)}}function __embind_register_integer(primitiveType,name,size,minRange,maxRange){name=readLatin1String(name);if(maxRange===-1){maxRange=4294967295}var shift=getShiftFromSize(size);var fromWireType=function(value){return value};if(minRange===0){var bitshift=32-8*size;fromWireType=function(value){return value<<bitshift>>>bitshift}}var isUnsignedType=name.indexOf("unsigned")!=-1;registerType(primitiveType,{name:name,"fromWireType":fromWireType,"toWireType":function(destructors,value){if(typeof value!=="number"&&typeof value!=="boolean"){throw new TypeError('Cannot convert "'+_embind_repr(value)+'" to '+this.name)}if(value<minRange||value>maxRange){throw new TypeError('Passing a number "'+_embind_repr(value)+'" from JS side to C/C++ side to an argument of type "'+name+'", which is outside the valid range ['+minRange+", "+maxRange+"]!")}return isUnsignedType?value>>>0:value|0},"argPackAdvance":8,"readValueFromPointer":integerReadValueFromPointer(name,shift,minRange!==0),destructorFunction:null})}function __embind_register_memory_view(rawType,dataTypeIndex,name){var typeMapping=[Int8Array,Uint8Array,Int16Array,Uint16Array,Int32Array,Uint32Array,Float32Array,Float64Array];var TA=typeMapping[dataTypeIndex];function decodeMemoryView(handle){handle=handle>>2;var heap=HEAPU32;var size=heap[handle];var data=heap[handle+1];return new TA(buffer,data,size)}name=readLatin1String(name);registerType(rawType,{name:name,"fromWireType":decodeMemoryView,"argPackAdvance":8,"readValueFromPointer":decodeMemoryView},{ignoreDuplicateRegistrations:true})}function __embind_register_std_string(rawType,name){name=readLatin1String(name);var stdStringIsUTF8=name==="std::string";registerType(rawType,{name:name,"fromWireType":function(value){var length=HEAPU32[value>>2];var str;if(stdStringIsUTF8){var decodeStartPtr=value+4;for(var i=0;i<=length;++i){var currentBytePtr=value+4+i;if(i==length||HEAPU8[currentBytePtr]==0){var maxRead=currentBytePtr-decodeStartPtr;var stringSegment=UTF8ToString(decodeStartPtr,maxRead);if(str===undefined){str=stringSegment}else{str+=String.fromCharCode(0);str+=stringSegment}decodeStartPtr=currentBytePtr+1}}}else{var a=new Array(length);for(var i=0;i<length;++i){a[i]=String.fromCharCode(HEAPU8[value+4+i])}str=a.join("")}_free(value);return str},"toWireType":function(destructors,value){if(value instanceof ArrayBuffer){value=new Uint8Array(value)}var getLength;var valueIsOfTypeString=typeof value==="string";if(!(valueIsOfTypeString||value instanceof Uint8Array||value instanceof Uint8ClampedArray||value instanceof Int8Array)){throwBindingError("Cannot pass non-string to std::string")}if(stdStringIsUTF8&&valueIsOfTypeString){getLength=function(){return lengthBytesUTF8(value)}}else{getLength=function(){return value.length}}var length=getLength();var ptr=_malloc(4+length+1);HEAPU32[ptr>>2]=length;if(stdStringIsUTF8&&valueIsOfTypeString){stringToUTF8(value,ptr+4,length+1)}else{if(valueIsOfTypeString){for(var i=0;i<length;++i){var charCode=value.charCodeAt(i);if(charCode>255){_free(ptr);throwBindingError("String has UTF-16 code units that do not fit in 8 bits")}HEAPU8[ptr+4+i]=charCode}}else{for(var i=0;i<length;++i){HEAPU8[ptr+4+i]=value[i]}}}if(destructors!==null){destructors.push(_free,ptr)}return ptr},"argPackAdvance":8,"readValueFromPointer":simpleReadValueFromPointer,destructorFunction:function(ptr){_free(ptr)}})}function __embind_register_std_wstring(rawType,charSize,name){name=readLatin1String(name);var decodeString,encodeString,getHeap,lengthBytesUTF,shift;if(charSize===2){decodeString=UTF16ToString;encodeString=stringToUTF16;lengthBytesUTF=lengthBytesUTF16;getHeap=function(){return HEAPU16};shift=1}else if(charSize===4){decodeString=UTF32ToString;encodeString=stringToUTF32;lengthBytesUTF=lengthBytesUTF32;getHeap=function(){return HEAPU32};shift=2}registerType(rawType,{name:name,"fromWireType":function(value){var length=HEAPU32[value>>2];var HEAP=getHeap();var str;var decodeStartPtr=value+4;for(var i=0;i<=length;++i){var currentBytePtr=value+4+i*charSize;if(i==length||HEAP[currentBytePtr>>shift]==0){var maxReadBytes=currentBytePtr-decodeStartPtr;var stringSegment=decodeString(decodeStartPtr,maxReadBytes);if(str===undefined){str=stringSegment}else{str+=String.fromCharCode(0);str+=stringSegment}decodeStartPtr=currentBytePtr+charSize}}_free(value);return str},"toWireType":function(destructors,value){if(!(typeof value==="string")){throwBindingError("Cannot pass non-string to C++ string type "+name)}var length=lengthBytesUTF(value);var ptr=_malloc(4+length+charSize);HEAPU32[ptr>>2]=length>>shift;encodeString(value,ptr+4,length+charSize);if(destructors!==null){destructors.push(_free,ptr)}return ptr},"argPackAdvance":8,"readValueFromPointer":simpleReadValueFromPointer,destructorFunction:function(ptr){_free(ptr)}})}function __embind_register_void(rawType,name){name=readLatin1String(name);registerType(rawType,{isVoid:true,name:name,"argPackAdvance":0,"fromWireType":function(){return undefined},"toWireType":function(destructors,o){return undefined}})}function _abort(){abort()}function _emscripten_memcpy_big(dest,src,num){HEAPU8.copyWithin(dest,src,src+num)}function abortOnCannotGrowMemory(requestedSize){abort("OOM")}function _emscripten_resize_heap(requestedSize){var oldSize=HEAPU8.length;abortOnCannotGrowMemory(requestedSize)}embind_init_charCodes();BindingError=Module["BindingError"]=extendError(Error,"BindingError");InternalError=Module["InternalError"]=extendError(Error,"InternalError");init_emval();UnboundTypeError=Module["UnboundTypeError"]=extendError(Error,"UnboundTypeError");var asmLibraryArg={"l":___cxa_allocate_exception,"d":___cxa_thread_atexit,"k":___cxa_throw,"i":__embind_register_bool,"h":__embind_register_emval,"g":__embind_register_float,"c":__embind_register_function,"b":__embind_register_integer,"a":__embind_register_memory_view,"f":__embind_register_std_string,"e":__embind_register_std_wstring,"j":__embind_register_void,"o":_abort,"m":_emscripten_memcpy_big,"n":_emscripten_resize_heap};var asm=createWasm();var ___wasm_call_ctors=Module["___wasm_call_ctors"]=function(){return(___wasm_call_ctors=Module["___wasm_call_ctors"]=Module["asm"]["q"]).apply(null,arguments)};var ___getTypeName=Module["___getTypeName"]=function(){return(___getTypeName=Module["___getTypeName"]=Module["asm"]["s"]).apply(null,arguments)};var ___embind_register_native_and_builtin_types=Module["___embind_register_native_and_builtin_types"]=function(){return(___embind_register_native_and_builtin_types=Module["___embind_register_native_and_builtin_types"]=Module["asm"]["t"]).apply(null,arguments)};var _malloc=Module["_malloc"]=function(){return(_malloc=Module["_malloc"]=Module["asm"]["u"]).apply(null,arguments)};var _free=Module["_free"]=function(){return(_free=Module["_free"]=Module["asm"]["v"]).apply(null,arguments)};var calledRun;function ExitStatus(status){this.name="ExitStatus";this.message="Program terminated with exit("+status+")";this.status=status}dependenciesFulfilled=function runCaller(){if(!calledRun)run();if(!calledRun)dependenciesFulfilled=runCaller};function run(args){args=args||arguments_;if(runDependencies>0){return}preRun();if(runDependencies>0){return}function doRun(){if(calledRun)return;calledRun=true;Module["calledRun"]=true;if(ABORT)return;initRuntime();preMain();if(Module["onRuntimeInitialized"])Module["onRuntimeInitialized"]();postRun()}if(Module["setStatus"]){Module["setStatus"]("Running...");setTimeout(function(){setTimeout(function(){Module["setStatus"]("")},1);doRun()},1)}else{doRun()}}Module["run"]=run;if(Module["preInit"]){if(typeof Module["preInit"]=="function")Module["preInit"]=[Module["preInit"]];while(Module["preInit"].length>0){Module["preInit"].pop()()}}run();
import { benchmark } from "./bench.js";
import { BinaryHeap } from "./binaryheap.js";
const results = await benchmark({
async run() {
const heap = new BinaryHeap((v) => v);
for (let i = 0; i < 1000000; i++) {
heap.push(Math.random());
}
let last = Number.NEGATIVE_INFINITY;
let current;
while (heap.size() > 0) {
if (current < last) {
throw Error("Invalid ordering!");
}
last = current;
current = heap.pop();
}
},
});
console.log(results);
// Binary heap implementation from:
// http://eloquentjavascript.net/appendix2.html
type ScoreFunction<T> = (v: T) => f32;
class BinaryHeap<T> {
content: T[];
scoreFunction: ScoreFunction<T>;
constructor(scoreFunction: ScoreFunction<T>) {
this.content = [];
this.scoreFunction = scoreFunction;
}
push(element: T): void {
// Add the new element to the end of the array.
this.content.push(element);
// Allow it to bubble up.
this.bubbleUp(this.content.length - 1);
}
pop(): T {
if (this.content.length <= 0) {
throw new Error("Can't pop an empty heap");
}
// Store the first element so we can return it later.
const result = this.content[0];
// Get the element at the end of the array.
const end = this.content.pop();
// If there are any elements left, put the end element at the
// start, and let it sink down.
if (this.content.length > 0) {
this.content[0] = end;
this.sinkDown(0);
}
return result;
}
peek(): T {
if (this.content.length <= 0) {
throw new Error("Can't peek an empty heap");
}
return this.content[0];
}
remove(node: T): void {
if (this.content.length <= 0) {
throw new Error("Can't remove from an empty heap");
}
const len = this.content.length;
// To remove a value, we must search through the array to find
// it.
for (let i = 0; i < len; i++) {
if (this.content[i] == node) {
// When it is found, the process seen in 'pop' is repeated
// to fill up the hole.
const end = this.content.pop();
if (i != len - 1) {
this.content[i] = end;
if (this.scoreFunction(end) < this.scoreFunction(node))
this.bubbleUp(i);
else this.sinkDown(i);
}
return;
}
}
throw new Error("Node not found.");
}
size(): u32 {
return this.content.length;
}
bubbleUp(n: u32): void {
// Fetch the element that has to be moved.
const element = this.content[n];
// When at 0, an element can not go up any further.
while (n > 0) {
// Compute the parent element's index, and fetch it.
const parentN = <i32>Math.floor((n + 1) / 2) - 1,
parent = this.content[parentN];
// Swap the elements if the parent is greater.
if (this.scoreFunction(element) < this.scoreFunction(parent)) {
this.content[parentN] = element;
this.content[n] = parent;
// Update 'n' to continue at the new position.
n = parentN;
}
// Found a parent that is less, no need to move it further.
else {
break;
}
}
}
sinkDown(n: u32): void {
// Look up the target element and its score.
const length = this.content.length,
element = this.content[n],
elemScore = this.scoreFunction(element);
while (true) {
// Compute the indices of the child elements.
const child2N: i32 = (n + 1) * 2,
child1N: i32 = child2N - 1;
// This is used to store the new position of the element,
// if any.
let swap: i32 = -1;
let child1: T, child1Score: f32, child2: T, child2Score: f32;
// If the first child exists (is inside the array)...
if (child1N < length) {
// Look it up and compute its score.
child1 = this.content[child1N];
child1Score = this.scoreFunction(child1);
// If the score is less than our element's, we need to swap.
if (child1Score < elemScore) swap = child1N;
}
// Do the same checks for the other child.
if (child2N < length) {
child2 = this.content[child2N];
child2Score = this.scoreFunction(child2);
if (child2Score < (swap == -1 ? elemScore : child1Score)) {
swap = child2N;
}
}
// If the element needs to be moved, swap it, and continue.
if (swap != -1) {
this.content[n] = this.content[swap];
this.content[swap] = element;
n = swap;
}
// Otherwise, we are done.
else {
break;
}
}
}
}
let heapInstance: BinaryHeap<f32>;
export function init(): void {
heapInstance = new BinaryHeap<f32>((v) => v);
}
export function push(v: f32): void {
heapInstance.push(v);
}
export function pop(): f32 {
return heapInstance.pop();
}
export function size(): u32 {
return heapInstance.size();
}
export function peek(): f32 {
return heapInstance.peek();
}
extern crate wee_alloc;
// Use `wee_alloc` as the global allocator.
#[global_allocator]
static ALLOC: wee_alloc::WeeAlloc = wee_alloc::WeeAlloc::INIT;
struct BinaryHeap(Vec<f32>);
impl BinaryHeap {
fn new() -> BinaryHeap {
BinaryHeap(Vec::with_capacity(10))
}
fn push(&mut self, v: f32) {
self.0.push(v);
self.bubble_up(self.0.len() - 1);
}
fn peek(&self) -> f32 {
unsafe { *self.0.get_unchecked(0) }
}
fn pop(&mut self) -> f32 {
let result = unsafe { *self.0.get_unchecked(0) };
let end = unsafe { *self.0.get_unchecked(self.0.len() - 1) };
// Avoid error handling code
self.0.pop();
if self.0.len() > 0 {
unsafe {
*self.0.get_unchecked_mut(0) = end;
}
self.sink_down(0);
}
result
}
fn size(&self) -> usize {
self.0.len()
}
fn bubble_up(&mut self, mut n: usize) {
let element = unsafe { *self.0.get_unchecked(n) };
while n > 0 {
// Compute the parent element's index, and fetch it.
let parent_n: usize = ((((n as f32) + 1.0) / 2.0) - 1.0).floor() as usize;
let parent: f32 = unsafe { *self.0.get_unchecked(parent_n) };
// Swap the elements if the parent is greater.
if element < parent {
unsafe {
*(self.0.get_unchecked_mut(parent_n)) = element;
*(self.0.get_unchecked_mut(n)) = parent;
}
n = parent_n;
}
// Found a parent that is less, no need to move it further.
else {
break;
}
}
}
fn sink_down(&mut self, mut n: usize) {
// Look up the target element and its score.
let length = self.0.len();
let element = unsafe { *self.0.get_unchecked(n) };
let elem_score = element;
loop {
// Compute the indices of the child elements.
let child2_n = (n + 1) * 2;
let child1_n = child2_n - 1;
// This is used to store the new position of the element,
// if any.
let mut swap: Option<usize> = None;
let child1: f32;
let mut child1_score: f32 = std::f32::NEG_INFINITY;
let child2: f32;
let child2_score: f32;
// If the first child exists (is inside the array)...
if child1_n < length {
// Look it up and compute its score.
child1 = unsafe { *self.0.get_unchecked(child1_n) };
child1_score = child1;
// If the score is less than our element's, we need to swap.
if child1_score < elem_score {
swap = Some(child1_n);
}
}
// Do the same checks for the other child.
if child2_n < length {
child2 = unsafe { *self.0.get_unchecked(child2_n) };
child2_score = child2;
if child2_score < swap.map(|_| child1_score).unwrap_or(elem_score) {
swap = Some(child2_n);
}
}
// If the element needs to be moved, swap it, and continue.
if let Some(swap) = swap {
unsafe {
// Double-borrow is safe
let n_value = &mut *(self.0.get_unchecked_mut(n) as *mut _);
let swap_value = &mut *(self.0.get_unchecked_mut(swap) as *mut _);
*n_value = *swap_value;
*swap_value = element;
n = swap;
}
}
// Otherwise, we are done.
else {
break;
}
}
}
}
static mut INSTANCE: Option<BinaryHeap> = None;
pub fn init() {
unsafe {
INSTANCE = Some(BinaryHeap::new());
}
}
pub fn push(v: f32) {
unsafe {
INSTANCE.as_mut().unwrap_unchecked().push(v);
}
}
pub fn pop() -> f32 {
unsafe { INSTANCE.as_mut().unwrap_unchecked().pop() }
}
pub fn size() -> usize {
unsafe { INSTANCE.as_ref().unwrap_unchecked().size() }
}
pub fn peek() -> f32 {
unsafe { INSTANCE.as_ref().unwrap_unchecked().peek() }
}
// Binary heap implementation from:
// http://eloquentjavascript.net/appendix2.html
class BinaryHeap<T> {
content: Array<T> = new Array<T>(10);
push(element: T): void {
// Add the new element to the end of the array.
this.content.push(element);
// Allow it to bubble up.
this.bubbleUp(<i32>this.content.length - 1);
}
pop(): T {
if (this.content.length <= 0) {
throw new Error("Can't pop an empty heap");
}
// Store the first element so we can return it later.
const result = unchecked(this.content[0]);
// Get the element at the end of the array.
const end = this.content.pop();
// If there are any elements left, put the end element at the
// start, and let it sink down.
if (this.content.length > 0) {
unchecked((this.content[0] = end));
this.sinkDown(0);
}
return result;
}
peek(): T {
if (this.content.length <= 0) {
throw new Error("Can't peek an empty heap");
}
return unchecked(this.content[0]);
}
remove(node: T): void {
if (this.content.length <= 0) {
throw new Error("Can't remove from an empty heap");
}
const len = this.content.length;
// To remove a value, we must search through the array to find
// it.
for (let i = 0; i < len; i++) {
if (unchecked(this.content[i]) == node) {
// When it is found, the process seen in 'pop' is repeated
// to fill up the hole.
const end = this.content.pop();
if (i != len - 1) {
unchecked((this.content[i] = end));
if (end < node) this.bubbleUp(i);
else this.sinkDown(i);
}
return;
}
}
throw new Error("Node not found.");
}
size(): u32 {
return this.content.length;
}
bubbleUp(n: u32): void {
// Fetch the element that has to be moved.
const element = unchecked(this.content[n]);
// When at 0, an element can not go up any further.
while (n > 0) {
// Compute the parent element's index, and fetch it.
const parentN = <i32>Math.floor((n + 1) / 2) - 1,
parent = unchecked(this.content[parentN]);
// Swap the elements if the parent is greater.
if (element < parent) {
unchecked((this.content[parentN] = element));
unchecked((this.content[n] = parent));
// Update 'n' to continue at the new position.
n = parentN;
}
// Found a parent that is less, no need to move it further.
else {
break;
}
}
}
sinkDown(n: u32): void {
// Look up the target element and its score.
const length = this.content.length,
element = unchecked(this.content[n]),
elemScore = element;
while (true) {
// Compute the indices of the child elements.
const child2N: i32 = (n + 1) * 2,
child1N: i32 = child2N - 1;
// This is used to store the new position of the element,
// if any.
let swap: i32 = -1;
let child1: T, child1Score: f32, child2: T, child2Score: f32;
// If the first child exists (is inside the array)...
if (child1N < length) {
// Look it up and compute its score.
child1 = unchecked(this.content[child1N]);
child1Score = child1;
// If the score is less than our element's, we need to swap.
if (child1Score < elemScore) swap = child1N;
}
// Do the same checks for the other child.
if (child2N < length) {
child2 = unchecked(this.content[child2N]);
child2Score = child2;
if (child2Score < (swap == -1 ? elemScore : child1Score)) {
swap = child2N;
}
}
// If the element needs to be moved, swap it, and continue.
if (swap != -1) {
unchecked((this.content[n] = unchecked(this.content[swap])));
unchecked((this.content[swap] = element));
n = swap;
}
// Otherwise, we are done.
else {
break;
}
}
}
}
let heapInstance: BinaryHeap<f32>;
export function init(): void {
heapInstance = new BinaryHeap();
}
export function push(v: f32): void {
heapInstance.push(v);
}
export function pop(): f32 {
return heapInstance.pop();
}
export function size(): u32 {
return heapInstance.size();
}
export function peek(): f32 {
return heapInstance.peek();
}
// Calculate Gaussian blur of an image using IIR filter
// The method is taken from Intel's white paper and code example attached to it:
// https://software.intel.com/en-us/articles/iir-gaussian-blur-filter
// -implementation-using-intel-advanced-vector-extensions
var a0, a1, a2, a3, b1, b2, left_corner, right_corner;
function gaussCoef(sigma) {
if (sigma < 0.5) {
sigma = 0.5;
}
var a = Math.exp(0.726 * 0.726) / sigma,
g1 = Math.exp(-a),
g2 = Math.exp(-2 * a),
k = ((1 - g1) * (1 - g1)) / (1 + 2 * a * g1 - g2);
a0 = k;
a1 = k * (a - 1) * g1;
a2 = k * (a + 1) * g1;
a3 = -k * g2;
b1 = 2 * g1;
b2 = -g2;
left_corner = (a0 + a1) / (1 - b1 - b2);
right_corner = (a2 + a3) / (1 - b1 - b2);
// Attempt to force type to FP32.
return new Float32Array([a0, a1, a2, a3, b1, b2, left_corner, right_corner]);
}
function convolveRGBA(src, out, line, coeff, width, height) {
// takes src image and writes the blurred and transposed result into out
var rgba;
var prev_src_r, prev_src_g, prev_src_b, prev_src_a;
var curr_src_r, curr_src_g, curr_src_b, curr_src_a;
var curr_out_r, curr_out_g, curr_out_b, curr_out_a;
var prev_out_r, prev_out_g, prev_out_b, prev_out_a;
var prev_prev_out_r, prev_prev_out_g, prev_prev_out_b, prev_prev_out_a;
var src_index, out_index, line_index;
var i, j;
var coeff_a0, coeff_a1, coeff_b1, coeff_b2;
for (i = 0; i < height; i++) {
src_index = i * width;
out_index = i;
line_index = 0;
// left to right
rgba = src[src_index];
prev_src_r = rgba & 0xff;
prev_src_g = (rgba >> 8) & 0xff;
prev_src_b = (rgba >> 16) & 0xff;
prev_src_a = (rgba >> 24) & 0xff;
prev_prev_out_r = prev_src_r * coeff[6];
prev_prev_out_g = prev_src_g * coeff[6];
prev_prev_out_b = prev_src_b * coeff[6];
prev_prev_out_a = prev_src_a * coeff[6];
prev_out_r = prev_prev_out_r;
prev_out_g = prev_prev_out_g;
prev_out_b = prev_prev_out_b;
prev_out_a = prev_prev_out_a;
coeff_a0 = coeff[0];
coeff_a1 = coeff[1];
coeff_b1 = coeff[4];
coeff_b2 = coeff[5];
for (j = 0; j < width; j++) {
rgba = src[src_index];
curr_src_r = rgba & 0xff;
curr_src_g = (rgba >> 8) & 0xff;
curr_src_b = (rgba >> 16) & 0xff;
curr_src_a = (rgba >> 24) & 0xff;
curr_out_r =
curr_src_r * coeff_a0 +
prev_src_r * coeff_a1 +
prev_out_r * coeff_b1 +
prev_prev_out_r * coeff_b2;
curr_out_g =
curr_src_g * coeff_a0 +
prev_src_g * coeff_a1 +
prev_out_g * coeff_b1 +
prev_prev_out_g * coeff_b2;
curr_out_b =
curr_src_b * coeff_a0 +
prev_src_b * coeff_a1 +
prev_out_b * coeff_b1 +
prev_prev_out_b * coeff_b2;
curr_out_a =
curr_src_a * coeff_a0 +
prev_src_a * coeff_a1 +
prev_out_a * coeff_b1 +
prev_prev_out_a * coeff_b2;
prev_prev_out_r = prev_out_r;
prev_prev_out_g = prev_out_g;
prev_prev_out_b = prev_out_b;
prev_prev_out_a = prev_out_a;
prev_out_r = curr_out_r;
prev_out_g = curr_out_g;
prev_out_b = curr_out_b;
prev_out_a = curr_out_a;
prev_src_r = curr_src_r;
prev_src_g = curr_src_g;
prev_src_b = curr_src_b;
prev_src_a = curr_src_a;
line[line_index] = prev_out_r;
line[line_index + 1] = prev_out_g;
line[line_index + 2] = prev_out_b;
line[line_index + 3] = prev_out_a;
line_index += 4;
src_index++;
}
src_index--;
line_index -= 4;
out_index += height * (width - 1);
// right to left
rgba = src[src_index];
prev_src_r = rgba & 0xff;
prev_src_g = (rgba >> 8) & 0xff;
prev_src_b = (rgba >> 16) & 0xff;
prev_src_a = (rgba >> 24) & 0xff;
prev_prev_out_r = prev_src_r * coeff[7];
prev_prev_out_g = prev_src_g * coeff[7];
prev_prev_out_b = prev_src_b * coeff[7];
prev_prev_out_a = prev_src_a * coeff[7];
prev_out_r = prev_prev_out_r;
prev_out_g = prev_prev_out_g;
prev_out_b = prev_prev_out_b;
prev_out_a = prev_prev_out_a;
curr_src_r = prev_src_r;
curr_src_g = prev_src_g;
curr_src_b = prev_src_b;
curr_src_a = prev_src_a;
coeff_a0 = coeff[2];
coeff_a1 = coeff[3];
for (j = width - 1; j >= 0; j--) {
curr_out_r =
curr_src_r * coeff_a0 +
prev_src_r * coeff_a1 +
prev_out_r * coeff_b1 +
prev_prev_out_r * coeff_b2;
curr_out_g =
curr_src_g * coeff_a0 +
prev_src_g * coeff_a1 +
prev_out_g * coeff_b1 +
prev_prev_out_g * coeff_b2;
curr_out_b =
curr_src_b * coeff_a0 +
prev_src_b * coeff_a1 +
prev_out_b * coeff_b1 +
prev_prev_out_b * coeff_b2;
curr_out_a =
curr_src_a * coeff_a0 +
prev_src_a * coeff_a1 +
prev_out_a * coeff_b1 +
prev_prev_out_a * coeff_b2;
prev_prev_out_r = prev_out_r;
prev_prev_out_g = prev_out_g;
prev_prev_out_b = prev_out_b;
prev_prev_out_a = prev_out_a;
prev_out_r = curr_out_r;
prev_out_g = curr_out_g;
prev_out_b = curr_out_b;
prev_out_a = curr_out_a;
prev_src_r = curr_src_r;
prev_src_g = curr_src_g;
prev_src_b = curr_src_b;
prev_src_a = curr_src_a;
rgba = src[src_index];
curr_src_r = rgba & 0xff;
curr_src_g = (rgba >> 8) & 0xff;
curr_src_b = (rgba >> 16) & 0xff;
curr_src_a = (rgba >> 24) & 0xff;
rgba =
((line[line_index] + prev_out_r) << 0) +
((line[line_index + 1] + prev_out_g) << 8) +
((line[line_index + 2] + prev_out_b) << 16) +
((line[line_index + 3] + prev_out_a) << 24);
out[out_index] = rgba;
src_index--;
line_index -= 4;
out_index -= height;
}
}
}
export function blurRGBA(src, width, height, radius) {
// Quick exit on zero radius
if (!radius) {
return;
}
// Unify input data type, to keep convolver calls isomorphic
var src32 = new Uint32Array(src.buffer);
var out = new Uint32Array(src32.length),
tmp_line = new Float32Array(Math.max(width, height) * 4);
var coeff = gaussCoef(radius);
convolveRGBA(src32, out, tmp_line, coeff, width, height);
convolveRGBA(out, src32, tmp_line, coeff, height, width);
}
import { benchmark } from "./bench.js";
const data = new Uint8ClampedArray(2048 * 2048 * 4);
data.forEach((_, i, arr) => arr[i] = Math.random() * 255);
const ascModule = new WebAssembly.Module(readbuffer(arguments[0]));
const results = await benchmark({
async before() {
this.instance = new WebAssembly.Instance(ascModule, {
env: {
abort() {
throw Error("ARRGGH");
},
},
});
this.data = new Uint8ClampedArray(data.slice());
},
async run() {
const arrayViewPtr = this.instance.exports.newUint8ClampedArray(
this.data.byteLength
);
const dataView = new DataView(this.instance.exports.memory.buffer);
// Get pointer to data section of the underlying array buffer
const dataPtr = dataView.getUint32(arrayViewPtr + 4, true);
// Copy image data into linear memory
new Uint8ClampedArray(
this.instance.exports.memory.buffer,
dataPtr,
this.data.byteLength
).set(this.data);
this.instance.exports.blurRGBA(arrayViewPtr, 2048, 2048, 100);
},
numWarmup: 0,
});
console.log(results);
import { benchmark } from "./bench.js";
import { blurRGBA } from "./blur.js";
const data = new Uint8ClampedArray(2048 * 2048 * 4);
data.forEach((_, i, arr) => arr[i] = Math.random() * 255);
const results = await benchmark({
async before() {
this.data = new Uint8ClampedArray(data.slice());
},
async run() {
blurRGBA(this.data, 2048, 2048, 100);
},
});
console.log(results);
let a0: f32,
a1: f32,
a2: f32,
a3: f32,
b1: f32,
b2: f32,
left_corner: f32,
right_corner: f32;
function gaussCoef(sigma: f32): Float32Array {
if (sigma < 0.5) {
sigma = 0.5;
}
let a: f32 = <f32>Math.exp(0.726 * 0.726) / sigma,
g1: f32 = <f32>Math.exp(-a),
g2: f32 = <f32>Math.exp(-2 * a),
k: f32 = ((1 - g1) * (1 - g1)) / (1 + 2 * a * g1 - g2);
a0 = k;
a1 = k * (a - 1) * g1;
a2 = k * (a + 1) * g1;
a3 = -k * g2;
b1 = 2 * g1;
b2 = -g2;
left_corner = (a0 + a1) / (1 - b1 - b2);
right_corner = (a2 + a3) / (1 - b1 - b2);
// Attempt to force type to FP32.
const r = new Float32Array(8);
const v = [a0, a1, a2, a3, b1, b2, left_corner, right_corner];
for (let i = 0; i < v.length; i++) {
r[i] = v[i];
}
return r;
}
function convolveRGBA(
src: Uint32Array,
out: Uint32Array,
line: Float32Array,
coeff: Float32Array,
width: i32,
height: i32
): void {
// takes src image and writes the blurred and transposed result into out
let rgba: i32;
let prev_src_r: f32, prev_src_g: f32, prev_src_b: f32, prev_src_a: f32;
let curr_src_r: f32, curr_src_g: f32, curr_src_b: f32, curr_src_a: f32;
let curr_out_r: f32, curr_out_g: f32, curr_out_b: f32, curr_out_a: f32;
let prev_out_r: f32, prev_out_g: f32, prev_out_b: f32, prev_out_a: f32;
let prev_prev_out_r: f32,
prev_prev_out_g: f32,
prev_prev_out_b: f32,
prev_prev_out_a: f32;
let src_index: i32, out_index: i32, line_index: i32;
let i: i32, j: i32;
let coeff_a0: f32, coeff_a1: f32, coeff_b1: f32, coeff_b2: f32;
for (i = 0; i < height; i++) {
src_index = i * width;
out_index = i;
line_index = 0;
// left to right
rgba = src[src_index];
prev_src_r = <f32>(rgba & 0xff);
prev_src_g = <f32>((rgba >> 8) & 0xff);
prev_src_b = <f32>((rgba >> 16) & 0xff);
prev_src_a = <f32>((rgba >> 24) & 0xff);
prev_prev_out_r = prev_src_r * coeff[6];
prev_prev_out_g = prev_src_g * coeff[6];
prev_prev_out_b = prev_src_b * coeff[6];
prev_prev_out_a = prev_src_a * coeff[6];
prev_out_r = prev_prev_out_r;
prev_out_g = prev_prev_out_g;
prev_out_b = prev_prev_out_b;
prev_out_a = prev_prev_out_a;
coeff_a0 = coeff[0];
coeff_a1 = coeff[1];
coeff_b1 = coeff[4];
coeff_b2 = coeff[5];
for (j = 0; j < width; j++) {
rgba = src[src_index];
curr_src_r = <f32>(rgba & 0xff);
curr_src_g = <f32>((rgba >> 8) & 0xff);
curr_src_b = <f32>((rgba >> 16) & 0xff);
curr_src_a = <f32>((rgba >> 24) & 0xff);
curr_out_r =
curr_src_r * coeff_a0 +
prev_src_r * coeff_a1 +
prev_out_r * coeff_b1 +
prev_prev_out_r * coeff_b2;
curr_out_g =
curr_src_g * coeff_a0 +
prev_src_g * coeff_a1 +
prev_out_g * coeff_b1 +
prev_prev_out_g * coeff_b2;
curr_out_b =
curr_src_b * coeff_a0 +
prev_src_b * coeff_a1 +
prev_out_b * coeff_b1 +
prev_prev_out_b * coeff_b2;
curr_out_a =
curr_src_a * coeff_a0 +
prev_src_a * coeff_a1 +
prev_out_a * coeff_b1 +
prev_prev_out_a * coeff_b2;
prev_prev_out_r = prev_out_r;
prev_prev_out_g = prev_out_g;
prev_prev_out_b = prev_out_b;
prev_prev_out_a = prev_out_a;
prev_out_r = curr_out_r;
prev_out_g = curr_out_g;
prev_out_b = curr_out_b;
prev_out_a = curr_out_a;
prev_src_r = curr_src_r;
prev_src_g = curr_src_g;
prev_src_b = curr_src_b;
prev_src_a = curr_src_a;
line[line_index] = prev_out_r;
line[line_index + 1] = prev_out_g;
line[line_index + 2] = prev_out_b;
line[line_index + 3] = prev_out_a;
line_index += 4;
src_index++;
}
src_index--;
line_index -= 4;
out_index += height * (width - 1);
// right to left
rgba = src[src_index];
prev_src_r = <f32>(rgba & 0xff);
prev_src_g = <f32>((rgba >> 8) & 0xff);
prev_src_b = <f32>((rgba >> 16) & 0xff);
prev_src_a = <f32>((rgba >> 24) & 0xff);
prev_prev_out_r = prev_src_r * coeff[7];
prev_prev_out_g = prev_src_g * coeff[7];
prev_prev_out_b = prev_src_b * coeff[7];
prev_prev_out_a = prev_src_a * coeff[7];
prev_out_r = prev_prev_out_r;
prev_out_g = prev_prev_out_g;
prev_out_b = prev_prev_out_b;
prev_out_a = prev_prev_out_a;
curr_src_r = prev_src_r;
curr_src_g = prev_src_g;
curr_src_b = prev_src_b;
curr_src_a = prev_src_a;
coeff_a0 = coeff[2];
coeff_a1 = coeff[3];
for (j = width - 1; j >= 0; j--) {
curr_out_r =
curr_src_r * coeff_a0 +
prev_src_r * coeff_a1 +
prev_out_r * coeff_b1 +
prev_prev_out_r * coeff_b2;
curr_out_g =
curr_src_g * coeff_a0 +
prev_src_g * coeff_a1 +
prev_out_g * coeff_b1 +
prev_prev_out_g * coeff_b2;
curr_out_b =
curr_src_b * coeff_a0 +
prev_src_b * coeff_a1 +
prev_out_b * coeff_b1 +
prev_prev_out_b * coeff_b2;
curr_out_a =
curr_src_a * coeff_a0 +
prev_src_a * coeff_a1 +
prev_out_a * coeff_b1 +
prev_prev_out_a * coeff_b2;
prev_prev_out_r = prev_out_r;
prev_prev_out_g = prev_out_g;
prev_prev_out_b = prev_out_b;
prev_prev_out_a = prev_out_a;
prev_out_r = curr_out_r;
prev_out_g = curr_out_g;
prev_out_b = curr_out_b;
prev_out_a = curr_out_a;
prev_src_r = curr_src_r;
prev_src_g = curr_src_g;
prev_src_b = curr_src_b;
prev_src_a = curr_src_a;
rgba = src[src_index];
curr_src_r = <f32>(rgba & 0xff);
curr_src_g = <f32>((rgba >> 8) & 0xff);
curr_src_b = <f32>((rgba >> 16) & 0xff);
curr_src_a = <f32>((rgba >> 24) & 0xff);
rgba =
((<i32>(line[line_index] + prev_out_r)) << 0) +
((<i32>(line[line_index + 1] + prev_out_g)) << 8) +
((<i32>(line[line_index + 2] + prev_out_b)) << 16) +
((<i32>(line[line_index + 3] + prev_out_a)) << 24);
out[out_index] = rgba;
src_index--;
line_index -= 4;
out_index -= height;
}
}
}
export function blurRGBA(
src: Uint8ClampedArray,
width: i32,
height: i32,
radius: f32
): Uint8ClampedArray {
if (radius <= 0) {
return new Uint8ClampedArray(0);
}
// Unify input data type, to keep convolver calls isomorphic
let src32 = Uint32Array.wrap(src.buffer);
let out = new Uint32Array(src32.length),
tmp_line = new Float32Array(<i32>Math.max(width, height) * 4);
let coeff = gaussCoef(radius);
convolveRGBA(src32, out, tmp_line, coeff, width, height);
convolveRGBA(out, src32, tmp_line, coeff, height, width);
return src;
}
export function newUint8ClampedArray(size: u32): Uint8ClampedArray {
return new Uint8ClampedArray(size);
}
let a0: f32,
a1: f32,
a2: f32,
a3: f32,
b1: f32,
b2: f32,
left_corner: f32,
right_corner: f32;
function gaussCoef(sigma: f32): StaticArray<f32> {
if (sigma < 0.5) {
sigma = 0.5;
}
let a: f32 = Mathf.exp(0.726 * 0.726) / sigma,
g1: f32 = Mathf.exp(-a),
g2: f32 = Mathf.exp(-2 * a),
k: f32 = ((1 - g1) * (1 - g1)) / (1 + 2 * a * g1 - g2);
a0 = k;
a1 = k * (a - 1) * g1;
a2 = k * (a + 1) * g1;
a3 = -k * g2;
b1 = 2 * g1;
b2 = -g2;
left_corner = (a0 + a1) / (1 - b1 - b2);
right_corner = (a2 + a3) / (1 - b1 - b2);
// Attempt to force type to FP32.
return StaticArray.fromArray<f32>([
a0,
a1,
a2,
a3,
b1,
b2,
left_corner,
right_corner,
]);
}
function convolveRGBA(
src: StaticArray<u32>,
out: StaticArray<u32>,
line: StaticArray<f32>,
coeff: StaticArray<f32>,
width: i32,
height: i32
): void {
// takes src image and writes the blurred and transposed result into out
let rgba: i32;
let prev_src_r: f32, prev_src_g: f32, prev_src_b: f32, prev_src_a: f32;
let curr_src_r: f32, curr_src_g: f32, curr_src_b: f32, curr_src_a: f32;
let curr_out_r: f32, curr_out_g: f32, curr_out_b: f32, curr_out_a: f32;
let prev_out_r: f32, prev_out_g: f32, prev_out_b: f32, prev_out_a: f32;
let prev_prev_out_r: f32,
prev_prev_out_g: f32,
prev_prev_out_b: f32,
prev_prev_out_a: f32;
let src_index: i32, out_index: i32, line_index: i32;
let i: i32, j: i32;
let coeff_a0: f32, coeff_a1: f32, coeff_b1: f32, coeff_b2: f32;
for (i = 0; i < height; i++) {
src_index = i * width;
out_index = i;
line_index = 0;
// left to right
rgba = unchecked(src[src_index]);
prev_src_r = <f32>(rgba & 0xff);
prev_src_g = <f32>((rgba >> 8) & 0xff);
prev_src_b = <f32>((rgba >> 16) & 0xff);
prev_src_a = <f32>((rgba >> 24) & 0xff);
prev_prev_out_r = prev_src_r * unchecked(coeff[6]);
prev_prev_out_g = prev_src_g * unchecked(coeff[6]);
prev_prev_out_b = prev_src_b * unchecked(coeff[6]);
prev_prev_out_a = prev_src_a * unchecked(coeff[6]);
prev_out_r = prev_prev_out_r;
prev_out_g = prev_prev_out_g;
prev_out_b = prev_prev_out_b;
prev_out_a = prev_prev_out_a;
coeff_a0 = unchecked(coeff[0]);
coeff_a1 = unchecked(coeff[1]);
coeff_b1 = unchecked(coeff[4]);
coeff_b2 = unchecked(coeff[5]);
for (j = 0; j < width; j++) {
rgba = unchecked(src[src_index]);
curr_src_r = <f32>(rgba & 0xff);
curr_src_g = <f32>((rgba >> 8) & 0xff);
curr_src_b = <f32>((rgba >> 16) & 0xff);
curr_src_a = <f32>((rgba >> 24) & 0xff);
curr_out_r =
curr_src_r * coeff_a0 +
prev_src_r * coeff_a1 +
prev_out_r * coeff_b1 +
prev_prev_out_r * coeff_b2;
curr_out_g =
curr_src_g * coeff_a0 +
prev_src_g * coeff_a1 +
prev_out_g * coeff_b1 +
prev_prev_out_g * coeff_b2;
curr_out_b =
curr_src_b * coeff_a0 +
prev_src_b * coeff_a1 +
prev_out_b * coeff_b1 +
prev_prev_out_b * coeff_b2;
curr_out_a =
curr_src_a * coeff_a0 +
prev_src_a * coeff_a1 +
prev_out_a * coeff_b1 +
prev_prev_out_a * coeff_b2;
prev_prev_out_r = prev_out_r;
prev_prev_out_g = prev_out_g;
prev_prev_out_b = prev_out_b;
prev_prev_out_a = prev_out_a;
prev_out_r = curr_out_r;
prev_out_g = curr_out_g;
prev_out_b = curr_out_b;
prev_out_a = curr_out_a;
prev_src_r = curr_src_r;
prev_src_g = curr_src_g;
prev_src_b = curr_src_b;
prev_src_a = curr_src_a;
unchecked((line[line_index] = prev_out_r));
unchecked((line[line_index + 1] = prev_out_g));
unchecked((line[line_index + 2] = prev_out_b));
unchecked((line[line_index + 3] = prev_out_a));
line_index += 4;
src_index++;
}
src_index--;
line_index -= 4;
out_index += height * (width - 1);
// right to left
rgba = unchecked(src[src_index]);
prev_src_r = <f32>(rgba & 0xff);
prev_src_g = <f32>((rgba >> 8) & 0xff);
prev_src_b = <f32>((rgba >> 16) & 0xff);
prev_src_a = <f32>((rgba >> 24) & 0xff);
prev_prev_out_r = prev_src_r * unchecked(coeff[7]);
prev_prev_out_g = prev_src_g * unchecked(coeff[7]);
prev_prev_out_b = prev_src_b * unchecked(coeff[7]);
prev_prev_out_a = prev_src_a * unchecked(coeff[7]);
prev_out_r = prev_prev_out_r;
prev_out_g = prev_prev_out_g;
prev_out_b = prev_prev_out_b;
prev_out_a = prev_prev_out_a;
curr_src_r = prev_src_r;
curr_src_g = prev_src_g;
curr_src_b = prev_src_b;
curr_src_a = prev_src_a;
coeff_a0 = unchecked(coeff[2]);
coeff_a1 = unchecked(coeff[3]);
for (j = width - 1; j >= 0; j--) {
curr_out_r =
curr_src_r * coeff_a0 +
prev_src_r * coeff_a1 +
prev_out_r * coeff_b1 +
prev_prev_out_r * coeff_b2;
curr_out_g =
curr_src_g * coeff_a0 +
prev_src_g * coeff_a1 +
prev_out_g * coeff_b1 +
prev_prev_out_g * coeff_b2;
curr_out_b =
curr_src_b * coeff_a0 +
prev_src_b * coeff_a1 +
prev_out_b * coeff_b1 +
prev_prev_out_b * coeff_b2;
curr_out_a =
curr_src_a * coeff_a0 +
prev_src_a * coeff_a1 +
prev_out_a * coeff_b1 +
prev_prev_out_a * coeff_b2;
prev_prev_out_r = prev_out_r;
prev_prev_out_g = prev_out_g;
prev_prev_out_b = prev_out_b;
prev_prev_out_a = prev_out_a;
prev_out_r = curr_out_r;
prev_out_g = curr_out_g;
prev_out_b = curr_out_b;
prev_out_a = curr_out_a;
prev_src_r = curr_src_r;
prev_src_g = curr_src_g;
prev_src_b = curr_src_b;
prev_src_a = curr_src_a;
rgba = unchecked(src[src_index]);
curr_src_r = <f32>(rgba & 0xff);
curr_src_g = <f32>((rgba >> 8) & 0xff);
curr_src_b = <f32>((rgba >> 16) & 0xff);
curr_src_a = <f32>((rgba >> 24) & 0xff);
rgba =
((<i32>(unchecked(line[line_index]) + prev_out_r)) << 0) +
((<i32>(unchecked(line[line_index + 1]) + prev_out_g)) << 8) +
((<i32>(unchecked(line[line_index + 2]) + prev_out_b)) << 16) +
((<i32>(unchecked(line[line_index + 3]) + prev_out_a)) << 24);
unchecked((out[out_index] = rgba));
src_index--;
line_index -= 4;
out_index -= height;
}
}
}
export function blurRGBA(
src: Uint8ClampedArray,
width: i32,
height: i32,
radius: f32
): Uint8ClampedArray {
if (radius <= 0) {
return new Uint8ClampedArray(0);
}
// Unify input data type, to keep convolver calls isomorphic
let src32 = changetype<StaticArray<u32>>(src.buffer);
// let src32 = StaticArray.fromArray<u32>(Uint32Array.wrap(src.buffer));
let out = new StaticArray<u32>(src32.length),
tmp_line = new StaticArray<f32>(<i32>Math.max(width, height) * 4);
let coeff = gaussCoef(radius);
convolveRGBA(src32, out, tmp_line, coeff, width, height);
convolveRGBA(out, src32, tmp_line, coeff, height, width);
return src;
}
export function newUint8ClampedArray(size: u32): Uint8ClampedArray {
return new Uint8ClampedArray(size);
}
export function sort(arr) {
var len = arr.length;
for (var i = len - 1; i >= 0; i--) {
for (var j = 1; j <= i; j++) {
if (arr[j - 1] > arr[j]) {
var temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
}
}
}
import { benchmark } from "./bench.js";
const ascModule = new WebAssembly.Module(readbuffer(arguments[0]));
const results = await benchmark({
async before() {
this.instance = new WebAssembly.Instance(ascModule, {
env: {
abort() {
throw Error("ARRGGH");
},
},
});
this.arr = new Float32Array(10000);
this.arr.forEach((_, i) => (this.arr[i] = Math.random()));
},
async run() {
const arrayPtr = this.instance.exports.newStaticArray(this.arr.length);
new Float32Array(
this.instance.exports.memory.buffer,
arrayPtr,
this.arr.length
).set(this.arr);
this.instance.exports.sort(arrayPtr);
},
numWarmup: 0,
});
console.log(results);
import { benchmark } from "./bench.js";
import { sort } from "./bubblesort.js";
const results = await benchmark({