Extreme data race

Hi, out of curiosity I wanted to see the effect of extreme data race in ocaml 5.0.0, and indeed it is quite extreme. In this test, one domain increases a global variable 100000 times, one domain decreases it 100000 times. Amongst the various random results (see below), I regularly get the answer r=100000, as if only one domain has been executed. Does this depend on the caching strategy of the CPU, or is there another explanation?

let main d1 d2 reset get =
  reset ();
  let h1 = Domain.spawn d1 in
  let h2 = Domain.spawn d2 in
  Domain.join h1;
  Domain.join h2;
  Printf.printf "r=%i\n" (get ());;

let test d1 d2 reset get s =
  print_endline s;
  for i = 0 to 100 do main d1 d2 reset get done;;

(* Has data race *)
let r = ref 0
let n = 100000
let d1 () = for i = 1 to n do r := !r + 1 done
let d2 () = for i = 1 to n do r := !r - 1 done;;

test d1 d2 (fun () -> r := 0) (fun () -> !r) "Data race";;

Results:

Data race
r=10024
r=-48252
r=-67379
r=-76508
r=-73210
r=-7266
r=-75997
r=-74175
r=-70645
r=-73290
r=-74627
r=-77045
r=-78305
r=-72376
r=-77470
r=-77833
r=-69270
r=-70535
r=-77083
r=2182
r=-53226
r=461
r=2970
r=-70661
r=2351
r=3495
r=3942
r=3411
r=2642
r=3618
r=3617
r=3037
r=38337
r=46287
r=847
r=2294
r=-65236
r=-71256
r=24792
r=-74338
r=1162
r=-964
r=3753
r=-67735
r=50172
r=-46508
r=-32071
r=-53965
r=100000
r=-73217
r=-19506
r=-72670
r=-62562
r=-73630
r=-65515
r=-74026
r=-73362
r=-71919
r=-74326
r=-74369
r=-72633
r=-75797
r=5775
r=-71294
r=2457
r=-70373
r=-75272
r=-74699
r=-77246
r=-76440
r=-74806
r=3823
r=-71966
r=-76373
r=-72220
r=-72158
r=-75437
r=-69900
r=-74736
r=-76066
r=-77740
r=-71857
r=-72086
r=-75901
r=-76337
r=-76412
r=-63709
r=-80743
r=-73191
r=-73041
r=16266
r=-74255
r=-67175
r=-75011
r=-77865
r=-77036
r=-74821
r=-77308
r=-75952
r=-71673
r=-76314

The behaviour depends on a large number of factors. The number of cores on your machine, when and where your OS schedules the domains and the relaxed memory model.

Thanks to the precise relaxed memory model that we have for OCaml, you will not need to reason at the level of caches, non sequentially consistent hardware behaviours and compiler optimisations. If you are keen to learn about the details of the memory model, we have a manual chapter that explains it in detail: OCaml - Memory model: The hard bits.

My recommendation is don’t do data races. :slight_smile:

Don’t worry I’m not trying to “use” data races, just trying to understand. I wrote this actually while reading chapter 10, trying to understand what was going on.

Here what would be the most plausible explanation for the result r=100000?

Suppose that the reset of r happens on core 0. Suppose d2 gets scheduled on core 1. It requests the value of r and either the main memory (or a shared cache) or core 0 answers; so, core 1 gets the value 0 and starts its computation. Except for the final value of r which is propagated thanks to a memory barrier, all the intermediate changes to r might go unnoticed from core 0. Now suppose that d1 gets scheduled on core 0. The value of r is still in cache since core 1 has not yet got the chance to advertise a new value. Now, both core 0 and core 1 have finished their computation and they race to publish their final value of r Core 0 wins, the final value of r is 100000.

1 Like

Are you asking for a possible execution that could result in your observation? I would guess a plausible execution could be d1 executes first to the point where it evaluates !r ==> 0, but before it writes the incremented value, then d2 executes to completion, setting the value of r to -100_000, and finally d1 is resumed, at which point it writes 0 + 1 to r and continues its execution, leaving r with the value 100_000.

2 Likes

thanks! interesting, this means that one core is authorized to do 100000 operations without advertising the result

thanks, indeed this is quite simple. Do you know what is the strategy for a core to advertise a write? it this after a certain number of operations, or after a certain amount of time?

It depends a lot on the architecture. If no one is hitting the same cache line (which is not the case here), it can take an arbitrary long time. Here, another core reading the same memory location (to put it into its cache) should cause the writing core to publish its latest value, which might still take some time to reach the other caches.

Even on an architecture like x86 with its exclusive caches (which theoretically means that writes from one core are instantly seen from any other core hitting the same cache line), invalidating lines can take a long time, during which cores do not stop executing code, unless an atomic operation or a memory barrier is used.

Moreover, your example is writing to the same memory location over and over, so the (speculative) writes do not even get to leave the store buffer. Thus, the cache is not even aware of the write, and neither do the caches of the other cores as a consequence.