Bug 223553

Summary: bsdgrep in -current is 10 times slower than before
Product: Base System Reporter: Wolfram Schneider <wosch>
Component: binAssignee: freebsd-bugs (Nobody) <bugs>
Status: Open ---    
Severity: Affects Only Me CC: emaste, kevans
Priority: --- Keywords: regression
Version: CURRENT   
Hardware: Any   
OS: Any   
Bug Depends on: 223532    
Bug Blocks: 230332    

Description Wolfram Schneider freebsd_committer 2017-11-09 09:18:05 UTC
While working on bug #223532 I noticed that bsdgrep on a recent FreeBSD12-current is much slower than on FreeBSD11-stable

On both machines runs the same bsdgrep version 2.6.0
$ /usr/bin/bsdgrep -V
bsdgrep (BSD grep, GNU compatible) 2.6.0-FreeBSD

How to repeat:

First, we create a 100MB text file:
for i in $(seq 1 20);do man tcsh;done > /tmp/tcsh20;
for i in $(seq 1 20); do cat /tmp/tcsh20;done > /tmp/tcsh400

$ du -hs /tmp/tcsh400
 99M    /tmp/tcsh400

# FreeBSD11-stable
LANG=en_CA.UTF-8 time /usr/bin/bsdgrep  -ic  foobar /tmp/tcsh400
        2.06 real         2.00 user         0.05 sys

# FreeBSD12-current 
LANG=en_CA.UTF-8 time /usr/bin/bsdgrep  -ic  foobar /tmp/tcsh400
       19.27 real        19.17 user         0.05 sys
Comment 1 Wolfram Schneider freebsd_committer 2017-11-09 09:39:13 UTC
It is also slow for LANG=C. Search times goes from 0.5 seconds to 4.3 seconds.

# FreeBSD 11-stable
LANG=C time /usr/bin/bsdgrep  -ic  foobar /tmp/tcsh400
        0.53 real         0.50 user         0.03 sys

# FreeBSD 12-current
LANG=C time /usr/bin/bsdgrep  -ic  foobar /tmp/tcsh400
        4.33 real         4.26 user         0.06 sys
Comment 2 Kyle Evans freebsd_committer 2017-11-09 13:16:59 UTC
Now that's odd- the difference between these two is that -HEAD defaults to WITHOUT_BSD_GREP_FASTMATCH (TRE). In all of my testing on three or four amd64 boxes, performance difference between the two never differed more than ~4%.

What kind of performance do you get on the -HEAD box if you flip BSD_GREP_FASTMATCH back on? With that kind of discrepancy, it might be worth fixing up TRE after all.
Comment 3 Kyle Evans freebsd_committer 2017-11-14 16:59:49 UTC
In testing, I've found that flipping GNU_GREP_COMPAT off by default in -HEAD is what caused the slowdown. Comparable performance can be achieved by turning it back on, which leads me to the conclusion that our regex(3) is the source of slowdown in this instance.

I think this leads me to two conclusions:

1.) Our regex(3) implementation needs optimized or replaced
2.) We need to improve our usage of regex(3)

These are both important, but #2 is something we've been needing to do anyways and probably the lower-hanging fruit. I think this would be accomplished by calling regex(3) less with larger chunks of text, rather than breaking up text line-by-line. This would allow us to take advantage of the optimizations to be had with larger subject strings and reduce the overhead (in most cases) by no longer having to search for all newlines.
Comment 4 Eitan Adler freebsd_committer freebsd_triage 2018-05-20 23:53:01 UTC
For bugs matching the following conditions:
- Status == In Progress
- Assignee == "bugs@FreeBSD.org"
- Last Modified Year <= 2017

- Set Status to "Open"