`del(f)` changes the order of keys

[mrazauskas]

Thanks for jaq. Great project!

I have noticed that del(f) changes the order of keys. That does not happen with jq:

• echo '{"a": 1, "b": 2, "c": 3, "d": 4}' | jaq 'del(.b)' -> {"a": 1, "d": 4, "c": 3}
• echo '{"a": 1, "b": 2, "c": 3, "d": 4}' | jq 'del(.b)' -> {"a": 1, "c": 3, "d": 4}

The output data is correct. Unnecessary diff in a large JSON file is the only issue.

[01mf02]

Hi @mrazauskas, thank you!

The culprit of this behaviour lies here. When removing an element from an object, changing the element order seems to be significantly more performant than preserving it.

I made a little benchmark, where I replaced swap_remove by shift_remove (which preserves order):

$ hyperfine -M5 -L jq jq,target/release/jaq-swap-remove,target/release/jaq-shift-remove "{jq} -n 'reduce (range(10000) | tostring) as \$i ({}; . + {(\$i): \$i}) | reduce keys[] as \$k (.; .[\$k] |= empty)'"
Benchmark 1: jq -n 'reduce (range(10000) | tostring) as $i ({}; . + {($i): $i}) | reduce keys[] as $k (.; .[$k] |= empty)'
  Time (mean ± σ):      1.382 s ±  0.007 s    [User: 1.372 s, System: 0.002 s]
  Range (min … max):    1.371 s …  1.387 s    5 runs
 
Benchmark 2: target/release/jaq-swap-remove -n 'reduce (range(10000) | tostring) as $i ({}; . + {($i): $i}) | reduce keys[] as $k (.; .[$k] |= empty)'
  Time (mean ± σ):      21.4 ms ±   0.4 ms    [User: 18.3 ms, System: 2.8 ms]
  Range (min … max):    20.9 ms …  21.9 ms    5 runs
 
Benchmark 3: target/release/jaq-shift-remove -n 'reduce (range(10000) | tostring) as $i ({}; . + {($i): $i}) | reduce keys[] as $k (.; .[$k] |= empty)'
  Time (mean ± σ):     148.5 ms ±   1.0 ms    [User: 146.3 ms, System: 1.2 ms]
  Range (min … max):   147.4 ms … 149.9 ms    5 runs
 
Summary
  target/release/jaq-swap-remove -n 'reduce (range(10000) | tostring) as $i ({}; . + {($i): $i}) | reduce keys[] as $k (.; .[$k] |= empty)' ran
    6.95 ± 0.13 times faster than target/release/jaq-shift-remove -n 'reduce (range(10000) | tostring) as $i ({}; . + {($i): $i}) | reduce keys[] as $k (.; .[$k] |= empty)'
   64.71 ± 1.21 times faster than jq -n 'reduce (range(10000) | tostring) as $i ({}; . + {($i): $i}) | reduce keys[] as $k (.; .[$k] |= empty)'

We can see that jq is significantly slower than both variants here, and changing order is about 7 times faster than preserving it. However, I used .[$k] |= empty to achieve the same effect as del(.[$k]) here. What happens if we use del, as in your example?

$ hyperfine -M5 -L jq jq,target/release/jaq-swap-remove,target/release/jaq-shift-remove "{jq} -n 'reduce (range(10000) | tostring) as \$i ({}; . + {(\$i): \$i}) | reduce keys[] as \$k (.; del(.[\$k]))'"
Benchmark 1: jq -n 'reduce (range(10000) | tostring) as $i ({}; . + {($i): $i}) | reduce keys[] as $k (.; del(.[$k]))'
  Time (mean ± σ):      24.9 ms ±   0.8 ms    [User: 21.4 ms, System: 3.3 ms]
  Range (min … max):    24.0 ms …  25.8 ms    5 runs
 
Benchmark 2: target/release/jaq-swap-remove -n 'reduce (range(10000) | tostring) as $i ({}; . + {($i): $i}) | reduce keys[] as $k (.; del(.[$k]))'
  Time (mean ± σ):      21.7 ms ±   0.3 ms    [User: 19.6 ms, System: 1.9 ms]
  Range (min … max):    21.3 ms …  22.0 ms    5 runs
 
Benchmark 3: target/release/jaq-shift-remove -n 'reduce (range(10000) | tostring) as $i ({}; . + {($i): $i}) | reduce keys[] as $k (.; del(.[$k]))'
  Time (mean ± σ):     150.6 ms ±   0.6 ms    [User: 148.1 ms, System: 1.7 ms]
  Range (min … max):   149.9 ms … 151.4 ms    5 runs
 
Summary
  target/release/jaq-swap-remove -n 'reduce (range(10000) | tostring) as $i ({}; . + {($i): $i}) | reduce keys[] as $k (.; del(.[$k]))' ran
    1.14 ± 0.04 times faster than jq -n 'reduce (range(10000) | tostring) as $i ({}; . + {($i): $i}) | reduce keys[] as $k (.; del(.[$k]))'
    6.94 ± 0.09 times faster than target/release/jaq-shift-remove -n 'reduce (range(10000) | tostring) as $i ({}; . + {($i): $i}) | reduce keys[] as $k (.; del(.[$k]))'

Here, we can see that jaq remains on par with jq only when using swap_remove.

It would be interesting to see how jq achieves del with such high performance without changing of order, and why this is so much faster than .[$k] |= empty ...
In any case, it should become clear that with jaq's current object datatype, we have to choose either performance or compatibility for this behaviour.