Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

每日一问-map #332

Open
woofyzhao opened this issue Apr 6, 2019 · 3 comments

Comments

@woofyzhao
Copy link

commented Apr 6, 2019

考虑一个value为struct的map比如

type User struct {
  id int
  age int
}
var m map[string]User

考虑以下一些操作

m = make(map[string]User)
// insert
m["woofy"] = User {
    id: 1001,
    age: 28
}
// addressing:  compile error
foo(&m["woofy"])
// modify: compile error
m["woofy"].id = 10001
m["woofy"].age++

为啥取地址和修改内容这类看起来还算"正常"的操作会编译报错?

一个常见的解释是,go的map数据是动态扩容和可迁移的,内存地址会过期,所以不能取地址,即value不是addressable的,因而不能单独更新结构体字段,一般用结构体指针作为value比如改用 map[string]*User, 上述那样赋值就没问题了.

那么问题来了

  1. 会临时搬数据的情况不是map特有, slice也是自动扩容,比如
    s := []int {...} 
    _ = append(s, ...)
   s[i]++

假设append发生了underlying array的重新分配,但此后ss[i]++之类的操作依然是有效的, 为什么不用特别注意呢.

  1. 只说地址可能会失效,也许能够解释为什么不能缓存地址操作(在语言层防止出现无效地址),但是仍然不太好解释为什么 m["woofy"].age++ 这样的操作非法. 因为从语义上来说, 执行到这句的时候m["woofy"]一定是存在、完整且无歧义的,map应当是采用逐个value均摊搬迁的策略来进行扩容,当前不会有其他(非业务)线程在操作map,也不会出现只搬了结构体一半字段的情况. 那么为什么当下不能对这个m["woofy"]实体做修改呢?

为什么说value这个过程中一定是存在完整且无歧义的呢,举例来说,假设map按如下常见方式来处理扩容:

  1. map的原本的m1存储不太够了,开一个更大的空间m2
  2. 对后续每次插入key操作:
    a) 如果m1中key/value不存在,则写到m2,同时如果m1不空,从m1中任取一个key/value迁移到m2
    b) 如果m1中存在,从m1中删除,再按a)处理
  3. 对后续每次删除key操作,从m2和m1中删除,同时如果m1不空,从m1中任取一个key/value迁移到m2
  4. 对后续每次查询key操作,从m2找,找不到再从m1找,同时如果m1不空,从m1中任取一个key/value迁移到m2

当m1为空时,完成动态扩容. � m1地址回收,因而之前在m1中的value会全部失效,故编译器禁止取地址.

但是同时可以看到,不论什么状态下,map中的每个存在的value都是完整且无歧义,因而理论上编译器可以允许类似m["woofy"].age++的操作,你说对不对呢?

@woofyzhao

This comment has been minimized.

Copy link
Author

commented Apr 7, 2019

个人思考:

go的map实现其实相对算比较简单,推荐先看下map作者的介绍视频https://www.youtube.com/watch?v=Tl7mi9QmLns&t=3s

视频里面也提到了取地址的原因,以及map的动态扩容过程,和上面的推测基本吻合。但视频并没有直接说m["woofy"].age++这种操作非法的原因,依旧需要我们自己进一步思考。

首先,业务代码不能取地址并不是说map操作过程中都没有发生取址操作,实际上无论什么value类型,runtime都是通过返回value的地址来进行的,比如查找:

//v = m[k] 被编译为如下runtime过程:

pk := unsafe.Pointer(&k)
pv := runtime.lookup(typeOf(m), m, pk)
v = *(*V)pv

package runtime
func lookup(t *mapType, m *mapHeader, k unsafe.Pointer) unsafe.Pointer

注意到lookup并不直接返回value,而是返回value指针,再赋值给查找接收变量. 可以推测,插入(整体更新)操作也是类似的过程,并且也是通过value的地址进行的. 这里能够使用value地址的原因是,用完马上就丢弃了,没有机会让他失效.

那么为什么m["woofy"].age++这样的操作不被允许呢? 既然地址都得到了,编译器为什么不多插几条语句搞定呢,比如拿到value的ponter后转成User类型指针,更新age字段, 指针用完就丢,不会有失效问题,看上去也很安全不是吗?

我们在看这类设计问题的时候,不能只看一个例子,像m["woofy"].age++这样的操作太简单,具有一定的迷惑性。我们应该考虑把这个口子放开后会有什么各式各样的情况,会不会失控。例如

  m["woofy"].age = foo(m["woofy"], ...) + bar(&m["woofy"].age, ...) + 1

其中foo bar什么的可能干各种乱起八糟的事情比如大规模写map起大量goroutine什么的。那么翻译这个复杂表达式过程中的产生的指针还能不能保证不失效呢,也许不能,也许完全没问题,这里暂时不能提供一个标准的答案。也许这里考虑问题的方向就错了,也许原本其实只是一个很简单的问题。但希望大家可以通过读map代码,结合具体案例思考,一起参与讨论,如有误区欢迎纠正!

@Astone-Chou

This comment has been minimized.

Copy link

commented Apr 8, 2019

正常情况下不应该是 var m map[string]*User 保存地址这种方式使用吗? 感觉这样应该不会有这个问题。

@woofyzhao

This comment has been minimized.

Copy link
Author

commented Apr 9, 2019

正常情况下不应该是 var m map[string]*User 保存地址这种方式使用吗? 感觉这样应该不会有这个问题。

是的,我在问题里也提到了。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
3 participants
You can’t perform that action at this time.