You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Copy file name to clipboardExpand all lines: README.md
+51-9Lines changed: 51 additions & 9 deletions
Original file line number
Diff line number
Diff line change
@@ -36,7 +36,7 @@ Type propagation means we can take the type information gathered from a single b
36
36
37
37
Type check removal means removing type checks in dynamic Python. E.g. if you have ``a + b``, the fast path in Python has to check that these are `int` or `str` or `float`, then if all those fail, rely on a generic `+` function. These type checks incur overhead at runtime. With type information, if we know the types, that we don't need any type checks at all! This means we can eliminate type checks.
38
38
39
-
We had a rudimentary test script and Doxygen documentation for all our functions to follow common SWE practices.
39
+
We have a rudimentary test script and Doxygen documentation for all our functions to follow common SWE practices.
40
40
41
41
#### Orbital
42
42
@@ -45,7 +45,7 @@ This Orbital, we intend to refine pyLBBV. These include but are not limited to:
45
45
-[X] Bug fixing
46
46
-[X] A more advanced type propagator.
47
47
-[X] A more comprehensive test suite with Continuous Integration testing.
48
-
-[] A copy and patch JIT compiler. (Not yet implemented!)
48
+
-[X] A copy and patch JIT compiler.
49
49
50
50
A JIT(Just-in-Time) compiler is just a program that generates native machine executable code at runtime. [Copy and Patch](https://arxiv.org/abs/2011.13127) is a new fast compilation technique developed rather recently. The general idea is that compilation normally requires multiple steps, thus making compilation slow (recall how many steps your SICP meta-circular evaluator needs to execute JS)! Copy and patch makes compilation faster by skipping all the intermediate steps, and just creating "templates" for
51
51
the final code. These "templates" are called *stencils* and they contain *holes*, i.e. missing values. All you have to do for compilation now is to copy and template, and patch in the holes. Thus making it very fast!
@@ -81,8 +81,41 @@ We did a major refactor of our code generation machinery. This makes the code ea
81
81
82
82
- All PRs require review and an approval before merging is allowed. All tests in CI must also pass. This follows standard best practices.
83
83
84
+
##### Copy and Patch JIT Compiler
85
+
86
+
The copy-and-patch JIT compiler uses a stencil compiler provided by Brandt Bucher.
87
+
88
+
- At runtime, each basic block, except the branches (exits) are compiled to machine code.
<
10000
/td>
89
+
- If compilation is successful, execution jumps into the machine code rather than the interpreter bytecode.
90
+
- The branches remain as CPython interpreter bytecode, to faciliatate easy branching.
91
+
- Upon encountering a branch, the interpreter leaves the machine code to go back into bytecode.
92
+
- Execution thus interleaves between machine code and the interpreter.
stencils[jit_stencil.h <br> JIT versions of <br> CPython bytecode]
104
+
tier2[Tier2 Execution]
105
+
instdef -- Used in --> tier2
106
+
stencils -- Used in --> tier2
107
+
typeprop -- Used in --> tier2
108
+
tier2 -- Component of --> python.exe
109
+
subgraph Our Project
110
+
dsl -- Generates --> instdef
111
+
dsl -- Generates --> typeprop
112
+
end
113
+
subgraph Brandt Bucher's Stencil Compiler
114
+
instdef -- Compiles into --> stencils
115
+
end
116
+
```
117
+
118
+
### Runtime
86
119
```mermaid
87
120
sequenceDiagram
88
121
autonumber
@@ -100,25 +133,29 @@ sequenceDiagram
100
133
end
101
134
Tier 1 ->> Tier 2: Code executed more <br> than 63 times and <br> Tier 1 instructions <br> present, triggers the <br> Tier 2 interpreter
102
135
loop Until exit scope executed
103
-
loop until Tier 2 encounters type-specialised tier 1 instruction
136
+
loop until Tier 2 encounters type-specialised tier 1 instruction or a branch instruction
104
137
Note over Tier 2: Tier 2 copies Tier 1 <br> instructions into a <br> buffer to be executed <br> according to runtime <br> type info
105
138
Tier 2 ->> Type Propagator: Requests type propagator
106
139
Type Propagator ->> Tier 2: Type propagator <br> updates runtime type <br> info based on <br>newly emitted code
107
140
end
108
-
Note over Tier 2: Emits a typeguard <br> and executes Tier 2 code <br> until typeguard is hit.
141
+
Note over Tier 2: Emits a typeguard <br> or branch
142
+
Note over Tier 2: JIT compiles current <br> basic block into <br> machine code
143
+
Note over Tier 2: Execute machine code <br> until the end of the <br> basic block
144
+
Note over Tier 2: Execute the Tier 2 <br> branch instruction <br> or type guard
109
145
Tier 2 ->> Type Propagator: Requests type propagator
110
146
Type Propagator ->> Tier 2: Type propagator updates <br> runtime type info <br> based on branch taken
111
-
Note over Tier 2: Emits type specialised <br> branch according to <br> runtime type info
147
+
Note over Tier 2: Starts emitting <br> type specialised <br> branch according to <br> runtime type info
112
148
end
113
149
```
114
150
115
151
## What's left for our project
116
152
117
-
- The Copy and Patch JIT compiler.
153
+
- Just general bugfixing.
154
+
- Evaluation and benchmarking
118
155
119
156
## Evaluation and benchmarks
120
157
121
-
We will run the [bm_nbody.py](./bm_nbody.py) script and the [bm_float_unboxed.py](./bm_float_unboxed.py) to gather results. For now we expect performance to have no improvement as we have yet to implement the copy and patch JIT compiler.
158
+
We will run the [bm_nbody.py](./bm_nbody.py) script and the [bm_float_unboxed.py](./bm_float_unboxed.py) to gather results.
122
159
123
160
## Changelog over CS4215
124
161
@@ -148,6 +185,8 @@ We will run the [bm_nbody.py](./bm_nbody.py) script and the [bm_float_unboxed.py
148
185
149
186
## Build instructions
150
187
188
+
You should install LLVM 16.0 for your system.
189
+
151
190
You should follow the official CPython build instructions for your platform.
0 commit comments