prac/repro/repro

#!/bin/bash

# Reproduce the PRAC experiments from our paper:

# Sajin Sasy, Adithya Vadapalli, Ian Goldberg. PRAC: Round-Efficient
# 3-Party MPC for Dynamic Data Structures

# cd into the directory containing this script (from the bash faq 028)
if [[ $BASH_SOURCE = */* ]]; then
  cd -- "${BASH_SOURCE%/*}/" || exit
fi

# Allow running only subsets of the experiment suite.  Valid values are
# "test", "all", "none".  ("none" is useful if you just want to re-parse
# the output of existing logs.)  You can also say "single" followed by
# all the arguments to "run" (below) to run a single experiment; for
# example:
# ./repro single read 20 1
if [ "$1" = "" ]; then
    whichexps="test"
else
    whichexps="$1"
fi

# The number of operations per run; the graphs in the paper use 3
if [ "$whichexps" = "single" -o "$2" = "" ]; then
    # If there's an explicit experiment on the command line, don't read
    # the next argument as the number of operations.  $numops will be
    # ignored, anyway, since it will be specified as part of the
    # command.
    numiters=3
else
    numiters="$2"
fi

# The maximum amount of memory to use (in GB).  Set the environment
# variable PRAC_MAXGB to increase it beyond 16 (don't set it lower
# than 16).  if you're using NUMA, where different parties don't all
# share the same memory pool, then instead set:
# - PRAC_P0_MAXGB to the max GB of memory to use in each NUMA node, if
#   you have at least three NUMA nodes, and each player gets their own
#   numa node
# - PRAC_P02_MAXGB to the max GB of memory to use in each NUMA node, if
#   you have two numa nodes, and P0 and P2 are in one, and P1 is in the
#   other

# P0 and P1 always use the same amount of memory.

# For preprocessing, in the event the total memory usage exceeds 16GB,
# P2's memory usage is no more than 1% of P0's.

# There's about 5 MB overhead when preprocessing.

if [ "$PRAC_P0_MAXGB" != "" ]; then
    # Each party uses its own NUMA memory pool
    max_preproc_p0_mb=$((PRAC_P0_MAXGB*1000-5))
    max_mb=$((PRAC_P0_MAXGB*3000))
elif [ "$PRAC_P02_MAXGB" != "" ]; then
    # P0 and P2 share a NUMA memory pool, P1 gets its own
    max_preproc_p0_mb=$((PRAC_P02_MAXGB*990-5))
    max_mb=$((PRAC_P02_MAXGB*1990))
elif [ "$PRAC_MAXGB" -gt 16 ]; then
    # All parties share one memory pool
    max_preproc_p0_mb=$((PRAC_MAXGB*497-5))
    max_mb=$((PRAC_MAXGB*1000))
else
    # Default to PRAC_MAXGB=16
    export PRAC_MAXGB=16
    max_preproc_p0_mb=$((PRAC_MAXGB*497-5))
    max_mb=$((PRAC_MAXGB*1000))
fi

logname='log'

# Run one experiment
# The arguments are just the arguments to run-experiment
run() {
    now=`date`
    echo "$now: Running $* ..."
    logfile="prac_${logname}.out${LOGSUFFIX}"
    mkdir -p data
    echo "Max MB: $max_mb" >> data/$logfile
    ../docker/run-experiment $* >> data/$logfile
}

# Run preprocessing, being careful to not exceed available memory. We
# typically preprocess a bunch of small resources that will easily fit
# in memory, as well as a number of instances of one large resource.  We
# create the small resources and as many of the instances of the large
# resource first we can (with -p), and then more batches of instances of
# the large resource (with -a, which means to append the newly created
# resources to the storage file, rather than overwriting old ones).

# Arguments:
# $1: a string (containing embedded whitespace) of the required small
#     resources
# $2: the mb required by P0 to create the small resources
# $3: the name of the large resource
# $4: the number of instances of the large resource we want
# $5: the mb required by P0 to create one instance of the large resource
preproc() {
    small_mb=$2
    large_left=$4
    large_mb_each=$5
    # the maximum number of instances of the large resource we can
    # create along with the small ones
    num_large=$(( (max_preproc_p0_mb-small_mb)/large_mb_each ))
    if [ $num_large -gt $large_left ]; then
        num_large=$large_left
    fi
    run -p $1 ${3}:${num_large}
    large_left=$((large_left-num_large))
    # the maximum number of instances of the large resource we can
    # create in a batch on their own
    max_large_batch=$((max_preproc_p0_mb/large_mb_each))
    if [ $max_large_batch = 0 ]; then
        echo "Not enough memory"
        return
    fi
    while [ $large_left -gt 0 ]; do
        num_large=$large_left
        if [ $num_large -gt $max_large_batch ]; then
            num_large=$max_large_batch
        fi
        run -a ${3}:${num_large}
        large_left=$((large_left-num_large))
    done
}

# The number of MB needed for P0 to create different kinds of resources
# of different sizes
declare -A rMB
rMB=([16]=6 [17]=11 [18]=20 [19]=38 [20]=76 [21]=150 [22]=297 [23]=593 [24]=1182 [25]=2361 [26]=4720 [27]=9440 [28]=18876 [29]=37755 [30]=75500)
declare -A r2MB
r2MB=([16]=9 [18]=32 [20]=125 [22]=494 [24]=1970 [26]=7870 [28]=31470 [30]=125850)
declare -A iMB
iMB=([15]=4 [17]=12 [19]=41 [21]=152 [23]=595 [25]=2364 [27]=9441 [29]=37753)
declare -A i3MB
i3MB=([15]=6 [17]=20 [19]=72 [21]=286 [23]=968 [25]=3955 [27]=15800 [29]=62950)

# Parse the output logs.  We run this in the docker in case you don't
# have perl installed on the host.
# Arguments: a list of logfiles
parse() {
    if [ "$PRAC_PARSE_HOST" = "1" ]; then
        ./parse_logs $*
    else
        cat $* | docker exec -w /root/prac/repro -i prac_p0 ./parse_logs
    fi
}

# A very small kick-the-tires test to ensure everything compiled and
# built properly
if [ "$whichexps" = "test" ]; then
    echo "Running test experiment..."
    logname='test'
    run -o read 16 1
    echo
    echo "# Test output"
    echo
    parse data/prac_test.out${LOGSUFFIX}
    echo
    echo "# End test output"
    echo
    exit
fi

# Be able to run a single experiment specified on the command line
if [ "$whichexps" = "single" ]; then
    echo "Running single experiment..."
    shift
    run $*
    exit
fi

now=`date`
echo "$now: Starting experiments"

if [ "$whichexps" = "fig6" -o "$whichexps" = "all" ]; then
    echo "Running Figure 6 experiments..."
    for iter in $(seq 1 $numiters); do
        # Figure 6(a)
        logname='fig6a'
        for num in 16 32 64 128 256 512 1024 2048; do
            preproc "" 0 r20 $num 76
            run read 20 $num
        done
        # Figure 6(b,c)
        logname='fig6bc'
        for size in 16 18 20 22 24 26 28 30; do
            preproc "" 0 r${size} 10 ${rMB[$size]}
            run read $size 10
        done
    done
fi

if [ "$whichexps" = "fig7" -o "$whichexps" = "all" ]; then
    echo "Running Figure 7 experiments..."
    for iter in $(seq 1 $numiters); do
        # Figure 7(a)
        logname='fig7a'
        for num in 4 8 16 32 64; do
            preproc "c:$((num*20))" 10 i19 $num 41
            run bsearch 20 $num
        done
        for num in 4 8 16 32 64; do
            preproc "m:$((num*20)) c:$((num*20))" 20 r20 $((num*20)) 76
            run bbsearch 20 $num
        done
        # Figure 7(b,c)
        logname='fig7bc'
        for size in 16 18 20 22 24 26 28; do
            preproc "c:${size}" 1 i$((size-1)) 1 ${iMB[$((size-1))]}
            run bsearch $size 1
        done
        for size in 16 18 20 22 24 26 28; do
            preproc "m:${size} c:${size}" 1 r${size} ${size} ${rMB[$size]}
            run bbsearch $size 1
        done
    done
fi

if [ "$whichexps" = "fig8" -o "$whichexps" = "all" ]; then
    echo "Running Figure 8 experiments..."
    for iter in $(seq 1 $numiters); do
        # Figure 8(a)
        logname='fig8a'
        for num in 4 8 16 32; do
            preproc "m:$((num*57)) a:$((num*19)) s:$((num*18)) c:$((num*38))" 35 i19.3 ${num} 68
            run heap -m 20 -d 20 -i 0 -e ${num} -opt 1 -s 0
        done
        for num in 4 8 16 32; do
            preproc "m:$((num*57)) a:$((num*19)) s:$((num*18)) c:$((num*38))" 35 r20 ${num} 76
            run heap -m 20 -d 20 -i 0 -e ${num} -opt 0 -s 0
        done
        # Figure 8(b,c)
        logname='fig8bc'
        for size in 16 18 20 22 24 26 28 30; do
            preproc "m:$((size*3-3)) a:$((size-1)) s:$((size-2)) c:$((size*2-2))" 3 i$((size-1)).3 1 ${i3MB[$((size-1))]}
            run heap -m ${size} -d ${size} -i 0 -e 1 -opt 1 -s 0
        done
        for size in 16 18 20 22 24 26 28 30; do
            preproc "m:$((size*3-3)) a:$((size-1)) s:$((size-2)) c:$((size*2-2))" 3 r${size} $((size*6-12)) ${rMB[$size]}
            run heap -m ${size} -d ${size} -i 0 -e 1 -opt 0 -s 0
        done
    done
fi

if [ "$whichexps" = "tab3" -o "$whichexps" = "all" ]; then
    echo "Running Table 3 experiments..."
    for iter in $(seq 1 $numiters); do
        # Table 3
        logname='tab3'
        for size in 16 20 24; do
            run -p m:$((size*2-1)) r5:1 i4:1 c:5
            run heap -m ${size} -d $((size-1)) -i 1 -e 0 -opt 1 -s 0
            run -p m:$((size-1)) c:$((size-1))
            run heap -m ${size} -d $((size-1)) -i 1 -e 0 -opt 0 -s 0
        done
    done
fi

if [ "$whichexps" = "tab4" -o "$whichexps" = "all" ]; then
    echo "Running Table 4 experiments..."
    for iter in $(seq 1 $numiters); do
        # Table 4
        logname='tab4'
        preproc "a:8 s:171 c:50" 3 r17 28 ${rMB[17]}
        run avl -m 16 -i 1 -e 0 -opt 1 -s 0
        preproc "a:10 s:201 c:60" 3 r21 33 ${rMB[21]}
        run avl -m 20 -i 1 -e 0 -opt 1 -s 0
        preproc "a:12 s:237 c:72" 3 r25 39 ${rMB[25]}
        run avl -m 24 -i 1 -e 0 -opt 1 -s 0
        preproc "m:1 a:30 s:867 r16.2:2 c:72" 26 r16 72 ${rMB[16]}
        run avl -m 16 -i 0 -e 1 -opt 1 -s 0
        preproc "m:1 a:36 s:1047 r20.2:2 c:87" 263 r20 87 ${rMB[20]}
        run avl -m 20 -i 0 -e 1 -opt 1 -s 0
        preproc "m:1 a:43 s:1263 r24.2:2 c:105" 3950 r24 105 ${rMB[24]}
        run avl -m 24 -i 0 -e 1 -opt 1 -s 0
    done
fi

if [ "$whichexps" = "heapsampler" -o "$whichexps" = "all" ]; then
    echo "Running heap sampler experiments..."
    for iter in $(seq 1 $numiters); do
        # Table 4
        logname='heapsampler'
        run -p m:1033 h:7497 a:3 s:118 r1:1 r2:6 r3:57 i1:6 i2:57 i1.3:2 i2.3:4 i3.3:57 c:610
        run heapsampler 64 10
        run -p m:2121 h:15561 a:6 s:246 r1:1 r2:6 r3:121 i1:6 i2:121 i1.3:2 i2.3:4 i3.3:121 c:1250
        run heapsampler 128 10
        run -p m:4297 h:31689 a:12 s:502 r1:1 r2:6 r3:249 i1:6 i2:249 i1.3:2 i2.3:4 i3.3:249 c:2530
        run heapsampler 256 10
        run -p m:8649 h:63945 a:24 s:1014 r1:1 r2:6 r3:505 i1:6 i2:505 i1.3:2 i2.3:4 i3.3:505 c:5090
        run heapsampler 512 10
        run -p m:17353 h:128457 a:48 s:2038 r1:1 r2:6 r3:1017 i1:6 i2:1017 i1.3:2 i2.3:4 i3.3:1017 c:10210
        run heapsampler 1024 10
        run -p m:34761 h:257481 a:96 s:4086 r1:1 r2:6 r3:2041 i1:6 i2:2041 i1.3:2 i2.3:4 i3.3:2041 c:20450
        run heapsampler 2048 10
        run -p m:1278 h:6237 a:4 s:167 r1:1 r2:6 r3:57 i1:6 i2:57 i1.3:2 i2.3:4 i3.3:8 i4.3:49 c:708
        run heapsampler 64 30
        run -p m:2686 h:14301 a:8 s:359 r1:1 r2:6 r3:121 i1:6 i2:121 i1.3:2 i2.3:4 i3.3:8 i4.3:113 c:1476
        run heapsampler 128 30
        run -p m:5502 h:30429 a:16 s:743 r1:1 r2:6 r3:249 i1:6 i2:249 i1.3:2 i2.3:4 i3.3:8 i4.3:241 c:3012
        run heapsampler 256 30
        run -p m:11134 h:62685 a:32 s:1511 r1:1 r2:6 r3:505 i1:6 i2:505 i1.3:2 i2.3:4 i3.3:8 i4.3:497 c:6084
        run heapsampler 512 30
        run -p m:22398 h:127197 a:64 s:3047 r1:1 r2:6 r3:1017 i1:6 i2:1017 i1.3:2 i2.3:4 i3.3:8 i4.3:1009 c:12228
        run heapsampler 1024 30
        run -p m:44926 h:256221 a:128 s:6119 r1:1 r2:6 r3:2041 i1:6 i2:2041 i1.3:2 i2.3:4 i3.3:8 i4.3:2033 c:24516
        run heapsampler 2048 30
        run -p m:3496 h:9891 a:11 s:521 r1:1 r2:6 r3:121 i1:6 i2:121 i1.3:2 i2.3:4 i3.3:8 i4.3:16 i5.3:32 i6.3:65 c:1800
        run heapsampler 128 100
        run -p m:7592 h:26019 a:23 s:1161 r1:1 r2:6 r3:249 i1:6 i2:249 i1.3:2 i2.3:4 i3.3:8 i4.3:16 i5.3:32 i6.3:193 c:3848
        run heapsampler 256 100
        run -p m:15784 h:58275 a:47 s:2441 r1:1 r2:6 r3:505 i1:6 i2:505 i1.3:2 i2.3:4 i3.3:8 i4.3:16 i5.3:32 i6.3:449 c:7944
        run heapsampler 512 100
        run -p m:32168 h:122787 a:95 s:5001 r1:1 r2:6 r3:1017 i1:6 i2:1017 i1.3:2 i2.3:4 i3.3:8 i4.3:16 i5.3:32 i6.3:961 c:16136
        run heapsampler 1024 100
        run -p m:64936 h:251811 a:191 s:10121 r1:1 r2:6 r3:2041 i1:6 i2:2041 i1.3:2 i2.3:4 i3.3:8 i4.3:16 i5.3:32 i6.3:1985 c:32520
        run heapsampler 2048 100
        run -p m:18994 h:45675 a:57 s:3083 r1:1 r2:6 r3:120 r4:385 i1:6 i2:120 i3:385 i1.3:2 i2.3:4 i3.3:8 i4.3:16 i5.3:32 i6.3:64 i7.3:128 i8.3:257 c:9613
        run heapsampler 512 300
        run -p m:40498 h:110187 a:121 s:6667 r1:1 r2:6 r3:120 r4:897 i1:6 i2:120 i3:897 i1.3:2 i2.3:4 i3.3:8 i4.3:16 i5.3:32 i6.3:64 i7.3:128 i8.3:769 c:20365
        run heapsampler 1024 300
        run -p m:83506 h:239211 a:249 s:13835 r1:1 r2:6 r3:120 r4:1921 i1:6 i2:120 i3:1921 i1.3:2 i2.3:4 i3.3:8 i4.3:16 i5.3:32 i6.3:64 i7.3:128 i8.3:1793 c:41869
        run heapsampler 2048 300
    done
fi

now=`date`
echo "$now: Experiments complete"

# If you specified a custom log suffix, you're going to be parsing the
# outputs differently.
if [ "$LOGSUFFIX" = "" ]; then

parse data/*.out > data/prac.dat

echo
echo "# Figure 6(a)"
egrep 'PRACOnln read 20 (16|32|64|128|256|512|1024|2048) .* s$' data/prac.dat | sort -k4 -n
echo
egrep 'PRACTotl read 20 (16|32|64|128|256|512|1024|2048) .* s$' data/prac.dat | sort -k4 -n
echo
echo "# Figure 6(b)"
egrep 'PRACOnln read ([0-9]+) 10 .* s$' data/prac.dat | sort -k3 -n
echo
egrep 'PRACTotl read ([0-9]+) 10 .* s$' data/prac.dat | sort -k3 -n
echo
echo "# Figure 6(c)"
egrep 'PRACOnln read ([0-9]+) 10 .* KiB$' data/prac.dat | sort -k3 -n
echo
egrep 'PRACTotl read ([0-9]+) 10 .* KiB$' data/prac.dat | sort -k3 -n
echo
echo "# Figure 7(a)"
egrep 'BasicPRACOnln bsearch 20 (4|8|16|32|64) .* s$' data/prac.dat | sort -k4 -n
echo
egrep 'BasicPRACTotl bsearch 20 (4|8|16|32|64) .* s$' data/prac.dat | sort -k4 -n
echo
egrep 'OptPRACOnln bsearch 20 (4|8|16|32|64) .* s$' data/prac.dat | sort -k4 -n
echo
egrep 'OptPRACTotl bsearch 20 (4|8|16|32|64) .* s$' data/prac.dat | sort -k4 -n
echo
echo "# Figure 7(b)"
egrep 'BasicPRACOnln bsearch ([0-9]+) 1 .* s$' data/prac.dat | sort -k3 -n
echo
egrep 'BasicPRACTotl bsearch ([0-9]+) 1 .* s$' data/prac.dat | sort -k3 -n
echo
egrep 'OptPRACOnln bsearch ([0-9]+) 1 .* s$' data/prac.dat | sort -k3 -n
echo
egrep 'OptPRACTotl bsearch ([0-9]+) 1 .* s$' data/prac.dat | sort -k3 -n
echo
echo "# Figure 7(c)"
egrep 'BasicPRACOnln bsearch ([0-9]+) 1 .* KiB$' data/prac.dat | sort -k3 -n
echo
egrep 'BasicPRACTotl bsearch ([0-9]+) 1 .* KiB$' data/prac.dat | sort -k3 -n
echo
egrep 'OptPRACOnln bsearch ([0-9]+) 1 .* KiB$' data/prac.dat | sort -k3 -n
echo
egrep 'OptPRACTotl bsearch ([0-9]+) 1 .* KiB$' data/prac.dat | sort -k3 -n
echo
echo "# Figure 8(a)"
egrep 'BasicPRACOnln heapExt 20 (4|8|16|32) .* s$' data/prac.dat | sort -k4 -n
echo
egrep 'BasicPRACTotl heapExt 20 (4|8|16|32) .* s$' data/prac.dat | sort -k4 -n
echo
egrep 'OptPRACOnln heapExt 20 (4|8|16|32) .* s$' data/prac.dat | sort -k4 -n
echo
egrep 'OptPRACTotl heapExt 20 (4|8|16|32) .* s$' data/prac.dat | sort -k4 -n
echo
echo "# Figure 8(b)"
egrep 'BasicPRACOnln heapExt ([0-9]+) 1 .* s$' data/prac.dat | sort -k3 -n
echo
egrep 'BasicPRACTotl heapExt ([0-9]+) 1 .* s$' data/prac.dat | sort -k3 -n
echo
egrep 'OptPRACOnln heapExt ([0-9]+) 1 .* s$' data/prac.dat | sort -k3 -n
echo
egrep 'OptPRACTotl heapExt ([0-9]+) 1 .* s$' data/prac.dat | sort -k3 -n
echo
echo "# Figure 8(c)"
egrep 'BasicPRACOnln heapExt ([0-9]+) 1 .* KiB$' data/prac.dat | sort -k3 -n
echo
egrep 'BasicPRACTotl heapExt ([0-9]+) 1 .* KiB$' data/prac.dat | sort -k3 -n
echo
egrep 'OptPRACOnln heapExt ([0-9]+) 1 .* KiB$' data/prac.dat | sort -k3 -n
echo
egrep 'OptPRACTotl heapExt ([0-9]+) 1 .* KiB$' data/prac.dat | sort -k3 -n
echo
echo "# Table 3"
egrep 'BasicPRACPreprc heapIns [0-9]+ 1 .* s$' data/prac.dat | sort -k3 -n
echo
egrep 'BasicPRACOnln heapIns [0-9]+ 1 .* s$' data/prac.dat | sort -k3 -n
echo
egrep 'BasicPRACPreprc heapIns [0-9]+ 1 .* latencies$' data/prac.dat | sort -k3 -n
echo
egrep 'BasicPRACOnln heapIns [0-9]+ 1 .* latencies$' data/prac.dat | sort -k3 -n
echo
egrep 'BasicPRACPreprc heapIns [0-9]+ 1 .* KiB$' data/prac.dat | sort -k3 -n
echo
egrep 'BasicPRACOnln heapIns [0-9]+ 1 .* KiB$' data/prac.dat | sort -k3 -n
echo
egrep 'OptPRACPreprc heapIns [0-9]+ 1 .* s$' data/prac.dat | sort -k3 -n
echo
egrep 'OptPRACOnln heapIns [0-9]+ 1 .* s$' data/prac.dat | sort -k3 -n
echo
egrep 'OptPRACPreprc heapIns [0-9]+ 1 .* latencies$' data/prac.dat | sort -k3 -n
echo
egrep 'OptPRACOnln heapIns [0-9]+ 1 .* latencies$' data/prac.dat | sort -k3 -n
echo
egrep 'OptPRACPreprc heapIns [0-9]+ 1 .* KiB$' data/prac.dat | sort -k3 -n
echo
egrep 'OptPRACOnln heapIns [0-9]+ 1 .* KiB$' data/prac.dat | sort -k3 -n
echo
echo "# Table 4"
egrep 'OptPRACPreprc avlIns [0-9]+ 1 .* s$' data/prac.dat | sort -k3 -n
echo
egrep 'OptPRACOnln avlIns [0-9]+ 1 .* s$' data/prac.dat | sort -k3 -n
echo
egrep 'OptPRACPreprc avlIns [0-9]+ 1 .* latencies$' data/prac.dat | sort -k3 -n
echo
egrep 'OptPRACOnln avlIns [0-9]+ 1 .* latencies$' data/prac.dat | sort -k3 -n
echo
egrep 'OptPRACPreprc avlIns [0-9]+ 1 .* KiB$' data/prac.dat | sort -k3 -n
echo
egrep 'OptPRACOnln avlIns [0-9]+ 1 .* KiB$' data/prac.dat | sort -k3 -n
echo
egrep 'OptPRACPreprc avlDel [0-9]+ 1 .* s$' data/prac.dat | sort -k3 -n
echo
egrep 'OptPRACOnln avlDel [0-9]+ 1 .* s$' data/prac.dat | sort -k3 -n
echo
egrep 'OptPRACPreprc avlDel [0-9]+ 1 .* latencies$' data/prac.dat | sort -k3 -n
echo
egrep 'OptPRACOnln avlDel [0-9]+ 1 .* latencies$' data/prac.dat | sort -k3 -n
echo
egrep 'OptPRACPreprc avlDel [0-9]+ 1 .* KiB$' data/prac.dat | sort -k3 -n
echo
egrep 'OptPRACOnln avlDel [0-9]+ 1 .* KiB$' data/prac.dat | sort -k3 -n
echo
echo '# Heap Sampler'
egrep 'PRACTotl heapsampler [0-9]+ [0-9]+ .* s' data/prac.dat | sort -k3,3n -k4,4n
echo
echo "# End figures"

fi