Memory Reallocation when Parsing CSV Files

教育   科技   2023-12-03 20:54   美国  

回顾上篇实现,可见会遇到内存重新分配问题,大文件读取存在隐性开销。

 1using result_type = std::vector<std::vector<std::string>>;
2
3auto read_csv(std::string_view file, std::string_view type = ""std::string_view delimiter = ",")
4    -> std::optional<result_type>
5
{
6    std::ifstream data_file(file.data());
7    if (!data_file.is_open())
8    {
9        return {};
10    }
11
12    std::string line;
13    std::getline(data_file, line); // skip the title
14    result_type result;
15    while (std::getline(data_file, line))
16    {
17        auto tokens = line
18                    | std::views::split(delimiter)
19                    | std::views::transform([](auto&& token) {
20                        return std::string_view(&*token.begin(), std::ranges::distance(token));
21                    });
22
23        auto it = std::ranges::begin(tokens);
24        std::ranges::advance(it, 2);
25        if (type.empty() || *it == type)
26        {
27            // save all records or filtered records.
28            result.push_back(result_type::value_type(tokens.begin(), tokens.end()));
29        }
30    }
31
32    return result;
33}

之所以存在该问题,主要是因为使用 std::vector 保存结果时,元素动态增长,已有内存渐匮,它便会分配更大的连续内存,并为数据挪窝。对于大文件,可能会发生多次挪窝行为,性能骤降。

深层问题在于,读取文件前,缺少一种常数复杂度的方法,能够提前得到文件行数。若是能够提前知道文件行数,便可以利用 std::vector::reverse 一次性分配所需内存,避免重新分配。

这种问题,三种解决方式较为常见。

第一种方式,二阶段读。读取文件之前,先读取一遍,以获取文件行数。

C++ 常见的计算文件行数方式如下:

 1// Count lines of a file line by line
2std::ifstream data_file(file.data());
3int lines = 0;
4std::string line;
5while (std::getline(data_file, line))
6   ++lines;
7
8// Count lines of a file using iterator
9std::ifstream data_file(file.data());
10auto lines = std::ranges::count(std::istreambuf_iterator<char>(data_file), std::istreambuf_iterator<char>(), '\n');
11std::cout << "Number of lines: " << lines << '\n';

两种方式都较为常用,不过迭代的方式按 '\n' 统计行数,若是文件并不按照其作为换行符,可能会统计出错。

既已知晓行数,便可以为 std::vector 预分配内存,避免重新分配。但是,这种方式将开销转移到了文件读取,首次迭代仅为获取文件行数,未免奢侈,文件过大时,开销亦不低。

第二种方式,便是当前的实现,不管大小,将开销转移到重新分配。缺点如前文所说,不再赘述。

第三种方式,先使用其他非连续内存容器替代 std::vector,再转换成连续内存容器。

比如,采用 std::list 来保存结果,它的插入性能很好,内存并不要求连续,也不会发生挪窝行为,避免了开销。

这种方式的问题在于,它将开销转移到了类型转换。虽然 std::list 的插入开销很低,但却无法快速随机访问,纵使不再转换为 std::vector 或其他数据结构,开销也会被转移到用户方。

既然开销已经转移到用户方,那又何必多此一举地保存结果呢?直接将思路由整体变为局部,处理一条记录,便交由用户做进一步处理。

这种方式实现如下:

 1template <class F>
2auto read_csv(std:
:string_view file, F fn, std::string_view delimiter = ",") -> void
3{
4    std::ifstream data_file(file.data());
5    if (!data_file.is_open())
6        return;
7
8    std::string line;
9    std::getline(data_file, line); // skip the title
10    while (std::getline(data_file, line))
11    {
12        auto tokens = line
13                    | std::views::split(delimiter)
14                    | std::views::transform([](auto&& token) {
15                        return std::string_view(&*token.begin(), std::ranges::distance(token));
16                    });
17
18        std::invoke(fn, tokens);
19    }
20}
21
22// 
23int main() {
24    csvpp::read_csv("../data/chip_dataset.csv", [](auto&& tokens) {
25        fmt::print("{}\n", tokens);
26    });
27}

处理方不再保存结果,用户方若想保存,便须自己设法解决以上问题。

另有一些思路,比如预估文件行数,只扫描部分文件数据,根据这些数据的行数,估计整个文件的行数,这种情况下无需精确到位,只需大致准确,向上取二次方整,便可避免重新分配。

纵观这些方法,可见多数时候,问题并不存在一个完美的解决方案。许多问题的一面是另一个问题的另一面,解决一个问题必然会带来另一个问题。因此,必须分清主次,把主要模块的问题潜移默化地转移到其他次要模块之中,先解决当下的问题。问题其实一直都未消失,只是在模块间滚来滚去。若要真正解决问题,就得从外部借力,增加新东西,以增量来解决旧的问题,随之而来的将会是新的问题,循环往复。

易用性和性能往往也难以兼备,以易用性为主,性能可能会大打折扣,反之易用性又难以顾及。是以这部分会被抽象出去,定制不同实现,转移问题,至于主次如何划分,则应具体问题具体分析了。

若要测试本节代码,可以直接:

1git clone https://github.com/lkimuk/csvpp.git
2mkdir build && cd build
3cmake ../
4make
5./test

有其他优化思路,可以评论指出。


CppMore
Dive deep into the C++ core, and discover more!
 最新文章