ArrayBuffer. Builder. Internal
You probably don’t want to import anything from this module.
We want our
Builder to be a data structure with
- O(1) monoid append
- O(n) fold
Builder implementation is an unbalanced binary tree.
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
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
, except that the
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
which “according to the benchmarks … beats all the alternatives.”
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
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
Null constructor of
In the longer term, it might make sense to try to change the
that it works like the
That’s the approach taken by
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.
Monoidal builder for
We can add two types of things to the
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.
TL;DR You probably don't want to use the
Buildermonoid directly in your code, it’s better to use the
PutMmonad with do-notation instead.
Buildermonoid in this library is efficient when we
snocsingle items onto the end of it, or when we only
conssingle items to the beginning, but it can be less efficient when we are mixing
snoc. Most of the time we want to
snoc, but the
<>is right-associative, which means it chains like
To solve this, we provide an operator
<>>is exactly the same as
<>, but left-associative, which means it chains like
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
If we build our
ArrayBuffers with the
PutMmonad instead of appending by using the
Builder, then we always get the efficient