Скорость чтения csv с разных носителей

@bedvit · Регистрация: 20.05.2016

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

Добрый день, джентльмены.
На днях набросал простой код поиска нужной строки в CSV-файле, см. под спойлером

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

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
55
56
57
58
59
60
61
62
63
extern "C" __declspec(dllexport) LPXLOPER12  WINAPI FindInCSV(char *  arg1, char *  arg2, wchar_t *  arg3)
{
    LPXLOPER12 OperOut = new XLOPER12;
    OperOut->xltype = xltypeStr | xlbitDLLFree;
    OperOut->val.str = new XCHAR[32767 + 2]; //+1 под размер + 1 под нуль-терминатор
    OperOut->val.str[0] = 0;
    OperOut->val.str[1] = '\0';
    std::filebuf fb;
    if (fb.open(arg1, std::ios::in | std::ios::binary))
    {
        int x = 0;
        int lenStrOut = 0; //0й элемент - размер строки
        int lenArg3 = wcslen(arg3);
        bool overflow = false;
        std::string str;
        std::istream is(&fb);
        XCHAR* strTmp= OperOut->val.str + 1;
 
        while (is) 
        {
            std::getline(is, str);
            size_t found = str.find(arg2);
            if (found != std::string::npos)
            {
                x++;
                if (lenArg3 > 0 && x > 1)
                {
                    if (lenStrOut + lenArg3 > 32767) { overflow = true;  goto end_; }
                    wcscpy(strTmp + lenStrOut, arg3);
                    lenStrOut = lenStrOut + lenArg3;
 
                    if (lenStrOut + str.length() > 32767) { overflow = true;  goto end_; }
                    MultiByteToWideChar(CP_ACP, MB_PRECOMPOSED, str.c_str(), -1, strTmp + lenStrOut, str.length() + 1);
                    lenStrOut = lenStrOut + str.length();
                }
                else if (lenArg3 > 0)
                {
                    if (lenStrOut + str.length() > 32767) { overflow = true;  goto end_; }
                    MultiByteToWideChar(CP_ACP, MB_PRECOMPOSED, str.c_str(), -1, strTmp + lenStrOut, str.length() + 1);
                    lenStrOut = lenStrOut + str.length();
                }
                else
                {
                    if (lenStrOut + str.length() > 32767) { overflow = true;  goto end_; }
                    MultiByteToWideChar(CP_ACP, MB_PRECOMPOSED, str.c_str(), -1, strTmp + lenStrOut, str.length() + 1);
                    lenStrOut = lenStrOut + str.length();
                    goto end_ ;
                }
            };
        }
    end_:
        if (overflow) {
            wcscpy(strTmp, L"Qverflow. Max char 32767\0");
            OperOut->val.str[0] = 24;
        }
        else
        {
            OperOut->val.str[0] = lenStrOut;
        }
        fb.close();
    }
    return OperOut;
}

Сегодня протестировал работу на з-х накопителях:
HDD WDC WD10EACS-00ZJB0 (1000 ГБ, SATA-II)
HDD WDC WD5000AAKX-001CA0 (500 ГБ, 7200 RPM, SATA-III)
SSD KINGSTON SV300S37A120G (120 ГБ, SATA-III)

В итоге время обработки CSW-файла размером 1ГБ у всех примерно одинаковое, что стало для меня откровением. Я предполагал, что в данном коде узкое место скорость чтения с накопителя. Чем можно объяснить такой результат теста?

@bedvit · 25.06.2020, 17:37 **[ТС]**

Avazart, вас, в очередной раз, подводит внимательность.

C++
1
2
3
4
5
6
const int N = 4000000; // количество строк
    std::string needle = "4000000";
    for (int i = 0; i < N; ++i)
    {
        Out.append(std::to_string(i + 1) + str + '\n');
    }

Ищем последнюю строку.

@Avazart · 25.06.2020, 17:38

Ищите к пример строку "3456789" т.е. то что будет найдено. Во вторых что бы символы были разные в подстроке.
В идеале нужно несколько тестов с разной длиной и уникальностью символов в искомой строке.

@bedvit · 25.06.2020, 18:06 **[ТС]**

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

т.е. то что будет найдено

4000000 тоже будет найдено в последней строке.

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

нужно несколько тестов с разной длиной и уникальностью символов

согласен. Но что успел, то и сделал, по предоставленному мне шаблону csv-файла (под свою конкретную задачу). Сейчас свободного времени в обрез, как и у вас. Желающие могут помочь, буду рад.

Добавлено через 17 минут
Вот результаты для поиска подстроки: "3456789Пятый; Тридацть четвертый; 44221100; BBB"
strstr: Time - 0.066000
std::find: Time - 0.192000
std::search: Time - 2.827000
std::boyer_moore_searcher: Time - 0.222000
std::boyer_moore_horspool_searcher: Time - 0.177000

Видно, что std::boyer_moore_horspool_searcher уже обгоняет std::find:
strstr() - пока на первом месте.
Тестирую в VS 2017.

@DrOffset · 25.06.2020, 18:15

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

strstr() - пока на первом месте.
Тестирую в VS 2017

Интересно было бы на код посмотреть.

@bedvit · 25.06.2020, 18:57 **[ТС]**

DrOffset, вот или ниже.
Если вынести часть расчета по подстроке, за рамки времени (к примеру считаем разово, далее используем при заливке каждого нового буфера). Как предложил zayats80888.

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

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
int main() {
    const int N = 4000000; // количество строк
    std::string str = "Пятый; Тридацть четвертый; 44221100; BBB; CIFRAPOLE; POLEPVTRETYE; ODIN ODIN - TRI; CC; 01.01.2013; 01.01.2013; 8963; 2UTY39ADVGKR; СU707039; 40200М У0026034; -; 11; 2; 150; 1998; 1; -; 21; 1980; 1490; НОМЕР ПЯТЬ; -; ПОЛЕ ОДИН; ПОЛЕ ОДИН ПЯТЬ; -; -";
    std::string Out("");
    std::string needle = "3456789Пятый; Тридацть четвертый; 44221100; BBB";
    Out.reserve(1027000000);
    for (int i = 0; i < N; ++i)
    {
        Out.append(std::to_string(i + 1) + str + '\n');
    }
 
    clock_t t1;
    clock_t t2;
 
    t1 = clock();
    auto s = strstr(Out.c_str(), needle.c_str());
    t2 = clock();
    printf("strstr: Time - %f\n", (t2 - t1 + .0) / CLOCKS_PER_SEC); // время отработки
 
    t1 = clock();
    auto f = Out.find(needle);
    t2 = clock();
    printf("find: Time - %f\n", (t2 - t1 + .0) / CLOCKS_PER_SEC); // время отработки
 
    t1 = clock();
    auto sr = std::search(Out.begin(), Out.end(), needle.begin(), needle.end());
    t2 = clock();
    printf("std::search: Time - %f\n", (t2 - t1 + .0) / CLOCKS_PER_SEC); // время отработки
 
    auto bms = std::boyer_moore_searcher(needle.begin(), needle.end());
    t1 = clock();
    auto srb = std::search(Out.begin(), Out.end(), bms);
    t2 = clock();
    printf("std::boyer_moore_searcher: Time - %f\n", (t2 - t1 + .0) / CLOCKS_PER_SEC); // время отработки
 
    auto bmhs = std::boyer_moore_horspool_searcher(needle.begin(), needle.end());
    t1 = clock();
    auto srbs = std::search(Out.begin(), Out.end(), bmhs);
    t2 = clock();
    printf("std::boyer_moore_horspool_searcher: Time - %f\n", (t2 - t1 + .0) / CLOCKS_PER_SEC); // время отработки
 
    system("pause");
    return 0;
}

strstr: Time - 0.067000
find: Time - 0.195000
std::search: Time - 2.822000
std::boyer_moore_searcher: Time - 0.204000
std::boyer_moore_horspool_searcher: Time - 0.181000

Добавлено через 33 минуты
отличия не сильные.

@XLAT · 25.06.2020, 19:44

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

strstr() - пока на первом месте.

у вас компилятор неправильный:
MSYS64 GCC 9.3

@XLAT · 25.06.2020, 19:46

@DrOffset · 25.06.2020, 19:54

bedvit, вообще это говорит о том, что в ms runtime функция strstr очень хорошо оптимизирована, а string.find - нет (или вообще не оптимизирована).
На MinGW, как и XLAT, я получил совершенно другие числа.
А вот boyer-moore на моей VS 2017 и MinGW сработал примерно одинаково.

Кстати, подобные баги с find были и в GCC ранее, например вот: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66414

@Avazart · 25.06.2020, 20:52

Речь шла не о strstr ибо понятно что тут оптимизация а была речь о самописной реализации для boyer-moore и std

@XLAT · 25.06.2020, 21:24

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

а была речь о самописной реализации

а кому интересны аутсайдеры?

@bedvit · 26.06.2020, 10:48 **[ТС]**

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

была речь о самописной реализации для boyer-moore и std

добавил код - Boyer-Moore algorithm.

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

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include "pch.h"
#include <string>
#include <ctime>
#include <algorithm>
#include <functional>
#include <iostream>
 
#define XSIZE 47
#define ASIZE 256
#define max(a,b) (((a) > (b)) ? (a) : (b))
 
void preBmBc(unsigned char *x, int m, int bmBc[]) {
    int i;
    for (i = 0; i < ASIZE; ++i)
        bmBc[i] = m;
    for (i = 0; i < m - 1; ++i)
        bmBc[x[i]] = m - i - 1;
}
 
 
void suffixes(unsigned char *x, int m, int *suff) {
    int f, g, i;
    suff[m - 1] = m;
    g = m - 1;
    for (i = m - 2; i >= 0; --i) {
        if (i > g && suff[i + m - 1 - f] < i - g)
            suff[i] = suff[i + m - 1 - f];
        else {
            if (i < g)
                g = i;
            f = i;
            while (g >= 0 && x[g] == x[g + m - 1 - f])
                --g;
            suff[i] = f - g;
        }
    }
}
 
void preBmGs(unsigned char *x, int m, int bmGs[]) {
    int i, j, suff[XSIZE];
    suffixes(x, m, suff);
    for (i = 0; i < m; ++i)
        bmGs[i] = m;
    j = 0;
    for (i = m - 1; i >= 0; --i)
        if (suff[i] == i + 1)
            for (; j < m - 1 - i; ++j)
                if (bmGs[j] == m)
                    bmGs[j] = m - 1 - i;
    for (i = 0; i <= m - 2; ++i)
        bmGs[m - 1 - suff[i]] = m - 1 - i;
}
 
 
int BM(unsigned char *x, int m, unsigned char *y, int n) {
    int i, j, bmGs[XSIZE], bmBc[ASIZE];
    /* Preprocessing */
    preBmGs(x, m, bmGs);
    preBmBc(x, m, bmBc);
    j = 0;
    while (j <= n - m) {
        for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
        if (i < 0) {
            return j;
        }
        else
            j += max(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
    }
    return -1;
}
 
int main() {
    const int N = 4000000; // количество строк
    std::string str = "Пятый; Тридацть четвертый; 44221100; BBB; CIFRAPOLE; POLEPVTRETYE; ODIN ODIN - TRI; CC; 01.01.2013; 01.01.2013; 8963; 2UTY39ADVGKR; СU707039; 40200М У0026034; -; 11; 2; 150; 1998; 1; -; 21; 1980; 1490; НОМЕР ПЯТЬ; -; ПОЛЕ ОДИН; ПОЛЕ ОДИН ПЯТЬ; -; -";
    std::string Out("");
    std::string needle = "4000000Пятый; Тридацть четвертый; 44221100; BBB";
    Out.reserve(1027000000);
    for (int i = 0; i < N; ++i)
    {
        Out.append(std::to_string(i + 1) + str + '\n');
    }
 
    clock_t t1;
    clock_t t2;
 
    t1 = clock();
    auto s = strstr(Out.c_str(), needle.c_str());
    t2 = clock();
    printf("strstr: Time - %f\n", (t2 - t1 + .0) / CLOCKS_PER_SEC); // время отработки
 
    t1 = clock();
    auto f = Out.find(needle);
    t2 = clock();
    printf("std::find: Time - %f\n", (t2 - t1 + .0) / CLOCKS_PER_SEC); // время отработки
    //std::cout << f << std::endl;
 
    t1 = clock();
    auto sr = std::search(Out.begin(), Out.end(), needle.begin(), needle.end());
    t2 = clock();
    printf("std::search: Time - %f\n", (t2 - t1 + .0) / CLOCKS_PER_SEC); // время отработки
    
    t1 = clock();
    auto srb = std::search(Out.begin(), Out.end(), std::boyer_moore_searcher(needle.begin(), needle.end()));
    t2 = clock();
    printf("std::boyer_moore_searcher: Time - %f\n", (t2 - t1 + .0) / CLOCKS_PER_SEC); // время отработки
 
    t1 = clock();
    auto srbs = std::search(Out.begin(), Out.end(), std::boyer_moore_horspool_searcher(needle.begin(), needle.end()));
    t2 = clock();
    printf("std::boyer_moore_horspool_searcher: Time - %f\n", (t2 - t1 + .0) / CLOCKS_PER_SEC); // время отработки
 
    //выносим часть разовых расчетов для подстроки поиска//
    auto bms2 = std::boyer_moore_searcher(needle.begin(), needle.end());
    t1 = clock();
    auto srb2 = std::search(Out.begin(), Out.end(), bms2);
    t2 = clock();
    printf("std::boyer_moore_searcher(needle_no_time): Time - %f\n", (t2 - t1 + .0) / CLOCKS_PER_SEC); // время отработки
 
    auto bmhs2 = std::boyer_moore_horspool_searcher(needle.begin(), needle.end());
    t1 = clock();
    auto srbs2 = std::search(Out.begin(), Out.end(), bmhs2);
    t2 = clock();
    printf("std::boyer_moore_horspool_searcher(needle_no_time): Time - %f\n", (t2 - t1 + .0) / CLOCKS_PER_SEC); // время отработки
    
    t1 = clock();
    auto bm = BM((unsigned char*)needle.c_str(), needle.length(), (unsigned char*)Out.c_str(), Out.length());
    t2 = clock();
    printf("BM: Time - %f\n", (t2 - t1 + .0) / CLOCKS_PER_SEC); // время отработки
    //std::cout << bm << std::endl;
 
 
    system("pause");
    return 0;
}

таиминг
strstr: Time - 0.079000
std::find: Time - 0.197000
std::search: Time - 3.311000
std::boyer_moore_searcher: Time - 0.213000
std::boyer_moore_horspool_searcher: Time - 0.177000
std::boyer_moore_searcher(needle_no_time ): Time - 0.203000
std::boyer_moore_horspool_searcher(needl e_no_time): Time - 0.174000
BM: Time - 0.293000

Видим, что BM: проигрывает std::

DrOffset, вопрос, чей код будет быстрее под Win, мой на strstr или XLAT на string.find?
Создать exe, обменяться и замерить?

@Avazart · 26.06.2020, 11:13

Как я понимаю Boyer-Moore становится тем эффективнее чем длинее искомая строка.
Очень интересно как же оптимизировали strstr что она все равно быстрее.

@bedvit · 26.06.2020, 11:21 **[ТС]**

DrOffset, по вашей ссылки

The C++17 library provides Boyer-Moore and Boyer-Moore-Horspool searchers, so that already offers you more control than basic_string::find or strstr.

Как видим boyer_moore в аутсайдерах. Возможно допилят со временем? Потому что для меня неожиданность, что boyer_moore на длинной строке с длинной подстрокой поиска (47 символов), с довольно широким спектром символов, с небольшим количеством повторов, проигрывает посимвольному перебору. Явно плохо реализован/оптимизирован алгоритм.

Добавлено через 5 минут

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

Очень интересно как же оптимизировали strstr что она все равно быстрее.

Да этот момент интересен. В особенности, std::find уже знает длину строки и подстроки, а strstr -должен каждый раз проверять, не закончилась ли, есть ли нулевой символ. И все равно быстрее (VS 2017).

@Avazart · 26.06.2020, 11:44

Не нужно путать сам алгоритм и низкоуровневую оптимизацию.

Да вот мы обсуждали недавно что strlen тоже оптимизируется и не всегда ищется \0

@DrOffset · 26.06.2020, 18:23

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

вопрос, чей код будет быстрее

Я взял ваш пример из #125, добавил вывод найденной позиции, скомпилировал в MinGW\g++ 9.2.0. Можете проверить у себя.
test.zip

@bedvit · 27.06.2020, 22:59 **[ТС]**

DrOffset, я не понял как у вас получилась найденная позиция 1070493176, если длина строки всего 1022888896.
Прилагаю свой exe, протестируйте у себя с учетом вопроса по позиции.
Мой тест, см. рис.

@DrOffset · 27.06.2020, 23:03

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

я не понял как у вас получилась найденная позиция 1070493176

У меня строки в UTF-8. На каждый русский символ - 2 байта.

@bedvit · 27.06.2020, 23:37 **[ТС]**

Задача на ansi. Протестируйте пожалуйста на 1байтовом тексте.

@DrOffset · 27.06.2020, 23:44

Переделал на CP1251 как у вас. Вот ваша программа:

Вот моя, на 1251, mingw/g++:

@DrOffset · 27.06.2020, 23:45

Вот программа: test.zip

Новые блоги и статьи Все статьи Все блоги /
Установка MinGW GCC 16.2 и CMake 8Observer8 10.08.2026 VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия	Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо anaschu 10.08.2026 Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .	Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .
Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .	Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники). Hrethgir 04.08.2026 Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .	Термопринтер QR701 Argus19 03.08.2026 Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .

@Avazart 8489 / 6156 / 615 Регистрация: 10.12.2010 Сообщений: 28,683 Записей в блоге: 30
	25.06.2020, 17:38
	Ищите к пример строку "3456789" т.е. то что будет найдено. Во вторых что бы символы были разные в подстроке. В идеале нужно несколько тестов с разной длиной и уникальностью символов в искомой строке. 0

@XLAT Just Do It! 4220 / 2683 / 656 Регистрация: 23.09.2014 Сообщений: 9,236 Записей в блоге: 3
	25.06.2020, 19:46
	0

@DrOffset 19505 / 10108 / 2463 Регистрация: 30.01.2014 Сообщений: 17,828
	25.06.2020, 19:54
	bedvit, вообще это говорит о том, что в ms runtime функция strstr очень хорошо оптимизирована, а string.find - нет (или вообще не оптимизирована). На MinGW, как и XLAT, я получил совершенно другие числа. А вот boyer-moore на моей VS 2017 и MinGW сработал примерно одинаково. Кстати, подобные баги с find были и в GCC ранее, например вот: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66414 0

@Avazart 8489 / 6156 / 615 Регистрация: 10.12.2010 Сообщений: 28,683 Записей в блоге: 30
	25.06.2020, 20:52
	Речь шла не о strstr ибо понятно что тут оптимизация а была речь о самописной реализации для boyer-moore и std 0

@Avazart 8489 / 6156 / 615 Регистрация: 10.12.2010 Сообщений: 28,683 Записей в блоге: 30
	26.06.2020, 11:13
	Как я понимаю Boyer-Moore становится тем эффективнее чем длинее искомая строка. Очень интересно как же оптимизировали strstr что она все равно быстрее. 0

@Avazart 8489 / 6156 / 615 Регистрация: 10.12.2010 Сообщений: 28,683 Записей в блоге: 30
	26.06.2020, 11:44
	Не нужно путать сам алгоритм и низкоуровневую оптимизацию. Да вот мы обсуждали недавно что strlen тоже оптимизируется и не всегда ищется \0 0

@bedvit 1210 / 261 / 22 Регистрация: 20.05.2016 Сообщений: 1,147 Записей в блоге: 22
	27.06.2020, 23:37 [ТС]
	Задача на ansi. Протестируйте пожалуйста на 1байтовом тексте. 0

@DrOffset 19505 / 10108 / 2463 Регистрация: 30.01.2014 Сообщений: 17,828
	27.06.2020, 23:44
	Переделал на CP1251 как у вас. Вот ваша программа: Вот моя, на 1251, mingw/g++: 0

@DrOffset 19505 / 10108 / 2463 Регистрация: 30.01.2014 Сообщений: 17,828
	27.06.2020, 23:45
	Вот программа: test.zip 0