此网站为连连棋牌演示网站
当前位置:首页 > C++ > 正文

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

10-11 C++

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  这里的输入要么是一个序列,要么是一个容器,输出也是一样。例如,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的发出的呼吁充耳不闻(当然,这是我个人的主观看法)。

版权保护: 本文由 首页 原创,转载请保留链接: http://www.wsxzr.com/News/231.html

博客主人bfyysw
男,文化程度不高性格有点犯二,已经20来岁至今未婚,闲着没事喜欢研究各种代码,资深技术宅。
  • 文章总数
  • 43823访问次数
  • 建站天数
  • 标签