<style>
.reveal {
font-size: 24px;
}
.reveal section img {
background:none;
border:none;
box-shadow:none;
}
pre.graphviz {
box-shadow: none;
}
</style>
# Search trees
*(AMH sections 12.1-12.3)*
Performance Engineering, Lecture 5
Sergey Slotin
May 14, 2022
---
```cpp
int lower_bound(int x) {
int l = 0, r = n - 1;
while (l < r) {
int m = (l + r) / 2;
if (t[m] >= x)
r = m;
else
l = m + 1;
}
return t[l];
}
```
----
```cpp
template <class _Compare, class _ForwardIterator, class _Tp>
_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
__lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
{
typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
difference_type __len = _VSTD::distance(__first, __last);
while (__len != 0)
{
difference_type __l2 = _VSTD::__half_positive(__len);
_ForwardIterator __m = __first;
_VSTD::advance(__m, __l2);
if (__comp(*__m, __value_))
{
__first = ++__m;
__len -= __l2 + 1;
}
else
__len = __l2;
}
return __first;
}
```
----
![](https://en.algorithmica.org/hpc/data-structures/img/search-std.svg =500x)
----
```nasm
│35: mov %rax,%rdx
0.52 │ sar %rdx
0.33 │ lea (%rsi,%rdx,4),%rcx
4.30 │ cmp (%rcx),%edi
65.39 │ ↓ jle b0
0.07 │ sub %rdx,%rax
9.32 │ lea 0x4(%rcx),%rsi
0.06 │ dec %rax
1.37 │ test %rax,%rax
1.11 │ ↑ jg 35
```
- Control hazard: the branch is impossible to predict if queries are random
- Data hazard: we need to wait for the middle key to be fetched
---
## Removing branches
----
```cpp
int lower_bound(int x) {
int *base = t, len = n;
while (len > 1) {
int half = len / 2;
base = (base[half] < x ? &base[half] : base);
len -= half;
}
return *(base + (*base < x));
}
```
----
![](https://en.algorithmica.org/hpc/data-structures/img/search-branchless.svg =500x)
Why worse on larger arrays? *Speculation → prefetching* <!-- .element: class="fragment" data-fragment-index="2" -->
----
```cpp
int lower_bound(int x) {
int *base = t, len = n;
while (len > 1) {
int half = len / 2;
__builtin_prefetch(&base[(len - half) / 2]);
__builtin_prefetch(&base[half + (len - half) / 2]);
base = (base[half] < x ? &base[half] : base);
len -= half;
}
return *(base + (*base < x));
}
```
----
![](https://en.algorithmica.org/hpc/data-structures/img/search-branchless-prefetch.svg =500x)
Still grows slightly faster as the branchy version also prefetches "grandchildren" and further descendants
---
![](https://en.algorithmica.org/hpc/data-structures/img/binary-search.png =500x)
- *Spatial locality*: only okay for the last 3 to 4 requests
- *Temporal locality*: only okay for the first dozen or so requests
----
```cpp
int lower_bound(int x) {
int l = 0, r = n - 1;
while (l < r) {
int m = l + rand() % (r - l);
if (t[m] >= x)
r = m;
else
l = m + 1;
}
return t[l];
}
```
----
![](https://en.algorithmica.org/hpc/data-structures/img/search-random.svg =500x)
~6x slower of larger arrays, although theoretically should only perform $\frac{2 \ln n}{\log_2 n} = 2 \ln 2 \approx 1.386$ more comparisons
----
![](https://i.imgur.com/DJ8oISX.png)
----
![](https://en.algorithmica.org/hpc/data-structures/img/binary-heat.png =500x)
The real problem: hot and cold elements are grouped together
---
**Michaël Eytzinger** is a 16th-century Austrian nobleman known for his work on genealogy, particularly for a system for numbering ancestors called *ahnentafel* (German for "ancestor table")
----
![](https://upload.wikimedia.org/wikipedia/commons/5/5c/Eytzinger_-_Thesaurus_principum.jpg =600x)
*Thesaurus principum hac aetate in Europa viventium Cologne, 1590*
----
- First, the person themselves is listed as number 1
- Then, recursively, for each person numbered $k$, their father is listed as $2k$, and their mother is listed as $(2k+1)$
----
Example for **Paul I**, the great-grandson of **Peter the Great**:
1. Paul I
2. Peter III (Paul’s father)
3. Catherine II (Paul’s mother)
4. Charles Frederick (Peter’s father, Paul’s paternal grandfather)
5. Anna Petrovna (Peter’s mother, Paul’s paternal grandmother)
6. Christian August (Catherine’s father, Paul’s maternal grandfather)
7. Johanna Elisabeth (Catherine’s mother, Paul’s maternal grandmother)
Apart from being compact, it has some nice properties:
<!-- .element: class="fragment" data-fragment-index="1" -->
* Ancestors are sorted by "distance" from the first person <!-- .element: class="fragment" data-fragment-index="2" -->
* All even-numbered persons $>1$ are male and all odd-numbered are female <!-- .element: class="fragment" data-fragment-index="3" -->
* You can find the number of an ancestor knowing their descendants' genders <!-- .element: class="fragment" data-fragment-index="4" -->
Example: Peter the Great's bloodline is:
Paul I → Peter III → Anna Petrovna → Peter the Great,
so his number should be $((1 \times 2) \times 2 + 1) \times 2 = 10$
<!-- .element: class="fragment" data-fragment-index="5" -->
---
## Back to Computer Science
This enumeration has been widely used for implicit implementations of heaps, segment trees, and other binary tree structures
![](https://en.algorithmica.org/hpc/data-structures/img/eytzinger.png)
----
![](https://en.algorithmica.org/hpc/data-structures/img/eytzinger-search.png =600x)
![](https://en.algorithmica.org/hpc/data-structures/img/eytzinger-heat.png =600x)
Temporal locality is much better
----
```cpp
int a[n], t[n + 1]; // the original sorted array and the eytzinger array we build
// ^ we need one element more because of one-based indexing
void eytzinger(int k = 1) {
static int i = 0; // <- careful running it on multiple arrays
if (k <= n) {
eytzinger(2 * k);
t[k] = a[i++];
eytzinger(2 * k + 1);
}
}
```
---
## Searching
Instead of ranges, start with $k=1$ and execute until $k < n$:
- If $x < a_k$, go left: $k := 2k$
- Otherwise, go right: $k := 2k + 1$
But if $k > n$, how do we restore the result? <!-- .element: class="fragment" data-fragment-index="1" -->
----
```
array: 1 2 3 4 5 6 7 8
eytzinger: 4 2 5 1 6 3 7 8
1st range: --------------- k := 1
2nd range: ------- k := 2*k (=2)
3rd range: --- k := 2*k + 1 (=5)
4th range: - k := 2*k + 1 (=11)
```
- Unless the answer is the last element, we compare $x$ against it at some point
- After we learn that $ans \geq x$, we start comparing $x$ against elements to the left
- All these comparisons will evaluate true ("leading to the right")
- $\implies$ We need to "cancel" some number of riht turns
<!-- .element: class="fragment" data-fragment-index="1" -->
----
- Right-turns are recorded in the binary notation of $k$ as 1-bits
- Right-shift $k$ by the number of trailing ones in its binary notation
- To do it, invert the bits of $k$ and use "find first set"
```cpp
int lower_bound(int x) {
int k = 1;
while (k <= n)
k = 2 * k + (t[k] < x);
k >>= __builtin_ffs(~k);
return t[k];
}
```
Note that $k$ will be zero if binary search returned no result
(all turns were right-turns and got canceled)
----
![](https://en.algorithmica.org/hpc/data-structures/img/search-eytzinger.svg =500x)
---
## Optimization: Prefetching
```cpp
alignas(64) int t[n + 1];
int lower_bound(int x) {
int k = 1;
while (k <= n) {
__builtin_prefetch(t + k * 16);
k = 2 * k + (t[k] < x);
}
k >>= __builtin_ffs(~k);
return t[k];
}
```
What is happening? What is $k \cdot B$?
It is $k$'s great-great-grandfather!
<!-- .element: class="fragment" data-fragment-index="1" -->
----
- When we fetch $k \cdot B$, we also fetch its $B - 1$ cache line neighbors
- If the array is **aligned**, they will all be our grandfathers
- As i/o is pipelined, we are always prefetching 4 levels in advance
![](https://en.algorithmica.org/hpc/data-structures/img/eytzinger.png)
----
![](https://en.algorithmica.org/hpc/data-structures/img/search-eytzinger-prefetch.svg =500x)
---
![](https://en.algorithmica.org/hpc/data-structures/img/search-eytzinger-small.svg =500x)
What are these bumps?
----
```cpp
t[0] = -1; // an element that is less than x
iters = std::__lg(n + 1);
int lower_bound(int x) {
int k = 1;
for (int i = 0; i < iters; i++)
k = 2 * k + (t[k] < x);
int *loc = (k <= n ? t + k : t);
k = 2 * k + (*loc < x);
k >>= __builtin_ffs(~k);
return t[k];
}
```
----
![](https://en.algorithmica.org/hpc/data-structures/img/search-eytzinger-branchless.svg =500x)
---
## B-trees
$B \ge 2$ keys in each node, increasing branching factor and reducing tree height
----
![](https://en.algorithmica.org/hpc/data-structures/img/b-tree.jpg =500x)
A B-tree of order 4
----
- For RAM, set $B$ to be the cache line size so that we don't waste reads
- $B=16$ reduces the tree height by $\frac{\log_2 n}{\log_17 n} = \frac{\log 17}{\log 2} = \log_2 17$ times
---
We can make static B-trees **implicit** by generalizing the Eytzinger numeration:
- The root node is numbered $0$
- Node $k$ has $(B + 1)$ child nodes numbered $\{k \cdot (B + 1) + i + 1\}$ for $i \in [0, B]$
----
> "The more you think about what the B in B-trees means, the better you understand B-trees"
- **B-tree**: balanced, broad, bushy, Boeing, Bayer
- **S-tree**: static, succinct, speedy, SIMDized <!-- .element: class="fragment" data-fragment-index="1" -->
----
```cpp
const int B = 16;
int nblocks = (n + B - 1) / B;
int btree[nblocks][B];
int go(int k, int i) { return k * (B + 1) + i + 1; }
```
----
```cpp
void build(int k = 0) {
static int t = 0;
if (k < nblocks) {
for (int i = 0; i < B; i++) {
build(go(k, i));
btree[k][i] = (t < n ? a[t++] : INT_MAX);
}
build(go(k, B));
}
}
```
---
### Searcihng
```cpp
int mask = (1 << B);
for (int i = 0; i < B; i++)
mask |= (btree[k][i] >= x) << i;
int i = __builtin_ffs(mask) - 1;
// now i is the number of the correct child node
```
----
```cpp
typedef __m256i reg;
int cmp(reg x_vec, int* y_ptr) {
reg y_vec = _mm256_load_si256((reg*) y_ptr); // load 8 sorted elements
reg mask = _mm256_cmpgt_epi32(x_vec, y_vec); // compare against the key
return _mm256_movemask_ps((__m256) mask); // extract the 8-bit mask
}
```
----
```cpp
int mask = ~(
cmp(x, &btree[k][0]) +
(cmp(x, &btree[k][8]) << 8)
);
int i = __builtin_ffs(mask) - 1;
k = go(k, i);
```
----
Problem: a local lower bound doesn't have to exist in the leaf node
We could also do indexing tricks to restore it, but instead we update it while descending <!-- .element: class="fragment" data-fragment-index="1" -->
----
```cpp
int lower_bound(int _x) {
int k = 0, res = INT_MAX;
reg x = _mm256_set1_epi32(_x);
while (k < nblocks) {
int mask = ~(
cmp(x, &btree[k][0]) +
(cmp(x, &btree[k][8]) << 8)
);
int i = __builtin_ffs(mask) - 1;
if (i < B)
res = btree[k][i];
k = go(k, i);
}
return res;
}
```
----
![](https://en.algorithmica.org/hpc/data-structures/img/search-btree.svg =500x)
---
Turn hugepages on:
```cpp
const int P = 1 << 21; // page size in bytes (2MB)
const int T = (64 * nblocks + P - 1) / P * P; // can only allocate whole number of pages
btree = (int(*)[16]) std::aligned_alloc(P, T);
madvise(btree, T, MADV_HUGEPAGE);
```
----
```cpp
constexpr int height(int n) {
// grow the tree until its size exceeds n elements
int s = 0, // total size so far
l = B, // size of the next layer
h = 0; // height so far
while (s + l - B < n) {
s += l;
l *= (B + 1);
h++;
}
return h;
}
const int H = height(N);
```
Provide the compiler with the exact number of iterations
----
```cpp
unsigned rank(reg x, int* y) {
reg a = _mm256_load_si256((reg*) y);
reg b = _mm256_load_si256((reg*) (y + 8));
reg ca = _mm256_cmpgt_epi32(a, x);
reg cb = _mm256_cmpgt_epi32(b, x);
reg c = _mm256_packs_epi32(ca, cb);
int mask = _mm256_movemask_epi8(c);
// we need to divide the result by two because we call movemask_epi8 on 16-bit masks:
return __tzcnt_u32(mask) >> 1;
}
void permute(int *node) {
const reg perm = _mm256_setr_epi32(4, 5, 6, 7, 0, 1, 2, 3);
reg* middle = (reg*) (node + 4);
reg x = _mm256_loadu_si256(middle);
x = _mm256_permutevar8x32_epi32(x, perm);
_mm256_storeu_si256(middle, x);
}
```
----
```cpp
const int translate[17] = {
0, 1, 2, 3,
8, 9, 10, 11,
4, 5, 6, 7,
12, 13, 14, 15,
0
};
void update(int &res, int* node, unsigned i) {
int val = node[translate[i]];
res = (i < B ? val : res);
}
```
----
```cpp
int lower_bound(int _x) {
int k = 0, res = INT_MAX;
reg x = _mm256_set1_epi32(_x - 1);
for (int h = 0; h < H - 1; h++) {
unsigned i = rank(x, &btree[k]);
update(res, &btree[k], i);
k = go(k, i);
}
// the last branch:
if (k < nblocks) {
unsigned i = rank(x, btree[k]);
update(res, &btree[k], i);
}
return res;
}
```
----
![](https://en.algorithmica.org/hpc/data-structures/img/search-btree-optimized.svg =500x)
----
- The `update` procedure is costly but useless 16 times out of 17
- We perform a non-constant number of iterations, causing pipeline stalls
---
## B+ trees
- *Internal nodes* store up to $B$ keys and $(B + 1)$ pointers to child nodes
- *Data nodes* or *leaves* store up to $B$ keys, the pointer to the next leaf node
----
![](https://en.algorithmica.org/hpc/data-structures/img/bplus.png =500x)
A B+ tree of order 4
----
- The last node or its next neighbor has the local lower bound (no `update`)
- The depth is constant because B+ trees grow at the root (no branching)
----
```cpp
// number of B-element blocks in a layer with n keys
constexpr int blocks(int n) {
return (n + B - 1) / B;
}
// number of keys on the layer previous to one with n keys
constexpr int prev_keys(int n) {
return (blocks(n) + B) / (B + 1) * B;
}
// height of a balanced n-key B+ tree
constexpr int height(int n) {
return (n <= B ? 1 : height(prev_keys(n)) + 1);
}
// where the layer h starts (layer 0 is the largest)
constexpr int offset(int h) {
int k = 0, n = N;
while (h--) {
k += blocks(n) * B;
n = prev_keys(n);
}
return k;
}
```
----
```cpp
const int H = height(N);
const int S = offset(H); // the tree size is the offset of the (non-existent) layer H
int *btree; // the tree itself is stored in a single hugepage-aligned array of size S
memcpy(btree, a, 4 * N);
for (int i = N; i < S; i++)
btree[i] = INT_MAX;
```
----
```cpp
for (int h = 1; h < H; h++) {
for (int i = 0; i < offset(h + 1) - offset(h); i++) {
// i = k * B + j
int k = i / B,
j = i - k * B;
k = k * (B + 1) + j + 1; // compare to the right of the key
// and then always to the left
for (int l = 0; l < h - 1; l++)
k *= (B + 1);
// pad the rest with infinities if the key doesn't exist
btree[offset(h) + i] = (k * B < N ? btree[k * B] : INT_MAX);
}
}
for (int i = offset(1); i < S; i += B)
permute(btree + i);
```
---
```cpp
int lower_bound(int _x) {
unsigned k = 0; // we assume k already multiplied by B to optimize pointer arithmetic
reg x = _mm256_set1_epi32(_x - 1);
for (int h = H - 1; h > 0; h--) {
unsigned i = permuted_rank(x, btree + offset(h) + k);
k = k * (B + 1) + i * B;
}
unsigned i = direct_rank(x, btree + k);
return btree[k + i];
}
```
----
![](https://en.algorithmica.org/hpc/data-structures/img/search-bplus.svg =500x)
(Spikes at the end due to L1 TLB spill)
----
![](https://en.algorithmica.org/hpc/data-structures/img/search-all.svg =500x)
----
![](https://en.algorithmica.org/hpc/data-structures/img/search-relative.svg =500x)
----
To measure *reciprocal throughput*:
```cpp
clock_t start = clock();
for (int i = 0; i < m; i++)
checksum ^= lower_bound(q[i]);
float seconds = float(clock() - start) / CLOCKS_PER_SEC;
printf("%.2f ns per query\n", 1e9 * seconds / m);
```
To measure *real* latency:
```cpp
int last = 0;
for (int i = 0; i < m; i++) {
last = lower_bound(q[i] ^ last);
checksum ^= last;
}
```
----
![](https://en.algorithmica.org/hpc/data-structures/img/search-relative-latency.svg =500x)
----
![](https://en.algorithmica.org/hpc/data-structures/img/search-bplus-other.svg =500x)
----
![](https://en.algorithmica.org/hpc/data-structures/img/search-latency-bplus.svg =500x)
----
### Possible optimizations
- Non-uniform block sizes
- Grouping generations together
- Prefetching specific layers
- Permute last layer as well if we need the index and not the value
- Reverse the order in which layers are stored
- Using `blend` instead of `packs`
- Using `popcount` instead of `tzcnt`
- Defining key $i$ as *maximum* on subtree $i$ instead of minimum on $(i + 1)$
- Rewrite the whole thing in assembly
---
As a *dynamic* tree?
----
![](https://en.algorithmica.org/hpc/data-structures/img/search-set-relative.svg =500x)
----
![](https://en.algorithmica.org/hpc/data-structures/img/search-set-relative-all.svg =500x)
---
## B− Tree
- Nodes in a B− tree do not store pointers or any metadata except for the pointers to internal node children
- We define key $i$ to be the *maximum* key in the subtree of the child $i$ instead of the *minimum* key in the subtree of the child $(i + 1)$
- We use a node size of $B=32$, which is much smaller than typical
----
```cpp
const int R = 1e8;
alignas(64) int tree[R];
for (int i = 0; i < R; i++)
tree[i] = INT_MAX;
const int B = 32;
int root = 0; // where the keys of the root start
int n_tree = B; // number of allocated array cells
int H = 1; // current tree height
```
To "allocate" a new node, we simply increase `n_tree` by $B$ or $2B$
----
- A leaf node has up to $(B - 1)$ keys but is padded to $B$ elements with infinities.
- An internal node has up to $(B - 2)$ keys padded to $B$ elements and up to $(B - 1)$ indices of its child nodes, also padded to $B$ elements.
- We use indices instead of pointers to save cache space and make SIMD faster
- We store indices right after the keys in memory
- We intentionally "waste" one array cell in leaf nodes and $2+1=3$ cells in internal nodes to store temporary result during a node split
---
```cpp
reg cmp(reg x, int *node) {
reg y = _mm256_load_si256((reg*) node);
return _mm256_cmpgt_epi32(x, y);
}
// returns how many keys are less than x
unsigned rank32(reg x, int *node) {
reg m1 = cmp(x, node);
reg m2 = cmp(x, node + 8);
reg m3 = cmp(x, node + 16);
reg m4 = cmp(x, node + 24);
// take lower 16 bits from m1/m3 and higher 16 bits from m2/m4
m1 = _mm256_blend_epi16(m1, m2, 0b01010101);
m3 = _mm256_blend_epi16(m3, m4, 0b01010101);
m1 = _mm256_packs_epi16(m1, m3); // can also use blendv here, but packs is simpler
unsigned mask = _mm256_movemask_epi8(m1);
return __builtin_popcount(mask);
}
```
----
```cpp
int lower_bound(int _x) {
unsigned k = root;
reg x = _mm256_set1_epi32(_x);
for (int h = 0; h < H - 1; h++) {
unsigned i = rank32(x, &tree[k]);
k = tree[k + B + i];
}
unsigned i = rank32(x, &tree[k]);
return tree[k + i];
}
```
---
```cpp
struct Precalc {
alignas(64) int mask[B][B];
constexpr Precalc() : mask{} {
for (int i = 0; i < B; i++)
for (int j = i; j < B - 1; j++)
// everything from i to B - 2 inclusive needs to be moved
mask[i][j] = -1;
}
};
constexpr Precalc P;
```
----
```cpp
void insert(int *node, int i, int x) {
// need to iterate right-to-left to not overwrite the first element of the next lane
for (int j = B - 8; j >= 0; j -= 8) {
// load the keys
reg t = _mm256_load_si256((reg*) &node[j]);
// load the corresponding mask
reg mask = _mm256_load_si256((reg*) &P.mask[i][j]);
// mask-write them one position to the right
_mm256_maskstore_epi32(&node[j + 1], mask, t);
}
node[i] = x; // finally, write the element itself
}
```
----
```cpp
// move the second half of a node and fill it with infinities
void move(int *from, int *to) {
const reg infs = _mm256_set1_epi32(INT_MAX);
for (int i = 0; i < B / 2; i += 8) {
reg t = _mm256_load_si256((reg*) &from[B / 2 + i]);
_mm256_store_si256((reg*) &to[i], t);
_mm256_store_si256((reg*) &from[B / 2 + i], infs);
}
}
```
----
```cpp
void insert(int _x) {
// the beginning of the procedure is the same as in lower_bound,
// except that we save the path in case we need to update some of our ancestors
unsigned sk[10], si[10]; // k and i on each iteration
// ^------^ We assume that the tree height does not exceed 10
// (which would require at least 16^10 elements)
unsigned k = root;
reg x = _mm256_set1_epi32(_x);
for (int h = 0; h < H - 1; h++) {
unsigned i = rank32(x, &tree[k]);
// optionally update the key i right away
tree[k + i] = (_x > tree[k + i] ? _x : tree[k + i]);
sk[h] = k, si[h] = i; // and save the path
k = tree[k + B + i];
}
unsigned i = rank32(x, &tree[k]);
// we can start computing the is-full check before insertion completes
bool filled = (tree[k + B - 2] != INT_MAX);
insert(tree + k, i, _x);
if (filled) {
// the node needs to be split, so we create a new leaf node
move(tree + k, tree + n_tree);
int v = tree[k + B / 2 - 1]; // new key to be inserted
int p = n_tree; // pointer to the newly created node
n_tree += B;
for (int h = H - 2; h >= 0; h--) {
// ascend and repeat until we reach the root or find a the node is not split
k = sk[h], i = si[h];
filled = (tree[k + B - 3] != INT_MAX);
// the node already has a correct key (the right one)
// and a correct pointer (the left one)
insert(tree + k, i, v);
insert(tree + k + B, i + 1, p);
if (!filled)
return; // we're done
// create a new internal node
move(tree + k, tree + n_tree); // move keys
move(tree + k + B, tree + n_tree + B); // move pointers
v = tree[k + B / 2 - 1];
tree[k + B / 2 - 1] = INT_MAX;
p = n_tree;
n_tree += 2 * B;
}
// if reach here, this means we've reached the root,
// and it was split into two, so we need a new root
tree[n_tree] = v;
tree[n_tree + B] = root;
tree[n_tree + B + 1] = p;
root = n_tree;
n_tree += 2 * B;
H++;
}
}
```
---
![](https://en.algorithmica.org/hpc/data-structures/img/btree-absolute.svg =800x)
----
![](https://en.algorithmica.org/hpc/data-structures/img/btree-relative.svg =800x)
----
![](https://en.algorithmica.org/hpc/data-structures/img/btree-absl.svg =800x)
---
### Other operations
- Deletion? <!-- .element: class="fragment" data-fragment-index="1" -->
- Iteration? <!-- .element: class="fragment" data-fragment-index="2" -->
- Drop-in `std::set` replacement? <!-- .element: class="fragment" data-fragment-index="3" -->
{"metaMigratedAt":"2023-06-17T00:49:22.702Z","metaMigratedFrom":"YAML","title":"Search trees","breaks":"true","slideOptions":"{\"theme\":\"white\"}","contributors":"[{\"id\":\"045b9308-fa89-4b5e-a7f0-d8e7d0b849fd\",\"add\":42987,\"del\":18985}]"}