CSE Roadmap

Core tier · about 6 hours · 7 parts

Part 3 of 7 · 3 min read

Sloppy counter

In plain words: The staff of a large shop each keep a tally on their own pad of paper. Every ten customers, a member of staff adds the ten to the shop's main sheet. The main sheet is a little behind the truth at any moment, and nobody has to queue for it on every customer. The analogy stops in one place: the staff can look at all pads, while a thread that reads the global count normally sees only the global value.

The slow part of the counter was the one shared variable. The remedy is to let each thread count in its own variable, with no lock, and to move the local count to the shared total only once per S increments. This is the sloppy counter (also called an approximate counter), described in OSTEP, chapter 29.

struct local { long count; char pad[56]; };         /* one cache line each (Level 2, page 6) */
static struct local loc[MAXT];
static long global;  static pthread_mutex_t gl = PTHREAD_MUTEX_INITIALIZER;

void increment(int id) {
    if (++loc[id].count >= S) {                      /* local count reached the threshold */
        pthread_mutex_lock(&gl);
        global += loc[id].count;                     /* add it to the global one          */
        pthread_mutex_unlock(&gl);
        loc[id].count = 0;
    }
}

The padding to 64 bytes keeps each thread's counter on its own cache line, avoiding the false sharing of Level 2, page 6. The lock is taken once for every S increments, so contention falls by a factor of S.

The cost is accuracy. The global value lags by up to n × S (n threads, S the threshold). A run of 2,000,000 increments per thread with S = 1,024 ended with:

sloppy S=1024, 4 threads: global 7,999,488, in local counters 512, total 8,000,000

The global value was 512 short, the sum of the local remainders (each thread ended with 128 left: 2,000,000 mod 1,024). Adding the local counts gives the exact total, and the total never lost an increment. The threshold is a dial: a small S gives an accurate global value and less speed, a large S the reverse.

Timings (median seconds, 2,000,000 increments for each thread):

Counter 1 thread 2 threads 4 threads
Mutex 0.042 0.291 0.573
Atomic 0.018 0.096 0.203
Sloppy, S = 16 0.005 0.027 0.051
Sloppy, S = 1,024 0.003 0.006 0.007

With S = 1,024, the 4-thread run, which does 4 times the work of the 1-thread run, took only 2.3 times as long (0.007 against 0.003, on two processors), and is about 80 times faster than the mutex. The structure scales, since the threads hardly ever touch shared data.

Sloppy counter

A sloppy counter (approximate counter) is a counter in which each thread increments a private count without locking and adds it to a shared global count, under a lock, only when it reaches a threshold, so that the global value lags the true total by at most the number of threads times the threshold.

Example: with a threshold of 1,024, a thread takes the global lock once for every 1,024 increments.

Check yourself: 1. How often does a thread take the lock for S = 1,024? 2. How far can the global value lag with 4 threads and S = 1,024? 3. Why is each local counter padded to 64 bytes?