Jak szybki jest grep? -> grep vs awk, python, rugby, java, perl, C - przeszukiwanie logów - część 11.



Zestawienie wyników:

multifindmaster – fork -32p0,5350,708
multifindmaster – ram -32p0,6970,691
multifindmaster – files -32p0,7020,714
grep0,8560,862
onlyfind_str0,9750,987
multifindmaster – ram -1p1,4691,468
multifindmaster – fork -1p1,4691,475
multifindmaster – files -1p1,6361,624
onlyfind_memmem1,9671,966
onlyfind_for2,8392,824
perl5,5485,484
java6,0846,14
ruby (fast)10,76310,755
python22,38522,543
ruby (slow 2)78,23477,708
ruby (slow 1)78,91978,175


***
Kiedyś wyróżniano trzy polecania grep:
  • fgrep - To polecenie nie miało być szybkim grepem (fast grep), często było wręcz najwolniejsze. Zużywał za to mało pamięci, co dawniej miało znaczenie w niektórych systemach. Ludzie nie pamiętający czasów przed Linuksem kojarzą fgrep'a z rozwinięciem: "Fixed-string Global Regular Expressions Print", co ma (wg. nich) powodować jego szybsze działanie.
  • grep - Akronim od "Global Regular Expressions Print".
  • egrp - Akronim od "Extended Regular Expressions Print" . Różnice dobrze obrazuje taki przykład: `grep "+" myfile.txt` zwróci każdą linię zawierająca znak "+". Polecenie `egrep "+" myfile.txt` zwróci każdą linię, ponieważ znak "+" potraktuje jako meta znak.

Obecnie (zazwyczaj, jak w systemach CentOS, Red Hat, Debian, FreeBSD,Oracle, SUN) występuje jedno polecenie "grep", a skrypty powodują następujące akcje:
fgrep -> exec grep -F "$@"
egrep -> exec grep -E "$@"

Kodem zakończenia grep jest:
0 - jeżeli znaleziono dopasowanie
1 - jeżeli nie znaleziono dopasowania
2 - jeżeli wystąpił błąd.
Jak widać łatwo jest obsłużyć takie kody.

Program AWK również występuje w kilku wersjach, przy czym GAWK jest chyba najpopularniejszy:
AWK - oryginalny od  AT&T (A. Aho, B. W. Kernighan and P. Weinberger).
NAWK - unowocześniony, również wprowadzony do Unix'a od AT&T.
GAWK - stworzony przez Free Software foundation's.
***
Powyższe testy kończą ten wpis, jednak nie kończą dalszych badań. Czy można zoptymalizować wieloprocesorowe wyszukiwanie? Tak, ale nie jest to banalne. Warto zapoznać się z wpisem: Wieloprocesorowe programy do pakowania plików - serwery Ux. Można zobaczyć jaką trudność sprawia przetwarzanie wieloprocesorowe. W kolejnych wpisach przedstawię gotowe programy służące równoległemu uruchamianiu programów jednowątkowych, oraz w spróbuję zmierzyć się z optymalizacją programów tutaj zaprezentowanych. Przy tworzeniu programów parsujących warto zwrócić uwagę na algorytmy Boyer-Moore'a i Railgun_Trolldom. Pozwala to lepiej zapoznać się z różnymi wynikami w zależności np.: od długości szukanego łańcucha. Wstępnie widzę potrzebę optymalizacji operacji dyskowych, a dalsza optymalizacja kodu wyszukującego może pójść np. w kierunku:
asm
    MOV CX, LENGTH BIGTAB
    CLD
    MOV DI,SEG BIGTAB
    MOV ES,DI
    MOV DI,OFFSET BIGTAB
P1: MOV AX,CHAR_1_2
    REPNE SCASW
    JNZ NOT_FOUND
P2: MOV DX,CHAR_3_4
    CMP WORD PTR ES:[DI],DX
    JNZ P1

Jak szybki jest grep? -> grep vs awk, python, rugby, java, perl, C - przeszukiwanie logów - część 10.



Spróbujmy kolejnej optymalizacji, rezygnuję z funkcji systemu operacyjnego exit(), zostając przy samym fork():
C++ - fork
 //
// Copyright (c) 2016 Rafal Jackiewicz
//
// Indent style: Berkeley
//
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <errno.h>
#include <sys/wait.h>
#include <fcntl.h>
#include <sstream>
#include <sys/times.h>
#include <sys/time.h>
#include <sys/resource.h>
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <string.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <fstream>
#define Dneedle_max 6
#define Dnew_line 10
using namespace std;
const int       maxPar = 3;
const int       maxProcess = 32;
static int      end_main = 0;
int             fd;
int             maxproc = 0;
unsigned long   len_max;
const key_t     shm_id = 8274;
char           *fileinmemory;
char            needle[Dneedle_max];
struct stat     fd_st;
struct process_struct {
    pid_t           pid;
    int             returnCode;
    time_t          timeProcSystem_us;
    time_t          timeProcUser_us;
    time_t          countTimeProcess_start;
    time_t          countTimeProcess_stop;
    char           *shm_start;
    unsigned long   shm_diff;
    unsigned long   shm_len;
    int             shm_return_len;
};
struct tms      bufor;
struct process_struct *process = new process_struct[maxProcess];
void            sygnal(int signo, siginfo_t * sigf, void *b);
int
main(int argc, char *argv[])
{
    pid_t           pid_tmp;
    sigset_t        sig_mask;
    int             returnCode,
                    opt_check;
    int             i;
    struct rusage   timeData;
    struct sigaction sigA;
    long            adressum = 0;
    unsigned long   sizetmp;
    unsigned long   shmComputeDiv;
    char           *copyfim = 0;
    if (argc == 1) {
    cout << "Nie podano parametrow w wywolaniu programu." << endl;
    return 128;
    }
    if (argc > (maxPar + 1)) {
    cout << "Za duzo parametrow, maksymalnie podaj " << maxPar <<
        " parametrow." << endl;
    return 129;
    }
    if (argc < (maxPar + 1)) {
    cout << "Za malo parametrow, podaj " << maxPar << " parametrow." <<
        endl;
    return 129;
    }
    while ((opt_check = getopt(argc, argv, "vh")) != (-1)) {
    switch (opt_check) {
    case 'v':
        cout << "Versja 1.0\n" << endl;
        return 130;
    case 'h':
        cout <<
        "Poprawne wywolanie programu: szukany ciąg 6 znaków, plik, ile procesów."
        << endl;
        cout << "Maksymalnie podaj " << maxPar << " parametrów." <<
        endl;
        return 130;
    }
    }
    fd = open(argv[2], O_RDONLY);
    if (fd == -1) {
    perror("Multifind: open.");
    return 1;
    }
    if (fstat(fd, &fd_st) == -1) {
    perror("Multifind: fstat.");
    return 1;
    }
    if (!S_ISREG(fd_st.st_mode)) {
    fprintf(stderr, "%sMultifind: to nie plik.\n", argv[2]);
    return 1;
    }
    len_max = fd_st.st_size;
    // System V API
    int             smid =
    shmget(shm_id, len_max, IPC_CREAT | SHM_NORESERVE | 0666);
    fileinmemory = (char *) shmat(smid, NULL, 0);
    if (*fileinmemory == -1) {
    perror("Multifind: shmat.");
    return 1;
    }
    int             readerr = read(fd, fileinmemory, len_max);
    if (readerr == -1) {
    fprintf(stderr, "Multifind: read.");
    return 1;
    }
    if (close(fd) == -1) {
    perror("Multifind: close.");
    return 1;
    }
    if (strlen(argv[1]) != Dneedle_max) {
    fprintf(stderr, "%sZla dlugośc needle.\n", argv[1]);
    return 1;
    else {
    strcpy(needle, argv[1]);
    }
    maxproc = atoi(argv[3]);
    if (maxproc > maxProcess) {
    fprintf(stderr, "Multifind: za duzo prosesow.");
    return 1;
    else {
    if (maxproc == 0) {
        fprintf(stderr, "Multifind: podales zero procesow.");
        return 1;
    }
    }
    shmComputeDiv = len_max / maxproc;
    for (i = 0; i < maxproc; ++i) {
    process[i].shm_start = fileinmemory + (shmComputeDiv * (i));
    process[i].shm_len = shmComputeDiv;
    }
    process[maxproc - 1].shm_len =
    (fileinmemory + len_max) - process[maxproc - 1].shm_start;
    printf("@ fileinmemory: %p \n", fileinmemory);
    printf("@      len_max: 0x%lX \n", len_max);
    printf("@          sum: 0x%lX \n",
       (long unsigned) fileinmemory + len_max);
    for (i = 1; i < maxproc; ++i) {
    sizetmp = process[i - 1].shm_len;
    copyfim = process[i - 1].shm_start;
    while ((copyfim[sizetmp] != (char) Dnew_line)) {    // ||
        // sizetmp!=0
        --sizetmp;
    }
    process[i - 1].shm_len = sizetmp;
    process[i].shm_start =
        process[i - 1].shm_start + process[i - 1].shm_len;
    }
    process[maxproc - 1].shm_len =
    (fileinmemory + len_max) - process[maxproc - 1].shm_start;
    printf("\n");
    for (i = 0; i < maxproc; ++i) {
    process[i].shm_diff = process[i].shm_start - fileinmemory;
    }
    adressum = 0;
    for (i = 0; i < maxproc; ++i) {
    printf("%2d: shm_start: %p ", i, process[i].shm_start);
    printf("  shm_len: %lX ", process[i].shm_len);
    printf("  shm_diff: %8lX ", process[i].shm_diff);
    adressum += process[i].shm_len;
    printf("  shm_start+shm_len: %lX \n",
           process[i].shm_len + (long int) process[i].shm_start);
    }
    printf("Addr len_max: %lX \n", len_max);
    printf("    Diff sum: %lX \n", adressum);
    printf("\n");
    sigemptyset(&sig_mask);
    sigfillset(&sig_mask);
    sigA.sa_handler = NULL;
    sigA.sa_sigaction = sygnal;
    sigA.sa_mask = sig_mask;
    sigA.sa_flags = SA_SIGINFO;
    sigA.sa_restorer = NULL;
    if (sigaction(SIGCHLD, &sigA, NULL)) {
    perror("Blad sigaction:");
    exit(33);
    }
    for (int i = 0; i < maxproc; i++) {
    process[i].countTimeProcess_start = times(&bufor);
    process[i].pid = fork();
    switch (process[i].pid) {
    case -1:
        cout << "Nie mozna utworzyc nowego procesu nr: " << i << endl;
        break;
    case 0:{
        // ###############################################3
        const int       needle_max = Dneedle_max;
        unsigned long   child_len_max = process[i].shm_len;
        char           *child_fileinmemory;
        int             needle_max_minusone = needle_max - 1;
        child_fileinmemory = fileinmemory + process[i].shm_diff;
        char           *endfileinmemory =
            child_fileinmemory + child_len_max - needle_max + 1;
        char           *mark = child_fileinmemory;
        char           *copymarkstart,
                       *copymarkstop;
        char           *needle_maxminus =
            needle + needle_max_minusone;
        char           *needle_plus = needle + 1;
        unsigned long   needle_max_minustwo = needle_max - 2;
        unsigned long   copylen_max = child_len_max;
        char           *mark_buff = mark;
        int             count_buff;
        while ((mark = (char *) memchr(mark, *needle, copylen_max))
               && (mark < endfileinmemory)) {
            if (mark[needle_max_minusone] == *needle_maxminus) {
            if (memcmp
                (++mark, needle_plus,
                 needle_max_minustwo) == 0) {
                copymarkstart = mark;
                while (*(--copymarkstart) != (char) Dnew_line);
                copymarkstop = mark + needle_max;
                while (*(++copymarkstop) != (char) Dnew_line);
                mark = copymarkstop;
                count_buff = copymarkstop - copymarkstart;
                memmove(mark_buff, ++copymarkstart,
                    count_buff);
                mark_buff += count_buff;
                copylen_max = endfileinmemory - mark;
                break;
            else {
                --copylen_max;
            }
            else {
            ++mark;
            --copylen_max;
            }
        }
        while ((mark = (char *) memchr(mark, *needle, copylen_max))
               && (mark < endfileinmemory)) {
            if (mark[needle_max_minusone] == *needle_maxminus) {
            if (memcmp
                (++mark, needle_plus,
                 needle_max_minustwo) == 0) {
                copymarkstart = mark;
                while (*(--copymarkstart) != (char) Dnew_line);
                copymarkstop = mark + needle_max;
                while (*(++copymarkstop) != (char) Dnew_line);
                mark = copymarkstop;
                count_buff = copymarkstop - copymarkstart;
                memcpy(mark_buff, ++copymarkstart, count_buff);
                mark_buff += count_buff;
                copylen_max = endfileinmemory - mark;
            else {
                --copylen_max;
            }
            else {
            ++mark;
            --copylen_max;
            }
        }
        int            *tmmp =
            (int *) (child_fileinmemory + child_len_max - 8);
        *tmmp = mark_buff - child_fileinmemory;
        return (44);
        break;
        }
    default:
        break;
    }
    }
    do {
    pause();
    }
    while (end_main < (maxproc - 1));
    // uzywam wait pokazujac zachowanie sie tablicy stanu procesu po jego
    // zakonczeniu
    // te dzialania mozna przeniesc do funkcji obslugujacej sygnal
    // i odpytywac sie tam o stan procesu, ktory wlasnie wyslal sysgnal
    // wait3 == wait4(0,...)
    while ((pid_tmp = wait4(0, &returnCode, 0, &timeData)) != (-1)) {
    for (int i = 0; i < maxproc; i++) {
        if (process[i].pid == pid_tmp) {
        process[i].timeProcSystem_us = timeData.ru_stime.tv_usec;
        process[i].timeProcUser_us = timeData.ru_utime.tv_usec;
        process[i].returnCode = returnCode;
        i = maxproc;
        }
    }
    }
    int            *len_buff;
    fstream         file_out;
    file_out.open("wynik_multifind.txt", ios::out);
    if (file_out.good() == true) {
    for (int i = 0; i < maxproc; ++i) {
        len_buff =
        (int *) (fileinmemory + process[i].shm_diff +
             process[i].shm_len - 8);
        file_out.write(process[i].shm_start, *len_buff);
    }
    file_out.close();
    }
    for (int i = 0; i < maxproc; ++i) {
    cout << "*** Proces: [" << i << "], kod zakonczenia: " <<
        (process[i].returnCode >> 8) << endl;
    cout << "Czas pracy procesu: " << (double) (process[i].
                            countTimeProcess_stop -
                            process[i].
                            countTimeProcess_start)
        / sysconf(_SC_CLK_TCK)
        << "s" << endl;
    cout << "Czas procesora w trybie uzytkownika: "
        << setw(8) << (double) process[i].timeProcUser_us /
        CLOCKS_PER_SEC << "s" << endl;
    cout << "Czas procesora w trybie systemowym: " << setw(9) <<
        (double) process[i].timeProcSystem_us /
        CLOCKS_PER_SEC << "s" << endl << endl;
    }
    int             r = shmdt(fileinmemory);
    if (r == -1) {
    perror("Multifind: shmdt.");
    }
    r = shmctl(smid, IPC_RMID, NULL);
    if (r == -1) {
    perror("Multifind: shmCTL.");
    }
    cout << endl;
    return 0;
}
void
sygnal(int signo, siginfo_t * sigf, void *b)
{
    for (int i = 0; i < maxproc; ++i) {
    if (process[i].pid == sigf->si_pid) {
        process[i].countTimeProcess_stop = times(&bufor);
        i = maxproc;
    }
    }
    end_main += 1;
}