文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

迷惑了,Go len() 是怎么计算出来的?

2024-12-03 00:23

关注

本文转载自微信公众号「脑子进煎鱼了」,作者陈煎鱼。转载本文请联系脑子进煎鱼了公众号。

大家好,我是煎鱼。

最近看到了一个很有意思的话题,我们平时常常会用 Go 的内置函数 len 去获取各种 map、slice 的长度,那他是怎么实现的呢?

正当我想去看看 len 的具体实现时,一展身手,却发现竟然是个空方法:

  1. func len(v Type) int 

看注解也没有 link 到其他 runtime 函数,那么 len 函数是如何被调用的呢?

先前也做了一些笔记,在此分享给大家,共同进步。

谜底

今天就由煎鱼带大家一同解开这个谜底。既然是谜底,那就一开始就揭开。

其实 Go 语言中并没有 len 函数的具体实现代码,他其实是 Go 编译器的 "魔法" ,不是实际的函数调用。

接下来将展开这部分,我们可以更深入地了解 Go 编译器的内部工作原理。

编译器

在 Go 编译器编译时会解析命令行参数中指定的标志和 Go 源文件,对解析后的 Go 包进行类型检查,将函数编译为机器代码。代码,最后将编译后的包定义写到磁盘上。

内部定义基本类型、内置函数和操作函数的阶段是在 types/universe.go 当中。同时会进行内置函数和具体的操作符匹配,可以明确知道内置函数 len 对应的是 OLEN:

  1. var builtinFuncs = [...]struct { 
  2.  name string 
  3.  op   Op 
  4. }{ 
  5.  {"append", OAPPEND}, 
  6.  {"cap", OCAP}, 
  7.  {"close", OCLOSE}, 
  8.  {"complex", OCOMPLEX}, 
  9.  {"copy", OCOPY}, 
  10.  {"delete", ODELETE}, 
  11.  {"imag", OIMAG}, 
  12.  {"len", OLEN}, 
  13.  ... 

在编译时,上分为五个阶段进行类型检查:

如果最后一个类型检查阶段遇到 len 函数,就会转换为 UnaryExpr 类型,一个 UnaryExpr 节点代表一个单数表达式,也最终就是不会成为函数调用:

  1. func typecheck1(n ir.Node, top int) ir.Node { 
  2.  if n, ok := n.(*ir.Name); ok { 
  3.   typecheckdef(n) 
  4.  } 
  5.  
  6.  switch n.Op() { 
  7.  ... 
  8.  case ir.OCAP, ir.OLEN: 
  9.   n := n.(*ir.UnaryExpr) 
  10.   return tcLenCap(n) 
  11.  } 

在调用 *ir.UnaryExpr 转换完毕后,会调用 tcLenCap,也就是 typecheck,使用 okforlen 数组来验证参数的合法性或发出相关错误信息:

  1. func tcLenCap(n *ir.UnaryExpr) ir.Node { 
  2.  n.X = Expr(n.X) 
  3.  n.X = DefaultLit(n.X, nil) 
  4.  n.X = implicitstar(n.X) 
  5.  ... 
  6.  var ok bool 
  7.  if n.Op() == ir.OLEN { 
  8.   ok = okforlen[t.Kind()] 
  9.  } else { 
  10.   ok = okforcap[t.Kind()] 
  11.  } 
  12.    
  13.  ... 
  14.  n.SetType(types.Types[types.TINT]) 
  15.  return n 

经历过上面的步骤后在对所有内容进行类型检查后,所有函数都将排队等待编译:

  1. base.Timer.Start("be""compilefuncs"
  2. fcount := int64(0) 
  3. for i := 0; i < len(typecheck.Target.Decls); i++ { 
  4.  if fn, ok := typecheck.Target.Decls[i].(*ir.Func); ok { 
  5.   enqueueFunc(fn) 
  6.   fcount++ 
  7.  } 
  8. base.Timer.AddEvent(fcount, "funcs"
  9.  
  10. compileFunctions() 

在经过在 buildssa 和 genssa 之后,再深入几层,就会将 AST 树中的 len 表达式转换为 SSA。接着我们就可以看到 Go 语言中的每种类型的长度是怎么获取的。

这块的处理对应 internal/ssagen/ssa.go 的 expr 方法,如下:

  1. case ir.OLEN, ir.OCAP: 
  2.  n := n.(*ir.UnaryExpr) 
  3.  switch { 
  4.  case n.X.Type().IsSlice(): 
  5.   op := ssa.OpSliceLen 
  6.   if n.Op() == ir.OCAP { 
  7.    op = ssa.OpSliceCap 
  8.   } 
  9.   return s.newValue1(op, types.Types[types.TINT], s.expr(n.X)) 
  10.  case n.X.Type().IsString(): // string; not reachable for OCAP 
  11.   return s.newValue1(ssa.OpStringLen, types.Types[types.TINT], s.expr(n.X)) 
  12.  case n.X.Type().IsMap(), n.X.Type().IsChan(): 
  13.   return s.referenceTypeBuiltin(n, s.expr(n.X)) 
  14.  default: // array 
  15.   return s.constInt(types.Types[types.TINT], n.X.Type().NumElem()) 
  16.  } 

若是数组(array)类型,则会调用 NumElem 方法来获取长度值:

  1. type Array struct { 
  2.  Elem  *Type  
  3.  Bound int64  
  4.  
  5. func (t *Type) NumElem() int64 { 
  6.  t.wantEtype(TARRAY) 
  7.  return t.Extra.(*Array).Bound 

若是字典(map)类型或通道(channel),将会调用 referenceTypeBuiltin 方法:

  1. func (s *state) referenceTypeBuiltin(n *ir.UnaryExpr, x *ssa.Value) *ssa.Value { 
  2.  lenType := n.Type() 
  3.  nilValue := s.constNil(types.Types[types.TUINTPTR]) 
  4.  cmp := s.newValue2(ssa.OpEqPtr, types.Types[types.TBOOL], x, nilValue) 
  5.  b := s.endBlock() 
  6.  b.Kind = ssa.BlockIf 
  7.  b.SetControl(cmp) 
  8.  b.Likely = ssa.BranchUnlikely 
  9.  
  10.  bThen := s.f.NewBlock(ssa.BlockPlain) 
  11.  bElse := s.f.NewBlock(ssa.BlockPlain) 
  12.  bAfter := s.f.NewBlock(ssa.BlockPlain) 
  13.  ... 
  14.  switch n.Op() { 
  15.  case ir.OLEN: 
  16.   s.vars[n] = s.load(lenType, x) 
  17.  ... 
  18.  return s.variable(n, lenType) 

该函数的作用是是获取 map 或chan 的内存地址,并以零偏移量引用其结构布局,就像 unsafe.Pointer(uintptr(unsafe.Pointer(s)) 一样,返回第一个字面字段的值。

那为什么要获取结构体的第一个字段的值呢,应该是和 map 和 chan 的基础数据结构有关:

  1. type hmap struct { 
  2.  count     int  
  3.   ... 
  4.  
  5. type hchan struct { 
  6.  qcount   uint     
  7.  ... 

是因为 map 和 chan 的基础数据结构的第一个字段就表示长度,自然也就通过计算偏移值来获取了。

其他的数据类型,大家可以继续深入代码,再细看就好了。主要还是枚举多同类的数据类型,接着调用相应的方法。

总结

每次我们看到内置函数时,总会下意识的以为是在 runtime 内实现的。看不到 runtime 内的实现方法,又会以为是通过注解 link 的方式来解决的。

 

但需要注意,其实还有像 len 内置函数这种直接编译器转换的,这也是一种不错的优化方式。

 

来源:脑子进煎鱼了内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯