[HN Gopher] A Basic Just-In-Time Compiler (2015)
___________________________________________________________________
A Basic Just-In-Time Compiler (2015)
Author : ibobev
Score : 97 points
Date : 2026-01-03 01:18 UTC (21 hours ago)
(HTM) web link (nullprogram.com)
(TXT) w3m dump (nullprogram.com)
| possiblywrong wrote:
| Following is the closed form solution linked in the article (from
| a since-deleted Reddit comment): from functools
| import reduce def recurrence(ops, a0, n):
| def transform(x, op): return eval(repr(x) + op)
| ops = ops.split() m = reduce(transform, [op for op in
| ops if op[0] in ('*', '/')], 1) b = reduce(transform,
| ops, 0) for k in range(n + 1):
| print('Term 0: ', a0 * m ** k + b * (m ** k - 1) / (m - 1))
|
| > This is really only interesting if a _particular_ (potentially
| really large) term of the sequence is desired, as opposed to
| _all_ terms up to a point. The key observation is that any
| sequence of the given set of operations reduces to a linear
| recurrence which has the given solution.
| kscarlet wrote:
| It seems that JIT is overloaded with at least 2 meaning.
|
| The canonical definition of JIT is "compilation _during_
| execution of a program ". Usually, a program is being interpreted
| first, then switches to compiled code in the middle of execution.
| This is _not_ what this article does.
|
| What this article does is sometimes called on-the-fly AOT, or
| just on-the-fly compilation. I'd prefer not overloading the term
| "JIT".
| MobiusHorizons wrote:
| I always took the distinction to be the executable memory bit
| as opposed to writing an executable and then launching it in
| the usual way. Of course high performance runtimes that contain
| JITs do typically interpret first in order to get type
| information and reduce startup latency, but that's more a
| function of the language not being efficiently AOT compileable
| rather than fundamental to the concept of a JIT
| kscarlet wrote:
| In that sense almost every compiled Lisp/Scheme
| implementation, GHC, etc. or any other interactive
| programming system, count as JIT. But virtually nobody in
| those circles refer to such implementations as JIT. Instead,
| people says "I wish our implementation was JIT to benefit
| from all those optimizations it enables"!
| MobiusHorizons wrote:
| Do they generate machine code in ram and jump to it? Or do
| they interpret byte code?
|
| EDIT: at least GHC seems to be a traditional AOT compiler.
| kscarlet wrote:
| They generate native machine code.
| throwaway17_17 wrote:
| Can you explain what mean by a "language not being
| efficiently AOT compileable"? I am guessing you are referring
| to languages that emphasize REPL based development or
| languages that are 'image' based (I think Smalltalk is the
| most common example).
|
| Like the guesses above, I can understand difficulty with AOT
| compilation in conjunction with certain use cases; however, I
| can not think of a language that based on its definition
| would be less amenable to AOT compilation.
| Nevermark wrote:
| The more context is narrowed down, the more optimizations
| that can applied during compilation.
|
| AOT situations where a lot of context is missing:
|
| * Loosly typed languages. Code can be very general. Much
| more general than how it is actually used in any given
| situation, but without knowing what the full situation is,
| all that generality must be complied.
|
| * Increment AOT compilation. If modules have been compiled
| separately, useful context wasn't available during
| optimization.
|
| * Code whose structure is very sensitive to data statistics
| or other conditional runtime information. This is the prime
| advantage of JIT over AOT. Unless the AOT compiler is
| working in conjunction with representative data and a
| profiler.
|
| Those are all cases where JIT has advantages.
|
| A language where JIT is optimal, is by definition, less
| amenable to AOT compilation.
| MobiusHorizons wrote:
| What I meant was dynamic typing primarily. Think JavaScript
| or lua. These are both languages where the choice is
| between interpreter and JIT rather than JIT or AOT. VM
| based languages like Java also fall in that category, not
| because of dynamic typing so much as because of shipping
| bytecode to the client for portability reasons.
| MobiusHorizons wrote:
| I should probably have said, not compilable to efficient
| code. rather than not efficiently compilable. Basically I
| was referring to dynamic typing. Typically such languages
| are interpreted, although there is probably a way to
| compile the same sequence the interpreter would take as an
| AOT compiler. When types are not known until runtime, the
| compiler can't emit efficient code, and instead has to emit
| code that checks the type on each function invocation which
| is basically exactly what the interpreter was already
| doing. This is where JITs really shine, since they can
| produce one or more compilations of the same function
| specialized to types that have been observed to be used
| frequently. the interpreter can then call those specialized
| versions of the functions directly when appropriate.
| dataflow wrote:
| > Usually, a program is being interpreted first, then switches
| to compiled code in the middle of execution.
|
| I agree what they have isn't JIT compilation, but not for that
| reason. Tiered execution was never a central part of JIT
| compilation either. It was a fairly new invention in
| comparison.
|
| The reason what they describe isn't JIT compilation is IMO
| fairly boring: it's not compiling the input program in any
| meaningful way, but simply writing hard-coded logic into
| executable memory that it already knows the program intended to
| perform. Sure there's a small degree of freedom based on the
| particular arithmetic operations being mentioned, but that's...
| very little. When your compiler already knows the high-level
| source code logic before it's even read the source code,
| it's... not a compiler. It's just a dynamic code emitter.
|
| As to the actual difference between JIT vs. AOT... it may just
| come down to accounting. That is, on whether you can always
| exclude the compilation time/cost from the overall program
| execution time/cost or not. If so, you're compiling ahead of
| (execution) time. If not, you're compiling during execution
| time.
| ordu wrote:
| _> it 's not compiling the input program in any meaningful
| way, but simply writing hard-coded logic into executable
| memory that it already knows the program intended to
| perform._
|
| The program reads the logic from stdin and translates it into
| machine instructions. I can agree that there is not a lot of
| a freedom in what can be done, but I think it just means that
| the source language is not Turing complete. I don't believe
| that compiler needs to deal with a Turing complete language
| to claim the title "JIT compiler".
| dataflow wrote:
| > The program reads the logic from stdin and translates it
| into machine instructions. I can agree that there is not a
| lot of a freedom in what can be done, but I think it just
| means that the source language is not Turing complete. I
| don't believe that compiler needs to deal with a Turing
| complete language to claim the title "JIT compiler".
|
| "Not Turing-complete" is _quite_ the understatement.
|
| A "compiler" is software that translates computer code from
| one _programming language_ into another language. Not just
| any software that reads input and produces output.
|
| The input language here is... not even a programming
| language to begin with. Literally all it can express is
| linear functions. My fixed-function calculator is more
| powerful than that! If this is a programming language then
| I guess everyone who ever typed on a calculator is a
| programmer too.
| tgv wrote:
| A compiler takes some language and translates it into
| something close(r) to the hardware. And that's what the
| OP does. And since it compiles in process and executed it
| too, it's JIT, as opposed to AOT.
|
| These terms are not related to the complexity of the
| problem. The first compilers could only translate for
| formulas, hence FORTRAN.
| Brian_K_White wrote:
| That's not compilation merely substitution.
| dataflow wrote:
| I'm not sure where you got your definition, but I
| basically copied Wikipedia's.
| kscarlet wrote:
| > As to the actual difference between JIT vs. AOT... it may
| just come down to accounting. That is, on whether you can
| always exclude the compilation time/cost from the overall
| program execution time/cost or not. If so, you're compiling
| ahead of (execution) time. If not, you're compiling during
| execution time.
|
| Well, this includes what I refer to as "on-the-fly" AOT, like
| SBCL, CCL, Chez Scheme... Even ECL can be configured to work
| this way. As I mentioned in another comment, people in those
| circles do not refer to these as "JIT" at all, instead saying
| "I wish my implementation was JIT instead of on-the-fly AOT"!
| orthoxerox wrote:
| I think if your program starts to execute machine code that
| wasn't present in the binary, then it counts as having a JIT
| compiler.
|
| Of course, there are edge cases like embedding libtcc, but I
| think it's a reasonable definition.
| ignoramous wrote:
| > _This is not what this article does._
|
| Discounting books, many other well written articles on JIT have
| been shared on HN over the years [0][1][2]; the one I
| particularly liked as it introduces the trinity in a concise
| way: _Compiler, Interpreter, JIT_
| https://nickdesaulniers.github.io/blog/2015/05/25/interprete...
| / https://archive.vn/HaFlQ (2015).
|
| [0] _How to JIT - an introduction_ ,
| https://eli.thegreenplace.net/2013/11/05/how-to-jit-an-intro...
| (2013).
|
| [1] _Bytecode compilers and interpreters_ ,
| https://bernsteinbear.com/blog/bytecode-interpreters/ (2019).
|
| [2] _Let 's build a Simple Interp_,
| https://ruslanspivak.com/lsbasi-part1/ (2015).
| MobiusHorizons wrote:
| Is it just me or is the author using static wrong? Someone
| mentioned it in the thread on the previous post, where it felt
| more like an oversight. But in this article it seems much more
| like an actual misunderstanding. Should it actually be the
| function level static variable? I feel like in the right context
| the optimizer might be able to leave that in a register if there
| the calling function is in the compilation unit.
| the-smug-one wrote:
| Man, I friggin despise how hard (in a very not fun way)
| generating x86 assembly is :-). Generating Aarch64 is a lot
| easier.
| mananaysiempre wrote:
| I mean, I can't do it by heart, but it's not fundamentally very
| hard? Thumb-2 is definitely much more annoying.
| senko wrote:
| Ah, I thought this was going to be about a JITted BASIC. No such
| luck.
| mananaysiempre wrote:
| > On x86-64, pages may be 4kB, 2MB, or 1GB
|
| But I believe sysconf(_SC_PAGESIZE) will always be 4KB, because
| the "may" is at the user's discretion, not the system's. Except
| on Cosmopolitan where it will always be 64KB, because Windows NT
| for Alpha (yes, seriously).
___________________________________________________________________
(page generated 2026-01-03 23:01 UTC)