paniq

The Arcmem Binary Interchange Format

The Arcmem heap can be partially serialized to a streamable format, here called .arc (spoken as "dot-arc"). This format is not a file format per se, but can be used as the payload of one.

Each .arc describes heap objects in arbitrary order, with the requirement that each object must be declared, in full or as forward declaration, before it can be referenced. An object may only be fully declared once, and forward declared once only before the full declaration appears.

By convention, the first element of a stream is considered to be the root object by which all other objects are reachable.

The header of a heap declaration looks as follows:

paniq

Arcmem: Fixing The C Memory Model

by Leonard Ritter, May 3rd 2024

Introduction

As part of bootstrapping the next iteration of the Scopes compiler, which, until now, oriented itself heavily along LLVM and C semantics, the author tackled the general issue of operating on memory, specifically solving longstanding usability issues that C programmers should be intimately familiar with, which increase cognitive load and make programming in C a never-ending nightmare. These issues are:

• There are at least three kinds of pointers which all use the same type but need to be treated differently: global, stack and heap.
• Rules of memory ownership and sharing are all informally specified, and difficult to enforce in a heterogeneous environment.
• Stack allocations may lead to stack overflow.

paniq

sdl wgpu := do
    using import backport
    use-backport-globals;
    import sdl wgpu

using import print String glm slice
using import compiler.target.SPIR-V

paniq

# optimally encoding a set of two integers

N := 32
N/2 := N // 2
NUMVALS := N * (N + 1) // 2

fn trienc (x y)
    assert (x < N)
    assert (y < N)
    assert (x >= y)

paniq

# note that with a custom heap implementation, these features can be supported
# without tagging.
# for more info, see
#   https://gist.github.com/paniq/429c96446e3e7e01f0c860987049d1cf

using import struct print format C.stdio

malloc := extern 'malloc (function voidstar usize)
realloc := extern 'realloc (function voidstar voidstar usize)
free := extern 'free (function void voidstar)

paniq

Idea for temporal bitnet optimization: one could perhaps avoid needing float accumulators during training; say we alter a random number of weights each pass (for a 1-bit bitnet that's a xor, always). the xor bits can be reconstructed from a global random seed value. if we memorize the resulting loss delta and the seeds of the past N steps, then we can compute a moving average for each xor bit with 1/N sub-bit precision.

with this, one could try doing N prospective measurements, and then accumulate the results (which cost very little in terms of space - so N could be high!) to get a really good and smooth gradient; that approach might be able to replace Adam completely.

Come to think of it, that approach might even work for float weights and Forward Gradient Optimization, since the seed can also be used to create random floats with gaussian distribution.

paniq

# perfect hash configuration:
    hash all values, then find substring of bits where keys don't
    collide within K attempts.
using import hash Array String format

# if false, use u64 xxhash, otherwise 128-bit scrambled polynomial rolling hash
USE_U128 := true

paniq

using import struct enum print itertools

enum Token plain
    None
    Word
    Open
    Close

@@ finite-state-machine
struct Tokenizer

paniq

64-bit Pointer Basing in O(1)

A problem that occasionally comes up when walking a dynamically typed heap is to find the base address for a given pointer i.e. the start of an allocation. With this ability, the following features are possible:

• Reference-counting slices of dynamic arrays
• Faster lookup during conservative garbage collection
• A copy-on-write that changes the pointer written to
• Bidirectional edges within objects (not just only at the boundary)

paniq

# Squarify
# subdivide a rectangle into squares whose sum have the same area using
# the identity:
#
#   w * h = min(w, h) ** 2 + (max(w,h) - min(w,h)) * min(w, h)

W,H = 1920, 1080

w,h = W, H
lengths = []