JQ Compiler Proposal

[jdroob]

Proposal for Compiled JQ Implementation

What will you do?

Implement a compiler for the JQ programming language.

How will you do it?

1. Familiarization

• I have read and will continue to refer to the JQ wiki for understanding core features, syntax, and semantics.
• I will analyze existing implementations (main JQ, gojq, jq.js) for insights into how language features were implemented.

2. Design

a. Frontend

i. Which language will you use to write the compiler?
- I'm considering either C or C++… most likely C++ as I'm considering using LLVM tools throughout this project.

ii. How will source programs be parsed?
- Bison will be used for parsing.

b. IR (Intermediate Representation)

i. What will the IR look like?
- LLVM IR if feasible.
- Block/Bytecode representation if LLVM is not suitable.

ii. Will you make any optimizations?
- I will implement as many of the "typical" compiler optimizations as possible. By this I mean: dead code elimination, constant folding, constant propagation, copy propagation, loop unrolling, etc. Essentially, as many of the optimizations covered in 6120 as I can.

c. Backend

i. What will the target be?
- The target will be x86 assembly since I'm using a Windows-AMD machine.

ii. Lowering Process
- The input to the backend will either be Bytecode or LLVM IR - in either case, the plan is to target abstract assembly followed by true assembly after the register allocation pass.

3. Implementation

• I will follow the specified design and project roadmap.
• I will maintain a journal to document implementation details and obstacles that I encounter along the way.

4. Testing

• I will test the compiled implementation against the main JQ implementation across a suite of benchmarks.

How will you empirically measure success?

• I will measure and compare the time it takes to compile and execute JQ benchmark programs using my implementation against the execution time of the main implementation.

Questions

• What do you think of using LLVM? I'm unsure if this would be possible since, from what I understand, LLVM is typically used for statically-typed languages whereas JQ is dynamically-typed.

• Do you recommend that I use the existing frontend and just build out the backend?

[sampsyo]

Cool; this sounds about right! Seems like a fun project. Here are a couple of comments:

I will measure and compare the time it takes to compile and execute JQ benchmark programs using my implementation against the execution time of the main implementation.

The other thing to answer here is: where will the benchmarks come from? Presumably, you'll need both the queries and the underlying JSON documents.

What do you think of using LLVM? I'm unsure if this would be possible since, from what I understand, LLVM is typically used for statically-typed languages whereas JQ is dynamically-typed.

It's a good question re. whether LLVM is the right tool for the job. I don't think the statically vs. dynamically typed question actually matters for the LLVM question, however. If your goal is to generate native code, then at some point, you will need to generate a very "static" and low-level program representation—i.e., something close to assembly. At this point, your choices are: (1) generate actual x86 assembly directly, (2) generate LLVM IR and let it translate that to assembly/machine code, or (3) use some other code generator that plays the same role as LLVM would in option #2 (e.g., Cranelift, DynASM, QBE).

All of these seem perfectly reasonable. The main trade-offs are engineering ones: generating x86 assembly will fundamentally involve doing more stuff (e.g., you have to implement register allocation yourself, whereas LLVM or any similar alternative does that for you), but LLVM is more complicated: it's a heavyweight dependency and has a lot of "surface area" one needs to learn to be productive.

Do you recommend that I use the existing frontend and just build out the backend?

I totally think you should just do the backend! There is a great opportunity here to reuse the existing bytecode inside the jq implementation… you can leave the parsing to them, and even some run-time support, and focus only on generating the code.

You could implement your own parser too, but I would keep this as a backup plan if it turns out to be too complicated to use the "official" frontend.

[jdroob]

Checkpoint 1: A Minimally Working "Compiler"

Table of Contents

1. Current Pipeline
2. Tools
3. Next steps
4. Questions

Current Pipeline

    +------------------+
    |       main()     |
    |    cjq/main.c    |
    +--------+---------+
             |
             | jq src, JSON data
             |
    +--------v---------+
    |  cjq_parse()     |
    |cjq/cjq_frontend.c|
    +--------+---------+
             | 
             | bytecode, temp struct for JSON
             |
    +--------v---------+
    |    jq_program()  |
    |      cjq/main.c  |
    +--------+---------+
             |
             | execute jq program
             |
    +--------v---------+
    |  cjq_execute()   |
    |cjq/cjq_frontend.c|
    +------------------+

At the time of this writing, the above diagram depicts the flow of execution from reading command line inputs to executing the program.

In the beginning of the pipeline, both the JQ source program and the input JSON data are read into the compiler's entry point and immediately passed to the compiler frontend. Using the same frontend used in the JQ interpreter, JQ source code is compiled to bytecode. Additionally, JSON data is stored in a more convenient struct at this point. The bytecode, JSON data, and additional JQ flags are saved into a global struct called cjq_state before control returns to the compiler entry point.

Next, a compiled LLVM IR function called jq_program is called. At this point, all jq_program does is call the C function cjq_execute which executes the JQ program based on data stored in cjq_state. NOTE: cjq_execute, is simply a wrapper function that invokes the JQ interpreter's VM. cjq_execute is also responsible for passing data from cjq_state to the VM.

Tools

The tools used to implement the CJQ compiler so far have been the programming languages C and Python as well as the Python library llvmlite.

The bulk of the compiler functionality required for actual program execution is written in C, as I believe implementing the stack-based execution functionality and all requisite data structures using something as low-level as LLVM IR would be error-prone. Python is used to build an LLVM IR program that makes calls to these C functions. Specifically, a Python library called llvmlite is used to build an LLVM IR program which compiles to machine code using clang.

Next steps

As it stands, the CJQ "compiler" produces a compiled program that simply makes a call to a function that executes the JQ program in the same way the JQ interpreter executes the JQ program. While this alone accomplishes nothing performance-wise, the work done so far has opened the door for potential performance gains and increased reusability.

To implement the improvements I have in mind, I first need to split the CJQ pipeline into two main stages.

1. In the first stage, which I'm currently referring to as "the tracing stage", the JQ source program will be compiled down to bytecode - and the cjq_state struct will be initialized exactly how it is now. By the time cjq_state has been initialized, the sequence of bytecode instructions is known. Since the sequence of bytecode instructions is known, Python and llvmlite can be used to generate a sequence of calls (in LLVM IR) to unique C functions that each perform the same tasks performed when the VM reads a particular opcode. This will bring more of the program out of C and into LLVM IR. This has two potential benefits: (1) Rather than one big switch statement that reads the current bytecode instruction and determines which actions to execute next (which is how the VM operates), we have a straightline sequence of function calls based on the compiled sequence of bytecode instructions. I believe this is where the CJQ implementation can begin to diverge from the JQ implementation. While the JQ implementation is a traditional bytecode interpreter, I'd like to capture the actions taken during the execution of a specific JQ program. I want these actions to be translated to equivalent LLVM IR instructions at compile time. I believe isolating these actions in the form of LLVM IR instructions opens the door for further optimizations. (2) Inlining functions. The details of how C functions will be inlined into an LLVM program remains to be determined.

Here is an example of the LLVM output I have in mind. Note that these "opcode-functions" still need to be implemented in C:

; ModuleID = '<string>'
source_filename = "<string>"
target triple = "x86_64-unknown-linux-gnu"

define void @jq_program() {
entry:
  call void @_opcode_TOP()
  call void @_opcode_SUBEXP_BEGIN()
  call void @_opcode_PUSHK_UNDER()
  call void @_opcode_INDEX()
  call void @_opcode_SUBEXP_END()
  call void @_opcode_SUBEXP_BEGIN()
  call void @_opcode_PUSHK_UNDER()
  call void @_opcode_INDEX()
  call void @_opcode_SUBEXP_END()
  call void @_opcode_CALL_BUILTIN_plus()
  call void @_opcode_RET()
  call void @_opcode_BACKTRACK_RET()
  call void @_cjq_execute()
  ret void
}

declare void @_opcode_TOP()

declare void @_opcode_BACKTRACK_TOP()

declare void @_opcode_SUBEXP_BEGIN()

declare void @_opcode_BACKTRACK_SUBEXP_BEGIN()

declare void @_opcode_PUSHK_UNDER()

declare void @_opcode_BACKTRACK_PUSHK_UNDER()

declare void @_opcode_INDEX()

declare void @_opcode_BACKTRACK_INDEX()

declare void @_opcode_SUBEXP_END()

declare void @_opcode_BACKTRACK_SUBEXP_END()

declare void @_opcode_CALL_BUILTIN_plus()

declare void @_opcode_BACKTRACK_CALL_BUILTIN_plus()

declare void @_opcode_RET()

declare void @_opcode_BACKTRACK_RET()

declare void @_cjq_execute()

2. In the second stage, or "the execution stage", a second C program can be used to read in new JSON data and pass it to the main function generated from the LLVM IR. Assuming the JSON data is formatted in such a way that it makes sense to be used as input given the context of the program, execution will presumably be faster since the LLVM IR code will simply be a sequence of function calls to "opcode functions". Moreover, this improves reusability as the JQ program only needs to be compiled once. Afterwards, it may be used on any compatible input JSON data.

I'd like to add that I've borrowed a collection of JQ programs that were used for testing the JQ interpreter. I'm currently finding appropriate JSON programs for the given tests and will use these tests to confirm the CJQ compiler produces the same results as the JQ interpreter, and later to compare the performance of each implementation.

Questions

First, do you agree with my overall approach in the 'Next Steps' section above?

Second - I'm currently just producing an LLVM module that calls a C function called _cjq_execute which executes the jq bytecode exactly how the VM currently does. This is what the current LLVM IR looks like:

; ModuleID = '<string>'
source_filename = "<string>"
target triple = "x86_64-unknown-linux-gnu"

define void @jq_program() {
    entry:
    call void @_cjq_execute()
    ret void
}

declare void @_cjq_execute()

My next milestone is to produce a sequence of function calls in LLVM to C functions that perform the same actions that the VM would perform while reading the sequence of bytecode instructions. Eventually, I'd like to somehow inline these C functions so the stack-based logic would truly be in LLVM. I'm not sure how important this truly is. It feels like it would open the door for more optimization opportunities but if clang already performs all these optimizations at compile time (i.e. when I compile the ir.ll file with the rest of the C code required for reading in JSON data and pass it to the main function in the LLVM IR) then I don't want to waste my time. So my question is: Is trying to inline functions worth it?

[jdroob]

UPDATE: Currently implementing opcode functions in granular branch. Some refactoring was required to ensure flow of execution matched that of the JQ interpreter. Per basic functionality test script, CJQ is able to match JQ output for all opcodes that have been implemented in CJQ so far.

My current plan is to implement all examples from the JQ manual as test cases which I believe should cover most, if not all, of the standard JQ functionality. I think following the manual will allow me to use more of a test-driven development approach to implementing the opcode functions.

Once the opcode functions are implemented, I plan to move on to measuring CJQ performance and comparing to the standard JQ implementation.

EDIT: I've also been looking into LLVM's inlining capabilities and believe I can accomplish this by simply passing the correct flags to clang when I compile. Will investigate this further shortly.

[sampsyo]

Sounds great! I'd be interested to see how those tests turn out. 😃

[jdroob]

All tests are passing! That is, the outputs produced by CJQ match the outputs produced by the standard JQ implementation for all examples from the JQ manual.

The last few things I wanted to get to before wrapping up are (i) serialization/deserialization (ii) ensuring that the generated LLVM IR inlines the bodies of the opcode functions being called and (iii) comparing the performance of CJQ to the standard JQ implementation.

I'm having some difficulties with part (i) and I'm hoping to get your take on the issue I'm running into. For background, I'm trying to serialize and deserialize a list of compiled_jq_state structures. I'm trying to do this because 1. I'm currently compiling source JQ code to bytecode in both the tracing stage and the execution stage (without going into too much detail, I'm compiling the jq source to bytecode in the execution stage to set up the stack properly before the sequence of opcode functions are called). I'd like to serialize so I don't compile a second time, and 2. CJQ currently only works for one input (e.g. one JSON file or one JSON text string from stdin). I'd like to extend this to support more than one input to match the standard implementation's flexibility.

Here's what a compiled_jq_state struct looks like

typedef struct {
    int* ret;
    int* jq_flags;
    int* dumpopts;
    int* options;
    int* last_result;
    int* raising;
    jv* value;
    jv* result;
    jv* cfunc_input;
    jq_state* jq;
    uint16_t* pc;
    uint16_t* opcode;
    int* backtracking;
    uint8_t* fallthrough;
} compiled_jq_state;

One of the members of a compiled_jq_state struct is a jq_state struct - here's what a jq_state struct looks like:

struct jq_state {
  void (*nomem_handler)(void *);
  void *nomem_handler_data;
  struct bytecode* bc;

  jq_msg_cb err_cb;
  void *err_cb_data;
  jv error;

  struct stack stk;
  stack_ptr curr_frame;
  stack_ptr stk_top;
  stack_ptr fork_top;

  jv path;
  jv value_at_path;
  int subexp_nest;
  int debug_trace_enabled;
  int initial_execution;
  unsigned next_label;

  int halted;
  jv exit_code;
  jv error_message;

  jv attrs;
  jq_input_cb input_cb;
  void *input_cb_data;
  jq_msg_cb debug_cb;
  void *debug_cb_data;
  jq_msg_cb stderr_cb;
  void *stderr_cb_data;
};

The issue I'm having is a well-known C issue - serializing a struct with pointers is tricky. There's no point in serializing the pointers since the addresses they point to won't hold the same data when the pointers are deserialized. To make things more confusing, jq_state has a function pointer member - which is a whole other can of worms when it comes to deserialization. One option I have is to come up with my own data layout, serialize all the data pointed to by the pointers in compiled_jq_state, and ensure that when I deserialize, I assign each data field in my data layout to the correct pointer. This will be tricky but (I think) doable. Also, I'm leaning towards ignoring function pointers for now. These are used for debugging purposes anyway. They'll be nice to have in the future, but I don't think they're necessary at this point in time.

What are your thoughts? Please feel free to let me know if you see a better approach 😆

[sampsyo]

Wow, that's awesome that it's working so far!

Interesting problem w/r/t serializing this state. I guess one big question I have is: do you really need the entire jq_state to be serialized, for the use case you're looking at? In particular, I could be totally wrong, but it kinda seems to me like all this state, to some degree, captures the intermediate state of a currently-running program (e.g., the pc). For the situations you mentioned (e.g., processing multiple inputs with the same compiled program), is that currently-executing state actually relevant? Or can you safely re-initialize that to zero? In that case, you would only need to serialize the parts of the program that persist across multiple executions—namely, stuff like the bytecode array. Would that make sense?

Anyway, if not, you are probably right that inventing a custom data layout is the way to go, although it sounds somewhat painful. You could also imagine trying to use an off-the-shelf serialization format just to simplify things, at the cost of some performance… for example, even JSON itself would be a possible candidate.

[jdroob]

I think you're right! I believe the bytecode struct member of jq_state is the only data structure that needs to be serialized. I think this is the case because, by definition, the bytecode struct is the structure initialized after the jq source code is compiled down to bytecode - so this data is obviously needed prior to the first and all subsequent executions. If there are multiple inputs, the stack should look the same before each execution since no instructions will have been executed at that point. I'm going to get started on serializing the bytecode struct. I'll keep you updated 😀

[jdroob]

Update

Hi @sampsyo - so after a lot of hacking together, testing, and debugging - serialization and deserialization works! And I'm very happy to say that you were right and that the bytecode struct was the only data structure that was required to be serialized in order to maintain the necessary information to run the jq programs without recompiling 😄

To refresh you (and myself) on the current state of the compilation pipeline, here's a brief summary:

1. JQ source code is compiled to bytecode
2. Given 0 or more JSON documents, the interpreter is invoked. While the interpreter is running, the dynamic sequence of bytecode opcodes is recorded, or traced. Using the trace, LLVM IR is generated. The generated LLVM IR is simply a sequence of calls to opcode functions which perform the same logic as the VM when it executes the same bytecode opcodes. [EDIT: I've since modified this so that rather than calling an opcode function for every dynamic opcode traced, I first create a set of unique subsequences of opcodes that, when put together in sequence in the correct order, are the equivalent sequence of opcodes to the dynamic sequence of opcodes traced.

For example,

source_filename = "<string>"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

define void @jq_program(i8* %.1) {
entry:
  call void @_subsequence_func32(i8* %.1)
  call void @_subsequence_func24(i8* %.1)
  call void @_subsequence_func25(i8* %.1)

....

; Function Attrs: noinline
define void @_subsequence_func24(i8* %.1) #1 {
subsequence_24:
  call void @_opcode_LOADVN(i8* %.1)
  call void @_opcode_SUBEXP_BEGIN(i8* %.1)
  ret void
}

; Function Attrs: noinline
define void @_subsequence_func25(i8* %.1) #1 {
subsequence_25:
  call void @_opcode_POP(i8* %.1)
  call void @_opcode_TRY_BEGIN(i8* %.1)
  ret void
}

...

; Function Attrs: noinline
define void @_subsequence_func32(i8* %.1) #1 {
subsequence_32:
  call void @_opcode_RET(i8* %.1)
  call void @_init_jq_next(i8* %.1)
  ret void
}

Each of the above subsequence functions calls 1 or more opcode functions. This helped with reducing compile time because originally, I was trying to inline all calls to opcode functions which was making the LLVM IR way too big and making the optimization passes either take hours or crash altogether. Now, the jq_program LLVM IR function makes calls to subsequence functions that are not inlined. The opcode functions on the other hand are inlined within each subsequence function. The difference is that across many tests there are only about 40 subsequence functions max, each containing only about 2-3 opcode function calls. So the amount of inlining that takes place using this subsequence approach is much less than was previously taking place. ]

3. Using clang, the LLVM IR is compiled with the code responsible for reading in JSON data, deserializing the serialized bytecode, constructing and initializing the cjq_state pointer, and passing this pointer to the entry point function of the LLVM IR. This is also the step where clang O3 optimizations and an inlining pass is performed to optimize the resulting executable as much as possible.
4. Now the user can simply pass in formatting flags and JSON data. Commands will take the form of:

<executable-name> <optional-formatting-flags> <json-file1> <json-file2> ...

Looking ahead

At this point, I'm not planning to add any additional functionality to the implementation until I've finished the thesis. I would like to get Cmake set up so that CJQ will work on machines other than my own. Aside from this, I've been spending most of my time working on my thesis. Here is my current outline - feel free to let me know if there's anything you'd like me to add, remove, or move around.

Thesis Outline

Abstract

JQ is a popular and powerful JSON processing tool known for its ability to easily filter, transform, and manipulate JSON data. To most JQ users' surprise, JQ is a functional programming language. One of the main appeals of the JQ programming language is that it offers expressive and concise syntax which allows users to perform complex data operations with minimal code. The standard implementation of JQ consists of a source-to-bytecode compiler and a virtual machine (VM) that decodes and executes the stream of bytecode opcodes. While this implementation achieves high performance for most workloads, its execution time can begin to reach a bottleneck when handling very large-scale JSON files.

This thesis introduces CJQ, a novel compiler that translates JQ bytecode into LLVM intermediate representation (IR). By leveraging the LLVM compiler infrastructure and re-purposing much of the standard JQ implementation's internals, CJQ significantly enhances performance, making it more efficient for handling megabyte-scale JSON data. Additionally, CJQ improves portability via the standard, platform-independent LLVM bitcode. CJQ also improves reusability with the new capability of compiling JQ programs into standalone executables. This approach lowers the barrier to entry for those unfamiliar with the JQ programming language, enabling a broader audience to harness the power of JQ without needing in-depth knowledge of the JQ language.
Through CJQ, we aim to combine the functional elegance of JQ with the high performance of compiled languages, delivering a robust tool that meets the demands of modern data processing tasks.

Background

JQ Background

• Key design points of the language, syntax, semantics, a couple of examples
• The standard implementation (overview of the stack-based VM)

LLVM Background

• What is LLVM?
• LLVM IR basics, syntax, semantics
• SSA review
• How LLVM optimization passes are key to making CJQ deliver on its promises

Other Bytecode to Machine Code Compilers

• Discuss 2 or 3 other bytecode to machine code compilers such as Numba or Liftoff
• Discuss the compile time / execution time tradeoffs of these implementations

Implementation

• General overview of the CJQ pipeline
• Tracing phase implementation details
• Lowering phase implementation details
• Optimization / Code Generation phase implementation details

Performance Evaluation

• Compare CJQ to the standard JQ implementation across two main benchmarks - the first consisting of small JSON documents and the second, using the same JQ programs but focusing on large JSON documents
• Compare CJQ to jaq using benchmarks put together by the creator of jaq and used in a paper he wrote.
• Discuss startup time / runtime tradeoffs across the two implementations

Conclusion and Future Thoughts

-Discuss ways to improve CJQ moving forward - such as tracing without the VM also executing the stream of opcodes.
-Discuss the possibility of using copy and patch approach to implement the JQ language using a JIT compiler which seems like it'd be a more reasonable tradeoff in terms of startup time : runtime.

Thanks for reading this very long update 😆 . One quick note is that I'm getting married on 6/26 so I won't be working on this between 6/24 and 6/29. I'm hoping to get a first draft to you before 6/24 but if not, then very soon after!

[sampsyo]

I trust you make it clear from context! 😃

(I will read the full report in detail soon!)

[sampsyo]

First of all, CONGRATULATIONS on your upcoming wedding! Wahoo! I hope it's a blast.

This all sounds awesome to me. I think it's cool that you found a way around the "inlining explosion" that would happen if you tried to inline every single opcode-call into one giant monolithic program; this way of breaking things up with an intermediate tier seems a totally reasonable hack.

The outline looks great overall! I think it will be really interesting to see some performance results, especially as data sizes scale up. TBH I think you could safely skip the comparison against jaq; while cool-looking and potentially interesting, it is not absolutely necessary IMO.

One thing you might consider thinking about as you're writing up the thesis: how might you publicize this in the world of open-source software? This seems like a thing people might want to use and build upon! Can you package it up with some documentation, examples, etc. to encourage the world to give it a try? 😃

[jdroob]

Thanks! It was an amazing week 😄

I will spend the next week or so finishing up the first draft of my thesis and I will leave out the jaq comparison (I agree it isn't necessary for my purposes). Hoping to schedule my M Exam for mid-July but am happy to pick a day that works best with your schedule. [EDIT: I reached out to the other member of my advisory committee - Zhiru Zhang, and he informed me that he can only attend the last week of July or the first week of August. Since I need to complete my defense before 8/1, does the last week of July work with your schedule?].

I'm happy you brought up the open-sourcing process - this is all very new to me but I'm very excited to share my first open-source tool with others in hopes that at least a few people might find it useful 😆 . I'm in a discord with the jq maintainers and am planning to share a copy of my thesis as well as a link to the repo with them once the thesis is finished.

Documentation-wise, I've spruced up the README a bit, although it's still under construction, and will add more thorough, tutorial-style documentation after the thesis is complete. I also need to make some minor changes to the command line interface and am currently working with friends of mine who use other platforms to try to minimize the pain of the setup process as much as possible 😆

[sampsyo]

Great! Yep, the last week of July works just fine for me. 😃

And that all sounds great! One thing we can think about (after your M-exam happens) is writing a blog-post-styled version of the thesis, which could serve as good vehicle to get the word out there. 😃

[jdroob]

That sounds great! I'd be more than happy to write a blog post to summarize my thesis 😀 - speaking of, I'm planning to have the first draft of my thesis to you after this weekend. Apologies for the delay! I've gained a newfound respect for the authors of research papers through this process 😆. I'm currently finishing up the section on the details of the cjq implementation. Then I just need to finish my performance comparison of cjq to the standard jq implementation.