起底 C++ Range 令人惊讶的局限性!

作者 | Jonathan Boccara

译者 | 苏本如 责编 | 胡巍巍

出品 | CSDN(ID:CSDNnews)

作者注:今天我们收到了一个来自亚历克斯·阿斯塔辛(Alex Astashyn)的客座帖子。Alex是美国国家生物技术信息中心的RefSeq(Reference Sequence–标准序列)资源的技术负责人。

注:本文所表达的观点是该帖子作者的观点。而且,我自己也不能算是个“range专家”,所以有些与range有关的信息实际上可能是不正确的(如果你发现有任何严重错误,请在下面留下你的评论)。

在本文中,我将讨论我在C++ range上遇到的问题和局限性。

我还将介绍我自己开发的库rangeless,它将所有我希望由range实现的功能提炼在一起,使得我能够处理更大范围的有趣的实际应用用例。

序言

和所有爱好面向函数的声明式无状态编程的开发者一样,我原以为ranges非常有前途。然而,在实践中使用它们的尝试,被证明是一个非常令人沮丧的经历。

我一直在尝试用range写出那些对我来说似乎很合理的代码,然而,编译器却不断地打印出一页页让我无法理解的错误消息。最后我意识到了我自己的错误。我原以为range和这样的UNIX管道一样:cat file | grep ... | sed ... | sort | uniq -c | sort -nr | head -n10,但事实并非如此……

示例:

示例1:Intersperse(插入分隔符)

让我们尝试编写一个view,在输入元素之间插入一个分隔符。

(此功能由range-v3提供,因此我们可以比较一下这些方法的不同)

  // inputs:    [x1, x2, ... xn] 
        // transform: [[x1, d], [x2, d], ... [xn, d]]
        // flatten:   [ x1, d, x2, d, ... xn, d ]
        // drop last: [ x1, d, x2, d, ... xn ]
        auto intersperse_view = 
        view::transform([delim](auto inp)
        {
            return std::array<decltype(inp), 2>{{ std::move(inp), delim }};
        })
      | view::join // also called concat or flatten in functional languages
      | view::drop_last(1); // drop trailing delim

transform | join上面 的合成是对流的一种常见操作,该操作将每个输入转换为一个输出序列,并对结果序列进行展平。

[x] -> (x -> [y]) -> [y]

有些语言对此有单独的抽象,例如Elixir语言中的flat_map或LINQ中的SelectMany。

基于最小惊呀的原则,看来上述办法应该奏效。(如果你还没看过这篇演讲,那说明我推荐的力度还不够)。

但是,上面的代码与range-v3一起无法编译通过。出什么事了?结果发现问题在于view::join不喜欢subrange(子范围 - 返回的集合)是一个作为右值(rvalue)返回的容器这一事实。我想出了以下的技巧:(有时)用这些视图(view)的右值组成视图,所以让我们将容器返回值包装为一个视图!

  view::transform([delim](auto inp)
        {
            return view::generate_n([delim, inp, i = 0]() mutable
            {
                return (i++ == 0) ? inp : delim;
            }, 2);
        })

或者,概括地说,我们可以返回一个容器,例如向量,作为其他用例的视图:

   view::transform([](int x)
        {
            auto vec = ... ;
            return view::generate_n([i = 0, vec = std::move(vec)]() mutable
            {
                return std::move(vec[i++]);
            }, vec.size());
        })
      | view::join // now join composes with transform

这是不是很聪明的做法?也许是吧,但是必须想出一些巧妙的技巧来做一些基本的事情,这并不是一个好兆头。

事实证明,我不是第一个遇到此问题的人。range库的实现者们提出了他们自己的变通方法。正如Eric Niebler在此处指出的那样,我的解决方案是“非法的”,因为通过在视图中捕获向量不再满足O(1)复制复杂性的要求。

也就是说,如果我们看看在view::generate或view::generate_n后台发生的事,我们就会看到它们缓存了最后一个生成的值,因此让view :: generate成生std :: string或std :: vector, 或一种包含这些类型的类型,你就已经不满足库的要求了。

这个例子我们讲完了吗?差不多了。

接下来,我们讲讲最后的两行代码:

      | view::join
      | view::drop_last(1);

你可能会认为drop_last在内部会将n个元素的队列保留在循环缓冲区中,并在最后一个输入到达时简单地将其丢弃。

然而,range-v3视图可能不会缓冲元素,因此view::drop_last必须在输入上施加SizedRange或ForwardRange 约束,而view::join返回一个InputRange(即使它接收到一个ForwardRange作为输入)。

这不仅扼杀了组合,也扼杀了任何延迟计算的希望(你必须立刻将整个InputRange(希望是有限的)转储到std::vector,然后将其转换为一个ForwardRange)。

那么,我们将如何实现这一点呢?我们稍后再谈……

示例 2:

下面是一个使用rangeless库实现的示例(这是Knuth-vs-McIlroy挑战的一个稍作修改的版本,使其更加有趣)。

   namespace fn = rangeless::fn;
    using fn::operators::operator%;
    //
    // Top-5 most frequent words from stream chosen among the words of the same length.
    //
    auto my_isalnum = [](const int ch)
    {
        return std::isalnum(ch) || ch == '_';
    };
    fn::from( // (1)
        std::istreambuf_iterator<char>(std::cin.rdbuf()),
        std::istreambuf_iterator<char>{ /* end */ })
      % fn::transform([](const char ch) // (2)
        {
            return std::tolower(uint8_t(ch));
        })
      % fn::group_adjacent_by(my_isalnum) // (3)
        // (4) build word->count map
      % fn::foldl_d([&](std::map<std::string, size_t> out, const std::string& w)
        {
            if(my_isalnum(w.front())) {
                ++out[ w ];
            }
            return out; // NB: no copies of the map are made
                                   // because it is passed back by move.
        })
      % fn::group_all_by([](const auto& kv) // (5) kv is (word, count)
        {
            return kv.first.size(); // by word-size
        })
      % fn::transform( // (6)
            fn::take_top_n_by(5UL, fn::by::second{})) // by count
      % fn::concat() // (7) Note: concat is called _join_ in range-v3
      % fn::for_each([](const auto& kv)
        {
            std::cerr << kv.first << "\t" << kv.second << "\n";
        })
      ;

正如你所看到的,这段代码在风格上与ranges非常相似,但是其幕后工作方式完全不同(稍后我们将进行讨论)。

尝试使用range-v3重写此代码时,我们会遇到以下问题:

  • (3)处:这将不起作用,因为view::group_by需要一个ForwardRange或更强的约束。

  • (4)处:如何使用ranges进行可组合的左折叠(filter/map/reduce习惯用法的三大支柱之一)?ranges::accumulate是一个可能的候选对象,但它不是“pipeable”,而且也不符合移动语义(面向数字)。

  • (5)处:foldl_d返回一个满足ForwardRange要求的STD::MAP,但由于它是一个右值,因此不会与下游的group-by组合。Ranges中没有group_all_by,因此我们必须先将中间结果转储到左值(lvalue)中才能应用sort(排序)操作

  • (6和7)处:transform,concat:这与我们在“intersperse”示例中已经看到的问题相同,在那个示例中,range-v3无法展平右值(rvalue)容器序列。

示例3:Transform-in-parallel(并行转换)

下面的函数取自aln_filter.cpp示例。(顺便说一下,它展示了在适用的用例中数据流延时操作的有用性)。

lazy_transform_in_parallel的目的是执行与普通transform相同的工作,不同之处在于,每次对transform函数的调用都与不超过指定数量的同时异步任务并行执行。(与c ++ 17的并行化std::transform不同的是,我们希望它可以和延时的InputRange一起工作。)

static auto lazy_transform_in_parallel = [](auto fn,
                                           size_t max_queue_size = std::thread::hardware_concurrency())
{
    namespace fn = rangeless::fn;
    using fn::operators::operator%;
    assert(max_queue_size >= 1);
    return [max_queue_size, fn](auto inputs) // inputs can be an lazy InputRange
    {
        return std::move(inputs)
        //-------------------------------------------------------------------
        // Lazily yield std::async invocations of fn.
      % fn::transform([fn](auto inp)
        {
            return std::async(std::launch::async,
                [inp = std::move(inp), fn]() mutable // mutable because inp will be moved-from
                {
                    return fn(std::move(inp));
                });
        })
        //-------------------------------------------------------------------
        // Cap the incoming sequence of tasks with a seq of _max_queue_size_-1
        // dummy future<...>'s, such that all real tasks make it
        // from the other end of the sliding-window in the next stage.
      % fn::append(fn::seq([i = 1UL, max_queue_size]() mutable
        {
            using fn_out_t = decltype(fn(std::move(*inputs.begin())));
            return i++ < max_queue_size ? std::future<fn_out_t>() : fn::end_seq();
        }))
        //-------------------------------------------------------------------
        // Buffer executing async-tasks in a fixed-sized sliding window;
        // yield the result from the oldest (front) std::future.
      % fn::sliding_window(max_queue_size)
      % fn::transform([](auto view) // sliding_window yields a view into its queue
        {
            return view.begin()->get();
        });
    };
};

有人会认为这包含了所有可以用ranges实现的部分,但事实并非如此。明显的问题是view::sliding需要一个ForwardRange。即使我们决定实现sliding的一个“非法”的缓存版本,仍有更多问题在代码中不可见,但会在运行时显现:

在range-v3中,view::transform的正确用法取决于以下假设:

  • 重新计算很便宜(这一点对在上例中的第一个transform中并不适用,因为它逐个接受和传递input输入,并启动一个异步任务)。

  • 可以在同一个input上多次调用它(这对于第二个transform不起作用,因为对std::future::get的调用使它处于无效状态,因此只能被调用一次)。

如果transform函数类似于“加一”或“对一个整数取平方”,那么上面的这些假设可能很正确,但是如果transform函数需要查询数据库或生成一个进程以运行一个繁重的任务,那么这些假设会有点自以为是了。

这个问题和乔纳森(Jonathan)在“增加一个智能迭代器的可怕问题”中描述的问题如出一辙。

这种行为不是一个bug,显然是设计使然–这是我们无法很好地使用range-v3的另一个原因。

在rangeless中,fn::transform既不会对同一input上多次调用transform函数,也不会缓存结果。

注:rangeless库中提供了transform_in_parallel。我们可以比较使用rangless(Ctrl+F pigz)和使用RaftLib对并行gzip压缩器的实现的不同。

上面这一切的结论是什么呢?

Ranges的复杂性

我们需要一种合理一致的语言,可以被“普通程序员”使用,他们的主要关注点是准时交付优秀的应用程序。

Ranges简化了基本用例的代码,比如说,你可以编写action::sort(vec)来代替std::sort(vec.begin(), vec.end())。然而,除了最基本的用法以外,它会导致代码的复杂度呈指数级增长。

举个例子,如何实现上述的intersperse适配器?

让我们先看看Haskell语言写的的示例,看看我们心目中的“简单”应该是什么样子的。

intersperse ::  a -> [ a ] -> [ a ]
intersperse     _ [ ] = [   ]
intersperse     _ [ x ] = [ x ]
intersperse delim    (x:xs) = x : delim : intersperse delim xs

即使你一生中从未见过Haskell代码,你也可能知道上面的代码是如何工作的。

下面是使用rangeless来完成它的三种不同的方法。就像Haskell的签名一样,my_intersperse接受delim作为参数并返回一个一元可调用函数,该函数可以接受Iterable参数并返回一个产生元素的序列 - interspersing delim。

作为一个generator函数使用:

auto my_intersperse = [](auto delim)
{
    return [delim = std::move(delim)](auto inputs)
    {
        return fn::seq([  delim,
                         inputs = std::move(inputs),
                             it = inputs.end(),
                        started = false,
                           flag = false]() mutable
        {
            if(!started) {
                started = true;
                it = inputs.begin();
            }
            return it == inputs.end() ? fn::end_seq()
                 :     (flag = !flag) ? std::move(*it++)
                 :                      delim;
        });
    };
};

通过使用rangeless中的fn::adapt这个用来实现自定义适配器的工具:

auto my_intersperse = [](auto delim)
{
    return fn::adapt([delim, flag = false](auto gen) mutable
    {
        return           !gen ? fn::end_seq()
             : (flag = !flag) ? gen()
             :                  delim;
    });
};

作为现有功能的组成部分(我们尝试用range-views实现但未能实现的功能):

auto my_intersperse = [](auto delim)
{
    return [delim = std::move(delim)](auto inputs)
    {
        return std::move(inputs)
      % fn::transform([delim](auto inp)
        {
            return std::array<decltype(inp), 2>{{ std::move(inp), delim }};
        })
      % fn::concat()
      % fn::drop_last(); // drop trailing delim
    };
};

我们也可以将intersperse作为一个协程(coroutine)来实现,而无需借助于rangeless::fn。

template<typename Xs, typename Delim>
static unique_generator<Delim> intersperse_gen(Xs xs, Delim delim)
{
    bool started = false;
    for (auto&& x : xs) {
        if(!started) {
            started = true;
        } else {
            co_yield delim;
        }
        co_yield std::move(x);
    }
};

auto my_intersperse = [](auto delim)
{
    return [delim](auto inps)
    {
        return intersperse_gen(std::move(inps), delim);
    };
};

上述所有的实现在代码复杂度方面都差不多。现在让我们看看range-v3实现的样子:intersperse.hpp。就我个人而言,这看起来非常复杂。如果你对它的复杂度印象还不够深刻的话,考虑一下作为一个协程来实现笛卡尔乘积的情形:

template<typename Xs, typename Ys>
auto cartesian_product_gen(Xs xs, Ys ys) 
  -> unique_generator<std::pair<typename Xs::value_type,
                                typename Ys::value_type>>
{
    for(const auto& x : xs)
        for(const auto& y : ys)
            co_yield std::make_pair(x, y);
}

我们把以上实现与range-v3的实现作一番比较。

用range-v3编写视图应该很容易,但是,正如示例所示,在后现代C++中被认为“容易”的标准已经提高到了普通人无法企及的高度。

应用程序代码中涉及range的情况并不简单。

如果我们比较一下日历格式化应用程序的Haskell,Rust,rangeless和range-v3的实现。我不知道你的情况如何,但最后一个实现(使用range-v3)并没有激发我去理解或编写这样的代码的热情。

注意,在range-v3的示例中,,开发者通过一个std::vector字段打破了在interleave_view本身的视图复制复杂度要求。

Range views的抽象泄漏

如果你回到上面基于range-v3库的intersperse和日历应用程序,并对其进行更详细的研究,你就会看到在视图的实现中,我们最终都是直接处理迭代器,实际上需要做非常多的事情。

除了在一个range上调用sort之外或某些类似的操作外,ranges并不能避免让你直接处理迭代器。相反,它是“以额外的步骤处理迭代器”。

编译时间开销

Range-v3库因其编译时间而臭名昭著。在我的机器上,上述日历示例的编译时间超过20秒,而相应的rangeless实现的编译可以2.4秒内完成,其中1.8秒是为了include<gregorian.hpp>,这几乎相差了整整一个数量级!

编译时间已经变成了C++开发中每天面临的一个大问题,而range让它变得更糟!以我个人的情况为例,仅仅编译时间这一项就排除了在生产代码中使用range的任何可能性。

Rangeless库

对于rangeless库,我没有想要浪费时间做无用功,而是遵循函数式编程语言中的streaming库(如Haskell的Data.List,Elixir的Stream,F#的 Seq,以及和LINQ)的设计。

与range-v3库不同,rangeless库没有ranges、views或actions,只是通过一个一元可调用函数链将值从一个函数传递到下一个函数,其中的一个值是容器或序列(输入范围,有界或无界)。

有一点语法上的甜头:

operator % (Arg arg, Fn fn) -> decltype(fn(std::forward<Arg>(arg)))
auto x1 = std::move(arg) % f % g % h; // same as auto x1 = h(g(f(std::move(arg))));

这相当于Haskell语言中的中缀运算符“&” 或F#语言中的“|>”运算符>in f。它允许我们以与数据流方向基本上一致的方式构造代码。这种方式对于一个单行的函数并没有什么影响,但是对于那些就地定义的多行lambda函数,就会很有帮助。

你可能想知道,为什么这里明确地使用“operator%”,而不用“>>”或者“?”操作符呢?

C++的可重载二进制运算符的列表并不长,前者往往由于流和管道运算符而大量地重载,通常用在有“smart”-flag 或“chaining”(也称为point-free composition)的地方,和在range中一样。

我考虑过使用可重载的运算符“operator->*”,但最终还是决定使用运算符“operator%”,因为考虑到上下文,它不太可能与整数取模运算混淆,而且还具有可以用于更改LHS(运算符左边的操作数)状态的“%=”对应项,例如:

vec %= fn::where(.../*satisfies-condition-lambda*/);

这里的输入要么是一个序列,要么是一个容器,输出也是一样。例如,fn::sort需要所有元素来完成它的工作,所以它会将整个输入序列转储到std::vector中,对其进行排序,然后返回std::vector。

另一方面,一个fn::transform将按值获取的输入封装为一个序列,它将惰性地生成转换后的输入元素。从概念上讲,这类似于一个带有eager sort和lazy sed的UNIX管道。

与range-v3中不同的是,input-ranges(序列)在rangeless中是一等公民。我们在range-v3中看到的由于实参(argument)和形参(parameter)之间概念不匹配而导致的问题是不存在的(例如,在期望有ForwardRange的地方,但却收到了InputRange这样的问题)。只要值类型兼容,一切都是可组合的。

结束语

我尝试过用ranges来编写表达性的代码。我是唯一那个经常“错误地使用它”的人吗?

当我得知委员会在C++20标准中接纳了range时,我相当惊讶,大多数C++专家对此都很兴奋。看起来好象上面提到的这些问题(有局限的可用性、代码复杂性、漏洞百出的抽象和完全不合理的编译时间)对委员会成员没有任何影响一样。

我觉得这一点严重背离了率先开发这门语言的C++专家和那些想用更简单的方法来做复杂事情的普通程序员的初衷。在我看来,似乎所有人都对C++之父(Bjarne Stroustrup)在Remember the Vasa的发出的呼吁充耳不闻(当然,这是我个人的主观看法)。

原文:https://www.fluentcpp.com/2019/09/13/the-surprising-limitations-of-c-ranges-beyond-trivial-use-cases/

本文为 CSDN 翻译,转载请注明来源出处。

【END】

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章