☰

Чтение копии `/usr/share/dict/words` в 10 раз медленнее, чем сам файл

tag-icon • tag-icon linux files c windows-subsystem-for-linux
Чтение копии `/usr/share/dict/words` в 10 раз медленнее, чем сам файл

Я экспериментировал с реализациями словарей на языке C и обнаружил, /usr/share/dict/wordsчто это довольно хороший файл для тестирования. По какой-то причине я хотел сделать копию файла слов в свой рабочий каталог, но, к моему удивлению, программа стала заметно медленнее читать файл. Чем можно объяснить такое поведение? Оба файла идентичны.

Если бы мне пришлось угадывать, то, возможно, /usr/share/dict/wordsон уже буферизован в памяти, потому что это часто используемый файл?

#define _GNU_SOURCE

#include <assert.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>

#define GET_TIME(now)                           \
    do {                                        \
        struct timeval t;                       \
        gettimeofday(&t, NULL);                 \
        now = t.tv_sec + t.tv_usec / 1000000.0; \
    } while (0)

#define REPORT(msg, time)                   \
    do {                                    \
        printf("%-10s- %f\n", msg, time);   \
    } while (0)

#define SHOW_INVALID    0

struct dict {
    int n;
    char *data[110000];
};

int valid_word(char *input)
{
    for (int i = 0; input[i]; i++) {
        if (!islower(input[i]) && !(input[i] == '\n')) {
            return 0;
        }
    }
    return 1;
}

struct dict *get_dict(char *file)
{
    struct dict *dict = calloc(1, sizeof(struct dict));
    FILE *fp = fopen(file, "r");
    char input[128];
    while (fgets(input, 128, fp)) {
        if (valid_word(input)) {
            dict->data[dict->n++] = strdup(input);
        } else {
#if SHOW_INVALID == 1
            printf("Skipping invalid word %s", input);
#endif
        }
    }
    fclose(fp);
    return dict;
}

void destroy_dict(struct dict *dict)
{
    for (int i = 0; i < dict->n; i++) {
        free(dict->data[i]);
    }
    free(dict);
}

int search(struct dict *dict, int l, int r, char *word)
{
    if (l > r) return -1;
    int mid = l + (r - l) / 2;
    if (!strcmp(dict->data[mid], word)) return mid;
    if (strcmp(dict->data[mid], word) > 0) return search(dict, l, mid - 1, word);
    return search(dict, mid + 1, r, word);
}

int match(struct dict *dict, char *word)
{
    return search(dict, 0, dict->n - 1, word);
}

void test(struct dict *dict, char *file)
{
    FILE *fp = fopen(file, "r");
    char input[128];
    while (fgets(input, 128, fp)) {
        if (valid_word(input)) {
            assert(match(dict, input) != -1);
        } else {
            assert(match(dict, input) == -1);
        }
    }
    fclose(fp);
}

int main(void)
{
    double init, start, end;
    GET_TIME(init);

    GET_TIME(start);
    struct dict *dict = get_dict("words");
    GET_TIME(end);
    REPORT("setup", end - start);

    GET_TIME(start);
    test(dict, "words");
    GET_TIME(end);
    REPORT("words", end - start);

    GET_TIME(start);
    test(dict, "words_random");
    GET_TIME(end);
    REPORT("randwords", end - start);

    GET_TIME(start);
    destroy_dict(dict);
    GET_TIME(end);
    REPORT("teardown", end - start);

    puts("");
    REPORT("total", end - init);

    return 0;
}

решение1

Как отметил @Vilinkameni, производительность ввода-вывода может отличаться в GNU/Linux, если файлы, к которым осуществляется доступ, находятся на другом физическом устройстве или в другом типе файловой системы.

В моем случае WSL2 использует виртуальный жесткий диск, но мой рабочий каталог (в который был cdнаправлен WSL) на самом деле находился на моем C:/диске. Таким образом, при доступе к /usr/share/dict/wordsфайлу я остаюсь в WSL2 VHD, но если я копирую файл на свой C:/диск, то именно здесь происходит падение производительности, поскольку файл приходится читать в другой «файловой системе».

Я проверил это, переместив свою программу в /usr/share/dict/, создав там копию файла words, и производительность теперь идентична.

Связанный контент