4.1 Constant-Time Array Access

pm-gawk preserves the efficiency of data access when data structures are created by one process and later re-used by a different process.

Consider the associative arrays used to analyze Mark Twain’s books in Examples. We created arrays ts[] and hf[] by reading files sawyer.txt and finn.txt. If N denotes the total volume of data in these files, building the associative arrays typically requires time proportional to N, or “O(N) expected time” in the lingo of asymptotic analysis. If W is the number of unique words in the input files, the size of the associative arrays will be proportional to W, or O(W). Accessing individual array elements requires only constant or O(1) expected time, not O(N) or O(W) time, because gawk implements arrays as hash tables.

The performance advantage of pm-gawk arises when different processes create and access associative arrays. Accessing an element of a persistent array created by a previous pm-gawk process, as we did earlier in BEGIN{print ts["river"], hf["river"]}, still requires only O(1) time, which is asymptotically far superior to the alternatives. Naïvely reconstructing arrays by re-ingesting all raw inputs in every gawk process that accesses the arrays would of course require O(N) time—a profligate cost if the text corpus is large. Dumping arrays to files and re-loading them as needed would reduce the preparation time for access to O(W). That can be a substantial improvement in practice; N is roughly 19 times larger than W in our Twain corpus. Nonetheless O(W) remains far slower than pm-gawk’s O(1). As we’ll see in Results, the difference is not merely theoretical.

The persistent memory implementation beneath pm-gawk enables it to avoid work proportional to N or W when accessing an element of a persistent associative array. Under the hood, pm-gawk stores script-defined AWK variables such as associative arrays in a persistent heap laid out in a memory-mapped file (the heap file). When an AWK script accesses an element of an associative array, pm-gawk performs a lookup on the corresponding hash table, which in turn accesses memory on the persistent heap. Modern operating systems implement memory-mapped files in such a way that these memory accesses trigger the bare minimum of data movement required: Only those parts of the heap file containing needed data are “paged in” to the memory of the pm-gawk process. In the worst case, the heap file is not in the file system’s in-memory cache, so the required pages must be faulted into memory from storage. Our asymptotic analysis of efficiency applies regardless of whether the heap file is cached or not. The entire heap file is not accessed merely to access an element of a persistent associative array.

Persistent memory thus enables pm-gawk to offer the flexibility of de-coupling data ingestion from analytic queries without the fuss and overhead of serializing and loading data structures and without sacrificing constant-time access to the associative arrays that make AWK scripting convenient and productive.

4.2 Virtual Memory and Big Data

Small data sets seldom spoil the delights of AWK by causing performance troubles, with or without persistence. As the size of the gawk interpreter’s internal data structures approaches the capacity of physical memory, however, acceptable performance requires understanding modern operating systems and sometimes tuning them. Fortunately pm-gawk offers new degrees of control for performance-conscious users tackling large data sets. A terse mnemonic captures the basic principle: Precluding paging promotes peak performance and prevents perplexity.

Modern operating systems feature virtual memory that strives to appear both larger than installed DRAM (which is small) and faster than installed storage devices (which are slow). As a program’s memory footprint approaches the capacity of DRAM, the virtual memory system transparently pages (moves) the program’s data between DRAM and a swap area on a storage device. Paging can degrade performance mildly or severely, depending on the program’s memory access patterns. Random accesses to large data structures can trigger excessive paging and dramatic slowdown. Unfortunately, the hash tables beneath AWK’s signature associative arrays inherently require random memory accesses, so large associative arrays can be problematic.

Persistence changes the rules in our favor: The OS pages data to pm-gawk’s heap file instead of the swap area. This won’t help performance much if the heap file resides in a conventional storage-backed file system. On Unix-like systems, however, we may place the heap file in a DRAM-backed file system such as /dev/shm/, which entirely prevents paging to slow storage devices. Temporarily placing the heap file in such a file system is a reasonable expedient, with two caveats: First, keep in mind that DRAM-backed file systems perish when the machine reboots or crashes, so you must copy the heap file to a conventional storage-backed file system when your computation is done. Second, pm-gawk’s memory footprint can’t exceed available DRAM if you place the heap file in a DRAM-backed file system.

Tuning OS paging parameters may improve performance if you decide to run pm-gawk with a heap file in a conventional storage-backed file system. Some OSes have unhelpful default habits regarding modified (“dirty”) memory backed by files. For example, the OS may write dirty memory pages to the heap file periodically and/or when the OS believes that “too much” memory is dirty. Such “eager” writeback can degrade performance noticeably and brings no benefit to pm-gawk. Fortunately some OSes allow paging defaults to be over-ridden so that writeback is “lazy” rather than eager. For Linux see the discussion of the dirty_* parameters at https://www.kernel.org/doc/html/latest/admin-guide/sysctl/vm.html. Changing these parameters can prevent wasteful eager paging:²

        $ echo 100    | sudo tee /proc/sys/vm/dirty_background_ratio
        $ echo 100    | sudo tee /proc/sys/vm/dirty_ratio
        $ echo 300000 | sudo tee /proc/sys/vm/dirty_expire_centisecs
        $ echo 50000  | sudo tee /proc/sys/vm/dirty_writeback_centisecs

Tuning paging parameters can help non-persistent gawk as well as pm-gawk. [Disclaimer: OS tuning is an occult art, and your mileage may vary.]

4.3 Sparse Heap Files

To be frugal with storage resources, pm-gawk’s heap file should be created as a sparse file: a file whose logical size is larger than its storage resource footprint. Modern file systems support sparse files, which are easy to create using the truncate tool shown in our examples.

Let’s first create a conventional non-sparse file using echo:

        $ echo hi > dense
        $ ls -l dense
        -rw-rw-r--. 1 me me 3 Aug  5 23:08 dense
        $ du -h dense
        4.0K    dense

The ls utility reports that file dense is three bytes long (two for the letters in “hi” plus one for the newline). The du utility reports that this file consumes 4 KiB of storage—one block of disk, as small as a non-sparse file’s storage footprint can be. Now let’s use truncate to create a logically enormous sparse file and check its physical size:

        $ truncate -s 1T sparse
        $ ls -l sparse
        -rw-rw-r--. 1 me me 1099511627776 Aug  5 22:33 sparse
        $ du -h sparse
        0       sparse

Whereas ls reports the logical file size that we expect (one TiB or 2 raised to the power 40 bytes), du reveals that the file occupies no storage whatsoever. The file system will allocate physical storage resources beneath this file as data is written to it; reading unwritten regions of the file yields zeros.

The “pay as you go” storage cost of sparse files offers both convenience and control for pm-gawk users. If your file system supports sparse files, go ahead and create lavishly capacious heap files for pm-gawk. Their logical size costs nothing and persistent memory allocation within pm-gawk won’t fail until physical storage resources beneath the file system are exhausted. But if instead you want to prevent a heap file from consuming too much storage, simply set its initial size to whatever bound you wish to enforce; it won’t eat more disk than that. Copying sparse files with GNU cp creates sparse copies by default.

File-system encryption can preclude sparse files: If the cleartext of a byte offset range within a file is all zero bytes, the corresponding ciphertext probably shouldn’t be all zeros! Encrypting at the storage layer instead of the file system layer may offer acceptable security while still permitting file systems to implement sparse files.

Sometimes you might prefer a dense heap file backed by pre-allocated storage resources, for example to increase the likelihood that pm-gawk’s internal memory allocation will succeed until the persistent heap occupies the entire heap file. The fallocate utility will do the trick:

        $ fallocate -l 1M mibi
        $ ls -l mibi
        -rw-rw-r--. 1 me me 1048576 Aug  5 23:18 mibi
        $ du -h mibi
        1.0M    mibi

We get the MiB we asked for, both logically and physically.

4.4 Persistence versus Durability

Arguably the most important general guideline for good performance in computer systems is, “pay only for what you need.”³ To apply this maxim to pm-gawk we must distinguish two concepts that are frequently conflated: persistence and durability.⁴ (A third logically distinct concept is the subject of Data Integrity.)

Persistent data outlive the processes that access them, but don’t necessarily last forever. For example, as explained in man mq_overview, message queues are persistent because they exist until the system shuts down. Durable data reside on a physical medium that retains its contents even without continuously supplied power. For example, hard disk drives and solid state drives store durable data. Confusion arises because persistence and durability are often correlated: Data in ordinary file systems backed by HDDs or SSDs are typically both persistent and durable. Familiarity with fsync() and msync() might lead us to believe that durability is a subset of persistence, but in fact the two characteristics are orthogonal: Data in the swap area are durable but not persistent; data in DRAM-backed file systems such as /dev/shm/ are persistent but not durable.

Durability often costs more than persistence, so performance-conscious pm-gawk users pay the added premium for durability only when persistence alone is not sufficient. Two ways to avoid unwanted durability overheads were discussed in Virtual Memory and Big Data: Place pm-gawk’s heap file in a DRAM-backed file system, or disable eager writeback to the heap file. Expedients such as these enable you to remove durability overheads from the critical path of multi-stage data analyses even when you want heap files to eventually be durable: Allow pm-gawk to run at full speed with persistence alone; force the heap file to durability (using the cp and sync utilities as necessary) after output has been emitted to the next stage of the analysis and the pm-gawk process using the heap has terminated.

Experimenting with synthetic data builds intuition for how persistence and durability affect performance. You can write a little AWK or C program to generate a stream of random text, or just cobble together a quick and dirty generator on the command line:

        $ openssl rand --base64 1000000 | tr -c a-zA-Z '\n' > random.dat

Varying the size of random inputs can, for example, find where performance “falls off the cliff” as pm-gawk’s memory footprint exceeds the capacity of DRAM and paging begins.

Experiments require careful methodology, especially when the heap file is in a storage-backed file system. Overlooking the file system’s DRAM cache can easily misguide interpretation of results and foil repeatability. Fortunately Linux allows us to invalidate the file system cache and thus mimic a “cold start” condition resembling the immediate aftermath of a machine reboot. Accesses to ordinary files on durable storage will then be served from the storage devices, not from cache. Read about sync and /proc/sys/vm/drop_caches at
https://www.kernel.org/doc/html/latest/admin-guide/sysctl/vm.html.

4.5 Experiments

The C-shell (csh) script listed below illustrates concepts and implements tips presented in this chapter. It produced the results discussed in Results in roughly 20 minutes on an aging laptop. You can cut and paste the code listing below into a file, or download it from http://web.eecs.umich.edu/~tpkelly/pma/.

The script measures the performance of four different ways to support word frequency queries over a text corpus: The naïve approach of reading the corpus into an associative array for every query; manually dumping a text representation of the word-frequency table and manually loading it prior to a query; using gawk’s rwarray extension to dump and load an associative array; and using pm-gawk to maintain a persistent associative array.

Comments at the top explain prerequisites. Lines 8–10 set input parameters: the directory where tests are run and where files including the heap file are held, the off-the-shelf timer used to measure run times and other performance characteristics such as peak memory usage, and the size of the input. The default input size results in pm-gawk memory footprints under 3 GiB, which is large enough for interesting results and small enough to fit in DRAM and avoid paging on today’s computers. Lines 13–14 define a homebrew timer.

Two sections of the script are relevant if the default run directory is changed from /dev/shm/ to a directory in a conventional storage-backed file system: Lines 15–17 define the mechanism for clearing file data cached in DRAM; lines 23–30 set Linux kernel parameters to discourage eager paging.

Lines 37–70 spit out, compile, and run a little C program to generate a random text corpus. This program is fast, flexible, and deterministic, generating the same random output given the same parameters.

Lines 71–100 run the four different AWK approaches on the same random input, reporting separately the time to build and to query the associative array containing word frequencies.

#!/bin/csh -f
# Set PMG envar to path of pm-gawk executable and AWKLIBPATH                        #   2
#    to find rwarray.so                                                             #   3
# Requires "sudo" to work; consider this for /etc/sudoers file:                     #   4
#    Defaults:youruserid    !authenticate                                           #   5
echo 'begin:      ' `date` `date +%s`                                               #   6
unsetenv GAWK_PERSIST_FILE  # disable persistence until wanted                      #   7
set dir = '/dev/shm'        # where heap file et al. will live                      #   8
set tmr = '/usr/bin/time'   # can also use shell built-in "time"                    #   9
set isz = 1073741824        # input size; 1 GiB                                     #  10
# set isz = 100000000       # small input for quick testing                         #  11
cd $dir   # tick/tock/tyme below are homebrew timer, good within ~2ms               #  12
alias tick 'set t1 = `date +%s.%N`' ; alias tock 'set t2 = `date +%s.%N`'           #  13
alias tyme '$PMG -v t1=$t1 -v t2=$t2 "BEGIN{print t2-t1}"'                          #  14
alias tsync 'tick ; sync ; tock ; echo "sync time:  " `tyme`'                       #  15
alias drop_caches 'echo 3 | sudo tee /proc/sys/vm/drop_caches'                      #  16
alias snd 'tsync; drop_caches'                                                      #  17
echo "pm-gawk:     $PMG" ; echo 'std gawk:   ' `which gawk`                         #  18
echo "run dir:     $dir" ; echo 'pwd:        ' `pwd`                                #  19
echo 'dir content:'      ; ls -l $dir |& $PMG '{print "             " $0}'          #  20
echo 'timer:      ' $tmr ; echo 'AWKLIBPATH: ' $AWKLIBPATH                          #  21

echo 'OS params:' ; set vm = '/proc/sys/vm/dirty'                                   #  22
sudo sh -c "echo 100     > ${vm}_background_ratio"     # restore these              #  23
sudo sh -c "echo 100     > ${vm}_ratio"                # paging params              #  24
sudo sh -c "echo 1080000 > ${vm}_expire_centisecs"     # to defaults                #  25
sudo sh -c "echo 1080000 > ${vm}_writeback_centisecs"  # if necessary               #  26
foreach d ( ${vm}_background_ratio  ${vm}_ratio \                                   #  27
            ${vm}_expire_centisecs  ${vm}_writeback_centisecs )                     #  28
    printf "             %-38s %7d\n" $d `cat $d`                                   #  29
end                                                                                 #  30
tick ; tock ; echo 'timr ovrhd: ' `tyme` 's (around 2ms for TK)'                    #  31
tick ; $PMG 'BEGIN{print "pm-gawk?     yes"}'                                       #  32
tock ; echo 'pmg ovrhd:  ' `tyme` 's (around 4-5 ms for TK)'                        #  33
set inp = 'input.dat'                                                               #  34
echo 'input size  ' $isz                                                            #  35
echo "input file:  $inp"                                                            #  36
set rg = rgen  # spit out and compile C program to generate random inputs           #  37
rm -f $inp  $rg.c $rg                                                               #  38
cat <<EOF > $rg.c                                                                   #  39
// generate N random words, one per line, no blank lines                            #  40
// charset is e.g. 'abcdefg@' where '@' becomes newline                             #  41
#include <stdio.h>                                                                  #  42
#include <stdlib.h>                                                                 #  43
#include <string.h>                                                                 #  44
#define RCH     c = a[rand() % L];                                                  #  45
#define PICK    do { RCH } while (0)                                                #  46
#define PICKCH  do { RCH } while (c == '@')                                         #  47
#define FP(...) fprintf(stderr, __VA_ARGS__)                                        #  48
int main(int argc, char *argv[]) {                                                  #  49
  if (4 != argc) {                                                                  #  50
    FP("usage:  %s  charset  N  seed\n",                                            #  51
                    argv[0]);   return 1; }                                         #  52
  char c, *a =      argv[1];    size_t L = strlen(a);                               #  53
  long int N = atol(argv[2]);                                                       #  54
  srand(       atol(argv[3]));                                                      #  55
  if (2 > N) { FP("N == %ld < 2\n", N); return 2; }                                 #  56
  PICKCH;                                                                           #  57
  for (;;) {                                                                        #  58
    if (2 == N) { PICKCH; putchar(c); putchar('\n'); break; }                       #  59
    if ('@' == c) { putchar('\n'); PICKCH; }                                        #  60
    else          { putchar( c  ); PICK;   }                                        #  61
    if (0 >= --N) break;                                                            #  62
  }                                                                                 #  63
}                                                                                   #  64
EOF                                                                                 #  65
gcc -std=c11 -Wall -Wextra -O3 -o $rg $rg.c                                         #  66
set t = '@@@@@@@' ; set c = "abcdefghijklmnopqrstuvwxyz$t$t$t$t$t$t"                #  67
tick ; ./$rg "$c" $isz 47 > $inp ; tock ; echo 'gen time:   ' `tyme`                #  68
echo "input file:  $inp"                                                            #  69
echo 'input wc:   ' `wc < $inp` ; echo 'input uniq: ' `sort -u $inp | wc`           #  70

snd ############################################################################    #  71
tick ; $tmr $PMG '{n[$1]++}END{print "output: " n["foo"]}' $inp                     #  72
tock ; echo 'T naive O(N):          ' `tyme` ; echo ''                              #  73
rm -f rwa                                                                           #  74
snd ############################################################################    #  75
echo ''                                                                             #  76
tick ; $tmr $PMG -l rwarray '{n[$1]++}END{print "writea",writea("rwa",n)}' $inp     #  77
tock ; echo 'T rwarray build O(N):  ' `tyme` ; echo ''                              #  78
snd  # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #    #  79
tick ; $tmr $PMG -l rwarray 'BEGIN{print "reada",reada("rwa",n); \                  #  80
                                   print "output: " n["foo"]}'                      #  81
tock ; echo 'T rwarray query O(W):   ' `tyme` ; echo ''                             #  82
rm -f ft                                                                            #  83
snd ############################################################################    #  84
tick ; $tmr $PMG '{n[$1]++}END{for(w in n)print n[w], w}' $inp > ft                 #  85
tock ; echo 'T freqtbl build O(N):  ' `tyme` ; echo ''                              #  86
snd  # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #    #  87
tick ; $tmr $PMG '{n[$2] = $1}END{print "output: " n["foo"]}' ft                    #  88
tock ; echo 'T freqtbl query O(W):   ' `tyme` ; echo ''                             #  89
rm -f heap.pma                                                                      #  90
snd ############################################################################    #  91
truncate -s 3G heap.pma  # enlarge if needed                                        #  92
setenv GAWK_PERSIST_FILE heap.pma                                                   #  93
tick ; $tmr $PMG '{n[$1]++}' $inp                                                   #  94
tock ; echo 'T pm-gawk build O(N):  ' `tyme` ; echo ''                              #  95
snd  # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #    #  96
tick ; $tmr $PMG 'BEGIN{print "output: " n["foo"]}'                                 #  97
tock ; echo 'T pm-gawk query O(1):    ' `tyme` ; echo ''                            #  98
unsetenv GAWK_PERSIST_FILE                                                          #  99
snd ############################################################################    # 100
echo 'Note:  all output lines above should be identical' ; echo ''                  # 101
echo 'dir content:' ; ls -l $dir |& $PMG '{print "              " $0}'              # 102
echo '' ; echo 'storage footprints:'                                                # 103
foreach f ( rwa ft heap.pma )  # compression is very slow, so we comment it out     # 104
    echo "    $f " `du -BK $dir/$f` # `xz --best < $dir/$f | wc -c` 'bytes xz'      # 105
end                                                                                 # 106
echo '' ; echo 'end:        ' `date` `date +%s` ; echo ''                           # 107

4.6 Results

Running the script of Experiments with default parameters on an aging laptop yielded the results summarized in the table below. More extensive experiments, not reported here, yield qualitatively similar results. Keep in mind that performance measurements are often sensitive to seemingly irrelevant factors. For example, the program that runs first may have the advantage of a cooler CPU; later contestants may start with a hot CPU and consequent clock throttling by a modern processor’s thermal regulation apparatus. Very generally, performance measurement is a notoriously tricky business. For scripting, whose main motive is convenience rather than speed, the proper role for performance measurements is to qualitatively test hypotheses such as those that follow from asymptotic analyses and to provide a rough idea of when various approaches are practical.

                            run time      peak memory    intermediate
        AWK script            (sec)      footprint (K)    storage (K)

        naive         O(N)   242.132       2,081,360           n/a
        rwarray build O(N)   250.288       2,846,868         156,832
        rwarray query O(W)    11.653       2,081,444
        freqtbl build O(N)   288.408       2,400,120          69,112
        freqtbl query O(W)    11.624       2,336,616
        pm-gawk build O(N)   251.946       2,079,520       2,076,608
        pm-gawk query O(1)     0.026           3,252

The results are consistent with the asymptotic analysis of Constant-Time Array Access. All four approaches require roughly four minutes to read the synthetic input data. The naïve approach must do this every time it performs a query, but the other three build an associative array to support queries and separately serve such queries. The freqtbl and rwarray approaches build an associative array of word frequencies, serialize it to an intermediate file, and then read the entire intermediate file prior to serving queries; the former does this manually and the latter uses a gawk extension. Both can serve queries in roughly ten seconds, not four minutes. As we’d expect from the asymptotic analysis, performing work proportional to the number of words is preferable to work proportional to the size of the raw input corpus: O(W) time is faster than O(N). And as we’d expect, pm-gawk’s constant-time queries are faster still, by roughly two orders of magnitude. For the computations considered here, pm-gawk makes the difference between blink-of-an-eye interactive queries and response times long enough for the user’s mind to wander.

Whereas freqtbl and rwarray reconstruct an associative array prior to accessing an individual element, pm-gawk stores a ready-made associative array in persistent memory. That’s why its intermediate file (the heap file) is much larger than the other two intermediate files, why the heap file is nearly as large as pm-gawk’s peak memory footprint while building the persistent array, and why its memory footprint is very small while serving a query that accesses a single array element. The upside of the large heap file is O(1) access instead of O(W)—a classic time-space tradeoff. If storage is a scarce resource, all three intermediate files can be compressed, freqtbl by a factor of roughly 2.7, rwarray by roughly 5.6x, and pm-gawk by roughly 11x using xz. Compression is CPU-intensive and slow, another time-space tradeoff.