BurntSushi / BurntSushi/ripgrep

potential missed optimization in extracting a capture group

Open
#1,981 3 comments 0 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
68.3k
Forks
2.8k
PR merge metrics
No merged PRs in 30d

Description

#### What version of ripgrep are you using?
```
ripgrep 13.0.0
-SIMD -AVX (compiled)
+SIMD +AVX (runtime)
```

#### How did you install ripgrep?
Arch Linux's `pacman`.

#### What operating system are you using ripgrep on?
Arch Linux

#### The Missed Optimization (?)

It seems like the following two commands should perform the same task, and that the first should be either faster than or the same speed as the second.

```bash
… | rg -or '$1' '"value":"([^"]+)","type"'
```

```bash
… | rg -o '"value":"[^"]+","type"' | rg -r '' '(?:^"value":"|","type"$)'
```

Instead, the second, pipelined version is four times slower on my machine.

#### What are the steps to reproduce the behavior?

I don't think I can post the data directly here, but I can link to it. It's an open data set. The following command should download it. (The `-L` is necessary for `curl` to follow the redirects.)

Fair warning, the compressed file is something like 11GB. Also, I believe the decompressed file is over 100GB, so you probably don't want to extract it.

```bash
curl -L https://opendata.rapid7.com/sonar.rdns_v2/2021-07-28-1627430820-rdns.json.gz -o 2021-07-28-1627430820-rdns.json.gz
```

If you'd rather not download a big file of domain names, the data generally take the form of the following.

```json
{"timestamp":"","name":"","value":"","type":""}
```

Then, I time the following two commands.

```bash
gzip -dc ./2021-07-28-1627430820-rdns.json.gz | head -n 1000000 | rg -or '$1' '"value":"([^"]+)","type"' | wc -l
```

```bash
gzip -dc ./2021-07-28-1627430820-rdns.json.gz | head -n 1000000 | rg -o '"value":"[^"]+","type"' | rg -r '' '(?:^"value":"|","type"$)'
```

The first version takes 2.7s, and the second takes 0.67s.

Contributor guide

Open the contributing guide

Research direction

Start by reproducing the two documented rg pipelines on a manageable sample of the JSON-shaped data and compare their timings. Trace the rg command entry point and the capture-group extraction path, then use the existing benchmark or test coverage you find to verify the optimization. Done means the capture-group command is no slower than the equivalent pipeline without changing its output.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
cli, performance, search
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
38/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.