Как повысить скорость чтения большого файла построчно в Go

Question

Я пытаюсь найти наиболее быстрый способ чтения большого файла построчно и проверки, содержит ли строка строку.Файл, который я тестирую, имеет размер около 680 МБ

    package main

    import (
        "bufio"
        "fmt"
        "os"
        "strings"
    )

    func main() {
        f, err := os.Open("./crackstation-human-only.txt")

        scanner := bufio.NewScanner(f)
        if err != nil {
            panic(err)
        }
        defer f.Close()

        for scanner.Scan() {
            if strings.Contains(scanner.Text(), "Iforgotmypassword") {
                fmt.Println(scanner.Text())
            }
        }
    }

После сборки и синхронизации программы на моем компьютере она запускается в течение 3 секунд ./speed 3.13s user 1.25s system 122% cpu 3.563 total

После увеличения буфера

buf := make([]byte, 64*1024)
scanner.Buffer(buf, bufio.MaxScanTokenSize)

Это становится немного лучше ./speed 2.47s user 0.25s system 104% cpu 2.609 total

Я знаю, что это может стать лучше, потому что другие инструменты справляются с этим за секунду без какой-либо индексации.Что кажется узким местом в этом подходе?

0.33s user 0.14s system 94% cpu 0.501 total

Answer 1

ПОСЛЕДНЕЕ РЕДАКТИРОВАНИЕ

Это «построчное» решение проблемы, которое занимает тривиальное время, печатает всю соответствующую строку.

package main

import (
    "bytes"
    "fmt"
    "io/ioutil"
)

func main() {
    dat, _ := ioutil.ReadFile("./jumble.txt")
    i := bytes.Index(dat, []byte("Iforgotmypassword"))
    if i != -1 {
        var x int
        var y int
        for x = i; x > 0; x-- {
            if dat[x] == byte('\n') {
                break
            }
        }
        for y = i; y < len(dat); y++ {
            if dat[y] == byte('\n') {
                break
            }
        }
        fmt.Println(string(dat[x : y+1]))
    }
}

real    0m0.421s
user    0m0.068s
sys     0m0.352s

---

ОРИГИНАЛЬНЫЙ ОТВЕТ

Если вам просто нужно посмотреть, есть ли строка в файле, почему бы не использовать регулярное выражение?

Примечание: Iсохранял данные в виде байтового массива вместо преобразования в строку.

package main

import (
    "fmt"
    "io/ioutil"
    "regexp"
)

var regex = regexp.MustCompile(`Ilostmypassword`)

func main() {
    dat, _ := ioutil.ReadFile("./jumble.txt")
    if regex.Match(dat) {
        fmt.Println("Yes")
    }
}

jumble.txt - это 859 МБ перемешанного текста с включенными символами новой строки.

Запуск с time ./code Я получаю:

real    0m0.405s
user    0m0.064s
sys     0m0.340s

Кпопробуйте ответить на ваш комментарий, я не думаю, что узкое место возникает в результате поиска построчно, Голанг использует эффективный алгоритм поиска строк / рун.

Я думаю, что узкое место возникает при чтениях ввода-вывода, когдапрограмма читает из файла, она обычно не первая в очереди в очереди чтения, поэтому программа должна ждать, пока она не сможет выполнить чтение, чтобы начать фактическое сравнение.Таким образом, когда вы читаете снова и снова, вы вынуждены ждать своей очереди в IO.

Чтобы дать вам некоторую математику, если ваш размер буфера равен 64 * 1024 (или 65535 байт), иВаш файл 1 ГБ.Разделение 1 ГБ / 65535 байт составляет 15249 операций чтения, необходимых для проверки всего файла.Где, как и в моем методе, я читаю весь файл "сразу" и проверяю этот построенный массив.

Еще одна вещь, о которой я могу подумать, это просто огромное количество циклов, необходимых для перемещения по файлу, и время, необходимое для каждого цикла:

Учитывая следующий код:

dat, _ := ioutil.ReadFile("./jumble.txt")
sdat := bytes.Split(dat, []byte{'\n'})
for _, l := range sdat {
    if bytes.Equal([]byte("Iforgotmypassword"), l) {
        fmt.Println("Yes")
    }
}

Я рассчитал, что каждый цикл занимает в среднем 32 наносекунды, строка Iforgotmypassword была в строке 100000000 в моем файле, таким образом, время выполнения этого цикла составляло примерно 32 наносекунды * 100000000 ~ = 3,2 секунды.

Answer 2

Используя мой собственный тестовый файл объемом 700 МБ с вашим оригиналом, время составило чуть более 7 секунд

с grep это было 0,49 секунды

С этой программой (которая не выводит строку, она просто говорит да) 0,082 секунды

package main

import (
    "bytes"
    "fmt"
    "io/ioutil"
    "os"
)

func check(e error) {
    if e != nil {
        panic(e)
    }
}
func main() {
    find := []byte(os.Args[1])
    dat, err := ioutil.ReadFile("crackstation-human-only.txt")
    check(err)
    if bytes.Contains(dat, find) {
        fmt.Print("yes")
    }
}

Answer 3

Вы можете попробовать использовать goroutines для параллельной обработки нескольких строк:

lines := make(chan string, numWorkers * 2) // give the channel enough room to put lots of things in so the reader isn't blocked

go func(scanner *bufio.Scanner, out <-chan string) {
  for scanner.Scan() {
    out <- scanner.Text()
  }
  close(out)
}(scanner, lines)

var wg sync.WaitGroup
wg.Add(numWorkers)

for i := 0; i < numWorkers; i++ {
  go func(in chan<- string) {
    defer wg.Done()
    for text := range in {
      if strings.Contains(text, "Iforgotmypassword") {
        fmt.Println(scanner.Text())
      }
    }
  }(lines)
}

wg.Wait()

Я не уверен, насколько это действительно ускорит процесс, поскольку это зависит от того, какое оборудование у вас имеется;Похоже, вы ожидаете увеличения скорости более чем в 5 раз, поэтому вы можете заметить, что вы запускаете что-то, что может поддерживать 8 параллельных рабочих потоков.Не стесняйтесь использовать лотов рабочих-подпрограмм.Удачи.