C++ 中文周刊第137期

王很水

发布于 2024-07-30 14:41:37

770

发布于 2024-07-30 14:41:37

文章被收录于专栏：C++ 动态新闻推送

RSS https://github.com/wanghenshui/cppweeklynews/releases.atom

欢迎投稿，推荐或自荐文章/软件/资源等

请提交 issue[2]

最近在找工作准备面试题，更新可能有些拖沓，见谅

以后可能要改变一下内容

一周发文章总结，一周发视频总结，这样两种内容交叉一下

本期发文章

本期由不语 cqs 赞助

资讯

CLion的新beta版本：CLion Nova https://blog.jetbrains.com/clion/2023/11/clion-nova/

mick投稿，说挺好用

标准委员会动态/ide/编译器信息放在这里十月邮件 https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/#mailing2023-10

编译器信息最新动态推荐关注hellogcc公众号 OSDT Weekly 2023-11-08 第227期

文章

• The power of ref-qualifiers[3]

其实就是限定接口

class Keeper {
  std::vector<int> data{2, 3, 4};

public:
  ~Keeper() { std::cout << "dtor\n"; }

  auto& items() & { return data; }

  //For rvalues, by value with move
  auto items() && { return std::move(data); }
};

之前也介绍过这种限定接口不容易用错

• Clang/GCC Target Attributes [4]

-march可以根据架构更精细配置

比如-march=znver4

那怎么保证代码移植兼容性呢？不同的架构有不同配置？宏？太不优雅

可以使用arrtribute(target) 分别实现，也可以用target_clones多个架构共用一个版本

#include <array>
#include <cstdio>

using Vector = std::array<float, 2>;
using Matrix = std::array<float, 4>;

__attribute__((target_clones("default","arch=core2","arch=znver2")))
Vector multiply(const Matrix& m, const Vector& v) {
    Vector r;
    r[0] = v[0] * m[0] + v[1] * m[2];
    r[1] = v[0] * m[1] + v[1] * m[3];
    return r;
}

#include <array>
#include <cstdio>

using Vector = std::array<float, 2>;
using Matrix = std::array<float, 4>;

Vector multiply(const Matrix& m, const Vector& v);

int main() {
    Matrix m{1,2,3,4};
    Vector v{1,2};
    Vector r = multiply(m,v);
    printf( "%f %f\n", r[0], r[1] );
}

目前clang会编译报错。应该是bug，我看maskray在研究 https://github.com/llvm/llvm-project/issues/61219

• xmake 2.8.5[5]

测试增强。挺好的

• Link-time optimisation (LTO) [6]

介绍LTO的

• 协程利器，std::generator for C++23用法入门与实现剖析(一)[7]

介绍generator实现的，可以体验一下这个 https://godbolt.org/z/5hcaPcfvP

• 论文阅读：Mimalloc Free List Sharding in Action[8]

介绍mimalloc实现的

•printing aggrrgates [9]

一个简单的结构化打印例子，使用boost pfr/magic_get


template <class T, typename = void>
consteval std::string_view type_name() {
    std::string_view s = std::source_location::current().function_name();
    auto i0 = s.find('T') + 4;
    auto i1 = s.find(';');
    return s.substr(i0, i1 - i0);
}

template <class T>
    requires(std::is_class_v<T> && std::is_aggregate_v<T>)
std::ostream& operator<<(std::ostream& os, const T& x) {
    os << type_name<T>();
    os << '(';
    boost::pfr::for_each_field(x, [&](const auto& field_val, auto field_idx) {
        if (field_idx > 0) {
            os << ", ";
        }
        os << boost::pfr::get_name<field_idx, T>() << '=' << field_val;
    });
    os << ')';
    return os;
}

struct Point {
    int x, y, z;
};

Point p(1, 2, 3);
std::cout << p << '\n';
// Point(x=1, y=2, z=3)

struct Line {
    Point a, b;
};
Line l(Point(1, 2, 3), Point(4, 5, 6));
std::cout << l << '\n';
// Line(a=Point(x=1, y=2, z=3), b=Point(x=4, y=5, z=6))

• Compile time string literals processing, but why?[10]

介绍一些编译期字符串组件，source_location magic_enum之类的不知道magic_num的看这里 https://github.com/Neargye/magic_enum

• Generic Topological Sort[11]

拓扑排序。感觉这个可以出算法题了

首先要明白什么是拓扑排序,可能直观印象就是leetcode那些题。这里的例子可能不太一样

那么std::sort能不能用于拓扑排序？

比如

/// `edge(u, v)` returns true if and only if there is an edge from `u` to `v`
template< class RandomIt, class F >
void topological_sort( RandomIt first, RandomIt last, F edge ) {
    std::sort(first, last, edge);
}

我们考虑一个场景

A -----> C -----> D
|
-------> B

一个简单的关系，ACDB ABCD ACBD 也就这三种走向，怎么写条件呢

#include <algorithm>
#include <iostream>
#include <string>

int main() {
    std::string vertices{'A', 'B', 'C', 'D'};
    auto edge = [](char u, char v) {
        return (u == 'A' && v == 'B')
            || (u == 'A' && v == 'C')
            || (u == 'C' && v == 'D')
            ;
    };

    do {
        auto sorted = vertices;
        std::sort(sorted.begin(), sorted.end(), edge);
        std::cout << vertices << " --> " << sorted << '\n';
    } while (std::next_permutation(vertices.begin(), vertices.end()));
}

讲道理，任何一种ABCD排列最终都会转化成上面列的三种，对不对？

但执行上面的例子你会发现有几个场景并不能转化成上面的三种

DABC --> CDAB
DACB --> CDAB
DBAC --> CDAB

为什么？sort排序的条件显然不能这么写，并没有一个有序的传递性

拓扑排序没有排序的传递性，所以被迫需要整体的视角，

而排序is sorted只要保证左右和自己就能把这个传递性推广开

那只好遍历了

/// topological sort, the brute force
template <std::random_access_iterator I, class S, class F>
void topological_sort(I first, S last, F edge) {
    for (; first != last; ++first) {
        // check if *first is a source.
        for (auto other = std::next(first); other != last; ++other) {
            if (edge(*other, *first)) {
                // *first is not a source; *other may be
                std::swap(*other, *first);
                // IMPORTANT! have to do the full search again for the new *first
                other = first;
            }
        }
    }
}

显然这个复杂度不能接受，哈哈接下来可能就要重新发行khan算法和DFS算法了。这里把khan代码列出来

/// topological sort, Kahn's algorithm
template <std::random_access_iterator I, class S, class F>
void topological_sort(I first, S last, F edge) {
    std::size_t n = std::ranges::distance(first, last);
    std::vector<std::size_t> in_degree(n);

    for (std::size_t i = 0; i < n; ++i) {
        for (std::size_t j = 0; j < n; ++j) {
            in_degree[i] += bool(edge(first[j], first[i]));
        }
    }
    
    // [s_first, s_last) are the sources of the sub-graph [s_first, last)
    auto s_first = first;
    auto s_last = s_first;

    for (std::size_t i = 0; i < n; ++i) {
        if (in_degree[i] == 0) {
            std::swap(first[i], *s_last);
            std::swap(in_degree[i], in_degree[s_last - first]);
            ++s_last;
        }
    }

    for (; s_first != s_last; ++s_first) {
        for (auto t_it = s_last; t_it != last; ++t_it) {
            if (edge(*s_first, *t_it) && --in_degree[t_it - first] == 0) {
                std::swap(*t_it, *s_last);
                std::swap(in_degree[t_it - first], in_degree[s_last - first]);
                ++s_last;
            }
        }
    }
}

说不定将来std::graph能进标准库，这些内建支持

如果你像我一样不知道上面说的是啥, 说明你该刷算法题了

比如看看这个 https://algo.itcharge.cn/08.Graph/02.Graph-Traversal/05.Graph-Topological-Sorting

• The dangers of releasing the last strong reference from within its own callback[12]

考虑类中注册回调函数，析构可能就要把注册的回调函数去掉，有一种可能，回调函数在调用的途中，类自己已经析构了，回调函数也unregister了

如何解决这种问题？

直观的解决办法就是析构的时候等待调用结束，其实就是引用计数，调用的时候+1 调用结束-1

这其实引入了shared_ptr循环依赖的的问题，导致永远不能析构，死锁

如何解决这种死锁问题？考虑引入weakptr？

考虑析构拆出来，弄个final_release静态方法？ https://learn.microsoft.com/zh-cn/windows/uwp/cpp-and-winrt-apis/details-about-destructors#deferred-destruction

或者把callback和类自身生命周期绑定在一起，结合weakptr 这种设计比较常见

class MyObject {
    MyObject()
    {
        m_widget.prime();
        // Do this last: Don't register for callbacks  
        // until all members are ready.                
        m_callback.register(&MyObject::callback, this);
    }

    ~MyObject()
    {
        // Do this first: Ensure all outstanding
        // callbacks have completed.            
        m_callback.reset();                     
        m_widget.disable();
    }
};
void MyObject::Callback(CallbackData* data, void* context)
{
    auto self = reinterpret_cast<MyObject*>(context);

    [](auto weak, auto important) -> fire_and_forget {
        co_await resume_background();
        if (auto strong = weak.get()) {
            ⟦ do stuff with "strong" ⟧
        }
    }(get_weak(), data->important);
}

How to use std::span from C++20 [13]

span相比string_view有个优点，就是可以改动

Why does unsafe multithreaded use of an std::unordered_map crash more often than unsafe multithreaded use of a std::map?[14]

客户的代码多线程裸奔，使用map来读写，崩溃次数还算少，就没怎么关注，某一天改成unordered_map 崩溃次数多了。只能加锁了

为什么？unordered_map冲突变更导致迭代器失效的概率比map这种有序的低

我觉得这种知识还是不要知道的好

开源项目需要人手

• asteria[15] 一个脚本语言，可嵌入，长期找人，希望胖友们帮帮忙，也可以加群384042845和作者对线

最近进展，优化JIT/基础组件调优，对于做语言的还是能见识到一点东西的

• Unilang[16] deepin的一个通用编程语言，点子有点意思，也缺人，感兴趣的可以github讨论区或者deepin论坛看一看。这里也挂着长期推荐了
• gcc-mcf[17] 懂的都懂
• https://github.com/hggq/paozhu 一个网络框架
• https://gitee.com/okstar-org/ok-edu-desktop 一个IM通信软件，做IM的可以关注，现在正在做全面整合阶段，开始组建商业团队阶段，年底开始融资，你参加了就快发财了，会的快来
• https://github.com/volt-software/Ichor/tree/v0.3.0 一个c++20 服务框架

视频

• [MUC++] Elizaveta Shulankina - Analyzing C++ applications for performance optimization[18]

intel的，主要还是并行化那几样，SOA改成AOS，使用intel的编译器以及SDLT[19]之类的

• Tristan Brindle - Iteration Revisited[20]

还是介绍flux的。部分场景比range快（为什么？）

• cppclubuk 166唠嗑讨论汇总 166. WG21 September 2023 mailing, Contracts, Modules, Cppfront

https://cppclub.uk/meetings/2023/166/ 会议记录在这里

视频在这里 https://www.youtube.com/watch?v=6L3Vk6Zax_w

我发了一份b站 BV17g4y1Q7XD

互动环节

工作环境还是比较差的，大家尽量不要离职。。

最近面试又遇到个奇葩的题

vector的push_back可以理解成均摊O1 那么考虑扩容的影响，假设扩容按照2备来算，复杂度应该是多少？

我回答N logN他说那是最大的，不对我说(LogN)^2他也说不对。我不会了

引用链接

[1] 手机qq点击进入: https://qm.qq.com/q/6NGizNPyG4 [2] 提交 issue: https://github.com/wanghenshui/cppweeklynews/issues [3] The power of ref-qualifiers: https://andreasfertig.blog/2022/07/the-power-of-ref-qualifiers/ [4] Clang/GCC Target Attributes : https://lucisqr.substack.com/p/clanggcc-target-attributes [5] xmake 2.8.5: https://github.com/xmake-io/xmake/wiki/Xmake-v2.8.5-released,-Support-for-link-sorting-and-unit-testing [6] Link-time optimisation (LTO) : https://convolv.es/guides/lto/ [7] 协程利器，std::generator for C++23用法入门与实现剖析(一): https://zhuanlan.zhihu.com/p/666365620 [8] 论文阅读：Mimalloc Free List Sharding in Action: https://zhuanlan.zhihu.com/p/665602526 [9] : https://biowpn.github.io/bioweapon/2023/11/11/printing-aggregates.html [10] Compile time string literals processing, but why?: https://a4z.gitlab.io/blog/2023/11/04/Compiletime-string-literals-processing.html [11] Generic Topological Sort: https://biowpn.github.io/bioweapon/2023/11/03/topological-sort.html [12] The dangers of releasing the last strong reference from within its own callback: https://devblogs.microsoft.com/oldnewthing/20230927-00/?p=108831 [13] How to use std::span from C++20 : https://www.cppstories.com/2023/span-cpp20/ [14] Why does unsafe multithreaded use of an std::unordered_map crash more often than unsafe multithreaded use of a std::map?: https://devblogs.microsoft.com/oldnewthing/20231103-00/?p=108966 [15] asteria: https://github.com/lhmouse/asteria [16] Unilang: https://github.com/linuxdeepin/unilang [17] gcc-mcf: https://gcc-mcf.lhmouse.com/ [18] [MUC++] Elizaveta Shulankina - Analyzing C++ applications for performance optimization: https://www.youtube.com/watch?v=M1D8iez1Ph0 [19] SDLT: https://www.intel.com/content/www/us/en/docs/dpcpp-cpp-compiler/developer-guide-reference/2023-2/simd-data-layout-templates.html [20] Tristan Brindle - Iteration Revisited: https://www.youtube.com/watch?v=bMitr8ReVeg