Пишемо заміну find(1) на golang під Linux

Для однієї внутрішньої утиліти мені знадобилося написати сканування змін до директорії, за аналогією з утилітою find, і я зіткнувся з несподіваною річчю: стандартний Open()+Readdir()+Close() в go дуже повільним у порівнянні з тим, як працює linux'овая утиліта find. На малюнку можна бачити strace цієї утиліти. Можна бачити, що вона робить якісь дуже дивні системні виклики, і в цих системних викликах ми і спробуємо розібратися і написати аналог find на go, який буде працювати тільки під Linux, але зате з порівнянною швидкістю.


Наївна реалізація
Давайте для початку напишемо «наївну» реалізацію find, яка буде для простоти рекурсивно виводити список файлів у директорії.

package main
import (...)

func readdir(dir string) {
dh, err := os.Open(dir)
defer dh.Close()
for {
fis, err := dh.Readdir(10)
якщо err == io.EOF {
break
}
for _, fi := range fis {
fmt.Printf("%s/%s\n", dir, fi.Name())
if fi.IsDir() {
readdir(dir + "/" + fi.Name())
}
}
}
}

func main() {
readdir(os.Args[1])
}

повний код, з импортами і обробкою помилок

Якщо ми запустимо цей код, то він, безумовно, буде працювати, але wall time і rusage будуть приблизно в 3 рази більше, ніж у find (різниця в один файл пояснюється тим, що ми не друкуємо саму потрібну директорію, на відміну від find):

$ time find /path/to/dir | wc -l
169561

real 0m0.333s
user 0m0.104s
sys 0m0.272s

$ time GOGC=300 ./find-simple /path/to/dir | wc -l
169560

real 0m1.160s
user 0m0.540s
sys 0m0.944s


Зауважимо, що system time вже дуже великий, і додамо буферизацію виводу:

@@ -7,5 +7,7 @@ import (
+var bufout = bufio.NewWriter(os.Stdout)
func readdir(dir string) {
@@ -28,3 +30,7 @@ func readdir(dir string) {
for _, fi := range fis {
- fmt.Printf("%s/%s\n", dir, fi.Name())
+ bufout.WriteString(dir)
+ bufout.WriteByte('/')
+ bufout.WriteString(fi.Name())
+ bufout.WriteByte('\n')
if fi.IsDir() {
@@ -44,2 +50,3 @@ func main() {
readdir(dir)
+ bufout.Flush()
}

повна версія

Результати будуть вже набагато краще, але все одно далекі від ідеалу:

$ time GOGC=300 ./find-simple-bufio /path/to/dir | wc -l
169560

real 0m0.796s
user 0m0.352s
sys 0m0.616s


Для прикладу, ось результат для такої ж програми на PHP:

$ php ~/find-ob.php /path/to/dir | wc -l
169560

real 0m0.777s
user 0m0.276s
sys 0m0.500s


Програма на PHP навіть трохи швидше і споживає вимірне менше ресурсів! Це явно не те, що хотілося б отримати від компилируемого мови…

Вивчаємо системні виклики Linux
Якщо вдивитися в strace від find, можна помітити, що він робить getdents64 і майже не робить stat! Але при цьому утиліта якимось чином знає, які імена відповідають директорій. Подивимося, що це за виклик getdents64 такий:

SYNOPSIS
int getdents(unsigned int fd, struct linux_dirent *dirp,
unsigned int count);

DESCRIPTION
This is not the function you are interested in. Look at readdir(3) for the POSIX conforming C library interface. This page documents the bare kernel system call interface. The system call getdents() reads several linux_dirent structures from the directory referred to by the open file descriptor fd into the buffer pointed to by dirp. The argument count is specifies the size of that buffer.

The linux_dirent structure is declared as follows:

struct linux_dirent {
...
char d_name[];
char pad; // Zero padding byte */
char d_type; // File type (only since Linux 2.6.4
}


Це саме те, що нам потрібно! Що цікаво, на BSD-системах при читанні директорії теж є поле з типом файлу (d_type), для деяких файлових систем. Нас всіляко відмовляють використовувати цей системний виклик, але ту ж утиліту find це анітрохи не бентежить.

Як виявилося, «під капотом» стандартна бібліотека go теж кличе getdents(2), так що нам залишається тільки видерти код, який це робить і очистити його від усього зайвого:

package main
import (...)
var bufout = bufio.NewWriter(os.Stdout)

func readdir(dir string, file string, dirfd int, pathbuf []byte) {
origbuf := make([]byte, 4096) // буфер, куди буде читати getdents
dh, err := syscall.Openat(dirfd, file, syscall.O_RDONLY, 0777) // відкриваємо файл директорії по відносному шляху
origpathbuf := pathbuf[0:0] // нам передають буфер для зберігання шляху файлу, скидаємо його

for {
n, errno := syscall.ReadDirent(dh, origbuf) // викликаємо getdents
if n <= 0 {
break // EOF
}

buf := origbuf[0:n] // нам повернули число прочитаних байт, це потрібно використовувати :)
for len(buf) > 0 {
// наступний код виламаний з коду ParseDirent:
dirent := (*syscall.Dirent)(unsafe.Pointer(&buf[0]))
buf = buf[dirent.Reclen:]
if dirent.Ino == 0 { // File absent in directory.
continue
}
bytes := (*[10000]byte)(unsafe.Pointer(&dirent.Name[0]))
name := bytes[0:clen(bytes[:])] // функція clen() повертає довжину сишной рядка
if len(name) == 1 && name[0] == '.' || len(name) == 2 && name[0] == '.' && name[1] == '.' {
continue
}

// пишемо повний шлях в буфер з кінцевим ім'ям файлу,
// щоб не виділяти пам'ять для маленьких шматочків
pathbuf = append(pathbuf, dir...)
pathbuf = append(pathbuf, '/')
pathbuf = append(pathbuf, file...)
dirlen := len(pathbuf)

pathbuf = append(pathbuf, '/')
pathbuf = append(pathbuf, name...)
pathbuf = append(pathbuf, '\n')

bufout.Write(pathbuf)

// тільки у разі, якщо це директорія, створюємо string
if dirent.Type == syscall.DT_DIR {
readdir(string(pathbuf[0:dirlen]), string name), dh, origpathbuf)
}

pathbuf = origpathbuf[0:0]
}

buf = origbuf[0:0]
}

syscall.Close(dh)
}

func main() {
dir := os.Args[1]
parentDir := filepath.Dir(dir)
dh, err := os.Open(parentDir)
pathbuf := make([]byte, 16 * 1024)
readdir(parentDir, filepath.Base(dir), int(dh.Fd()), pathbuf)
bufout.Flush()
}

повний вихідний код програми, з обробкою помилок і функцією clen

Результати
З усіма оптимизациями і використанням системного виклику getdents вдалося зменшити споживання ресурсів до такої міри, що воно працює швидше, ніж find:

$ time GOGC=300 ./find-simple /path/to/dir | wc -l
169560

real 0m1.160s
user 0m0.540s
sys 0m0.944s

$ time GOGC=300 ./find-optimized /path/to/dir | wc -l
169560

real 0m0.200s
user 0m0.060s
sys 0m0.160s

$ time find /path/to/dir | wc -l
169561

real 0m0.333s
user 0m0.104s
sys 0m0.272s


Споживання ресурсів і загальний час роботи менше в півтора рази, ніж у find. Основні причини цього полягають у тому, що find видає сортированый список файлів, а також приймає умови для фільтрації списку.

Очевидно, що просто отримання списку файлів і виведення його на екран не представляють особливої цінності, але такий спосіб дозволяє прискорити багато програми go, які, наприклад, надають альтернативу grep за рахунок зменшення накладних витрат на читання списку файлів з директорії.

Посилання:


Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.