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.
345
questions
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 ...
-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/...
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-...
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 ...
-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 ...
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 ...
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 ...
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
{
...
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 ...
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 ...
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/...
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:...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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;
...
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 ...
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 ...
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 ...
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 ...
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:
/**
* ...
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 ...
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);
...
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) / (...
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, &...
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 ...
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 ...
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 ...
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;
...
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 ...
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 ...
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)?
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, ...
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 ...
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 ...
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 ...
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::...
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 ...
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 ...