Linus's stream

There is always too much to write. And too much to read. And too much to make. And too much to feel.

Everything demands to be heard now. And felt now. And thought about now. And it feels as if everything that I can't fit into this hopelessly infinitesimal slice of time called now screams at me of injustice, of being ignored, of being stolen from their deserved chance at skewing ever so slightly who I am in the moment after now.

Benchmarking fib(n) in Oak

I'm in a benchmarking mood today. So I implemented the (naive, not-memoized) Fibonacci function in both Oak and Python (the language it's probably most comparable to in performance) and ran them through some measurements.

Here's the Oak version:

fn fib(n) if n {
	0, 1 -> 1
	_ -> fib(n - 1) + fib(n - 2)
}

print(string(fib(34)) + '\n')

And here's the Python version, a direct port of the Oak one:

def fib(n):
    if n == 0 or n == 1:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

print(fib(34))

I also made a Node.js version compiled from the Oak implementation, with oak build --entry fib.oak -o out.js --web.

With the magic of Hyperfine, we see ...

Benchmark 1: node out.js
  Time (mean ± σ):     259.4 ms ±   1.9 ms    [User: 252.6 ms, System: 11.7 ms]
Benchmark 2: python3 fib.py
  Time (mean ± σ):      2.441 s ±  0.042 s    [User: 2.421 s, System: 0.011 s]
Benchmark 3: oak fib.oak
  Time (mean ± σ):     13.536 s ±  0.047 s    [User: 14.767 s, System: 0.729 s]

Summary
  'node out.js' ran
    9.41 ± 0.18 times faster than 'python3 fib.py'
   52.19 ± 0.43 times faster than 'oak fib.oak'

The gap between Python and native Oak isn't too surprising -- Oak is generally 4-5 times slower than Python on numerical code, so this looks right. But I was quite surprised to see just how much faster Node.js runs. V8 is very, very good at optimizing simple number-crunching code.

It's very encouraging to see documentation of failed approaches to problems in technical write-ups, even if brief — for example, in How to speed up the Rust compiler in 2022.

Anecdotally, at least half of the big interface/architectural design ideas I'm trying these days (and many more small approaches to performance debugging, etc.) don't end up working out, and the important ones always get a postmortem in my notes for future reference. They've proven invaluable when discussing these issues with other people or when attempting later solutions, because I can look beyond my imperfect memory to see what issues I must design against.

Random fact I learned while making some measurements:

The overhead of an Oak loop (std.loop or any other general iteration construct) in the native Go interpreter is around 2µs per loop. std.loop(10000000, fn {}) takes just under 18s.

Milestone. 5,000 paragraphs of notes (we call them "nodes") in Ligature3/Notation.

I find this implementation of a dot product in Oak so satisfyingly elegant: sum of elementwise products.

fn dot(xs, ys) sum(zip(xs, ys, fn(x, y) x * y)...)

Standard library on oaklang.org

Syntax-highlighted source code for Oak's entire standard library is now available on oaklang.org for anyone's easy browsing. I think it turned out quite well!

Instarchiver

I wrote a little pair of scripts today to download and archive my "Saved" media on Instagram. I first reached for an official API to do this, but it turns out there aren't any (at least, that I could find in a few minutes). So I decided to just scrape via internal APIs. The full scripts are here on GitHub Gist, though they may stop working at any time, obviously.

My final system ended up being in two parts:

• a "frontend" JavaScript snippet that runs in the browser console on the instagram.com domain, using the browser's stored credentials, to ping Instagram's internal APIs and generate a list of all the image URLs
• a "backend" Oak snippet that runs on my computer, locally, and downloads each image from the list of URLs to a unique filename.

Some interesting notes:

• They don't have a rate limit on their internal API (or it's very high, such that my nonstop sequential requests for many minutes never hit it).
• They have an extra layer of request authentication beyond cookies and CSRF, headers like x-ig-www-claim (an HMAC digest?) and x-asbd-id. They don't seem like message signatures because I could vary the message without changing these IDs.
• Their primary GraphQL API is quite nice. Queries are referenced using build-time generated hashes and responses support easy cursor-based pagination.
• Their internal API for media (by carousel, resolution, codec, etc.), just like Reddit's, is kind of a mess, with field names like image_versions2. I'm guessing lots of API churn?

After adding some remedial tests for poorly tested parts of the syntax stdlib, Oak now has 1000 behavior tests written in Oak itself and tested on both native and web runtimes, covering the language itself and all of the standard library's API surface! Feels like a milestone to celebrate.

A particularly satisfying patch to Oak today, ec3a188a. It simplifies implementations of the standard library's str.startsWith? and str.endsWith?.

Before, these functions compared both strings byte-by-byte, short-circuiting the loop if any mismatch was found. This was theoretically more efficient than comparing an entire substring to the given substring, because of the short-circuiting possibility. But in practice, the overhead of the extra VM ops when evaluating such iteration negated any gains.

Now, these functions create substrings of the original string that should equal the given prefix or suffix, and do a single, simple string comparison delegated to the underlying runtime. As a bonus, these one-line implementations are very simple and easy on the eyes.

fn startsWith?(s, prefix) s |> slice(0, len(prefix)) = prefix
fn endsWith?(s, suffix) s |> slice(len(s) - len(suffix)) = suffix

Especially on long inputs, the efficiency gain is significant:

Benchmark 1: oak input.oak (old implementation)
  Time (mean ± σ):      3.197 s ±  0.010 s    [User: 3.792 s, System: 0.200 s]
  Range (min … max):    3.179 s …  3.214 s    10 runs

Benchmark 2: ./oak input.oak (new implementation)
  Time (mean ± σ):      2.141 s ±  0.024 s    [User: 2.539 s, System: 0.144 s]
  Range (min … max):    2.117 s …  2.187 s    10 runs

Summary
  './oak input.oak' ran
    1.49 ± 0.02 times faster than 'oak input.oak'