paniq

Following conditions need to be met to make the C heap serializable:

1. get start of allocation from offset pointer
2. get size of allocation
3. addresses appearing in allocation must be tagged as pointers (1:64 metadata)
4. associate foreign pointers/allocations with plugins; the simplest is dlsym, but there's also file handles, graphics resources, JIT functions, stack vars etc.

(4) is what makes the whole affair very interesting.

above conditions also make it possible to run a GC. it is also possible to perfectly deduplicate the heap in subquadratic time, to validate pointers, guard against bad load/stores & to merge different heaps.

paniq

Loop Integration

by Leonard Ritter

This article proposes loop integration, a generalization of loop unrolling to an arithmetic loop summation operator that permits static loop analysis and expansion with logarithmic complexity.

Rationale

In program optimization, we often encounter loops whose complexity we aim to reduce. Some loops can even be removed completely through folding of constant expressions. The classical technique for this is called loop unrolling: apply initial arguments to the loop body, evaluate, and if the result is constant, then reapply it again, and so forth, until the only path left leads out of the loop.

paniq

# scattersort
# by Leonard Ritter

inline changebits (arr)
    # find bits that change over the set
    local mn : u64 = -1:u64
    local mx : u64
    for v in arr
        mn = mn & v
        mx = mx | v

paniq

idea for massively parallelizable unstable O(n log n) sort

let's use this simple example, sorting 9 values with 8-bit keys:

00000011
00000100
01011010
00110011
00010110
10001000

paniq

The Wireworld CA encoding does not seem to be axially independent:

00 = empty
01 = wire
10 = head (only on wire)
11 = tail (only on wire)

While bit 1 always indicates the presence of a charge, bit 0 does not reliably encode the presence of a wire, and is repurposed by the signal state.

paniq

Scoped Refcounting

by Leonard Ritter, Duangle GbR

In the course of developing a programmable compiler that aspires to become as convenient as a scripting language, I've identified only two popular features of dynamically typed languages that are non-trivial to implement in compiled languages:

1. Polymorphic return values: A conditional block returns a value of different type on each path. This is a specific instance of a greater issue in unstructured control flow: we enter a block of code with differently typed arguments (as in SSA and CPS, there are no "return values" - we only goto). Do we inline those arguments and specialize the blocks for the different types, possibly causing an explosion of code or do we attempt to merge the types, possibly combining them into a sum type and putting more weight on runtime evaluation? A good heuristic for this question is still missing.
2. Garbage collection: All acyclical digraphs can be cleaned up with reference counting. A garbage collec

paniq

Hash Integrals: Slice Hashing below O(log n)

Update: the technique employed here is called a polynomial rolling hash as I have recently learned.

Some notes on how to enable fast computation of hashes of slices of vectors (below complexity O(log n)), as well as hashes of joined vectors.

We start from first principles. To simplify matters, a vector has the same element type as our hash, which stands in for the actual data element we wish to hash.

Each vector v is paired with a secondary summed-hash vector h of which each element i stores hash(v[0..i]) to form a tuple of vectors (v,h). Appending a new element p to v is then performed in O(1) as follows, with a simple auxiliary linear operation:

paniq

Practical Type Coercion

A quick summary of how the author sees type coercion / casting / conversion in programming languages, followed by a somewhat novel proposal.

Type casting is a special form of functional programming, where we rewrite a function B(source:A, options...) as a cast operation A -> B<options...>, where B is now a type template, and options... is an optional list of auxiliary compile time constants that become attributes of the type template.

Type casting is effectively data conversion. You have source data in format A that you would like to transform to target data in format B. And as in actual data conversion, we have two levels of quality:

1. Lossless conversion, which transforms the data without destroying information, which means the conversion is invertible, the mapping is bijective and time-symmetrical. Some examples of a lossless conversion are "big endian to little endian", "upcast type to tagged union", "sign-extend integer from 32-bit to 64-bit",

paniq

differentiable smoothfloor function:

f(x) = x - sin(2πx)/(2π)

(rescaled integral of (1/2 -1/2*cos(2πx))^t for t = 1)

the function can be applied recursively for harder floors

alternative: differentiable smoothable infinite frequency waves (for t = 0..1):

paniq

def measure_error_variance(values):
    avgs = []
    for stp in range(2,N):
        for u in range(N):
            v = u + stp
            assert (u != v)
            ct = 0
            x = 0
            for i in range(u,v):
                x += values[i%N]