reu*_*man 1 c++ sorting algorithm performance
我有一个名为的集合Dataframe，本质上是一个std::vector<char>. 它包含records特定的长度record_size，可以由1个或多个不同类型的字段组成。的定义Dataframe是不可协商的，因为它与代码库的其余部分紧密耦合。一般来说，该结构可以包含数百万数量级的大量记录和数百数量级的大量列。
根据我上面所说的，可能只有一个列或多列。单例列，就是我所说的简单情况，因为字符向量可以转换为实际类型，并且排序非常有效。
我遇到的问题是，对于多个列，我需要有一个指向记录的指针向量，应用一个跳转到内存中访问实际数据的比较器函数，然后交换指针，当排序过程结束时，应用到真实数据由指针标识的排列。这会比较慢，尤其是当Dataframe包含真实世界数据时。
下面的代码摘录可以更好地解释这种情况。有没有其他方法可以解决这个问题？
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <functional>
class Dataframe {
public:
enum class Base : char
{
SIGNED = 'S',
UNSIGNED = 'U',
CHAR = 'A',
// and other types like floats, date, timestamp, etc.
};
class Dtype
{
public:
Dtype(Base base_dtype, std::size_t size) : m_base_dtype(base_dtype), m_size(size) {}
auto base_dtype() const { return m_base_dtype; }
auto size() const { return m_size; }
private:
Base m_base_dtype;
std::size_t m_size;
};
class Comparator {
public:
using comparator_fn = std::function<std::int8_t(const char*, const char*)>;
static comparator_fn make_comparator(Dataframe::Base base_dtype, std::size_t size, std::size_t offset) {
switch (base_dtype) {
case Dataframe::Base::CHAR:
return [offset](const char *a, const char *b) {
return std::strcmp(a + offset, b + offset);
};
case Dataframe::Base::SIGNED:
return [offset](const char *a, const char *b) {
const auto v1 = *reinterpret_cast<const int*>(a + offset);
const auto v2 = *reinterpret_cast<const int*>(b + offset);
return (v1 < v2) ? -1 : (v1 > v2) ? 1 : 0;
};
case Dataframe::Base::UNSIGNED:
return [offset](const char *a, const char *b) {
const auto v1 = *reinterpret_cast<const unsigned int*>(a + offset);
const auto v2 = *reinterpret_cast<const unsigned int*>(b + offset);
return (v1 < v2) ? -1 : (v1 > v2) ? 1 : 0;
};
default:
throw std::runtime_error("Unknown base dtype");
}
}
static comparator_fn make_composite_comparator(const std::vector<Dataframe::Dtype> &dtypes) {
std::vector<comparator_fn> F;
std::size_t offset = 0;
for (auto &dtype : dtypes) {
F.push_back(make_comparator(dtype.base_dtype(), dtype.size(), offset));
offset += dtype.size();
}
return [F](const char *a, const char *b) {
for (auto &f : F) {
if (const int8_t result = f(a, b); result != 0)
return result < 0;
}
return false;
};
}
};
Dataframe(const std::vector<char> &raw_data, const std::vector<Dtype> &dtypes) : m_raw_data(raw_data), m_dtypes(dtypes)
{
cols_count = m_dtypes.size();
m_record_size = std::accumulate(m_dtypes.begin(), m_dtypes.end(), 0, [](std::size_t acc, const Dtype &dtype) {
return acc + dtype.size();
});
m_records_count = m_raw_data.size() / m_record_size;
std::cout << "Info:" << std::endl;
std::cout << " - cols count: " << cols_count << std::endl;
std::cout << " - record size: " << m_record_size << std::endl;
std::cout << " - records count: " << m_records_count << std::endl;
std::cout << std::endl;
}
void print() {
// cycle over the records
std::cout << "Dataframe:" << std::endl;
for (std::size_t i = 0; i < m_records_count; i++) {
// cycle over the dtypes (e.g. columns)
auto current_field = m_raw_data.data() + i * m_record_size;
for (std::size_t j = 0; j < m_dtypes.size(); j++) {
auto dtype = m_dtypes[j];
auto base_dtype = dtype.base_dtype();
auto size = dtype.size();
current_field += j > 0 ? m_dtypes[j - 1].size() : 0;
// print the data
switch (base_dtype) {
case Base::CHAR:
std::cout << std::setw(1) << *current_field << ";";
break;
case Base::SIGNED:
std::cout << std::setw(4) << *reinterpret_cast<int*>(current_field) << ";";
break;
case Base::UNSIGNED:
std::cout << std::setw(4) << *reinterpret_cast<unsigned int*>(current_field) << ";";
break;
}
}
std::cout << std::endl;
}
std::cout << std::endl;
}
void sort() {
if (cols_count == 1) {
auto dtype = m_dtypes[0];
auto base_dtype = dtype.base_dtype();
auto size = dtype.size();
auto data = m_raw_data.data();
// print the data
switch (base_dtype) {
case Base::CHAR:
std::sort(data, data + m_raw_data.size());
break;
case Base::SIGNED:
std::sort((int*)data, (int*)data + m_raw_data.size() / size);
break;
case Base::UNSIGNED:
std::sort((unsigned int*)data, (unsigned int*)data + m_raw_data.size() / size);
break;
}
} else {
// This is a naive implementation, it works but it's not efficient
// use the ptr, compare and then swap the records
auto comparator = Comparator::make_composite_comparator(m_dtypes);
// create a set of pointers to the records
std::vector<char*> ptrs;
for (std::size_t i = 0; i < m_records_count; i++) {
ptrs.push_back(m_raw_data.data() + i * m_record_size);
}
// sort the pointers
std::sort(ptrs.begin(), ptrs.end(), comparator);
// apply pointers permutation
std::vector<char> tmp(m_raw_data.size());
for (std::size_t i = 0; i < m_records_count; i++) {
std::copy(ptrs[i], ptrs[i] + m_record_size, tmp.data() + i * m_record_size);
}
m_raw_data = tmp;
}
}
private:
std::vector<char> m_raw_data;
std::vector<Dtype> m_dtypes;
std::size_t m_records_count;
std::size_t m_record_size;
std::size_t cols_count;
};
void trivial_case_with_1_column() {
std::vector<char> raw;
// Example, trivial case with 1 column into the dataframe
int data[] = {8, 30, 8, 19, 7, 6, 10, 5, 3, 2, 1, 5};
raw.insert(raw.end(), (char*)data, (char*)data + sizeof(data));
Dataframe df(raw, {Dataframe::Dtype(Dataframe::Base::SIGNED, sizeof(int))});
df.print();
df.sort();
std::cout << "AFTER SORTING" << std::endl;
df.print();
}
void problematic_case_with_2_or_more_columns() {
std::vector<char> raw;
int column1[] = {8, 30, 8, 19, 7, 6, 10, 5, 3, 2, 1, 5};
char column2[] = {'z', 'a', 'a', 'b', 'c', 'd', 'e', 'x', 'g', 'h', 'i', 'a'};
for (std::size_t i = 0; i < sizeof(column1) / sizeof(int); i++) {
raw.insert(raw.end(), (char*)&column1[i], (char*)&column1[i] + sizeof(int));
raw.insert(raw.end(), (char*)&column2[i], (char*)&column2[i] + sizeof(char));
}
const auto dtypes = {Dataframe::Dtype(Dataframe::Base::SIGNED, sizeof(int)), Dataframe::Dtype(Dataframe::Base::CHAR, sizeof(char))};
Dataframe df(raw, dtypes);
df.print();
df.sort();
std::cout << "AFTER SORTING" << std::endl;
df.print();
}
int main(int argc, char const *argv[])
{
std::cout << "This case can be sorted by using a std::sort that casts the pointer to the correct type and it's efficient" << std::endl;
trivial_case_with_1_column();
std::cout << "----------------------------------------------------------------\n" << std::endl;
std::cout << "I don't know how to manage effectively this case" << std::endl;
problematic_case_with_2_or_more_columns();
return 0;
}
在线版本： https: //onlinegdb.com/gP5-8LOmv
这是我最初回答的更详细的后续内容。
我构建了一些工具来使用综合生成的数据集来测量不同排序算法的性能。代码和构建说明可在 GitHub 存储库core-cpp/sort中找到。
根据OP的问题描述，我使用了以下三个数据集，每个数据集有10M行，作为基准：
uint64_t该列上有一个排序键。uint64_t第一列有一个排序键。uint64_t排序键由前 8 列组成。虽然std::sort使用了几乎无分支的高度优化版本的快速排序，但没有一种明显的方法来调用它来直接对编译时长度未知的记录进行排序。
一种选择是使用指针或索引的间接寻址，而不实际对数据本身进行排序。对于大型数据集，存在很大的非局部性惩罚，因为关键比较需要从数据集中读取有效的随机行。这远远抵消了任何好处。
另一种选择是使用也实现
std::swap. 但这对于 来说是不够的std::sort，因为它在叶子上使用插入排序，这需要为动态记录大小分配动态内存。
基于这样的理解，我实现了以下排序算法进行比较：
std::sort仅适用于案例 #1作为一种特殊情况，如果记录只是单个 uint64_t，则直接调用 std::sort 传递指向数据的指针和 lambda 以直接比较 uint64_t 值。这代表了可能的最佳性能。一般情况下，我们在编译时不会知道记录长度或键类型，因此该方法只是一个比较基准。
std::sort对于情况 #1 仅使用通用比较与上面的第一种情况类似，但使用通用比较函数而不是假设编译时已知的键类型。这代表了预期性能的更现实的上限，因为通常在编译时密钥是未知的。在一般情况下，我们在编译时不会知道记录长度，因此该方法只是另一个比较基准。
qsort_rC 库函数qsort_r提供了一个允许指定记录长度和比较函数的接口。这使得能够以直接的方式直接对记录进行排序。OSX和Linux之间的函数接口有所不同，因此需要一些条件编译。
基本的快速排序算法在概念上很简单，我实现了一个简单的版本，允许运行时记录长度和比较函数。我仍然需要尝试更高级的枢轴选择。
std::sort有指针构造一个引用数据集行的指针向量，并std::sort使用自定义比较 lambda 调用指针。
std::sort带索引构造一个引用数据集行的索引向量，并std::sort使用自定义比较 lambda 调用该索引向量。
基本基数排序算法在概念上很简单，我实现了一个简单的版本，允许运行时记录长度和比较函数。
我测量了三种不同架构的性能（所有硬件都具有相对于数据集大小而言充足的主内存）。
跨硬件平台的不同算法之间的相对性能存在惊人的差异。特别是，其中一种基数方法在 arm64 和 Intel 上显示出极好的前景，但在 AMD 上表现最差。
以下是基准案例 1 的一些典型运行：
$ make sort1 && sort1 -n 10000000 -r 8 u64:0
std::sort-direct: 637 ms
std::sort-direct-compare-function: 1290 ms
qsort_r-direct: 1859 ms
quick-sort: 1560 ms
quick-block-sort: 1596 ms
std::sort-pointer: 1879 ms
std::sort-index: 1956 ms
radix-index-sort: 615 ms
radix-mem-index-sort: 415 ms
merge-bottom-up-sort: 2031 ms
$ make sort1 && sort1 -n 10000000 -r 8 u64:0
std::sort-direct: 966 ms
std::sort-direct-compare-function: 2481 ms
qsort_r-direct: 3705 ms
quick-sort: 3122 ms
quick-block-sort: 3416 ms
std::sort-pointer: 3863 ms
std::sort-index: 4068 ms
radix-index-sort: 5151 ms
radix-mem-index-sort: 1797 ms
merge-bottom-up-sort: 3869 ms
$ make sort1 && sort1 -n 10000000 -r 8 u64:0
std::sort-direct: 1121 ms
std::sort-direct-compare-function: 2461 ms
qsort_r-direct: 3718 ms
quick-sort: 3333 ms
quick-block-sort: 3752 ms
std::sort-pointer: 7712 ms
std::sort-index: 7141 ms
radix-index-sort: 13216 ms
radix-mem-index-sort: 11665 ms
merge-bottom-up-sort: 4497 ms
如果我们std::sort-direct-compare-function作为基准，自定义quicksort实现和qsort_rC 库函数是最一致的执行者。下表显示了相对于基线的运行时间。
| 算法\CPU | M1 | 英特尔 | AMD |
|---|---|---|---|
quicksort |
1.21 | 1.26 | 1.35 |
qsort_r |
1.44 | 1.49 | 1.51 |
radix-mem |
0.32 | 0.72 | 4.74 |
与任何优化策略一样，实际数据和特定硬件将是重要因素。