Questions tagged [compare-and-swap]

Compare and swap (compare and exchange) is an atomic operation that writes a value to a memory location only if its current value is equal to a given expected value.

Filter by
Sorted by
Tagged with
1 vote
0 answers
14 views

why are CAS / other common operations limited to fractions of a cache line?

My understanding is that CAS, FAA, and similar operations usually operate on the machine word size (e.g. 64 bits). The hard parts of implementing these operations in hardware has to do with ...
ajp's user avatar
  • 1,767
-1 votes
1 answer
28 views

Can we use Compare-and-Swap operation on non-atomic variable?

Hi I noticed that the CAS Compare-and-Swap operations are usually operated on atomic variables, see https://en.cppreference.com/w/cpp/atomic/atomic/compare_exchange, https://docs.oracle.com/javase/8/...
Dachuan Huang's user avatar
1 vote
1 answer
65 views

What happens if `compare_exchange_weak` is called on a dangling pointer? How is the code in my textbook safe?

I feel like there could about the a dangling pointer in this example implementation of a lock-free stack in C++: Concurrency in Action. The author, Anthony Williams, provides a beginning for the lock-...
teddy's user avatar
  • 115
0 votes
1 answer
33 views

How to determine whether the minimum number of adjacent swaps required for sorting is odd or even?

I don't know if bubble sort is optimal under the condition that only adjacent swaps are allowed? Is there a more optimal algorithm that can directly determine the parity of the minimum number of swaps ...
埃博拉酱's user avatar
-1 votes
3 answers
129 views

How can I check for null at a specific index of a String Array to change its value?

I am trying to print an array of randomly generated sets of three numbers. Sometimes the sets include a null value when they are printed to the console. Curiously, it is only and always, two of the ...
Coding Noob Unfiltered's user avatar
0 votes
1 answer
131 views

How to use atomic operations with user-space variable in BPF?

I am trying to do a CAS with __sync_val_compare_and_swap in my eBPF code. As this operation needs to be atomic I cannot use bpf_probe_read_user. With a regular kernel variable ...
Victor's user avatar
  • 9
1 vote
1 answer
118 views

What does this compare_exchange_weak example loop do, on atomic boolean, from a talk about the difference between weak and strong?

This is referencing the slide at 37:00 in this CppCon lecture here: https://youtu.be/DS2m7T6NKZQ While the presenter is talking about the difference between compare_exchange_swap_strong and ...
bot654321's user avatar
0 votes
0 answers
115 views

I built a stack using CAS, is it thread-safe?

I'm using std::atomic to create a stack that utilizes CAS. To solve the ABA problem, I used tagged pointer. The code is shown below. template <typename T> union tagged_ptr { struct { ...
tongstar's user avatar
1 vote
1 answer
146 views

Optimistic Offline Lock: Achieve this in database offering Serializability without Linearizability? (i.e., DB does not provide strict serializability)

I'm looking into the optimistic offline lock pattern. i.e., https://martinfowler.com/eaaCatalog/optimisticOfflineLock.html I've seen many references suggesting that this pattern can be achieved ...
S Lover's user avatar
  • 11
0 votes
1 answer
75 views

Is Interlock.CompareExchange atomic inside an if statement?

I am assuming that the piece of code is threadsafe, if ((Interlocked.CompareExchange(ref semaphore, 1, 0) == 0)) { //Do Stuff semaphore = 0; } However I am wondering why: In my mind I see this as ...
Somecode's user avatar
0 votes
1 answer
54 views

Using most significant bits of pointers as a tag in non-blocking queue c++

I am trying to implement a concurrent non-blocking queue where the tag is in the 16 most significant bits of the pointer. It follows this algorithm here: http://www.cs.rochester.edu/research/...
callum arul's user avatar
0 votes
1 answer
106 views

C++ atomics using memory_order_acquire without a matching memory_order_release

Is there any case where we'd want to load an atomic with memory_order_acquire without a corresponding store to the same atomic with memory_order_release? For example, if I have this piece of code: std:...
ktqq99's user avatar
  • 25
1 vote
1 answer
115 views

Performing an atomic swap in solidity with a disposable smart-contract

I want to perform an atomic token swap without a pre-deployed smart-contract and I am wondering how to do that in Solidity. The most common approach to do atomic swaps between tokenA and tokenB is the ...
Thibauld's user avatar
  • 303
0 votes
1 answer
108 views

Is cache coherency only an issue when storing and not when loading?

I came across this code emission for x64 were "Atomic Load" is using a simple movq whereas "Atomic Store" is using xchgq. This link explains that Atomic Load/Stores on aligned ...
Dan's user avatar
  • 2,704
0 votes
0 answers
62 views

Difference between `CMPXCHG8B m64` and `CMPXCHG r/m64, r64`?

According to https://www.agner.org/optimize/instruction_tables.pdf They are different in zen4 LOCK CMPXCHG, Ops=5, Latency=9 LOCK CMPXCHG8B, Ops=15, Latency=10 instruction reference: // can't see ...
grumpyNeko's user avatar
0 votes
1 answer
64 views

Swapping Nodes into Ascending Order

I have a method that adds elements into a doubly linked list, and swaps elements into ascending order if the first element is greater than the second element. If I input 23, 24, 16, it skips swapping ...
Jax's user avatar
  • 1
0 votes
2 answers
66 views

How does Unsafe library help atomic variables to achieve thread safety?

I've been reading web articles about how Compare and Swap (CAS) works under the hood. Since AtomicInteger, AtomicLong and other atomic variables all use JNI's "Unsafe" library's ...
user2606235's user avatar
0 votes
1 answer
112 views

Atomically increment and assign to another atomic

Suppose I have some global: std::atomic_int next_free_block; and a number of threads each with access to a std::atomic_int child_offset; that may be shared between threads. I would like to allocate ...
konsolas's user avatar
  • 1,071
5 votes
1 answer
123 views

How to "mark" pointers by setting the last bit to 1?

I am trying to mark and unmark pointers so I can implement Non-Blocking linked lists. I checked that on my architecture the last bit is never used, so I am trying to use change it to mark/unmark ...
Andrejcc's user avatar
  • 134
1 vote
1 answer
148 views

C++: Atomic Tagged pointer with 16-bit counter in upper bits, can't seem to increment the counter

I'm trying to implement an atomic tagged/packed pointer, for the sake of learning. I want to use the upper 16 bits for a uint16_t counter, and the lower 3 bits for a 3-bit tag. So far, I've managed to ...
Gavin Ray's user avatar
  • 595
0 votes
1 answer
194 views

Why in my code cpp compare_exchange_strong updates and return false

The problem: So I'm pretty new to CPP and i was trying to implement a simple comparison code using some atomicity concepts. The problem is that I'm not getting a desired result, that is: even after ...
Lucas Paixão's user avatar
0 votes
1 answer
260 views

How atomic is Compare and Swap against global variable in modern computer?

Assume we implement in a modern programming language like C++. Let's say we have 5 threads t1 to t5, and we also have an array of timestamps TS[5] one for each thread. We also have a global timestamp ...
libinzhou's user avatar
2 votes
1 answer
93 views

Is a combination of atomic CAS for 64 and 32 bit ok?

My global array contains struct {float,float}. The first thing I do to it is a 64bit CAS on one of the structs. Depending on the return value I (may) want to modify the second float. Now I have the ...
John's user avatar
  • 145
1 vote
1 answer
576 views

What is the difference between the 'Compare And Swap' and 'Compare And Set' operations?

I'm trying to understand the 'Compare And Swap' operation, briefly called CAS. I found that it has a variant called 'Compare And Set'. They work the same way but the return is different. 'Compare And ...
taher bouali's user avatar
0 votes
1 answer
329 views

Concurrency vs parallelism in Golang

I'm trying to implement double compare and swap (and maybe MWCAS) both in Golang and Rust, and since no CPU supports this instruction I need to find a way using what the language offers me. Let's take ...
Mascarpone's user avatar
  • 2,506
0 votes
1 answer
202 views

Why the Semaphore implementation uses CAS (U.compareAndSetInt) instead of wait/notify?

I've decided to implement some clasess from the concurrency package from scratch and implemented Semaphore with wait/notify. It seems very easy and intuitive to do so. When I checked the build in ...
Iaroslav Baranov's user avatar
0 votes
2 answers
101 views

what atomicity does compare_exchange_weak provide?

quote from https://en.cppreference.com/w/cpp/atomic/atomic/compare_exchange bool compare_exchange_weak( T& expected, T desired, std::memory_order success, std::memory_order failure ) noexcept; ...
codesavesworld's user avatar
1 vote
1 answer
203 views

Java 8 impl on Compare And Exchange (Not Compare and Set!)

In java 17, AtomicReference has the compareAndExchange method which is like compareAndSet, but instead of returning a boolean, it returns the value right before the atomic action. I need that to ...
李浩穎's user avatar
1 vote
1 answer
266 views

CUDA customized atomicCAS for floating point types (like double)

atomicCAS allows using integral types of various lengths (according to specs word sizes of 16/32/64 bit). It works fine for integral types like int, unsigned long long,... I want to use atomic ...
Chris G.'s user avatar
  • 826
1 vote
1 answer
305 views

How to implement a lock and unlock sequence in a metal shader?

How should I implement a lock/unlock sequence with Compare and Swap using a Metal compute shader. I’ve tested this sample code but it does not seem to work. For some reason, the threads are not ...
Magodbaru's user avatar
1 vote
1 answer
143 views

Atomic increment via operate command using java client (5.1.5.1) fails

I am trying to do atomic operations on a single bin set. However I am noticing a strange behaviour where randomly record is not getting incremented/decremented. Operate command is returning null in ...
CodeInfinity's user avatar
0 votes
1 answer
78 views

compareAndSwap a common member ( non-volatile member ) still has memory semantics of volatile read and write

When i read AbstractQueuedSynchronizer in jdk1.8, i see the comment that compareAndSetState method has memory semantics of a volatile read and write . The comment and code are as follows: /** * ...
liuchiself's user avatar
1 vote
1 answer
161 views

Is there a DPC++/SYCL equivalent of CUDA's atomicCAS?

From my understanding, CUDA's atomicCAS has the following definition (this is one of the four) int atomicCAS(int* address, int compare, int val); and it compares atomically the values located at ...
Elle's user avatar
  • 305
2 votes
1 answer
91 views

How does the inline assembly in this compare-exchange function work? (%H modifier on ARM)

static inline unsigned long long __cmpxchg64(unsigned long long *ptr,unsigned long long old,unsigned long long new) { unsigned long long oldval; unsigned long res; prefetchw(ptr); ...
Yanel's user avatar
  • 79
0 votes
1 answer
77 views

i am trying to implement the double pivot partition function in reference to quicksort. Can someone help me?

hi I'm trying to implement this double pivot function and then pass the found indices to the recursive quicksort function with three calls (arr, left, pivot_sx) / (arr, pivot_sx + 1, pivot_dx-1) / (...
mimmolg99's user avatar
0 votes
1 answer
63 views

What's the use of `offset` in the version of `Atomic::cmpxchg` in Hotspot?

Here is a version of implementation of function Atomic::cmpxchg used for CAS: jbyte Atomic::cmpxchg(jbyte exchange_value, volatile jbyte* dest, jbyte compare_value) { assert(sizeof(jbyte) == 1, &...
wuxj's user avatar
  • 1
0 votes
0 answers
27 views

Spin Loop vs Cache Miss: which is costlier?

For atomic operations on a integers whose size is bigger larger than the size of a pointer, is it better to use a spin loop to implement it or is it better to dynamically allocate the object, and use ...
Samuel Okechukwu's user avatar
0 votes
1 answer
92 views

Reduce omp critical section to compare_exchange_weak in BFS

I have this working implementation of BFS. std::unordered_map<decltype(root->id()), std::atomic<bool>> visited; #pragma omp parallel { #pragma omp for for ... #pragma ...
John Doe's user avatar
4 votes
1 answer
244 views

sizeof(atomic<T>) is not always equal to sizeof<T>

The return value of sizeof(atomic<T>) is not always equal to the return value of sizeof(T), based on following sentence from [atomics.types.generic]/p9: Note: The representation of an atomic ...
douglas's user avatar
  • 41
3 votes
1 answer
109 views

CMPXCHG – safe to ignore the ZF flag?

The operation pseudocode for cmpxchg is as follows (Intel® 64 and IA-32 Architectures Software Developer’s Manual, Volume 2A: Instruction Set Reference, A-M, 2010): IF accumulator = DEST THEN ZF ← 1; ...
Zoltán Bíró's user avatar
0 votes
0 answers
47 views

What ist faster? atomic<..>.store or atomic<..>compare_exchange_weak [duplicate]

I am experimenting with lock-free algorithms. In some cases, I only need an atomic store() operation and no compare_exchange. I have done simple measurements to get a feel for the performance ...
gerdi's user avatar
  • 165
0 votes
1 answer
229 views

C program to partitition a simply linked list

so i've been working on a small function(part of a bigger program) that basically does the following: define a list and the number of elements N, then input N elements. after this, input a value X; I ...
Radu's user avatar
  • 1
0 votes
1 answer
127 views

Does Java support double-width CAS?

Is there a way to perform a double-width (16-byte) compare-and-swap in Java if the hardware supports it (e.g. using CMPXCHG16B on Intel)?
galym's user avatar
  • 133
0 votes
0 answers
98 views

Nested spin-lock vs volatile check

I was about to write something about this, but maybe it is better to have a second opinion before appearing like a fool... So the idea in the next piece of code (android's room package v2.4.1, ...
Delark's user avatar
  • 1,171
3 votes
2 answers
3k views

Is it good idea to use atomic boolean in kotlin?

Hey I am learning in atomic in kotlin. I am wondering is this good idea to use atomic boolean in my scenario? Can someone suggest, how to do in atomic way. Scenario 1 Not for first time call var ...
Kotlin Learner's user avatar
2 votes
1 answer
179 views

Writing a terminating atomic increment function

If I have the following increment function void increment(atomic_int *v) { int temp; do { temp = *v; } while (temp != compare_and_swap(v, temp, temp+1)); } How do I modify this to make it a ...
sidewala's user avatar
2 votes
1 answer
132 views

Which memory barriers are minimally needed for updating array elements with greater values?

What would be the minimally needed memory barriers in the following scenario? Several threads update the elements of an array int a[n] in parallel. All elements are initially set to zero. Each thread ...
Oleg's user avatar
  • 1,037
2 votes
2 answers
782 views

How does a compare and swap loop achieve atomicity?

This page talks about a CAS loop in details: https://preshing.com/20150402/you-can-do-any-kind-of-atomic-read-modify-write-operation/ An example of fetch_multiply in C++: uint32_t fetch_multiply(std::...
Dan's user avatar
  • 2,704
0 votes
1 answer
309 views

Should I use compare_exchange_weak(or strong) when check atomic<bool> variable is set?

Below code is an usage example of atomic<bool> from book c++ concurrency in action chapter 5. Why do they use compare_exchange_weak for checking b is set and why do they use !expected inside ...
myoldgrandpa's user avatar
3 votes
3 answers
377 views

Is there a way to have a version of std::atomic's compare_exchange_strong method that exchanges on inequality?

I have an atomic type where I need to atomically compare it with a value, and if the two values are not equal then exchange the value of the atomic. Put another way, where compare_exchange_strong ...
Bri Bri's user avatar
  • 2,179

1
2 3 4 5
7