Live data from Hacker News

Dear sir, you have built a compiler

rachitnigam.com

171–177 of 177 posts

Re: Dear sir, you have built a compiler

#171
post #131

Earlier quoted context omitted.

> SBCL, for example, has C bindings in the /runtime subdirectory. So nothing to do with SBCL's compiler (which is somewhat confusingly named 'Python' and written entirely in Lisp), then.

Well, handwave handwave . Nothing to do with the compiler except that I'd assume if you rip out the /runtime directory you'll get a compiler that can't output working code. The point is that these domains have a tendency to eventually overlap each other.

The Python compiler can output working code just fine. It takes either a Lisp structure (COMPILE) and generates a code object in memory, or takes a text file (COMPILE-FILE) and generates a FASL file. This has absolutely nothing to do with the runtime, except perhaps for COMPILE-FILE's need to read and write a file which ultimately needs to go through a syscall in the runtime. But the compiler is not even partially written in C. (And considering that Python originated as part of the CMUCL project in the mid-80's era of Lisp machines which didn't even include any C code whatsoever, writing even a part of Python in C would have been a curious design decision back then.)

Re: Dear sir, you have built a compiler

#172

Earlier quoted context omitted.

The way I see it, Forth is the architecture-independent assembly that is optimized for ease of bootstrapping on new hardware at the cost of efficiency.

I agree that assembly is a good comparison. With a threaded-code interpreter, yes, Forth's overhead is considerable, but with a native-code Forth compiler, performance is generally only slightly worse than C. This is presumably because modern optimising C compilers are incredibly sophisticated, whereas modern Forth engines tend to be essentially one-man projects, even the commercial ones.

> performance is generally only slightly worse than C

I've built a couple of projects both in C and Forth, the latter usually to prototype and once I had a good understanding of the problem space the final version in C. Typically the C version outperformed the Forth version by 3:1 or better, and I would not have known how to bridge that gap.

Well written C is quite performant and Forth's overhead (which is relatively small, but it is there) translates into Forth's threaded interpreter executing a JMP instruction at least once per Forth word and that alone is probably enough to explain a good chunk of that gap. FWIW, my experience with Forth is limited to one implementation and a whole bunch of applications (after being introduced to the language by a veritable Forth wizard in 1985 or so, Hi, LS). Even the code of experienced Forth programmers was no match for my then 6 year old experience with C. Nowadays with far larger caches Forth might do better, I haven't really worked with it for years.

Re: Dear sir, you have built a compiler

#173
post #152

Earlier quoted context omitted.

I somewhat disagree — there really is a finite amount of Computer Science to know. The more you dive deep into different domains, the more you find yourself ending up in the same places, learning the same things with different names. What is a SQL query planner but a compiler? Is an OS scheduler really that different from an HPC workload manager, or your GPU's computer-shader arbitrator? Is RDMA against an NVMe stora…

Yes, but also no- I see what you're saying from a high level, but my point is that the devil's in the details and that you can't know all the details of each domain, the best you can do is be aware that those details are there. Just being exposed to even a subset of the high-level is pushing the limits of a 4-year undergrad curriculum. > What is a SQL query planner but a compiler? Kind of? Lexing, sure, and to some e…

> but my point is that the devil's in the details and that you can't know all the details of each domain, the best you can do is be aware that those details are there.

IMHO you can do slightly better — you can know enough about isomorphic decisions you've made in other domains to drive design in a new domain, without necessarily understanding implementation.

(Especially "design" in the sense of "where does the shear-layer exist where I would expect to find libraries implementing the logic below that layer" — allowing you to understand that there should exist a library to solve constrained problem X, and so you should go looking for such a library as a starting point to solving the problem; rather than solving half of problem X, and then looking for a library to solve overly-constrained sub-problem Y.)

Or, to put it another way: knowledge of strategy is portable, even if knowledge of tactics is not. An Army General would — in terms of pure skill — pick up the job of being a Naval Admiral pretty quickly, because there's a lot about high-level strategy that isn't domain specific. And that experience — combined with hard-won domain experience in other domains — could guide them on absorbing the new domain's lower-level tactics very quickly.

Or, another analogy: linguists learn languages more easily than non-linguists, because 1. it turns out that, past a certain point, languages are more similar than they are different; but more importantly, 2. there are portable high-level abstractions that you begin to pick up from experience that can accelerate your understanding of a new language, but which you can also be taught academically, skipping the need to derive those concepts yourself. (You still need practical domain knowledge in at least some domains to root those concepts to, but you can do that in your own head when studying the concepts in a book, rather than "in anger" in the field.)

This belief — that there exists portable high-level strategic knowledge to software engineering — is exactly why some companies promote programmers into product managers. A product manager will be tasked to drive the strategy for writing a new piece of software, potentially in domains they've never worked in. They won't be implementing this software themselves — so they don't actually need to understand the domain with high-enough precision to implement it. But they'll nevertheless be relied upon to make architectural decisions, buy-vs-build decisions, etc. — precisely because these decisions can be made using the portable high-level strategic knowledge of software engineering.

(Though, once again, this knowledge must be rooted in something; which is why I don't really believe in CS / SWEng as programs people should be taking fresh out of university. The best time to learn them is when you already have 10 years' programming experience under your belt. They should be treated as "officer's finishing school", to turn an experienced apprentice 'programmer' into a professional Software Engineer.)

On to specific hand-wavy rebuttals, since my original rhetorical questioning didn't do the job of being particularly clear what I meant:

> but an execution plan is not built from an instruction set

What is a logical-level write-ahead log, but a long bytecode program that replicas execute? What does executing SQL do, but to compile your intent into a sequence of atomic+linearized commands — an instruction stream — in said write-ahead log?

(Alright, in a multi-master scenario this isn't as true. But you can get back to this property if your DBMS is using a CRDT event-streaming model; and AFAIK all the scalable multi-master DBMSes do something approximating that, or a limited subset of that.)

> Hypervisors need to integrate with higher-level RBACs, for one; distributed schedulers also need to be able to evict bad machines from the same system.

Perhaps you haven't dealt with machines of sufficient scale—the abstractions really do come back together! The IBM z/OS kernel knows about draining+evicting hotplug NUMA nodes as schedulable resources (and doing health-checks to automatically enable that), in exactly the same way that Mosix or TORQUE or kube-scheduler knows about draining+evicting machines as schedulable resources (and doing health-checks to automatically enable that.)

Even regular microcomputer OS kernels have some level of support for this, too — though you might be surprised why it's there. It doesn't exist for the sake of CPU hotplug+healthcheck; but rather for the sake of power efficiency. An overheating CPU core is, at least temporarily, a "bad" CPU core, and on CPU paradigms like big.LITTLE, the entire "big" core-complex might be drained+evicted as a response! That code, although different in purpose, shares a lot algorithmically with what the distributed schedulers are doing — to the point that one could easily be repurposed to drive the other. (IIRC, the Xeon Phi did exactly this.)

> e.g. what's your resilience story against a network failure (someone cutting a fiber line, or losing a subgraph of a clos fabric)?

My point with mentioning hierarchical persistence+caching for a distributed key-value store, is that these same problems also occur there. From the perspective of a client downstream of these systems, a network partition in tiered storage, is a network partition in tiered storage, and you have to make the same decisions — often involving (differently-tuned implementations of) the same algorithms! — in the solution domain for both; and, perhaps more importantly, expose the same information to the client in the solution domain for both, to allow the client to make decisions (where needing to capture and make this information available will heavily constrain your design in both cases, forcing some of the similarity.)

Re: Dear sir, you have built a compiler

#174
post #157

I feel like this easily could have been addressed to a much younger version of myself on a particular project more than a decade ago (~12 years). My story happened in the early days of SPARQL, when SPARQUl (SPARQL Update Language) was very new, a draft, and definitely not merged into SPARQL yet. Oh, and dinosaurs roamed the earth. That last is from my daughter. My project involved semi-autonomous software agents that…

The nerve and brain concept sounds fascinating, but I don't have enough background in sensors to quite grasp what you mean. Could you please provide a specific example?

One example is using it for network monitoring. Imagine an SNMP agent as a sensor, managed by a nerve, which gathers information via SNMP Gets and other techniques to build a semantic model from one or more SNMP Management Information Blocks (MIBs). This then is reasoned over, aggregated up the chain, further reasoned over, and fed into rules that trigger model changes that get propagated to the nerves, who translate those changes into SNMP management actions.

Re: Dear sir, you have built a compiler

#175

Earlier quoted context omitted.

I agree that assembly is a good comparison. With a threaded-code interpreter, yes, Forth's overhead is considerable, but with a native-code Forth compiler, performance is generally only slightly worse than C. This is presumably because modern optimising C compilers are incredibly sophisticated, whereas modern Forth engines tend to be essentially one-man projects, even the commercial ones.

> performance is generally only slightly worse than C I've built a couple of projects both in C and Forth, the latter usually to prototype and once I had a good understanding of the problem space the final version in C. Typically the C version outperformed the Forth version by 3:1 or better, and I would not have known how to bridge that gap. Well written C is quite performant and Forth's overhead (which is relatively…

With respect you've ignored the point I was making. There exist several Forth engines with native code-compilation, for instance VFX Forth, SwiftForth, and iForth.

> Typically the C version outperformed the Forth version by 3:1 or better, and I would not have known how to bridge that gap.

With a threaded-code Forth interpreter I'd expect the C version to outperform it by something closer to 5:1, so 3:1 doesn't sound too bad. The only way you can close the gap is with good quality native-code compilation.

> Nowadays with far larger caches Forth might do better, I haven't really worked with it for years.

It's interesting how advances in CPU architecture change the relative performance of the different threading strategies. This has been nicely studied by the gforth folks. [0][1] Threaded-code interpreters still easily lose to optimising native-code compilers though, [2] and I expect they always will.

More on how Forth collides with low-level CPU matters: [3][4][5]

[0] https://www.complang.tuwien.ac.at/forth/threading/

[1] https://www.complang.tuwien.ac.at/forth/threaded-code.html

[2] https://github.com/ForthHub/discussion/issues/88#issuecommen...

[3] The Behavior of Efficient Virtual Machine Interpreters on Modern Architectures - https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.12...

[4] Branch Prediction and the Performance of Interpreters - Don't Trust Folklore https://hal.inria.fr/hal-01100647/document

[5] Optimizing Indirect Branch Prediction Accuracy in Virtual Machine Interpreters - https://www.scss.tcd.ie/David.Gregg/papers/toplas05.pdf

Re: Dear sir, you have built a compiler

#176

Earlier quoted context omitted.

To me it was the recursive mapping over a closed set of types, whatever you do you should end up with an element of your type/grammar. That and the graph walk space of the AST.

I'm currently writing a compiler so I'm not new to this, but I've no idea what you just said. Have you any links to explain it? TIA

The closed set of types describes how each pass in a compiler pipeline tends to build an intermediate representation of some sort, analyze/modify it, and then output it to the next stage. The IR is closed in that it is not open for everyone to extend willy-nilly. It is this property that makes it even possible to analyze and manipulate in a sound manner.

In a sense, compilers literally build a bunch of linguistic 'worlds' within their pipeline, each one emphasizing something different.

Re: Dear sir, you have built a compiler

#177
post #173

Earlier quoted context omitted.

Yes, but also no- I see what you're saying from a high level, but my point is that the devil's in the details and that you can't know all the details of each domain, the best you can do is be aware that those details are there. Just being exposed to even a subset of the high-level is pushing the limits of a 4-year undergrad curriculum. > What is a SQL query planner but a compiler? Kind of? Lexing, sure, and to some e…

> but my point is that the devil's in the details and that you can't know all the details of each domain, the best you can do is be aware that those details are there. IMHO you can do slightly better — you can know enough about isomorphic decisions you've made in other domains to drive design in a new domain, without necessarily understanding implementation. (Especially "design" in the sense of " where does the shear…

> you can know enough about isomorphic decisions you've made in other domains to drive design in a new domain, without necessarily understanding implementation.

That's certainly true!

I'm not at 5 years yet in the industry myself, but I've definitely started to notice these patterns - the strategy vs tactics is a nice way to describe it :)

> Perhaps you haven't dealt with machines of sufficient scale—the abstractions really do come back together! The IBM z/OS kernel knows about draining+evicting hotplug NUMA nodes as schedulable resources (and doing health-checks to automatically enable that), in exactly the same way that Mosix or TORQUE or kube-scheduler knows about draining+evicting machines as schedulable resources (and doing health-checks to automatically enable that.)

Oh, this is interesting. My experience has been as a Google-internal user of Borg, where although the fleet is large, most of the machines are individually small enough that it's easier for us to simply evict a machine from the fleet rather than block a core. (The whole "commodity" server strategy, whereas z/OS follows a very different architecture, but I see exactly what you mean there.)

Post reply on HN