Как обогнать grep?

@Pavlin27 · Регистрация: 24.09.2016

Студворк — интернет-сервис помощи студентам

Пока учусь только, исходник grep разобрать не по силам.

В общем, возникла идея написать программу, которая бы осуществляла поиск строк с ключевой фразой быстрее grep. Базируется она на том, что grep утилита универсальная и о структуре файла ей заранее ничего не известно, в отличие от подобной программы.
В качестве подопытного был взят лог dchp сервера. Поиск осуществляется по mac.

Для простоты сначала решил найти конкретную строчку.

C++
1
2
3
4
char str[305];
while(f.getline(str, 305)){
    if ((str[60] == '7') && (str[61] == 'b') && (str[63] == 'e') ...)
        printf ("%s\n", str);

grep оказался в 2-3 раза быстрее такого кода

попробовал, тоже самое через fgets, тоже самое - grep быстрее

попробовал через read из fcntl.h - также.

В итоге склоняюсь, к тому, что grep или другими механизмами файл читает, или задействует многоядерность процессора, или на данной машине какие-то ограничения на пользовательские программы (не знаю возможно ли такое).

Подскажите, пожалуйста, куда копать.

OxEED0 · 15.11.2017, 13:22

Сообщение от karat39

и память не закеширована?

Кеширование не зависит от того, как ты данные загрузил в память, mmap'ом, или read'ом.

@Pavlin27 · 18.11.2017, 01:51 **[ТС]**

Пока таким образом:

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
 
int main()
{
        FILE *f = fopen("log", "r");
        if (!f)
        {
                printf ("file not open\n");
                return -1;
        }
        long int str[30000];
        int cc = 0;
        while(cc = fread(str, 8, 30000, f))
        {
                int i = 0;
                while (i++ < cc )
                {
                        if ((i < cc ) && (i < cc ) && (i < cc ) && (i < cc ) && (i < cc ) && (i < cc ) && (i < cc ) && (i < cc ));
                }
        }
        fclose(f);
        return 0;

удалось пробежаться по файлу быстрее грепа на 30 мс (180 против 210)
Осталось теперь сформировать 8 сравнений с подстрокой длиной в 8 байт.

Правда будет засада, если компилятор преобразовал if ((i < cc ) && (i < cc ) && (i < cc ) && (i < cc ) && (i < cc ) && (i < cc ) && (i < cc ) && (i < cc )); в if (i < cc );
В ином случае форы в 30 мс надеюсь хватить.

Завтра - послезавтра постараюсь проверить.

Кстати, 30 мс сэкономил, используя while (i++ < cc ) вместо for (in i = 0; i < 30000; i++)

@Pavlin27 · 20.11.2017, 21:53 **[ТС]**

Компилятор судя по всему вообще данное сравнение проигнорировал. Как только добавляешь реальные инструкции к данному сравнению, время значительно увеличивается.

Файл, на котором тестирую, 200 с лишним МБ. Так вот, если скомпилировать программу содержащую только 200 млн итераций, то она уже уступает grep по времени.

Добавлено через 4 часа 3 минуты
Чуть глаза не вытекли от чтения исходника grep, но решение нашел:

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <string.h>
#include <stdio.h>
 
void print_string(char *p)
{
        char * k = p;
        int l = 0;
        while( k[--l] != '\n'){}
        while( k[++l] != '\n')
        {
                printf ("%c", k[l]);
        }
        printf ("\n");
        }
 
int main()
{
        FILE *f = fopen("log", "r");
 
        if (!f)
        {
                printf ("file not open\n");
                return -1;
        }
 
        char str[262144];
        int cc = 0;
        const char *c = "b8:70:f4:a4:05:94";
        while(cc = fread(str, 1, 262144, f))
        {
                char *p1 = str;
                char *p2 = &str[cc - 1];
                char *p3 = 0;
                *p2 = '\n';
 
                while (p2 > p1++)
                {
                        p3 = p1;
                        p1 = (char*)memchr(p1, '\n', 305);
                        p3 = (char*)memchr(p3, 'b', p1-p3);
                        if(p3)
                        {
                                if(memcmp(c, p3, 17) == 0)
                                        print_string(p3);
                        }
 
                }
        }
 
        fclose(f);
 
        return 0;
 
}

memchr ищет нужные символы быстрее, чем прохождение по буферу в цикле и сравнение каждого байта с заданным.

В таком виде время одинаковое получается, но думаю можно его улучшить будет

@Pavlin27 · 25.11.2017, 00:43 **[ТС]**

Пытался понять за счет чего memchr настолько быстрее обход осуществляет. Судя по той информации, что удалось найти, она на ассемблере написана. Т.к. те исходники, что удалось найти значительно уступают. Поздние версии, кстати, используют обход по лонг интам.

Новые блоги и статьи Все статьи Все блоги /
сукцессия 5 anaschu 26.06.2026 ПЛАН РАЗРАБОТКИ математической модели сукцессии микоризных систем Переход AM → EcM (Endo + ErM) · Шумилов А. С. · ИФХиБПП РАН · Пущино · 2026 . . .	сукцессия 4 anaschu 25.06.2026 Более детализированный план разработки План доработки модели динамики микоризных симбиозов (EcM с гистерезисом) Цель: Реализовать логику переключения между эрикоидным (ErM) и эктомикоризным. . .	сукцессия 3 anaschu 25.06.2026 Примерный план работ по модели	сукцессия 2 anaschu 25.06.2026 параметризировочная калибровочная таблица будущей модели
Многофункциональное здание: как одно здание порождает конфликты требований, которые никто не планировал (мат мет мод 29) anaschu 23.06.2026 Многофункциональное здание: как одно здание порождает конфликты требований, которые никто не планировал Материалы для обсуждения с МГСУ · 2026 Рисунки внутри приложенного ворд файла. Что за. . .	28. Конкретное развертывание плана номер 1 из поста номер 27 anaschu 22.06.2026 Можно ли из модели получить конкретные строительные требования? Честно — напрямую из текущей модели такие ответы не получить. Но цепочка логики есть, и она не такая длинная. Где разрыв . . .	27. Планы на разработку функциональных требований к строительству внутри модели пищеблока (или не только его?) anaschu 22.06.2026 Что уже реализовано и даёт конфликты «бесплатно» Самый простой конфликт уже работает — конфликт за ресурс-работника. Заданий больше, чем доступных поваров → очередь в queue1. Это прямое отражение. . .	26. мед мат модель.Какие типы конфликтов функциональных требований можно рассчитать через ДЕС-моделирование (СМО) в AnyLogic? anaschu 22.06.2026 Что ДЕС/ СМО умеет считать напрямую: Конфликты за ресурсы (очереди, узкие места). Несколько типов агентов (повара, учителя, рабочие, пациенты) претендуют на один ресурс (лифт, вход, коридор,. . .

@Pavlin27 1 / 1 / 2 Регистрация: 24.09.2016 Сообщений: 15
	25.11.2017, 00:43 [ТС]
	Пытался понять за счет чего memchr настолько быстрее обход осуществляет. Судя по той информации, что удалось найти, она на ассемблере написана. Т.к. те исходники, что удалось найти значительно уступают. Поздние версии, кстати, используют обход по лонг интам. 0