# Trustworthy Mandelbrot

# 2.1 Optimisations

• bit-packed quad tree saves memory (to be investigated if it saves/costs time vs byte-packed quad tree)
• storing edges as pairs of node ids in two sorted arrays (for binary search) saves memory compared to pointers and linked lists
• when constructing the graph, use one unique node for all exterior targets
• speculatively allocate a large graph and fill it in one pass, giving up on overflow, instead of calculaing size first in another pass
• uint24 for node ids in edge arrays is too slow, uint32 is less frugal space-wise but much faster
• glibc qsort() may allocate up to 1/4 of physical memory, which is highly undesirable when there are many threads
• naively-implemented binary most-significant-digit radix sort with uint32 keys is very competitive time-wise with glibc qsort()
• each thread allocates all its memory up-front, and manages it internally (memory allocation/deallocation mostly follows a stack pattern, the remainder can be solved by moving the top item(s) to another stack at the other end of memory)
• store Julia sets (compressed) on OOM, to avoid having to recalculate when the concurrency is reduced and more memory is available per thread

# 4.1 Dump

0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 10 / 11

This represents about 5 days of computation (wall-clock time; mostly with 16 threads active) on an AMD 2700X CPU with 32GB RAM.

# 4.2 Format

File format:

• ASCII header contains
  • magic data format identifying string
  • complex interval that the image represents (currently always [-2.75,1.25]+[-2,2]i)
  • number of branch nodes in the quad tree, from which the number of size bits for branch nodes is determined (see TREE_size_size_for_tree_size() in tree.h, it would be better for archival if the actually used size size were stored in the file directly)
  • indication that binary data follows
  • header terminated by \n\f (new line followed by form feed)
• uncompressed bit-packed binary quad tree follows

  • sequence of 8-bit bytes, bits in little endian order in each byte

  • last byte may have unused trailing bits with arbitrary values

  • 2 bits per node

    • 00 red (zone of unknown)
    • 01 black (100% interior)
    • 10 white (100% exterior)
    • 11 branch (size in units of 2 bits in even number of following bits)

  • following a branch node and its size, the 4 quadrants follow in order (bottom left, bottom right, top left, top right)

  • last two nodes of tree are unused (set to black) when the interval is symmetric about the real axis (redundancy elimination)