5 ms·
I'm the author of the tweet. Here's some more context: The main purpose of the testing was to measure compile time scaling on simple code that has straightforw
by psykotic 6y ago
I'm the author of the tweet. Here's some more context:
The main purpose of the testing was to measure compile time scaling on simple code that has straightforward equivalents in all languages. This meant integer and float operations, compound expressions making use of the full range of arithmetic and bitwise operators, local variables, function definitions and calls. So the code wasn't trivial (unlike most of the marketing-oriented tests or benchmarks I came across), but I also wasn't claiming that this was directly representative of a real-world code base of comparable size.
I was working on a fast compiler (which generated machine code somewhere between gcc -O0 and -O1 in code quality) and wanted to have something to compare it across languages and compilers while being able to easily vary test parameters like total code size, size of each module, complexity of the module graph, identifier/whitespace/comment length distribution, etc.
"Lines of code" is a pretty poor metric for engineering but unlike "tokens of code" or "bytes of code" it's something for which programmers have an intuitive sense of scale, so it made more sense for a tweet. Tokens of code is the most useful code size parameter for measuring one-pass compiler performance if you have to pick a single number. In an expression like "x + 1" you can assign the cost of the parsing, type checking and code generation of the expression (separate from the sub-expressions "x" and "1") to the "+" token. Even the cost of lexing is often dominated by the per-token cost (the switch jump on the leading byte is usually a forced branch mispredict of ~15 cycles) if you do the per-byte handling for variable-length tokens like identifiers efficiently. [1] If you fix the token distribution, you get almost-linear scaling with token count. [2]
[1] Identifier bytes make up 60-70% of a typical code base, so micro-optimization can really pay off here if the rest of the compiler is fast. I used a SIMD method with a mispredict-free fast path for identifiers shorter than 16/32 bytes, with vectorized scanning and hashing, and the symbol table lookup/insertion was done at the same time and tuned such that it was mispredict-free 90% of the time for lookups and only had 1 mispredict for inserts which occur the first time a given identifier is seen in a module.
[2] Except for threshold effects when your working set starts pushing you out of a level of the cache hierarchy. There's two factors: the size of your symbol working set, and your utilization of symbol hash tables. E.g. if a region of code is using a tiny subset of a huge symbol table, each loaded cacheline from the hash table is only expected to contain one symbol from your working set due to the pseudo-random distribution of hashes, but that caps out pretty quickly. With 64-byte cachelines and interleaved key/value pairs of 16 bytes, this part can't get worse than 25% cache utilization. So the worst-case footprint from the symbol working set is one 64-byte cacheline per symbol in the working set plus whatever associated symbol data is accessed. This utilization is improved if you put more symbol data directly into the hash table cacheline but unfortunately that would mean you don't have stable pointers to that data when you need to rehash.
- 1wd 6y agoI did a similar test some years ago: https://imgur.com/a/jQUav#xVgi2ZA https://imgur.com/a/jQUav#xVgi2ZA (Have you tried plotting some data?) I found some interesting and perhaps surprising results. (But I also acknowledge that it was very far from real-world code, any conclusions drawn from that were only for fun.)
- psykotic 6y agoYeah, I remember seeing your measurements at the time. I did plots, but for most of the compilers I only measured at a handful of points in the parameter space since it took forever to run and I wanted to be able to regenerate the measurements in a reasonable amount of time if I changed the generator or parameters. I did dense multi-parameter measurements and model fitting for my own compiler; that's how it started, so the comparative data for other languages and compilers came later.