Can multiple threads do "atomic" lockfree writes to different bytes in an array?

Question

Can N threads do "atomic" lockfree writes of length k non-overlapping intervals of x-bit elements in an array of M x-bit elements (for N at most M)?

Eg. suppose N is 10, M is 10, k is 1 and x is 8.

Then we have 10 threads, an array of 10 bytes, and each threads writes 1 byte to the array. (Each thread writes to a different byte, because the intervals are non-overlapping, by hypothesis.)

---

Here's a program that tests whether this is possible, or if a thread "steps on his neighbor's toes".

/*
t gcc-8  bytes1.c -o bytes1  -lpthread  &&  t ./bytes1
*/
#include <stdint.h>
typedef  uint8_t   u8;
typedef  int32_t  i32;
typedef  int64_t  i64;

#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <pthread.h>

// ----------------------------------------------------------------------------------------------------------------------------#
/* @blk1  test if multiple threads can do 1-byte aligned lockfree atomic writes to an array! */
#define THRS_TEST_LOCKFREE_WRITES_DX    0x20
#define THRS_TEST_LOCKFREE_WRITES_TMUL  2  // thread multiplier (for the numbre of threads)!

typedef struct{
  i32       idx;
  i32       tdim;
  pthread_t pthr;

  i32       dx;
  u8*       g_data;
}thr_t;

void* thr_test_lockfree_write(void* arg){
  thr_t* thr = (thr_t*)arg;
  for(int i=0; i<thr->dx; ++i)
    thr->g_data[thr->idx*thr->dx + i] = thr->idx;
  return NULL;
}

void thrs_test_lockfree_writes(){
  i32    thrs_idim = THRS_TEST_LOCKFREE_WRITES_TMUL * sysconf(_SC_NPROCESSORS_ONLN);
  thr_t* thrs      = alloca(sizeof(thr_t)*thrs_idim);
  i32    x_dx      = THRS_TEST_LOCKFREE_WRITES_DX;
  i64    x_idim    = x_dx*thrs_idim;
  u8*    x_data    = aligned_alloc(0x1000, sizeof(u8)*x_idim);

  for(int i=0; i<thrs_idim; ++i){
    thrs[i].idx    = i;
    thrs[i].tdim   = thrs_idim;
    thrs[i].dx     = x_dx;
    thrs[i].g_data = x_data;
    pthread_create(&thrs[i].pthr, NULL, thr_test_lockfree_write, &thrs[i]);
  }

  for(int i=0; i<thrs_idim; ++i){
    pthread_join(thrs[i].pthr, NULL);
  }

  putchar(0x0a);
  for(int i=0; i<x_idim/x_dx; ++i){
    printf("\x1b[32m%02x\x1b[91m/\x1b[37m%02x  \x1b[0m", i,thrs_idim-1);
    i32 flag = 1;
    for(int j=0; j<x_dx; ++j){
      printf("%02x", x_data[i*x_dx+j]);
      flag &= x_data[i*x_dx+j]==i%0x100;
    }
    printf(" %d\n",flag);
  }

  free(x_data);
}

// ----------------------------------------------------------------------------------------------------------------------------#
int main(){
  thrs_test_lockfree_writes();
  puts("\nbye!");
}

Answer 1

Can N threads do "atomic" lockfree writes

On architectures where writing a single byte to memory is possible (which is all modern architectures), yes.

See also this answer, and note that the level of parallelism your program will actually achieve will be far lower than one might expect due to false sharing.