ansaurus

Question

Answer 1

+7 A:

A normal increment is not guaranteed to be atomic.

Most languages have an Atomic Increment instruction which is atomic and is usually faster than a lock. (Interlocked.Increment, InterlockedIncrement, and others)

SLaks 2010-07-09 12:36:45

Emm, you just said what my question is explaining in details. Question what is atomic then.

Andrey 2010-07-09 12:39:49

I disassembled InterlockedIncrement. It emits `lock inc` which is kind of lock, but at lowest possible level

Andrey 2010-07-09 12:45:50

So from your answer comes that there is nothing atomical at all. All atomicity is achieved by locking.

Andrey 2010-07-09 12:52:25

But a lock on the memory bus is much much cheaper than a software implemented lock (e.g. CriticalSection). Plus, some architectures could choose to implement granular locking which applies only to the single cache line. With MOESI cache coherency protocol, CPU knows if another core touched the cache line meanwhile and can retry with expensive lock only in that case.

Ben Voigt 2010-07-09 14:05:05

@Ben Voigt thanks for MOESI, interesting to read about it.

Andrey 2010-07-09 14:36:17

Answer 2

+1 A:

Is increment atomic or not?

No.

It can't be interrupted on single CPU but participate in race condition in multi CPU.

Yes.

We can atomize it with lock prefix but for me it sounds not atomic, but execution with lock. So what is atomic then?

Locks essentially make a group of operations atomic, so it is atomic.

wj32 2010-07-09 12:37:20

No, `lock` prefix to the instruction only makes a single instruction atomic. I guess you're thinking about a critical section (software-implemented locking) which is something else.

Ben Voigt 2010-07-09 14:06:22

"Is increment atomic or not?" - "No" is not correct. it is pretty atomic in case of single core/cpu if it is compiled to `inc`

Andrey 2010-07-09 14:51:27

Answer 3

A:

I'd question your test code showd , the compiler(atleast with optimization on) might just figure out "i is going to be 1000000, I'll just make i 1000000 and not even bother generate code for that useless loop"

Anyhow, it might not be atomic. What'll often happen is:

  read i from memory into register
  increment register
  store i back to memory. (this step might not even be done, or only done at the end of the loop)

Perhaps, with a certain compiler, with a certain optimization, AND depending on what the code otherwise uses i for, it might just do

increment i in memory

There's no guarantee for that though, and the generated code might change drastically if e.g. something inside the loop uses i, or passes i to another function. Even "increment in memory" might not be atomic or visible in regards to other processors/cores and their caches. You should use atomic builtins/apis for this sort of things.

For .NET you should use Interlocked.Increment , for MSVC, use InterlockedIncrement, for gcc use the atomic builtins

nos 2010-07-09 12:40:57

the funny thing that "increment i in memory" is essentially impossible. even if ++ is compiled to single instruction (`inc`) it is executed in several steps which are safe in case of single core and not in multiple.

Andrey 2010-07-09 12:48:17

Depends on the processor. For example, Microchip PICs can and do perform atomic memory increment. Of course, with only 128 bytes of directly addressable memory, it's pretty comparable to an operation on a register.

Ben Voigt 2010-07-09 16:48:26

Answer 4

+1 A:

The only atomic operations are the Aritmethic-Logic unit operations itself, that means, load a register is atomic, calculate an address is atomic, etc...

But those are too low level operations to be used. Assembly code is not atomic because each instruction can be splitted in several operations for this ULA (or ALU, i don't know the acronym in English, it's a component of the CPU). The only instruction atomic is the one that provides locks (makes sense).

The only way to ensure atomicity is to use the lock instructions to lock instructions, and hence, lock fragments of code.

pakore 2010-07-09 12:40:58

ansaurus

tags:

views:

answers:

Can ++ (increment) be called atomic?

related questions