What are common traps when writing JQ queries in terms on code complexity? Any profiling tools?

user_10085368 0
Viewed 93

I have a 300-lines JQ code which run (literally hours) on the files I deal with (plain list of 200K-2.5M JSON objects, 500MB-6GB size).

On the first glance the code looks linear in complexity, but I can easily miss something.

Are there most common traps to be aware of in terms of code complexity in JQ? Or some tools to identify the key bottlenecks in my code?

I'm bit reluctant with making my code public, for size&complexity on one hand, and for its somewhat proprietary nature on the other.

PS. Trimming the input file to keep only most relevant objects AND pre-deflating it to keep only the fields I need are obvious steps towards optimizing my processing flow. I'm wondering what can be done specifically on query complexity side.

jq time-complexity query-optimization
2 Answers

Since you are evidently not a beginner, the likelihood of your making beginners' mistakes seems small, so if you cannot figure out a way to share some details about your program and data, you might try breaking up the program so you can see where the computing resources are being consumed. Well-placed debug statements can be helpful in that regard.

The following filters for computing the elapsed clock time might also be helpful:

def time(f):
  now as $start | f as $out | (now - $start | stderr) | "", $out;

def time(f; $msg):
  now as $start | f as $out | ("\(now - $start): \($msg)" | stderr) | "", $out;

Example

def ack(m;n):
  m as $m | n as $n
  | if $m == 0 then $n + 1
    elif $n == 0 then ack($m-1; 1)
    else ack($m-1; ack($m; $n-1))
    end ;

time( ack(3;7) | debug)

Output:

["DEBUG:",1021]
0.7642250061035156
1021
user_9973580

Often, a program that takes longer than expected is also producing incorrect results, so perhaps the first thing to check is that the results are correct. If they are, then the following might be worth checking:

  • avoid slurping (i.e., use input and/or inputs in preference);
  • beware of functions with arity greater than 0 that call themselves;
  • avoid recomputing intermediate results unnecessarily, e.g. by storing them in $-variables, or by including them in a filter's input;
  • use functions with "short-circuit" semantics when possible, notably any and all
  • use limit/2, first/1, and/or foreach as appropriate;
  • the implementation of index/1 on arrays can be a problem for large arrays, as it first computes all the indices;
  • remember that unique and group_by should be used carefully since both involve a sort.
  • use bsearch for insertion and for binary search for an item in a sorted array;
  • using JSON objects as dictionaries is generally a good idea.

Note also that the streaming parser (invoked with the --stream option) is designed to make the tradeoff between time and space in favor of the latter. It succeeds!

Finally, jq is stream-oriented, and using streams is sometimes more efficient than using arrays.

user_9973580
Related