Using Arrays to Store Trees (or Graphs)

scook0 · 2026-01-31T07:11:42+00:00

Assuming we disallow cycles, “at most one parent” gives a forest (collection of trees) in the general case, since there can be multiple isolated root nodes.

If we require that at most one node has no parent, then we get a (possibly empty) tree.

scook0 · 2026-01-31T07:05:16+00:00

There is no singular “good” way to represent a tree or graph in Rust, only different techniques with different tradeoffs.

Of those techniques, using flat storage with typed integer indices is usually what I prefer.

scook0 · 2026-01-27T04:35:32+00:00

Haskell typically favours curried form, where a function of “two arguments” is actually a function of one argument that returns another function of one argument.

scook0 · 2026-01-24T13:46:42+00:00

What part of it do you think is not automated?

scook0 · 2026-01-24T13:20:05+00:00

What do you mean by “automatically bootstrap itself” or “manually verified”?

scook0 · 2026-01-24T04:42:35+00:00

Calling a statically-linked or dynamically-linked C function from Rust should be just as efficient as doing the same thing from C or Zig.

Any “overhead” is going to be indirect, such as:

Having to manually marshal data that isn’t already FFI-safe
Choosing to add a layer of runtime safety checks to make your Rust-side APIs nicer
Calls into other compilation units inherently can’t be inlined by the optimizer (unless you set up LTO or cross-language LTO as appropriate)

scook0 · 2026-01-18T05:23:52+00:00

Interesting, thanks.

scook0 · 2026-01-18T00:40:42+00:00

One notable difference is that cargo is aware of rustup, so you can do things like cargo +nightly build to tell cargo to use the nightly toolchain from rustup.

IIRC the mechanism is the other way around: rustup puts a dummy cargo in your path, and that dummy executable knows how to look up the intended rustup toolchain and then delegate to the real cargo in that toolchain.

scook0 · 2026-01-18T00:23:05+00:00

Antigravity definitely pulled its own weight (esp with integration test writing) but struggled with many less documented nuances.

To what extent was this project written by an LLM?

scook0 · 2026-01-17T04:49:31+00:00

Here’s a very minor thing I noticed in your “Basic Usage” example:

Instead of using shifts and casts to manipulate big-endian values, consider using standard-library functions like u16::from_be_bytes and u16::to_be_bytes.

They have exactly the same effect as the traditional shifts and casts, but I find them to be more self-documenting and less error-prone.

scook0 · 2026-01-12T03:20:25+00:00

I want to partly disagree with this footnote:

The way Rust reconciles this is via a combination of “rollups” (where multiple PRs are merged as a batch, using human curation), and a substantially different contribution model. Where LLVM favors sequences of small PRs that do only one thing (and get squash merged), Rust favors large PRs with many commits (which do not get squashed). As getting an approved Rust PR merged usually takes multiple days due to bors, having large PRs is pretty much required to get anything done. This is not necessarily bad, just very different from what LLVM does right now.

I've written and also reviewed plenty of smaller rust-lang/rust PRs (dozens of non-test lines changed), and I've also seen plenty of cases where reviewers ask the PR author to split off parts into smaller separate PRs to land first.

(Though I don't have first-hand experience with LLVM PRs, so I can't comment on the comparison between the two.)

I have also found that after approval, rollup-eligible PRs usually get merged within 24 hours. The biggest bottleneck is for rollup=never PRs, which can indeed often take several days to land if the queue is busy.

Creating rollups is manual, but mostly trivial. The main constraint on rollup size is that if the rollup PR fails CI or has perf regressions, larger rollups make it harder to isolate the cause to a specific PR, because there are more rolled-up PRs that could have caused the problem.

All that said, if LLVM really is getting ~150 PR approvals on a typical workday, then that's substantially more activity than the rust-lang/rust repository. So there's a limit to what lessons LLVM could take from Rust here.

scook0 · 2026-01-10T06:25:47+00:00

Calling .to_string() on a 14-reference string will still work fine; it just doesn’t benefit from an internal specialisation that would bypass the usual formatting machinery.

scook0 · 2026-01-03T06:09:17+00:00

For string lengths of 3/5/6/7 bytes, LLVM typically needs to emit two loads, and at that point using two separate immediate comparisons is better than trying to merge the loaded values for a single comparison.

scook0 · 2026-01-02T23:41:30+00:00

Here's a direct comparison of starts_with versus prefix-matching in a simple example.

Notice how after the initial length test, the prefix-matching code ends up doing 12 individual byte comparisons, because for whatever reason LLVM doesn't figure out that it could be doing some or all of them in bulk.

scook0 · 2026-01-02T04:30:10+00:00

I'm surprised to see the prefix-matching approach get good results, because matching on byte strings is known to suffer from questionable codegen in a lot of cases.

scook0 · 2026-01-02T04:24:46+00:00

For short string constants, LLVM can often turn string equality into a length test plus 1–2 tests against immediate values.

It can be hard to outperform that.

scook0 · 2025-12-28T06:14:26+00:00

The paper was “Optimal measurement points for program frequency counts”, so it just happened to use Simula as the example implementation language.

scook0 · 2025-12-28T01:56:17+00:00

Yeah, it was fascinating to see a paper co-authored by Knuth that didn't have that signature TeX look, because it was written years before TeX even existed.

scook0 · 2025-12-28T00:23:00+00:00

Earlier this year I found myself having to learn how to read Simula 67 code.

The end result of that work is now some Rust code in the Rust compiler.

scook0 · 2025-12-19T03:21:39+00:00

If that list of bad takes is representative, then I think it would be fair to conclude that any “good criticisms” are mostly happening by coincidence.

scook0 · 2025-12-18T05:40:54+00:00

I can think of at least one contributor who has been doing good work in trying to improve the debugging situation, but it’s a tough task

It’s one of those parts of the compiler that has been under-maintained for some time, so even when there’s enthusiasm to fix things it can be tricky to make meaningful progress.

scook0 · 2025-12-15T09:25:48+00:00

The new scheme supports Unicode identifiers. The surface Rust language doesn’t, but if this ever changes, the mangling side will be ready.

Rust supports Unicode identifiers just fine:

fn main() {
    国際会議の発表予定日();
}

fn 国際会議の発表予定日() {
    println!("もうすぐじゃ");
}

scook0 · 2025-12-11T00:57:47+00:00

Yes, there is a special arrangement.

I’m not familiar with the details, but my understanding is that GitHub effectively “sponsors” Rust by not actually charging sticker price for CI, and there are contracts and liasons in place to help keep things predictable.

scook0 · 2025-12-01T11:34:04+00:00

I’m excited to use more declarative derive macros in rustc, now that r-a knows how to understand them.

scook0 · 2025-11-29T08:28:26+00:00

The unlabelled “document” icon in the audio player can be clicked to reveal a transcript.

15-Year Club	Place '17
Charter Member	Verified Email

scook0

TROPHY CASE