1

For example, considering there is a character array we add entries from both ends. I want to create a function that given 2 strings, it atomically determines where to insert the two strings in the two ends. I want to use an offset to record the end of the forward direction and an offset to record the end of the backward direction. I wish to modify two variables atomically using fech_add/subtract. One possible way I'm thinking of is to combine the two offsets into 1 64 bits long integer, and combine the two operations into a single atomic operation. The code should look like the following:

atomic<long> combined_offset;
char* array;
long combine_two_lengths(std::string& forward_st, std::string& backward_st){
    long size1 = forward_st.length();
    long size2 = -1*backward_st.length();
    return size1<<32|size2;
}
void append_two_strings(std::string forward_st, std::string backward_st){
    long value_to_update = combine_two_lengths(forward_st,backward_st);//combine two string sizes into one 64 bits long
    long new_offset = combined_offset.fetch_add(value_to_update);
    if(is_still_valid(new_offset))//check the two offsets do not cross
        insert_array(array,forward_st,backward_st,new_offset);
    else
        std::cout<<"Array out of bounds\n";
        //enter a critical section and expand the array
}
libinzhou
  • 37
  • 6
  • 5
    It is valid to combine two 32-bit integers into a single 64-bit integer so you can perform atomic operations on them. Note though that your code combines them incorrectly, and if `is_still_valid` is `false`, the code leaves the `combined_offset` at an invalid value. You probably want to use one of the compare_exchange variants (in a loop with early-out). – Raymond Chen Oct 02 '22 at 15:57
  • You can even have `std::atomic>` or even `std::atomic`. it would be atomic (but not necessary lock-free). – Jarod42 Oct 02 '22 at 15:58
  • @RaymondChen: What's wrong with the way they are combined? It looks correct to me, assuming all the lengths and offsets are nonnegative and always less than 2^31. (And granting all the implementation-specific assumptions about the size and representation of `long`; `uint64_t` would be safer.) – Nate Eldredge Oct 02 '22 at 16:26
  • 2
    @Jarod42: You can't have `std::atomic>` because `std::pair` isn't trivially copyable. https://godbolt.org/z/sWda3jEzj The struct works, though. But I think the idea is to be able to take advantage of a potentially fast `fetch_add`. The struct would have to be updated with a compare-exchange loop. – Nate Eldredge Oct 02 '22 at 16:32
  • 2
    Consider having `combine_two_lengths` be passed the two string parameters by const reference instead of by value. I know the compiler can optimize away the copies if it can inline it, but why leave that to chance? If the compiler can't optimize that call, the gains from using atomics will be wiped out from string copies. I don't know what `insert_array` does, but I hope it passes those strings by (const) ref as well. – selbie Oct 02 '22 at 16:51
  • Semi-related: [How can I implement ABA counter with c++11 CAS?](https://stackoverflow.com/q/38984153) for a union hack that works in practice with GCC. (And some stuff about a pair of 8-byte integers on x86-64; a pair of 32-bit integers is much easier and more efficient in the asm.) – Peter Cordes Oct 02 '22 at 17:13
  • @NateEldredge You're right, I missed that `size1` was already promoted to `long`. – Raymond Chen Oct 02 '22 at 17:19
  • Yes. You can play bit portioning games with atomics and treat a 64-bit integer as 2 32-bit integers and using shift is endianness independent. You can't update different sections the 64-bit atomic asynchronously. Though your code isn't trying to do anything like update different halves of the value from different threads. – Persixty Oct 02 '22 at 17:23
  • @RaymondChen Thank you for the reply. I see your point. Yes ideally the array will need to be resized and new offset values need to be set. I didn't include them there to make the code too complicated. Now I feel I just need to have the string length from the forward string and negative string length from the backward string and add the bit-shifted combined value then. Thank you so much. – libinzhou Oct 02 '22 at 17:44
  • Hello @NateEldredge, thank you for the suggestion about the value. But here I want to do a bit extra so I originally stayed with long instead of uint64_t. Because the array contents grow in 2 directions, I want to add the length to one offset while subtracting another length from another offset. This make me feel using long is safer. – libinzhou Oct 02 '22 at 17:47
  • Ah, the `-1` wasn't there when I looked before. Your plan of adding `size1 << 32 | size2` is not correct when `size2` is negative. Try for example what happens when `size1 == 1` and `size2 == -1`. I *think* that `(size1 << 32) + size2` works, so long as both results remain nonnegative (i.e. no borrows), but you should verify that carefully. – Nate Eldredge Oct 02 '22 at 18:19
  • @NateEldredge Hello, yes sorry I added the -1 later, and I'm currently writing a code snippet to try to test if it's correct. Also planning on adding additional state checks that if the atomic 64 bits int is not valid, don't do the atomic operations on it. – libinzhou Oct 02 '22 at 18:24
  • @libinzhou: I don't see how you'll be able to do that without a race condition. What if the value changes between your test and when you do the `fetch_add`? You can do it safely with a compare-exchange loop, but I think that's what you're trying to avoid. – Nate Eldredge Oct 02 '22 at 18:25
  • @NateEldredge Oh yes, you are right. A compare and swap will make more sense. Or just treat the original value as garbage then. Thank you so much for the input. I wasn't thinking about that correctly. – libinzhou Oct 02 '22 at 18:30
  • Note also that updating the `combined_offset` may not be good enough. For example, another thread can see the updated `combined_offset`, and then it uses those offsets to try to read the values, only to find that the values aren't there because `insert_array` hasn't finished yet. – Raymond Chen Oct 02 '22 at 22:26
  • @RaymondChen thank you for the suggestion here. I think it is very important. I will definitely add more protection to not let others read in progress inserts. – libinzhou Oct 02 '22 at 22:28

0 Answers0