MiSawa / xq

Pure rust implementation of jq
MIT License
318 stars 18 forks source link

Improve keys, keys_unsorted performance #102

Closed itchyny closed 2 years ago

itchyny commented 2 years ago

The definition of keys_unsorted using path/1 is very interesting (honestly I didn't come up with this definition), but should have some overhead. Since keys is used widely, improving its performance by internal implementation is worth considering. What do you think?

❯ env q='[range(10000)] | keys' hyperfine --warmup 10 'xq-new -n "$q"' 'xq-old -n "$q"'
Benchmark 1: xq-new -n "$q"
  Time (mean ± σ):      17.2 ms ±   0.8 ms    [User: 14.5 ms, System: 2.2 ms]
  Range (min … max):    15.9 ms …  21.9 ms    153 runs

  Warning: Statistical outliers were detected. Consider re-running this benchmark on a quiet PC without any interferences from other programs. It might help to use the '--warmup' or '--prepare' options.

Benchmark 2: xq-old -n "$q"
  Time (mean ± σ):      37.6 ms ±   1.2 ms    [User: 34.8 ms, System: 2.2 ms]
  Range (min … max):    36.3 ms …  45.0 ms    75 runs

  Warning: Statistical outliers were detected. Consider re-running this benchmark on a quiet PC without any interferences from other programs. It might help to use the '--warmup' or '--prepare' options.

Summary
  'xq-new -n "$q"' ran
    2.18 ± 0.12 times faster than 'xq-old -n "$q"'

By the way, note that keys_unsorted is not the insertion order.

❯ xq -nc '{c:1,a:2,b:3} | keys_unsorted'
["c","a","b"]

❯ xq -nc '{c:1,a:2,b:3} | keys_unsorted' # oops, changes each execution
["a","c","b"]
MiSawa commented 2 years ago

Thank you!