Module

Data.ArrayBuffer.Builder.Internal

Package
purescript-arraybuffer-builder
Repository
jamesdbrock/purescript-arraybuffer-builder

Internal module.

You probably don’t want to import anything from this module.

Implementation Details

We want our Builder to be a data structure with

  • O(1) monoid append
  • O(n) fold

Our Builder implementation is an unbalanced binary tree.

For monoid append, what we actually get is O(1) when either the left or right tree is a singleton. If that's not true, then in the unlikely worst case append might be O(n).

Builder is optimized for what we consider to be normal usage, that is, snocing singleton elements to the end of the Builder.

If a Builder is built entirely by snocing, it will look like a left-only binary tree, a.k.a. a linked list.

           ④
          ╱
         ③
        ╱
       ②
      ╱
     ①

If two of these snoc-built trees are appended, then the new tree will look like

           ④
          ╱  ╲
         ③  ⑧
        ╱   ╱
       ②  ⑦
      ╱   ╱
     ①  ⑥
        ╱
       ⑤

This is all similar to bytestring-tree-builder , except that the Tree structure in bytestring-tree-builder only carries values in its leaves, which is how it achieves consistent O(1) appending, at the cost of a higher coefficient time factor on the fold.

We hope that this implementation is fairly fast, since it is similar to bytestring-tree-builder which “according to the benchmarks … beats all the alternatives.” However, we haven’t chosen this implementation because it’s fast, we've chosen this implementation because it’s simple. If someone wants to create a fast PureScript ArrayBuffer serialization library, then they can benchmark against this one to prove that the new one is fast.

One relatively cheap and simple performance improvement for this library would be to remove the Null constructor of Builder and instead use Javascript nulls?

In the longer term, it might make sense to try to change the Builder so that it works like the https://hackage.haskell.org/package/bytestring/docs/Data-ByteString-Builder.html . That’s the approach taken by https://pursuit.purescript.org/packages/purescript-dynamic-buffers .

Here are some benchmarks of different Haskell ByteString builders https://github.com/haskell-perf/strict-bytestring-builders

We've tried to design the API for this library with minimal assumptions, so that if we want to change the Builder implementation later then we can.

#Builder Source

data Builder

Monoidal builder for ArrayBuffers.

We can add two types of things to the Builder:

  1. ArrayBuffer
  2. DataView

We might prefer to add a DataView to a Builder when we’re adding a large slice of data from some other ArrayBuffer, so that we don’t need an extra intermediate copy of the slice.

Constructors

Instances

  • Semigroup Builder

    Left-associative <>> append operator

    TL;DR You probably don't want to use the Builder monoid directly in your code, it’s better to use the PutM monad with do-notation instead.

    The Builder monoid in this library is efficient when we snoc single items onto the end of it, or when we only cons single items to the beginning, but it can be less efficient when we are mixing cons and snoc. Most of the time we want to snoc, but the Semigroup append operator <> is right-associative, which means it chains like cons.

    To solve this, we provide an operator <>> for appending Builders. <>> is exactly the same as <>, but left-associative, which means it chains like snoc.

    This only matters when we're chaining together three or more Builders in a single associative expression. Instead of

    builder₁ <> builder₂ <> builder₃

    we should always prefer to write

    builder₁ <>> builder₂ <>> builder₃

    so that we get the efficient snocing of Builders.

    If we build our ArrayBuffers with the PutM monad instead of appending by using the Semigroup instance of Builder, then we always get the efficient snoc case.

  • Monoid Builder

#(<>>) Source

Operator alias for Data.Semigroup.append (left-associative / precedence 5)

#DataBuff Source

data DataBuff

For distinguishing between ArrayBuffer and DataView.

Constructors

#toView Source

toView :: DataBuff -> DataView

View the contents of DataBuff as a DataView.

#execBuilder Source

execBuilder :: forall m. MonadEffect m => MonadRec m => Builder -> m ArrayBuffer

Build a single ArrayBuffer from a Builder. O(n)

#length Source

length :: Builder -> ByteLength

Calculate the total byte length of the Builder, without actually building it yet. O(n)

#foldl Source

foldl :: forall a. (a -> DataBuff -> a) -> a -> Builder -> a

Stack-safe foldl over a Builder. O(n)

#foldM Source

foldM :: forall m a. MonadRec m => (a -> DataBuff -> m a) -> a -> Builder -> m a

Stack-safe foldM over a Builder. O(n).

#singleton Source

singleton :: DataBuff -> Builder

Construct a Builder with a single DataBuff. O(1)

#cons Source

cons :: DataBuff -> Builder -> Builder

Prepend a DataBuff to the beginning of the Builder. O(1)

#snoc Source

snoc :: Builder -> DataBuff -> Builder

Append a DataBuff to the end of the Builder. O(1)

#encodeUint8 Source

encodeUint8 :: forall m. MonadEffect m => UInt -> m ArrayBuffer

Serialize an 8-bit unsigned integer (byte) into a new ArrayBuffer.

#encodeInt8 Source

encodeInt8 :: forall m. MonadEffect m => Int -> m ArrayBuffer

Serialize an 8-bit two’s-complement signed integer (char) into a new ArrayBuffer.

#encodeUint16be Source

encodeUint16be :: forall m. MonadEffect m => UInt -> m ArrayBuffer

Serialize a 16-bit big-endian unsigned integer into a new ArrayBuffer.

#encodeUint16le Source

encodeUint16le :: forall m. MonadEffect m => UInt -> m ArrayBuffer

Serialize a 16-bit little-endian unsigned integer into a new ArrayBuffer.

#encodeInt16be Source

encodeInt16be :: forall m. MonadEffect m => Int -> m ArrayBuffer

Serialize a 16-bit big-endian two’s-complement signed integer into a new ArrayBuffer.

#encodeInt16le Source

encodeInt16le :: forall m. MonadEffect m => Int -> m ArrayBuffer

Serialize a 16-bit little-endian two’s-complement signed integer into a new ArrayBuffer.

#encodeUint32be Source

encodeUint32be :: forall m. MonadEffect m => UInt -> m ArrayBuffer

Serialize a 32-bit big-endian unsigned integer into a new ArrayBuffer.

#encodeUint32le Source

encodeUint32le :: forall m. MonadEffect m => UInt -> m ArrayBuffer

Serialize a 32-bit little-endian unsigned integer into a new ArrayBuffer.

#encodeInt32be Source

encodeInt32be :: forall m. MonadEffect m => Int -> m ArrayBuffer

Serialize a 32-bit big-endian two’s-complement signed integer into a new ArrayBuffer.

#encodeInt32le Source

encodeInt32le :: forall m. MonadEffect m => Int -> m ArrayBuffer

Serialize a 32-bit little-endian two’s-complement signed integer into a new ArrayBuffer.

#encodeFloat32be Source

encodeFloat32be :: forall m. MonadEffect m => Float32 -> m ArrayBuffer

Serialize a 32-bit big-endian IEEE single-precision float into a new ArrayBuffer.

#encodeFloat32le Source

encodeFloat32le :: forall m. MonadEffect m => Float32 -> m ArrayBuffer

Serialize a 32-bit little-endian IEEE single-precision float into a new ArrayBuffer.

#encodeFloat64be Source

encodeFloat64be :: forall m. MonadEffect m => Number -> m ArrayBuffer

Serialize a 64-bit big-endian IEEE double-precision float into a new ArrayBuffer.

#encodeFloat64le Source

encodeFloat64le :: forall m. MonadEffect m => Number -> m ArrayBuffer

Serialize a 64-bit little-endian IEEE double-precision float into a new ArrayBuffer.

Modules
Data.ArrayBuffer.Builder
Data.ArrayBuffer.Builder.Internal