V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Biwood
V2EX  ›  程序员

Linus Torvalds 在 TED 演讲上所说的有品味的代码

  •  2
     
  •   Biwood ·
    oodzchen · 2022-05-19 22:02:14 +08:00 · 11286 次点击
    这是一个创建于 679 天前的主题,其中的信息可能已经有所发展或是发生改变。

    需求是从单向链表中删除一个指定节点。

    教科书上的(普通的)写法:

    void remove_cs101(list *l, list_item *target)
    {
            list_item *cur = l->head, *prev = NULL;
            while (cur != target) {
                    prev = cur;
                    cur = cur->next;
            }
            if (prev)
                    prev->next = cur->next;
            else
                    l->head = cur->next;
    }
    

    优雅的(有品味的)写法:

    void remove_elegant(list *l, list_item *target)
    {
            list_item **p = &l->head;
            while (*p != target)
                    p = &(*p)->next;
            *p = target->next;
    }
    

    目测充分利用的指针的特性,代码量少了不少。

    代码仓库和详细解释在这里: https://github.com/mkirchner/linked-list-good-taste/blob/main/README.md

    120 条回复    2022-05-25 01:50:41 +08:00
    1  2  
    pastor
        101
    pastor  
       2022-05-23 14:50:04 +08:00
    我上一楼代码里那个 cnt 和 cnt++ 只是为了调试用的,粘贴的时候忘了去掉
    cnbatch
        102
    cnbatch  
       2022-05-23 15:04:22 +08:00
    @pastor 其他人就不知道了。

    就说我自己吧,上面那么多回复我还没有全都看完,我个人关注点全在 FreeBSD 和 Linux 对 container_of 的态度区别。
    ColorfulBoar
        103
    ColorfulBoar  
       2022-05-23 15:05:10 +08:00
    @pastor 你往上翻一下#88 ,我在那里解释了为什么我管它叫 list_head (以及最大的问题并不是它叫什么,而是 target 因为 non-owning 的性质不应该用同样的类型)和为什么后来我觉得这个强制转换不是 UB 。
    首先最快速验证正确性的话……你可以丢进 compiler explorer 里面看汇编。gcc 整蛊就不说了(在那个时候我这个版本生成更短的汇编,而主楼那个写法不知道为什么看起来循环被手动展开了一层),在 msvc 和 clang 下面都会生成跟主楼的写法一模一样的汇编。当然,编译语言不是实验科学,生成汇编一样也不一定语义上正确,所以还需要再解释一下这里在干什么:你不要想着谁是几级指针这种事,这里做的是把指向一个 struct 第一个元素的指针转化成了指向这个 struct 本身的指针,这个是 C/C++标准明确允许的指针转换,所以我才刻意把 next 放在 value 前面,并不是运气好,所有符合标准的编译器都会保证它是对的。在转换后我对那个指针的唯一用法是使用它所指的 struct 的第一个元素,而不是解引用之后对整个 object 做什么,这意味着我始终在用同样的类型访问同样的一块内存,不会产生 strict aliasing 的问题。
    你后面打算把它写成 auto p = head;肯定是不对的,p 大概代表比原来链表的头更前的一个节点,你这么写是删不掉第一个节点的。你可以再跟#25 那个版本比较一下,主体是差不多的,我只不过是没有给那边的「头节点」分配不必要的内存而已。
    delpo
        104
    delpo  
       2022-05-23 15:07:41 +08:00
    之前看过 linus 的这段代码,第二种写法的好处是使用二维指针**p 可以保存当前节点的前一个节点的指针信息,而这个正好是删除某个节点的必要信息.
    我记得 linus 说第二种的好处是不用特地处理头节点后第一个节点为待删除节点的情况,抽象性比较高
    pastor
        105
    pastor  
       2022-05-23 15:22:37 +08:00
    @ColorfulBoar #103
    指向 list 的第一个元素也应该是取 list_node 的地址,而不是取 list_node*的地址,你应该是把取数组地址、取数组第一个元素的地址搞混了吧,由于数组的内存布局和 c 类型的原因,数组变量、取数组地址的指针、0 元素地址都是相同的值,但结构体是不一样的

    你看下我前面贴的代码的注释的部分,你这个写法在 list_node 的 next 不是第一个字段的布局情况下,应该是不行的,或者你自己改改 list_node 字段布局跑下就知道了

    关于 list_head 的命名,一般的 list 是单独一个 struct{ list_node/list_item * head, tail }之类的,估计你可能是没怎么自己真动手写过所以想直接用 head 来表示整个 list 所以才会这样命名,这样不实用的
    pastor
        106
    pastor  
       2022-05-23 15:25:09 +08:00
    @ColorfulBoar 所以其实我对 c++11 之前的引用的理解好像没啥问题,你两个楼层里说我不懂的时候我还以为是 c++11 以后的原因导致我真的错了,但其实你应该还没有看过或者真正看懂我最初列的问题里的二级指针的问题。内存布局导致取 head 地址跟 next 值重合的巧合可能掩盖了你对指针的误解
    pastor
        107
    pastor  
       2022-05-23 15:27:01 +08:00
    @cnbatch 恩恩我知道你没怎么看他代码,我只是戏谑一句。。我是想表达那几位给了 ColorfulBoar 代码点赞的有点奇怪。。
    pastor
        108
    pastor  
       2022-05-23 15:36:33 +08:00
    习惯了指针思维,你脑子里是直接在跟内存打交道,那感觉就是:一切尽在我掌控

    c++本身也是提供了底层能力,但却又想用引用之类的提供给你一些不用陷入内存细节的便利,或许让你轻松了些,但反倒某种程度上悄悄阉割了使用者对内存、对系统的思考能力、降低了理解水平,真要说区别,相比于 c 可能 c++更适合逻辑程序员吧,只是在自欺欺人地以为自己的用法更好了。但看下语言排行吧,c 地位稳定(虽然有 linux 内核及其相关领域比如安卓之类的离不开 c 的原因),cpp 被其他语言蚕食。。
    cnbatch
        109
    cnbatch  
       2022-05-23 15:42:13 +08:00
    @pastor 主要是楼层盖到那么多以后,想要认真看完每一层楼、每一段代码实在太费神了,这种情况下扫一眼后觉得思路顺眼就点赞,其实不算奇怪。毕竟对于这种容易造成吵架的主题帖,越到后面就越是磨掉看贴人的耐心。
    让我意外的是,第一页中后段语言律师洋洋洒洒连续写了 4 贴长文字,实属罕见。
    pastor
        110
    pastor  
       2022-05-23 15:59:29 +08:00
    @cnbatch
    恩,好多楼层我也没看,但是他贴代码那个图其实挺漂亮的所以我就多看了一眼
    幻的几层楼我也没细看,因为十几年前就看过太多幻和大伙对于律法与哲学的无意义辩论了。十几年过去了,除了对新的 c++标准也熟悉了,幻几乎没什么变化:joy:
    cnbatch
        111
    cnbatch  
       2022-05-23 16:03:48 +08:00
    顺便说说我用 cpp 的原因。非常简单,跟内存无关,单纯就是看中“实时”的 RAII 和模板(仅限简单的通用模板,黑科技骚操作我也写不来)。一般来说用 C++的依然需要跟 C 打交道,就算用到 C++23 照样如此,如果经常需要跟底层打交道(前提是“经常”),那么这方面的理解能力也不会差的。

    为什么要给 RAII 加上“实时”两个字呢,因为十年前我被 C# 的垃圾回收坑过。C# 也有 RAII ,也有析构函数,但由于垃圾回收的存在,作用域结束后并不保证立即执行析构操作。而 C++ 保证立即执行。

    C# 虽然真的很顺手,但析构函数这一块我是被坑怕了。不知道现在最新的 C# 能不能保证立即执行,只是我已经不敢再用 C# 的析构了。至于为什么不完全转向 rust ,那是因为我从 C# 跑到 C++ 的时候,rust 才发布没多久。
    pastor
        112
    pastor  
       2022-05-23 16:14:29 +08:00
    @ColorfulBoar #103
    "这里做的是把指向一个 struct 第一个元素的指针转化成了指向这个 struct 本身的指针"
    如果初衷就是这样,那功能上没问题,我前面回复的数组指针搞混是我之前没看自己你这块的解释回复唐突了
    但是从易于理解的角度讲,这并比 linus 二级指针版本更友好吧兄弟。。
    pastor
        113
    pastor  
       2022-05-23 16:17:29 +08:00
    #112 cpp 最被 cer 诟病的原因之一就是 cpp 有太多背后的行为,比如构造析构,比如并不写在 main 的显示流程里、而是放在小角落那种对象偷偷靠构造函数初始化一些东西,看上去奇技淫巧,实际上都是茴字的 N 种写法,除了让人摸不着头脑、浪费更多时间经历,对工程并无好处
    FrankHB
        114
    FrankHB  
       2022-05-24 01:18:10 +08:00
    @chbatch 不污染内核树不等于要 vendored ,你这还不是官方源里了嘛……至少原则上不保证不重复的大坨通用代码就不适合原样放 in-tree 的具体业务模块里。
    而且看这文件里就远不只 container_of ,逻辑上不适合放这的代码数量就多得离谱。既然都__FBSDID("$FreeBSD$")了,显然不是照搬的;更何况文件名看就是给 FreeBSD 特供的,还这么一整套,看着就像复制粘贴以后懒得维护一样,味儿太冲了。

    Clang 也支持 GNU 扩展还当卖点。不过({})这种一旦引入就难以排除,大约因为比 C++ lambda 鸡肋,还有 Clang block 之类的竞品,所以难以标准化,有洁癖也不奇怪。

    “转换成左值引用”是很传统的用法,虽然能转换为左值引用的操作数通常就是个左值而不再怎么强调是左值引用。
    真“转换”,也就定义个 operator T&。
    单个&在 C++11 后能用 ref-qualifier 和 lambda-capture 里,之前没这语法。之前有的倒不需要关心变化。

    (铜币不够,剩下的隔天再说。)
    cnbatch
        115
    cnbatch  
       2022-05-24 06:27:00 +08:00
    @FrankHB container_of 对于 FreeBSD 来说还真的不是“通用代码”,那当然是只能丢在“具体业务模块里面”。

    FreeBSD 的这个 drm 文件,实际上它来自于 freedesktop.org ,显然这个文件是移植过来给 FreeBSD 做适配。
    https://www.freebsd.org/cgi/man.cgi?query=drm&sektion=7&manpath=freebsd-release-ports
    连他们自己的帮助页面都说得很清楚,遇到 bug 就找 freedesktop ,不关 FreeBSD 团队的事。

    源码全文原封不动照搬肯定不可能,毕竟不少 API 都是各家特有的,那肯定要根据目标系统去改。然而给 drm 做移植的那些人当然是能省事就省事,来自 Linux 的代码和习惯看得出能搬就搬,显然他们很想用 container_of 。但是 FreeBSD 自己不用 container_of ,更别说公共头文件了。所以这样只能单独提供在 drm 项目文件里面。其他类似的“Linux 提供了但 FreeBSD”的 #define 同理。Linux 虽然很流行,但也不能强行要求其他开源系统全盘提供 Linux 的“公共文件”呀。

    如果因为这种文件存在于官方代码树里面就认为是 FreeBSD 自己的人来写,那还是不要觉得理所当然,“外部团队专门给 FreeBSD 移植或定制”的代码可不少,他们写完后都是合并到 FreeBSD 官方代码树里面的。

    至于里面合并进来的代码各种版面问题,FreeBSD 团队不可能具备 Linus 那样的脾气苛责贡献者。能有第三方驱动合并进来就谢天谢地了,哪有脾气苛责驱动贡献者?过于苛责的后果可以看 OpenBSD ,驱动支持比 FreeBSD 更少。
    (站在外部贡献者立场说“大白话”就是:我能给你写驱动都算你走运了,你要是把我惹烦的话,以后我就不理你)


    回到 container_of 本身,就以“肥宅快乐水”来打比方。

    Linux 就好比:
    大家几乎都喜欢喝肥宅快乐水,于是就主动在公共区域放置了汽水柜,想要的就去拿。极少数人喜欢不同口味或品牌的,就在自己桌子上单独放其他种类的。

    FreeBSD 就好比:
    大家都不爱喝肥宅快乐水,所以公共区域就不会放置汽水柜。有个别外包的驻场团队喜欢喝,那就在只放在他们自己的桌子上,没必要放在公共区域。至于因此造成部分团队桌面过于杂乱,那就是这些团队自己的事情了。





    至于“左值引用”……我就是因为知道它已经很传统了所以特意表明“没谁会特意这样提”,如果你真要强调的话……我觉得其实你是想跟前面的那位用户讲,要不单独隔个楼然后直接 at 一下给对方?

    我可不想一边重新解释汉字语言表达、一边处理编程语言历史时间线。如果你很还想提的话,欢迎另起一层单独讲,没必要 at 我。
    FrankHB
        116
    FrankHB  
       2022-05-24 08:49:56 +08:00   ❤️ 1
    cnbatch
        117
    cnbatch  
       2022-05-24 17:51:46 +08:00
    @FrankHB
    原因很简单,container_of 一开始就靠 GCC 的私有扩展,并且长期以来都依赖于 GCC 私有扩展,而 FreeBSD 又有 GPLv3/GCC 洁癖,这种情况下 container_of 再流行,他们也不会愿意全局地加进去的。除非 container_of 能够转正变成标准的一部分,那他们就会迅速采用。

    相反的案例也有,NetBSD 就没有 GPLv3/GCC 洁癖,核心代码树里面大量使用 container_of 。


    “更应该自己做”
    不得不说,这有点站着说话不腰疼的味道。
    FreeBSD 团队当然想自己做,问题是论人力规模、资金支持,他们都没有 Linux 那么丰富。须知道,正是因为人少钱少,FreeBSD 连 WiFi 5 (802.11ac)的支持都不完善,直到去年才请来了专人(并且只有 1 人)完善 WiFi 5 的支持。WiFi 6 就更不用说了。

    就这种窘况,真敢“多拆个文件吧”?先不管会不会惹毛移植 drm 的那群人,整理文件也是需要额外的时间精力,刚刚说了,人手本来就不多。
    如果站在 FreeBSD 团队的角度来看,以大白话来说那就是:反正是别人给的,烂就烂吧。

    对于来自 freedesktop 的外来物,我觉得这种处理方式既然无可厚非,也无可奈何。反正 freedesktop 已经不是第一次被人说烂 /摆烂的了,早期 wayland 的“烂”连 V2EX 都有人吐槽( https://v2ex.com/t/430734 ),更不用说 wayland 到现在依然还没完成 FreeBSD 的移植。
    这种大背景下跟他们急?得到的只会是“让自己距离高血压又进了一步”。

    至于这个 drm 为什么会出现在 man page ,这又是一个历史遗留,比如 Arch Linux 还保留了这个痕迹:
    https://man.archlinux.org/man/drm.7.en

    为什么不单独拆出来放到在 Freebsd 自己的 wiki 里面呢?那就又回到刚才说过的——人少。


    FreeBSD 在代码管理、用户需求管理方面的各种“妥协”,真追究起来都可以发现是指向同一个源头:钱少。


    至对于我为什么从 C# 转向 C++ 那个表述,不好意思,我所讲的“实时”并不是指 real-time operating system 的那个实时。也许我当时用“接着就立即”可以让你不会误解吧。
    cnbatch
        118
    cnbatch  
       2022-05-24 17:54:02 +08:00
    @cnbatch 澄清:
    「这种大背景下跟他们急?得到的只会是“让自己距离高血压又进了一步”」
    此处的“他们”是指代“移植 drm 的那群人”
    FrankHB
        119
    FrankHB  
       2022-05-25 00:27:37 +08:00
    @cnbatch 破案了。
    TL;DR:
    我一开始没注意到就有 cdefs.h 里本来就有__containerof ,就是 drm2 这代码没有用。
    你要是有看到了,早提一下,就不会那么多问题了。

    详细讨论更新在上面的 gist 里。
    cnbatch
        120
    cnbatch  
       2022-05-25 01:50:41 +08:00
    @FrankHB “说人力不够我懂,不过这不就是承认了没充分 review 过而没法解决问题嘛”

    对呀,这不正正印证了我说的“就这种窘况”。哪有什么承认不承认呢,这个窘况是活生生的现实,都不需要特意去承认或者否认。对于来自外面的代码,尤其是来自于又长又臭 bug 又多的 freedesktop ,换成是我,我也没那么多动力去好好地 review ,能用就行,多一事不如少一事。说实话,对于各 BSD 基金会而言,基本上都处于有求于人(大白话:看别人脸色)的地位,就连代码管理也不例外。多年前 FreeBSD 、OpenBSD 曾经分别喊穷求救,我也多少有点理解为什么他们对外来代码照单全收。责怪也没用,正经做法是帮他们解决资金问题(这难度……不是一般人能做到)

    不过也好,这个提醒让我也看到了 __containerof 挺不错。
    1  2  
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5190 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 38ms · UTC 01:21 · PVG 09:21 · LAX 18:21 · JFK 21:21
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.