Since len() for slice and map are O(1), why len() is not thread-safe?

huangapple go评论89阅读模式
英文:

Since len() for slice and map are O(1), why len() is not thread-safe?

问题

我阅读了一些帖子(https://stackoverflow.com/questions/57596213/are-lenstring-and-lenslices-o1-operation-in-go,https://stackoverflow.com/questions/35005261/how-to-check-if-a-map-is-empty-in-golang),发现切片和映射的len()操作的时间复杂度是O(1),实现方式是获取结构体的成员(例如大小、长度)。
但是测试(https://stackoverflow.com/questions/52710882/is-len-thread-safe-in-golang)显示len()操作不是线程安全的,为什么呢?

英文:

I read some post(https://stackoverflow.com/questions/57596213/are-lenstring-and-lenslices-o1-operation-in-go, https://stackoverflow.com/questions/35005261/how-to-check-if-a-map-is-empty-in-golang) and found that len() for slice and map are O(1), the implementation is get a member(e.g. size, length) of the structure.
But the test(https://stackoverflow.com/questions/52710882/is-len-thread-safe-in-golang) show len() is not thread-safe, why?

答案1

得分: 3

你所指的是一种称为“良性数据竞争”的情况。地图大小只是一个int,所以可以假设读取和写入单个int是原子操作,对吗?实际上并不是这样。

Go的内存模型源自C的内存模型,在该模型中,如果两个或多个线程从同一内存中访问数据,其中至少一个线程在写入,而没有进行同步,就会发生数据竞争,这是一种未定义行为。无论你是访问单个int还是更复杂的结构,都是如此。

良性数据竞争不存在的原因有两个:

1. 硬件。 CPU缓存架构有两种类型:一种是具有强缓存一致性的架构(例如x86),另一种是具有弱缓存一致性的架构(例如ARM)。根据硬件的不同,对内存的常规写入可能不会立即在其他核心上“可见”。需要使用特殊的“原子”指令才能使数据在核心之间可见。

2. 软件。 根据内存模型,假设每个线程都在独立执行(直到发生具有happens-before语义的同步事件)。编译器可以假设对同一内存位置的读取将提供相同的结果,并且例如,可以提升循环中的这些读取(从而破坏程序)。这就是为什么在针对具有强缓存一致性的硬件时,同步必须在代码中显式指定的原因。

以下程序可能会或可能不会完成,这取决于CPU和编译器优化标志:

func main() {
	x := 0
	go func() {
		x = 1
	}()
	for x == 0 {  // 数据竞争!此外,编译器可以将“x == 0”简化为“true”
		// 等待...
	}
}

为了使其正确,使用同步来让编译器知道存在并发:

func main() {
	var mtx sync.Mutex
	x := 0
	go func() {
		mtx.Lock()
		x = 1 // 通过互斥锁保护写操作
		mtx.Unlock()
	}()
	for {
		mtx.Lock()
		x_copy := x // 是的,读取也必须受到保护
		mtx.Unlock()
		if x_copy != 0 {
			break
		}
		// 等待...
	}
}

对同一个互斥锁进行锁定和解锁会创建一个“获取-释放屏障”,使得在解锁互斥锁之前完成的所有内存写入都会“释放”,并对随后锁定互斥锁并“获取”这些写入的线程可见。

英文:

What you're referring to is called a benign data race. The map size is just an int, so one could assume that reading and writing a single int is atomic, right? Well, no.

The Go memory model is derived from the C memory model, in which accessing the same memory from two or more threads, at least one of which is writing, without synchronization is a data race - a form of undefined behavior. It does not matter if you're accessing a single int or a more complex structure.

There are two reasons why a benign data race does not actually exist:

1. Hardware. There are two types of CPU cache architectures: one with strong cache coherency (e.g. x86) and another with weak cache coherency (e.g. ARM). Regular writes to memory may not become "visible" on other cores immediately, depending on the hardware. Special "atomic" instructions are required to make data visible between cores.

2. Software. According to the memory model, each thread is assumed to execute in isolation (until a synchronization event with happens-before semantics occurs). The compiler is allowed to assume that reading the same memory location will provide the same result, and for example, hoist these reads of the loop (thus breaking your program). This is why synchronization must be explicit in the code, even when targeting hardware with strong cache coherency.


The following program may or may not ever finish, depending on the CPU and compiler optimization flags:

func main() {
	x := 0
	go func() {
		x = 1
	}()
	for x == 0 {  // DATA RACE! also, the compiler is allowed to simplify "x == 0" to "true" here
		// wait ...
	}
}

To make it correct, use synchronization to let the compiler know there is concurrency involved:

func main() {
	var mtx sync.Mutex
	x := 0
	go func() {
		mtx.Lock()
		x = 1 // protect writes by a mutex
		mtx.Unlock()
	}()
	for {
		mtx.Lock()
		x_copy := x // yes, also reads must be protected
		mtx.Unlock()
		if x_copy != 0 {
			break
		}
		// wait ...
	}
}

The locking and unlocking of the same mutex creates an acquire-release fence such that all memory writes done before unlocking the mutex are "released" and become visible to the thread that subsequently locks the mutex and "acquires" them.

huangapple
  • 本文由 发表于 2021年11月29日 16:02:53
  • 转载请务必保留本文链接:https://go.coder-hub.com/70151404.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定