HNHacker News
TopNewBestAskShowJobs

matklad

1,382 karma · joined February 17, 2014

https://github.com/matklad
submissionscomments
matklad··on Unified versus Split Diff
Like this:

https://user-images.githubusercontent.com/1711539/277602101-...

matklad··on Unix Structured Concurrency
Two scenarios where this breaks:

* parent process is killed after it forks, but before it calls `waitpid`. Nothing even attempts to kill&wait for the child

* parent process is killed after it issues `waitpid` syscall. The child continues to happily execute while the parent is dead.

matklad··on Unix Structured Concurrency
waitpid is inherently racy. wait is covered by

    This can not be achieved using a pattern equivalent to { ... }.
    The parent process itself might be abruptly killed, and the finally blocks / destructors / atexit hooks are not run in this case.
matklad··on How LSP could have been better
No, I am just spelling-impaired (even in my mother tongue) :)
matklad··on How LSP could have been better
There's some truth to this! I strongly encourage to architect language servers as libraries first and foremost, with LSP being a relatively thin layer on top of protocol-agnostic library, and only _one_ of the ways to consume the results of the analysis.

At the same time, libraries, sadly, do not actually exist. I can not easily cook up an `.so` and then hook that up with Emacs, Vim, VS Code, and Helix. Moreover, any crash in an `.so` library brings down the whole process, which isn't a good idea for an IDE.

Maybe several years in the future we get an actually good implementation of libraries (I have high hopes for WebAssembly component model), but until then, text-over-stdio can actually be better in practice for some use-cases!

matklad··on How LSP could have been better
Agree this is not a problem. rust-analyzer also includes a boatload of custom extensions. Here's how "query type of the selected expression" works, for example:

https://github.com/rust-lang/rust-analyzer/blob/master/docs/...

matklad··on Role of Algorithms
I think our observations are consistent: I would say that candidates ability to solve leetcode-style problem during an interview reveals very little of their ability to code in the small or in the large. "Algorithms during code interview" is a completely separate genre to what's discussed in the article.

To give a positive example here: when someone sends a 1k lines PR implementing a new big feature, how well a body of a single function is implemented is often a good predictor of whether the whole PR makes sense.

matklad··on Role of Algorithms
https://cses.fi/problemset/ is by far the best resource I know.
matklad··on TypeScript is surprisingly ok for compilers
language-centric: the language you are compiling is flexible (you are also the language designer), you want to build the best possible language

implementation-centric: the language you are compiling is mostly fixed and/or defined by an external entity. You want to build the fastest compiler for this language, which emits the fastest code.

matklad··on Fastest branchless binary search
> BUT ZIG.. There’s no binary search implementation in Zig that I could find, rather it calls to C++.

Zig’s binary search is here, it’s an unoptimized textbook version: https://github.com/ziglang/zig/blob/b835fd90cef1447904d3b009...

At TigerBeetle, we have our own branchless implementation here:

https://github.com/tigerbeetle/tigerbeetle/blob/e996abcf7154...

matklad··on Error Handling in Zig
Note that Zig supports general sum types and pattern matching. It however deliberately chooses not to use those features for idiomatic error handling.
matklad··on Can you trust a compiler to optimize your code?
Not at all, Rust and C++ are more-or-less equivalent here. In C++, like in Rust, each lambda gets a unique unnamable type, and you can use template parameters to express direct calls.

> The lambda expression is a prvalue expression of unique unnamed non-union non-aggregate class type, known as closure type, which is declared (for the purposes of ADL) in the smallest block scope, class scope, or namespace scope that contains the lambda expression.

https://en.cppreference.com/w/cpp/language/lambda

matklad··on Memory Copy Hunting
Depends on the context! For close-to-the-human high level languages, you generally want to solve these things through optimizations. For close-to-the-cpu low-level languages, you rather want tools to express the desired behavior in the source code. That is, you need an ability to write code in a way that _guarantees_ that optimization triggers. Eg, you want explicit SIMD types rather than just loop auto-vectorization.

Zig is very much on the close-to-cpu side of the spectrum here. When it comes to copies, the current version of the language/compiler doesn't _yet_ provide the required guarantees with required ergonomics, but this is being actively worked on:

- https://github.com/ziglang/zig/issues/2765 - https://github.com/ziglang/zig/issues/12251 - https://github.com/ziglang/zig/issues/5973

In the meantime, you need to look one level below the source language to ensure that the runtime behavior of the code is what you want it to be.

matklad··on Memory Copy Hunting
Yup!

Ideally, you want to do this analysis on compiler IR, _before_ it gets lowered to LLVM IR. But to do that in a sustainable way, you need a quasi-stable internal IR format. Zig is rather new, and, while the compiler is a delight to hack on, there are no stable extension interfaces, and the code itself is very much not settled yet. So that's the main thing we get out of LLVM IR here is relative stability. You can quickly hack something together, and be reasonably sure that you won't have to spend a lot of time upgrading the infra with every compiler upgrade. LLVM IR of course is not absolutely stable, but it is stable enough, and way more stable than compiler internals at the moment.

matklad··on Durable Incrementality
Derived from Rust code. With some proc macro magic, function declarations like `fn my_query(arg: Foo)` are decorated with prologue&epilogue which do required runtime tracking of dependencies.
matklad··on Durable Incrementality
A bit more context in lobste.rs discussion: https://lobste.rs/s/te7x8n/durable_incrementality
matklad··on Problems of C, and how Zig addresses them
Compare these two methods:

https://github.com/ziglang/zig/blob/0dffab7356685c7643aa6e3c...

https://github.com/ziglang/zig/blob/0dffab7356685c7643aa6e3c...

One of them requires passing an allocator (and can allocate), the other doesn’t have an allocator argument (and thus can’t allocate). If you only pass allocator to `init` method of your application, and don’t store it anywhere, only init will be able to call allocating methods, the rest of the app will be allocation free, by construction.

matklad··on Problems of C, and how Zig addresses them
That's not quite it: with heapless, memory is fully static, the size of hash map is a compile-time parameter, which is a part of HashMap's type.

In Zig, the map could be initialized and sized at runtime, but you still can enforce, statically, that it doesn't do any allocations after that.

In both nightly Rust and Zig, heapless version can be expressed by passing a fixed-buffer-backed allocator to the standard hash map.

matklad··on Problems of C, and how Zig addresses them
As counter point, the way that Zig implements hash maps is absolutely instrumental for TigerBeetle.

Zig hashmaps _are_ quite a bit more cumbersome than, eg, in Rust --- you need to decided whether you want the allocator to be bundled with the hasmap, and its also up to the user of the hash map to provide equality and hash code (and, of course, there's manual defer instead of RAII).

However, this flexibility and verbosity comes with a super-power --- you can pass an allocator to a hash map at creation time, and then _not_ pass an allocator when you actually use the hash map. This is huge. This means that we get compile-time guarantee that we follow rule 3 of NASA's 10 rules

    3. Do not use dynamic memory allocation after initialization.
And we _still_ can enjoy using a hashmap from the standard library! No other language I know has an equivalent tool.
matklad··on My First Impressions of Nix
I am not an expert, but here’s my attempt at a useful comment.

On the highest level, `nix` is an alternative build system. So, if someone packages your app with `nix`, there’s now extra work to keep that working, and it’s on the packager to keep it working. If they packaged your app such that it’s using different dependencies than those required, that’s a bug in the package. As a maintainer, you can help here by making it clearer what versions are accepted, and by making it easier to run the tests for a package.

If we open a black box, there are two things in play here: Nix-the-build-system and nixpkgs package collection.

The build system is very open ended and can specify all dependencies precisely, but it’s on the user to define what that means exactly.

nixpkgs is a coherent collection of nix packages, a bit like a Linux distro. In particular, it _generally_ has one version of each package, and there’s some testing to make sure that all the packages work together.

Now, to package a Python app with Nix you can either pull dependencies from nixpkgs, in which case the situation would be similar to, eg, packaging for Debian.

Or you could create a hermetic environment, where an app gets an isolated copy of dependencies, specific just to the single app, a situation similar to using virtual env.

It sounds like what happened here is that your app got packaged in the fist way, but actually it can work only in the second way. I assume you do specify specific compatible version of Django somewhere, and if a package (be it .deb, .rpm, or .nix) doesn’t respect that, that’s a bug in the package.

Hope this helps!

matklad··on Iterating on Testing in Rust
No need for test_context, we can add an optional argument to functions marked with test.
matklad··on Zig language server and cancellation
I covered this a bit here:

https://rust-analyzer.github.io/blog/2020/07/20/three-archit...

I don't actually _know_ how exactly clangd works, especially post modules, but pre-modules C++ has a compilation model which is actually quite friendly for an IDE, because of the header files.

Headers essentially explicitly encode body/interface separation that more advanced incremental compilation systems like Salsa try to recover implicitly.

Looking at a slightly simplified typical C++

    #include <iostream>

    void main() {
        std::cout << "Hello, World!" << std::
    }
what a language server could do is that it can run bog-standard phased compiler, and just _freeze_ its state after all includes are parsed&expanded. After that, any typing inside the file needs to re-analyzer just the file itself. Also, the code in included `.h` files is typically far smaller then the code in the corresponding `.cpp` files. So, a language server gets ability to analyse only the relevant code, and skip the rest, for free, it is encoded in compilation model.

Compare this with Rust, where, in the general case, changing a file can affect any other file in CU in arbitrary ways (_usually_ it doesn't, but it _could_, and the complexity lies precisely in figuring out which edits are local and which are not). And CU's themselves are meatier, as macro expansion can run arbitrary code, so you need to somehow cache that, taking into account that macro expansion _anywhere_ in CU can potentially affect _anything_ in CU. So, you need full build systems a-la carte incremental compilation, which is a) hard b) different from how the command line compiler works.

The second point explains the success of clangd I think: _usually_, when you have a command-line compiler and want a language server, you want to rewrite, because the architectures are too different. But because of the way C++ (and OCaml) work, for those two languages you actually can soundly re-use existing code with relatively minor modifications.

matklad··on Zig language server and cancellation
I am not entirely sure about C#, if we speak about “static analysis based IDE” tooling. I think this only became focus with Roslyn, and Roslyn came later, after JetBrains did their own thing with resharper.

But yeah, directionally we are getting there: Microsoft seems to be the main popularizer of the idea (TypeScript and LSP), and Google seems to be most acutely aware about the “tooling gap” (Go, Dart, and, most recently, Carbon are cognizant of tooling needs. Carbon has signatures for tooling, and Dart shipped a better version of LSP before LSP became a thing).

matklad··on Zig language server and cancellation
> Most languages with "advanced" features and type systems really need a full semantic tree to do anything meaningful due to the complexities of compile time code and type instantiation.

I wouldn’t say this depends on abstract complexity of “type system”. For example, Rust is pretty advanced, but lazy query architecture works well for it. Usually, it’s the name resolution/macro expansion that puts the wrench in the works, not a Turing-complete type system.

That being said, yes, in Zig you probably can’t do lazy query-based IDE. It really is a compile-time smalltalk, and wants to have an image.

matklad··on Zig language server and cancellation
Descriptively, yes, the shape of the language determines how you can structure an interactive compiler. There are at least three wildly different ways to do that:

https://rust-analyzer.github.io/blog/2020/07/20/three-archit...

Which one can work depends on the language in question. Java, Rust, C++ lead to different answers, and that’s not because of the “interesting” differences like borrowchecker vs gc, but rather due to the “boring” differences in name resolution and module system.

Prescriptively, whether we _should_ do this (or, rather, how much), is unclear.

My biased answer is that, while language designers talk a lot about making languages tooling friendly, there’s little of that actually happening (at least with “current” languages, “next” ones seem to fare better). Like, it was said that “rust macros are designed with tooling friendliness in mind”, but overall the language is pretty tooling-hostile, mostly for accidental reasons. It seems to me that if we _actually_ co-design a tooling-first language, without trying to innovate too much, but by just ensuring that existing techniques work robustly, we might arrive at a close, but meaningfully different point in the design space.

Specifically, here’s my version of IDE-friendliness diff for language design:

Push conditional compilation far further in the pipeline, such that it is done after all semantic analysis. This is a pre-requisite for making automated refactors which are _guaranteed_ to work.

Similarly, push meta programming further down, such that code analysis doesn’t invoke user-defined code (which might be arbitrary slow), but, at the same time, meta parts can fully reflect on existing code, including resolved types. C#-style source generators are an interesting design here.

Have strong signatures on micro and macro level. Macro, have well-defined compilation units with explicitly specified dag of dependencies and signature files. Micro, annotate types of the functions. Use tooling to reduce double-annotation burden.

Ensure that each source file can be somewhat deeply analyzed in complete isolation. The last two points should unlock both embarrassingly parallel (distributed) compilation, and snappy completion.

matklad··on Zig language server and cancellation
This depends on the compilation model in use. If that’s a traditional pipeline of phases, where the result is an AST data structure for the whole CU which gets annotated with types, then, yes, “enqueue new analysis” makes sense.

If the compilation model lazy & query based, then theres’s just no “enqueue a subsequent parse”, but rather “give me the type on this thing doing as little analysis as possible”. You got to re-use symbols and declarations not because you heuristicsly adjust offsets and assume they are otherwise valid, but because underlying analysis reasons, precisely, they they are valid and re-usable.

The two models are quite different at the core, and aren’t really an evolution of one into another.

Which of the two approaches to use, and, consequently, whether to think about cancellation at all, depends heavily on the language in question. If the language allows for lazy analysis, it’s probably a better bet, as that gives you correct results faster.

matklad··on Why I Left Rust
There are two completely orthogonal questions here:

- Is the content of the talk suitable for a keynote?

- Given that the talk was accepted as a keynote, is it ok for the organizers to change their mind and unilaterally demote the talk?

https://hackmd.io/mwCWfJpIT024vBYvKeHCtw?view gives an informed perspective on the second question.

matklad··on How much memory do you need to run 1M concurrent tasks?
Benchmarks for threads might slightly underestimate memory usage. For threads, some amount of memory is spent by the kernel (eg, memory maps themselves) and won’t show as maxrss.

> a high number of concurrent tasks can consume a significant amount of memory,

So Go needs 3gigs for a million tasks. Relatively speaking, for an app that does a million concurrent somethings, 3gb is probably peanuts.

It seems that memory isn’t the limiting factor here.

matklad··on Why SAT Is Hard
The other way around: to prove that X is NP-complete you need to reduce SAT(or any other known NP complete problem) to X.

The intuition here is that if you have a magic algorithm which solves X efficiently, you should be able to use this algorithm to solve any other NP problem, like SAT.

matklad··on <3 Deno
Thanks, it was confused thinking on my part, corrected!
← PreviousPage 3 of 7Next →