Ignore a line containing a pattern from a long text file in Go

I'm trying to implement a function to ignore a line containing a pattern from a long text file (ASCII guaranteed) in Go

The functions I have below withoutIgnore and withIgnore, both take a filename argument input and return a *byte.Buffer, which can be subsequently used to write to a io.Writer.

The withIgnore function takes an additional argument pattern to exclude the line containing the pattern from the file. The function works, but with benchmarking, found it to be 5x slower than withoutIgnore. Is there a way it could be improved?

package main

import (
	"bufio"
	"bytes"
	"io"
	"log"
	"os"
)

func withoutIgnore(f string) (*bytes.Buffer, error) {
	rfd, err := os.Open(f)
	if err != nil {
		log.Fatal(err)
	}

	defer func() {
		if err := rfd.Close(); err != nil {
			log.Fatal(err)
		}
	}()

	inputBuffer := make([]byte, 1048576)
	var bytesRead int

	var bs []byte
	opBuffer := bytes.NewBuffer(bs)

	for {
		bytesRead, err = rfd.Read(inputBuffer)

		if err == io.EOF {
			return opBuffer, nil
		}

		if err != nil {
			return nil, nil
		}

		_, err = opBuffer.Write(inputBuffer[:bytesRead])
		if err != nil {
			return nil, err
		}
	}
	return opBuffer, nil
}

func withIgnore(f, pattern string) (*bytes.Buffer, error) {
	rfd, err := os.Open(f)
	if err != nil {
		log.Fatal(err)
	}

	defer func() {
		if err := rfd.Close(); err != nil {
			log.Fatal(err)
		}
	}()

	scanner := bufio.NewScanner(rfd)
	var bs []byte
	buffer := bytes.NewBuffer(bs)
	for scanner.Scan() {
		if !bytes.Contains(scanner.Bytes(), []byte(pattern)) {
			_, err := buffer.WriteString(scanner.Text() + "\n")
			if err != nil {
				return nil, nil
			}
		}
	}

	return buffer, nil
}

func main() {
	// buff, err := withoutIgnore("base64dump.log")
	buff, err := withIgnore("base64dump.log", "AUDIT")
	if err != nil {
		log.Fatal(err)
	}

	_, err = buff.WriteTo(os.Stdout)
	if err != nil {
		log.Fatal(err)
	}
}

Benchmark test

package main

import "testing"

func BenchmarkTestWithoutIgnore(b *testing.B) {
	for i := 0; i < b.N; i++ {
		_, err := withoutIgnore("base64dump.log")
		if err != nil {
			b.Fatal(err)
		}
	}
}

func BenchmarkTestWithIgnore(b *testing.B) {
	for i := 0; i < b.N; i++ {
		_, err := withIgnore("base64dump.log", "AUDIT")
		if err != nil {
			b.Fatal(err)
		}
	}
}

and the "base64dump.log" can be generated in the command line using

base64 /dev/urandom | head -c 10000000 > base64dump.log

Since ASCII is guaranteed, one can work directly at byte level.

Still if one checks each byte for line breaks when reading the input and then searches for the pattern again within the line, operations are applied to each byte.

If, on the other hand, one reads chunks of the input and performs an optimized search for the pattern in the text, not even examining each input byte, one minimizes the operations per input byte.

For example, there is the Boyer-Moore string search algorithm. Go's built-in bytes.Index function is also optimized. The achieved speed depends of course on the input data and the actual pattern. For the input as specified in the question, `bytes.Index turned out to be significantly more performant when measured.

Procedure

• read in a chunk, where the chunk size should be significantly longer than the maximum line length, a value >= 64KB should probably be good, in the test 1MB was used as in the question.
• a chunk usually doesn't end at a linefeed, so search from the end of the chunk to the next linefeed, limit the search to this slice and remember the remaining data for the next pass
• the last chunk does not necessarily end in a linefeed
• with the help of the performant GO function bytes.Index you can find the places where the pattern occurs in the chunk
• from the found location one searches for the preceding and the following linefeed
• then the block is output up to the corresponding beginning of the line
• and the search is continued from the end of the line where the pattern occurred
• if the search does not find another location, the rest is output
• read the next chunk and apply the described steps again until the end of the file is reached

Noteworthy

A read operation may return less data than the chunk size, so it makes sense to repeat the read operation until the chunk size data has been read.

Benchmark

Optimized code is often significantly more complicated, but the performance is also significantly better, as we will see in a moment.

BenchmarkTestWithoutIgnore-8   	     270	   4137267 ns/op
BenchmarkTestWithIgnore-8      	      54	  22403931 ns/op
BenchmarkTestFilter-8          	     150	   7947454 ns/op

Here, the optimized code BenchmarkTestFilter-8 is only about 1.9x slower than the operation without filtering while the BenchmarkTestWithIgnore-8 method is 5.4x slower than the comparison value without filtering.

Looked at another way: the optimized code is 2.8 times faster than the unoptimized one.

Code

Of course, here is the code for your own tests:

func filterFile(f, pattern string) (*bytes.Buffer, error) {
rfd, err := os.Open(f)
if err != nil {
log.Fatal(err)
}
defer func() {
if err := rfd.Close(); err != nil {
log.Fatal(err)
}
}()
reader := bufio.NewReader(rfd)
return filter(reader, []byte(pattern), 1024*1024)
}
// chunkSize must be larger than the longest line
// a reasonable size is probably >= 64K
func filter(reader io.Reader, pattern []byte, chunkSize int) (*bytes.Buffer, error) {
var bs []byte
buffer := bytes.NewBuffer(bs)
chunk := make([]byte, chunkSize)
var remaining []byte
for lastChunk := false; !lastChunk; {
n, err := readChunk(reader, chunk, remaining, chunkSize)
if err != nil {
if err == io.EOF {
lastChunk = true
} else {
return nil, err
}
}
remaining = remaining[:0]
if !lastChunk {
for i := n - 1; i > 0; i-- {
if chunk[i] == '\n' {
remaining = append(remaining, chunk[i+1:n]...)
n = i + 1
break
}
}
}
s := 0
for s < n {
hit := bytes.Index(chunk[s:n], pattern)
if hit < 0 {
break
}
hit += s
startOfLine := hit
for ; startOfLine > 0; startOfLine-- {
if chunk[startOfLine] == '\n' {
startOfLine++
break
}
}
endOfLine := hit + len(pattern)
for ; endOfLine < n; endOfLine++ {
if chunk[endOfLine] == '\n' {
break
}
}
endOfLine++
_, err = buffer.Write(chunk[s:startOfLine])
if err != nil {
return nil, err
}
s = endOfLine
}
if s < n {
_, err = buffer.Write(chunk[s:n])
if err != nil {
return nil, err
}
}
}
return buffer, nil
}
func readChunk(reader io.Reader, chunk, remaining []byte, chunkSize int) (int, error) {
copy(chunk, remaining)
r := len(remaining)
for r < chunkSize {
n, err := reader.Read(chunk[r:])
r += n
if err != nil {
return r, err
}
}
return r, nil
}

And the benchmark part might look something like this:

func BenchmarkTestFilter(b *testing.B) {
for i := 0; i < b.N; i++ {
_, err := filterFile("base64dump.log", "AUDIT")
if err != nil {
b.Fatal(err)
}
}
}

The filter function was split and the actual job is done in func filter(reader io.Reader, pattern []byte, chunkSize int) (*bytes.Buffer, error).

By injecting a reader and a chunkSize, the creation of unit tests is already prepared or contemplated, which is missing here, but is definitely recommended when dealing with indexes.

However, the main point here was to find a way to significantly improve it in terms of performance.