| slug | title | date | authors | tags | |||||
|---|---|---|---|---|---|---|---|---|---|
2022-07-20-js-backend-prim-types |
Primitive Type Representation in GHC's upcoming JS-backend |
July 20, 2022 |
|
|
One of the key challenges in any novel backend is representing GHC primitive
types in the new backend. For JavaScript, this is especially tricky, as
JavaScript only has 8 primitive types and some of those types, such as number do
not directly map to any Haskell primitive type, such as Int8#. This post walks
through the most important GHC primitives and describes our implementation for
each in the JavaScript backend. This post is intended to be an
explanation-oriented post, light on details, but just enough to understand how
the system works.
There are 36 primtypes that GHC defines in primops.txt.pp:
Char#Int8#,Int16#,Int32#,Int64#,Int#Word8#,Word16#,Word32#,Word64#,Word#Double#,Float#,Array#,MutableArray#,,SmallArray#,SmallMutableArray#ByteArray#,MutableByteArray#Addr#MutVar#,TVar#,MVar#,IOPort#,State#,RealWorld,ThreadId#Weak#,StablePtr#,StableName#,Compact#,BCO,Fun,Proxy#StackSnapshot#VECTOR
Some of these are unsupported in the JS-backend, such as VECTOR or lower
priority such as StackSnapshot#. We’ll begin with the easy cases.
The easy cases are the cases that are implemented as JavaScript objects. In general, this is the big hammer used when nothing else will do. We’ll expand on the use of objects—especially representing heap objects—in a future post, but for the majority of cases we mimic the STG-machine behavior for GHC heap objects using JavaScript heap objects. For example,
var someConstructor =
{ f = // entry function of the datacon worker
, m = 0 // garbage collector mark
, d1 = first arg // First data field for the constructor
, d2 = arity = 2: second arg // second field, or object containing the remaining fields
arity > 2: { d1, d2, ...} object with remaining args (starts with "d1 = x2"!)
}
This is the general recipe; we define a JavaScript object that contains
properties which correspond to the entry function of the heap object; in this
case that is the entry function, f for a constructor, some meta data for garbage
collection m, and pointers to the fields of the constructor or whatever else the
heap object might need. Using JavaScript objects allows straightforward
translations of several GHC types. For example TVars and MVars:
// stg.js.pp
/** @constructor */
function h$TVar(v) {
TRACE_STM("creating TVar, value: " + h$collectProps(v));
this.val = v; // current value
this.blocked = new h$Set(); // threads that get woken up if this TVar is updated
this.invariants = null; // invariants that use this TVar (h$Set)
this.m = 0; // gc mark
this._key = ++h$TVarN; // for storing in h$Map/h$Set
#ifdef GHCJS_DEBUG_ALLOC
h$debugAlloc_notifyAlloc(this);
#endif
}
// stm.js.pp
function h$MVar() {
TRACE_SCHEDULER("h$MVar constructor");
this.val = null;
this.readers = new h$Queue();
this.writers = new h$Queue();
this.waiters = null; // waiting for a value in the MVar with ReadMVar
this.m = 0; // gc mark
this.id = ++h$mvarId;
#ifdef GHCJS_DEBUG_ALLOC
h$debugAlloc_notifyAlloc(this);
#endif
}
Notice that both implementations defined properties specific to the semantics of
the Haskell type. JavaScript functions which create these objects follow the
naming convention h$<something> and reside in Shim files. Shim files are
JavaScript files that the JS-backend links against and are written in pure
JavaScript. This allows us to save some compile time by not generating code
which doesn’t change, and decompose the backend into JavaScript modules.
This strategy is also how functions are implemented in the JS-backend. Function
objects are generated by StgToJS.Expr.genExpr and StgToJS.Apply.genApp but
follow this recipe:
var myFUN =
{ f = <function itself>
, m = <garbage collector mark>
, d1 = free variable 1
, d2 = free variable 2
}
To summarize; for most cases we write custom JavaScript objects which hold
whatever machinery is needed as properties to satisfy the expected semantics of
the Haskell type. This is the strategy that implements: TVar, MVar, MutVar and
Fun.
For some types, such as ByteArray# we make engineering tradeoffs to optimize for
common use-cases. Consider the mem.js.pp shim, which defines ByteArray#:
// mem.js.pp
function h$newByteArray(len) {
var len0 = Math.max(h$roundUpToMultipleOf(len, 8), 8);
var buf = new ArrayBuffer(len0);
return { buf: buf
, len: len
, i3: new Int32Array(buf)
, u8: new Uint8Array(buf)
, u1: new Uint16Array(buf)
, f3: new Float32Array(buf)
, f6: new Float64Array(buf)
, dv: new DataView(buf)
, m: 0
}
}
ByteArray# follows the same recipe, buf is the payload of the ByteArray#,
len is the length of the ByteArray#. This is implemented using JavaScripts
ArrayBuffer object to yield a generic fixed-length raw binary data buffer. The
remaining properties are views over the payload to provide fast conversion at
the cost of extra memory allocation during object construction.
Addr# and StablePtr# are implemented as a pair of ByteArray# and an Int#
offset into the array. We’ll focus on Addr# because StablePtr# is the
same implementation, with the exception that the StablePtr# is tracked in the
global variable h$stablePtrBuf. Addr#s do not have an explicit constructor,
rather they are implicitly constructed. For example, consider h$rts_mkPtr
which creates a Ptr:
function h$rts_mkPtr(x) {
var buf, off = 0;
if(typeof x == 'string') {
buf = h$encodeUtf8(x);
off = 0;
} else if(typeof x == 'object' &&
typeof x.len == 'number' &&
x.buf instanceof ArrayBuffer) {
buf = x;
off = 0;
} else if(x.isView) {
buf = h$wrapBuffer(x.buffer, true, 0, x.buffer.byteLength);
off = x.byteOffset;
} else {
buf = h$wrapBuffer(x, true, 0, x.byteLength);
off = 0;
}
return (h$c2(h$baseZCGHCziPtrziPtr_con_e, (buf), (off)));
}
The function does some type inspection to check for the special case on
string, if we do not have a string then a Ptr which contains an Addr# is
returned by creating a new ArrayBuffer and an offset into that buffer. Or to
be more precise, the Addr# is "constructed" by creating a new ArrayBuffer
and an offset into that buffer. The object case checks for idempotency; if the
input is already such a Ptr, then just return the input. The interesting cases
are the cases which call to h$wrapBuffer:
// mem.js.pp
function h$wrapBuffer(buf, unalignedOk, offset, length) {
if(!unalignedOk && offset && offset % 8 !== 0) {
throw ("h$wrapBuffer: offset not aligned:" + offset);
}
if(!buf || !(buf instanceof ArrayBuffer))
throw "h$wrapBuffer: not an ArrayBuffer"
if(!offset) { offset = 0; }
if(!length || length < 0) { length = buf.byteLength - offset; }
return { buf: buf
, len: length
, i3: (offset%4) ? null : new Int32Array(buf, offset, length >> 2)
, u8: new Uint8Array(buf, offset, length)
, u1: (offset%2) ? null : new Uint16Array(buf, offset, length >> 1)
, f3: (offset%4) ? null : new Float32Array(buf, offset, length >> 2)
, f6: (offset%8) ? null : new Float64Array(buf, offset, length >> 3)
, dv: new DataView(buf, offset, length)
};
}
h$wrapBuffer is a utility function that does the allocation for the typed array,
and stores extra fields to coerce the data in the buf payload efficiently.
Translating numbers has three issues. First, JavaScript has no concept of
fixed-precision 64-bit types such as Int64# and Word64#. Second, JavaScript
bitwise operators only support signed 32-bit values (except the unsigned
right
shift
operator of course). Third, numbers are atomic types and do not require any
special properties for correct semantics, thus using wrapping objects gains us
nothing at the cost of indirection.
To express 64-bit numerics, we simply use two 32-bit numbers, one to express
the high bits, one for the low bits. For example, consider comparing two Int64#:
// arith.js.pp
function h$hs_ltInt64(h1,l1,h2,l2) {
if(h1 === h2) {
var l1s = l1 >>> 1;
var l2s = l2 >>> 1;
return (l1s < l2s || (l1s === l2s && ((l1&1) < (l2&1)))) ? 1 : 0;
} else {
return (h1 < h2) ? 1 : 0;
}
}
The less than comparison function expects four inputs, two for each Int64# in
Haskell. The first number is represented by h1 and l1 (high and low),
and similarly the second number is represented by h2 and l2. The comparison
is straightforward, we check equivalence of our high bits, if equal then we
check the lower bits while being careful with signedness. No surprises here.
For the bitwise operators we store both Word32# and Word# as 32-bit signed
values, and then map any values greater or equal 2^31 bits to negative values.
This way we stay within the 32-bit range even though in Haskell these types only
support nonnegative values.
I mentioned earlier that wrapper objects are inefficient for numerics. To
implement efficent numerics we use an optimization that detects if an object is
going to be a number, if so then we remove the wrapper object and return just
the payload, i.e., the number itself.
Fixed-precision Integer types are implemented in the rts.js.pp shim, for
example:
function h$rts_mkInt8(x) { return (x<<24)>>24; }
function h$rts_getInt8(x) { return ((typeof(x) === 'number')?(x):(x).d1); }
Notice that the getInt8 function calls the typeof operator to check the type
of the input object. In JavaScript, we can think of this as a form of pointer
tagging
the native code generator uses. typeof scrutinizes the input and checks if it
is actually number. If it is a number then it is UnBoxed, if it is an object
then it is Boxed, and is a heap object. The difference is between the type
Int8, which is Boxed (a pointer to the heap, and lifted; can contain ⊥)
and Int8# which is UnBoxed and is not a pointer but actually the value.
In general, in the JS-backend we deal with Boxed values that are heap objects.
But numbers are different. Consider the case where we want to add two Int8
(both are boxed) in the JS backend. We really only care whether both Int8s are
Thunks or not, if they are thunks then we have to inspect them on the heap,
and call their entry functions which eventually returns their values; but this
process is expensive! If they are not Thunks, then we do not need to treat
them like heap objects and can represent the Int8 directly as an Int8#
(UnBoxed). Thus an Int8# is always a JavaScript number, never a JS object,
but an Int8 can be either a JS number or an object depending on the code
involved and whether it was subject to this optimization.
The optimization is applicable when:
- We have a single data type with a single data constructor.
- The constructor holds a single field that can only be a particular type.
If these invariants hold then, we remove the wrapping object and instead refer
to the value held by the constructor directly. Int8 is the simplest case for
this optimization. In Haskell we have:
data Int8 = Int8 Int8#
Notice that this definition satisfies the requirements. A direct translation in the JS backend would be:
// Int8 represented as an Object with an entry function, f, and payload, d1.
var anInt8 = { d1 = <Int8# payload>
, f : entry function which would scrutinize the payload
}
But we can operationally distinguish between a Thunk and an Int8 because
these will have separate types in the StgToJS GHC pass, whereas in Haskell an
Int8 may actually be a Thunk until it is scrutinized and then becomes the
Int8 payload (i.e., call-by-need). So this means that we will always know when
we have an Int8 rather than a Thunk and therefore we can omit the wrapper
object and convert this code to just:
// no object, just payload
var anInt8 = = <Int8# payload>
For the interested reader, this optimization takes place in the JavaScript code
generator module GHC.StgToJS.Arg, specifically the functions allocConStatic,
isUnboxableCon, and primRepVt.
Char#: is represented by anumber, i.e., the code pointAddr#a pair of an array created byh$newByteArrayand an offset that indexesFloat#/Double#: Both represented as a JavaScript Double. This means thatFloat#has excess precision and thus we do not generate exactly the same answers as other platforms which are IEEE754 compliant. Full emulation of single precision Floats does not seem to be worth the effort as of writing. Our implementation represents these in aByteArray#, where eachFloat#takes 4 bytes in theByteArray#. This means that the precision is reduced to a 32-bit Float.