☰

Das Einlesen einer Kopie von `/usr/share/dict/words` ist 10x langsamer als das Einlesen der Datei selbst

tag-icon • tag-icon linux files c windows-subsystem-for-linux
Das Einlesen einer Kopie von `/usr/share/dict/words` ist 10x langsamer als das Einlesen der Datei selbst

Ich habe mit Wörterbuchimplementierungen in C experimentiert und fand /usr/share/dict/wordseine ziemlich gute Datei zum Testen. Aus irgendeinem Grund wollte ich eine Kopie der Wörterdatei in meinem Arbeitsverzeichnis erstellen, aber zu meiner Überraschung war das Programm beim Lesen der Datei merklich langsamer. Was könnte dieses Verhalten erklären? Die beiden Dateien sind identisch.

Wenn ich raten müsste, könnte es sein, dass /usr/share/dict/wordses bereits im Speicher gepuffert ist, weil es eine häufig verwendete Datei ist?

#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;
}

Antwort1

Wie @Vilinkameni bemerkte, kann die E/A-Leistung unter GNU/Linux unterschiedlich sein, wenn sich die aufgerufenen Dateien auf einem anderen physischen Gerät oder Dateisystemtyp befinden.

In meinem Fall verwendet WSL2 eine virtuelle Festplatte, aber mein Arbeitsverzeichnis ( cdauf das WSL zugegriffen hat) befand sich tatsächlich auf meinem C:/Laufwerk. Beim Zugriff auf die /usr/share/dict/wordsDatei bleibe ich also in der WSL2-VHD, aber wenn ich die Datei auf mein C:/Laufwerk kopiere, kommt es dort zu Leistungseinbußen – weil die Datei auf einem anderen „Dateisystem“ gelesen werden muss.

Ich habe dies getestet, indem ich mein Programm nach verschoben /usr/share/dict/und dort eine Kopie der wordsDatei erstellt habe. Die Leistung ist jetzt identisch.

verwandte Informationen