<commit_before>Q: What is it?  A: A "thread-safe global variable" for C
--------------------------------------------------------

A thread-safe global variable lets readers keep using a value read from
it until they read the next value.  Memory management is automatic:
values are automatically destroyed when the last reference is released
or the last referring thread exits.  Reads are always fast and never
block writes.  Writes are serialized but otherwise also always fast and
never block reads.

This is not unlike a Clojure "ref".  It's also similar to RCU, but
unlike RCU, this has a much simpler API with nothing like
`synchronize_rcu()`, and doesn't require any cross-CPU calls nor the
ability to make CPUs/threads run, and it has no application-visible
concept of critical sections, therefore it works in user-land with no
special kernel support.

 - One thread needs to create the variable by calling
   `pthread_var_init_np()` and providing a value destructor.
 - Most threads only ever need to call `pthread_var_get_np()`, and maybe
   once `pthread_var_wait_np()` to wait until at least one value has
   been set.
 - One or more threads may call `pthread_var_set_np()` to publish new
   values.

The API is:

    typedef struct pthread_var_np *pthread_var_np_t;
    typedef void (*pthread_var_destructor_np_t)(void *);
    int  pthread_var_init_np(pthread_var_np_t *var, pthread_var_destructor_np_t value_destructor);
    void pthread_var_destroy_np(pthread_var_np_t var);
    int  pthread_var_get_np(pthread_var_np_t var, void **valuep, uint64_t *versionp);
    int  pthread_var_set_np(pthread_var_np_t var, void *value, uint64_t *versionp);
    int  pthread_var_wait_np(pthread_var_np_t var);
    void pthread_var_release_np(pthread_var_np_t var);

Value version numbers increase monotonically when values are set.

Why?  Because read-write locks are teh worst
--------------------------------------------

So you have rarely-changing global data (e.g., loaded configuration,
plugins, ...), and you have many threads that read this, and you want
reads to be fast.  Worker threads need stable configuration/whatever
while doing work, then when they pick up another task they can get a
newer configuration if there is one.  How would you implement that?  A
safe answer is: read-write locks around reading/writing the global
variable, and reference count the data.  But read-write locks are
inherently bad: readers either can starve writers or can be blocked by
writers.

A thread-safe global variable, on the other hand, is always fast to
read, even when there's an active writer, and reading does not starve
writers.

How?
----

Two implementations are included at this time.

The two implementations have slightly different characteristics.

 - One implementation ("slot pair") has O(1) reads and writes.

   But readers call free() and the value destructor, and, sometimes have
   to signal a potentially-waiting writer -- a blocking operation,
   though on uncontended resources.

   This implementation has a pair of slots, one containing the "current"
   value and one containing the "previous"/"next" value.  Writers make the
   "previous" slot into the next "current" slot, and readers read from
   whichever slot appears to be the current slot.  Values are wrapped
   with a wrapper that includes a reference count, and they are released
   when the reference count drops to zero.

   The trick is that writers will wait until the number of active
   readers of the previous slot is zero.  Thus the last reader of a
   previous slot must signal a potentially-awaiting writer (which
   requires taking a lock that the awaiting writer should have
   relinquished in order to wait).  Thus reading is mostly lock-less and
   never blocks on contended resources.

 - The other implementation ("slot list") has O(1) reads, and O(N)
   writes (where N is the maximum number of live threads that have read
   the variable), with readers never calling the allocator after the
   first read in any given thread, and writers never calling the
   allocator while holding a lock.

   But readers have to loop over their fast path, a loop that can run
   indefinitely if there are higher-priority writers who starve the
   reader of CPU time.

   This implementation has a list of referenced values, with the head of
   the list always being the current one, and a list of "subscription"
   slots, one per-reader thread.  Readers allocate a slot on first read,
   and thence copy the head of the values list to their slots.  Writers
   have to perform garbage collection on the list of referenced values.

   Subscription slot allocation is lock-less.  Indeed, everything is
   lock-less in the reader.

A test program is included that hammers the implementation.  Run it in a
loop, with or without valgrind, ASAN (address sanitizer), or other
memory checkers, to look for racy bugs.

Both implementations perform similarly well on the included test.

The test pits 20 reader threads waiting various small amounts of time
between reads (one not waiting at all), against 4 writer threads waiting
various small amounts of time between writes.  This test found a variety
of bugs during development.  In both cases writes are, on average, 5x
slower than reads, and reads are in the ten microseconds range on an old
laptop, running under virtualization.

Performance
-----------

On an old i7 laptop, virtualized, reads on idle thread-safe global
variables (i.e., no writers in sight) take about 15ns.  This is because
the fast path in both implementations consists of reading a thread-local
variable and then performing a single acquire-fenced memory read.<commit_msg>Add testing section to README<commit_after>Q: What is it?  A: A "thread-safe global variable" for C
--------------------------------------------------------

A thread-safe global variable lets readers keep using a value read from
it until they read the next value.  Memory management is automatic:
values are automatically destroyed when the last reference is released
or the last referring thread exits.  Reads are always fast and never
block writes.  Writes are serialized but otherwise also always fast and
never block reads.

This is not unlike a Clojure "ref".  It's also similar to RCU, but
unlike RCU, this has a much simpler API with nothing like
`synchronize_rcu()`, and doesn't require any cross-CPU calls nor the
ability to make CPUs/threads run, and it has no application-visible
concept of critical sections, therefore it works in user-land with no
special kernel support.

 - One thread needs to create the variable by calling
   `pthread_var_init_np()` and providing a value destructor.
 - Most threads only ever need to call `pthread_var_get_np()`, and maybe
   once `pthread_var_wait_np()` to wait until at least one value has
   been set.
 - One or more threads may call `pthread_var_set_np()` to publish new
   values.

The API is:

    typedef struct pthread_var_np *pthread_var_np_t;
    typedef void (*pthread_var_destructor_np_t)(void *);
    int  pthread_var_init_np(pthread_var_np_t *var, pthread_var_destructor_np_t value_destructor);
    void pthread_var_destroy_np(pthread_var_np_t var);
    int  pthread_var_get_np(pthread_var_np_t var, void **valuep, uint64_t *versionp);
    int  pthread_var_set_np(pthread_var_np_t var, void *value, uint64_t *versionp);
    int  pthread_var_wait_np(pthread_var_np_t var);
    void pthread_var_release_np(pthread_var_np_t var);

Value version numbers increase monotonically when values are set.

Why?  Because read-write locks are teh worst
--------------------------------------------

So you have rarely-changing global data (e.g., loaded configuration,
plugins, ...), and you have many threads that read this, and you want
reads to be fast.  Worker threads need stable configuration/whatever
while doing work, then when they pick up another task they can get a
newer configuration if there is one.  How would you implement that?  A
safe answer is: read-write locks around reading/writing the global
variable, and reference count the data.  But read-write locks are
inherently bad: readers either can starve writers or can be blocked by
writers.

A thread-safe global variable, on the other hand, is always fast to
read, even when there's an active writer, and reading does not starve
writers.

How?
----

Two implementations are included at this time.

The two implementations have slightly different characteristics.

 - One implementation ("slot pair") has O(1) reads and writes.

   But readers call free() and the value destructor, and, sometimes have
   to signal a potentially-waiting writer -- a blocking operation,
   though on uncontended resources.

   This implementation has a pair of slots, one containing the "current"
   value and one containing the "previous"/"next" value.  Writers make the
   "previous" slot into the next "current" slot, and readers read from
   whichever slot appears to be the current slot.  Values are wrapped
   with a wrapper that includes a reference count, and they are released
   when the reference count drops to zero.

   The trick is that writers will wait until the number of active
   readers of the previous slot is zero.  Thus the last reader of a
   previous slot must signal a potentially-awaiting writer (which
   requires taking a lock that the awaiting writer should have
   relinquished in order to wait).  Thus reading is mostly lock-less and
   never blocks on contended resources.

 - The other implementation ("slot list") has O(1) reads, and O(N)
   writes (where N is the maximum number of live threads that have read
   the variable), with readers never calling the allocator after the
   first read in any given thread, and writers never calling the
   allocator while holding a lock.

   But readers have to loop over their fast path, a loop that can run
   indefinitely if there are higher-priority writers who starve the
   reader of CPU time.

   This implementation has a list of referenced values, with the head of
   the list always being the current one, and a list of "subscription"
   slots, one per-reader thread.  Readers allocate a slot on first read,
   and thence copy the head of the values list to their slots.  Writers
   have to perform garbage collection on the list of referenced values.

   Subscription slot allocation is lock-less.  Indeed, everything is
   lock-less in the reader.

Testing
-------

A test program is included that hammers the implementation.  Run it in a
loop, with or without valgrind, ASAN (address sanitizer), or other
memory checkers, to look for racy bugs.

Both implementations perform similarly well on the included test.

The test pits 20 reader threads waiting various small amounts of time
between reads (one not waiting at all), against 4 writer threads waiting
various small amounts of time between writes.  This test found a variety
of bugs during development.  In both cases writes are, on average, 5x
slower than reads, and reads are in the ten microseconds range on an old
laptop, running under virtualization.

Performance
-----------

On an old i7 laptop, virtualized, reads on idle thread-safe global
variables (i.e., no writers in sight) take about 15ns.  This is because
the fast path in both implementations consists of reading a thread-local
variable and then performing a single acquire-fenced memory read.
{'fraction_non_alphanumeric': 0.06299973640277656, 'fraction_numerical': 0.0022845092698356912, 'mean_word_length': 3.728707935189032, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1706512', 'n_tokens_mistral': 2996, 'n_tokens_neox': 2901, 'n_words': 1616}