Hi everyone!
Since Francisco announced his ambition to create NumElm, a package for machine learning in elm, I’ve been very excited about seing more of this math stuff in elm. One of the key building blocks would be an efficient fixed size multi-dimensional array (also called a tensor). I though I could leverage typed arrays to do so. Here is my shot at providing the JavaScript typed arrays API in elm: mpizenberg/elm-js-typed-array. As stated in the readme, my reasons are two-fold:
- Grow the cover of Web APIs in elm.
Typed arrays are use for ArrayBuffers, Blobs, Files, WebGL, network exchange,
canvas data etc. So having them in elm is important in my opinion. - They are the only fixed-size, typed structures in JS. Due to this,
I’m convinced they can be used as a solid ground for fixed size
efficient mathematical (Linear Algebra) library.
In the following of this post, I detail:
- design goals
- use cases
- performances
- current API design
- main API issues
I would love to have feedback on any of these, either here or in issues on the repo.
Design Goals
- cover full
TypedArrayAPI (except few bits that don’t make sense in elm) - be elm compliant:
- appear as immutable data structure: modification create copies
- type safe polymorphism: add type parameters
- be interoperable with elm data structures:
- from elm data structures:
fromList,fromArray - to elm data structures:
toList,toArray
- from elm data structures:
- be interoperable with JavaScript: 0-cost encoders / decoders
- be as minimalist as possible. It aims to follow the successful approach
of Skinney/elm-array-exploration which splits its array implementation in two parts.
First a minimal wrapper of JavaScript array in native code (Native/JsArray.js
andArray/JsArray.elm),
and second, a pure elm implementation on top of it (Array/Hamt.elm). - be flexible yet efficient:
- most functions are benchmarked and optimized
- most functions are also provided in an “indexed” form
- some functions have an “unsafe” form to avoid overcost of functor type returned
Use Cases
In this blog post introducing typed arrays, the author list APIs making use of typed arrays, providing some examples.
I tried to implement one example of each use case (except MediaSource) with this elm-js-type-array package to improve design. Corresponding issue on github for more details.
- [x] WebGL:
examples/WebGL/{Main.elm, index.html, webgl.js}. Typed arrays are used to pass the vertices attributes at initialization and projection matrices at each animation frame. - [x] Canvas 2D:
examples/CanvasImageData/{Main.elm, index.html}. Canvas 2DImageDatabuffer is generated in elm and sent through port to JS that usesctx.putImageDatato draw it on the canvas. - [x] XMLHttpRequest:
examples/XMLHttpRequest/{Main.elm, index.html, answer.bin}. The request is sent through port in JS since there is no support of ArrayBuffer in the Expect type of elm http package. Once array buffer is received in JS land, it is directly sent back through port to elm. - [x] File:
examples/File/{Main.elm, index.html, answer.bin}. A File input is used to load a file, sent through port to callreadAsArrayBuffer()in JS, array buffer result sent back to elm through port. - [ ] MediaSource
- [x] WebSocket:
examples/WebSocket/{Main.elm, index.html}. The exchanged data with WebSocket is done through port in JS since there is no support ofArrayBufferin the kind of data sendable through elm websocket api. The array buffer is extracted in JS from theBlobreceived and sent directly back to elm as anArrayBuffer.
Performances
Benchmarks Structure
The goal of the benchmarks is to make sure that typed arrays are fast for all potential use cases, ranging from small array manipulation, to big image-like (~10^6 pixels) matrices. Therefore, I’m comparing each key function at different scales (set in Constants.sizeScales) with three data structures, List, Array and JsTypedArray (4 actually since testing both Uint8 and Float64).
Therefore, every benchmark file looks like the following:
module Append exposing (..)
-- imports
main : BenchmarkProgram
main =
program <|
describe "Append" <|
[ lists
, hamtArrays
, uint8Arrays
, float64Arrays
]
lists : Benchmark
lists =
-- scale benchmark
Constants.sizeScales
|> List.map (\size -> ( size, List.repeat size 0 ))
|> List.map (\( size, list ) -> ( toString size, \_ -> List.append list list ))
|> scale "List"
hamtArrays : Benchmark
-- scale benchmark
uint8Arrays : Benchmark
-- scale benchmark
float64Arrays : Benchmark
-- scale benchmark
Results
Detailed results with plots are available in this document. As can be seen there, the different functions benchmarked can be grouped into five categories:
- Typed arrays behave roughly like
Array. - Typed arrays are generally faster probably because of some implementation detail.
- Type (1) or (2) but with Uint8 implementation faster than Float64 since it benefits from lower memory size.
- Typed arrays are orders of magnitude faster due to a constant time implementation.
- Typed arrays are order of magnitude slower, due to full copy of array.
In category (1) (similar performance) we have:
-
all: return true if all elements satisfy the predicate. -
any: return true if at least one element satisfies the predicate. -
initialize: initialize an array with a function of the index. -
filter: recreate an array by keeping only values verifying predicate. -
foldl: reduce array from the left. -
length: get the length of data structure. -
map: map over array to create a new one.
In category (2) (generally faster) we have:
-
equal: the native implementation, restricted to numeric values, help a lot compared to elm==implementation. -
foldr: reduce array from right. Native implementation is faster. - get: slightly faster since in constant time instead of log time. Even faster in unsafe form that do not check out of bounds.
- slice first half: I’m not sure how exactly slicing is implemented in
Array. It is faster here though.
In category (3) (faster with smaller byte size) we have:
-
append: append two arrays. Faster with Uint8 since it takes a lot less memory. -
zeros: create an array of zeros.
In category (4) (order of magnitude faster) we have:
- slice second half: with typed arrays, slicing is in constant time.
In category (5) (order of magnitude slower) we have:
- set (
replaceWithConstant): used to modify one or multiple values of an array with a new one. Orders of magnitude slower due to full copy of array.
In summary, we have globally better performances, plus one trade of: slicing is in constant time, but modifying data is in linear time due to a full copy.
Current API Design
Currently, the API is split into 6 modules (+ 2 mutable experiments):
- JsArrayBuffer: manipulation of array buffers
- JsDataView: operations on data views
- JsTypedArray: polymorphic operations on typed arrays
- JsUint8Array: creation of Uint8 typed arrays
- JsFloat32Array: creation of Float32 typed arrays
- JsFloat64Array: creation of Float64 typed arrays
The other integer array creation modules are still missing since I’m waiting for more feedback first. The full API documentation, as of commit 1accc47 is available here: doc-1accc47.txt. More details are available in this issue on Github. Below is a brief summary of the API.
Typed Arrays
In the typed array creation modules (JsUint8Array, JsFloat32Array, JsFloat64Array), with have:
- Creation from scratch:
zeros,repeat,initialize - Creation from existing data:
fromBuffer,fromArray,fromList,fromTypedArray,unsafeIndexedFromList - Decoding from JS value:
fromValue,decode
In the module JsTypedArray of polymorphic functions we have:
- Types:
JsTypedArray a b,Uint8,Float32,Float64 - Interoperability:
toList,toArray,encode - Basic requests:
length,getAt,unsafeGetAt,buffer,bufferOffset - Predicates:
all,any,findIndex,filter, and theirindexed...equivalent - Comparison:
equal - Extraction and appending:
extract,append - Array transformations:
replaceWithConstant,map,map2,reverse,sort,reverseSort,indexedMap,indexedMap2 - Array reductions:
join,foldl,foldr,foldl2,foldr2,foldlr, and theirindexed...versions.
For questions about why two type parameters a and b, refer to the last part of the discussion of the main issues of the current API.
DataView and ArrayBuffer
JavaScript DataView provides a low-level interface for reading and writing multiple number types in an ArrayBuffer, with control over endianness. Current API in JsDataView do not let you choose endianness. It really won’t be an issue to just add this control when we first figure the best fitting API.
The JsDataView module provides functions that match almost exactly the JS implementation except for setters. More on this in next section.
The JsArrayBuffer API is very short like its JS counterpart. Basically, you almost never manipulates buffers directly, but as data views or typed arrays.
API Issues
Two Type Parameters
There can be many ways to choose a type in elm for JavaScript TypedArray. In discussions with Ian and Francisco, few forms were mentionned in comments, in the issue about API design:
- Fully generic:
JsTypedArray. No type parameter at all. The same type is used for all different typed arrays. - Fully specialized:
JsUint8Array,JsInt8Array, etc. Each module has its own set of operations. - One elm type parameter:
JsTypedArray bwherebwould beIntorFloat. - Two type parameters:
JsTypedArray a bwhereais a type describing the typed array (Uint8,Float32, etc.) andbis eitherIntorFloat.
Fully generic:
In the fully generic case, the main advantage is that the type is way simpler and functions only need to be implemented once. There would still be different functions to initialize a JS Uint8Array or Float32Array etc.
The main drawback is that functions taking two typed arrays (like map2) could be called with different typed arrays. This would imply that we have to do a lot of manual error handling. This is a critical drawback for performances in case functions manipulating multiple typed arrays, like mathematical operations for example.
Fully specialized:
In the fully specialized case, all operations are type safe. The main advantage is that it is super explicit what you’re dealing with.
The main drawbacks are that it implies a loooot of boilerplate and it prevents user to write a function once that would work on multiple typed arrays. Boilerplate is really annoying, and increases the chances that the documentation gets outdated, or that we forget to change something specific to the typed array. Preventing API users to easily write a function once, that would work with multiple typed arrays is also not a very good user experience.
One type parameter:
Using one type parameter that would be Int or Float depending on the compatible elm type still does not prevent type safety issues mentionned in the fully generic case. This is probably a half mesure not solving our main issues.
Two type parameters:
Using two type parameters like JsTypedArray Uint8 Int as one big advantage, it solves all issues with previous options. The first type parameter a (here Uint8) provide the specific typed array type, and thus enable us to prevent type safety issues related to underlying typed arrays. The second type parameter b (here Int) provide type safety for operations involving elm typed and typed arrays (like fold). The polymorphic aspect enable us to write all polymorphic functions only once. Only functions specific to each type (like creations of arrays) have to be written once for each typed array.
The main disadvantage of this approach is the possible unfamiliarity of programmers with types holding two type parameters. Since this drawback is hypothetical and it solves concrete issues of other approaches I chose this one for the time being.
DataView
In JavaScript, DataView provides a low-level interface for reading and writing multiple number types in an ArrayBuffer, with control over endianness. It has a constructor and three other properties: buffer, byteLength, byteOffset that have their equivalent elm functions in the JsDataView module. DataView methods are of two types, getters and setters, 8 of each, for every type.
Getters have the corresponding elm functions. Setters however, cannot be implemented as so if we want to keep immutability guaranties of elm. As a minimalist wrapper, I couldn’t figure how to deal with those setters. So for the time being I created an experimental module MutableJsDataView. It defines a type MutableJsDataView which is an alias to JsDataView and setters functions using this MutableJsDataView type in type signatures. This of course does not have any compile time guaranties that those functions will not be used on data views that are not supposed to be mutated. However by putting those in a separate module, with a different type in type signature, it makes the caller strongly aware of the mutability nature of those operations.
There might be a solution though (or multiple solutions) as suggested by Laurin in still this same API design issue. This solution would be to embrace the encoder/decoder api. As such, one might describe how to read/write all data on a buffer and the actual reading or writing “transaction” would happen once. This has many advantages over the getter/setter approach regarding immutability. It also has one inconvenient consequence, the API wouldn’t be anymore a minimalist wrapper around JS equivalents.
Another slightly inconvenient aspect, is that whether we use getters/setters or encoders/decoders, we will have to specify the positions (the “offset”) where to read/write data. Yet buffers are sequential data structures so it is possible that most use cases only need to read/write data sequentially (this, then that, then toto, etc.). As mentionned by Ian in this same github issue, the parser approach is very well fitted for reading such sequential data. I’m not sure what is the equivalent of a parser for writing data though.
Immutability
One of the design strengths of elm is the immutability guaranty. However, in some rare cases, it can be a performance chasm. Such cases are for example the modification of a 2D canvas data at frame rate. In this case, with immutability, we are creating a new array of millions of values, at roughly 30 hz. This implies a lot of garbage collection.
Such example is available in folder examples/CanvasImageData/. Use elm-make Main.elm --output Main.js to compile it and spawn any static http server to load index.html in your browser. Garbage Collection events are noticeable by small freezes in the color animation.
I did an experimentation by creating a module MutableJsTypedArray containing two functions unsafeSetAt and unsafeSet. Those functions are not used anywhere else in the API, only in this example experiment. You can find the example in examples/CanvasImageDataMutable/. When running this code, you won’t notice any garbage collection freeze, and it will globally consume less memory and CPU usage.
I’m aware that this module MutableJsTypedArray and the one mentionned in previous part MutableJsDataView break the immutability constraint guaranty of elm so I’m not very satisfied with them. I recently heard of Linear type systems that might provide some solution to a class of problems solved currently by mutability like the previous canvas 2D example. I am wondering if there would be a way to do something similiar in elm, by describing the transformation, and letting the elm runtime (or something else) do the immutable transformation “in place”.
