Small Snippets with Wisp
Small snippets from my Wisp REPL.
Scheme overhead of records, lists and cons-pairs
If I have many lists of 16 elements, what’s the overhead of records, lists and cons-pairs? This is adapted from cost-of-records that only looked at two-element structures.
Preparation:
;; 20 MiB res memory import : srfi srfi-9 ;; records only (srfi srfi-1) fold ;; 37 MiB res memory define-record-type <roll-result> roll-result a b c d e f g h i j k l m n o p . roll-result? . (a ra) (b rb) (c rc) (d rd) (e re) (f rf) (g rg) (h rh) . (i ri) (j rj) (k rk) (l rl) (m rm) (n rn) (o ro) (p rp) ;; 48 MiB res memory define up-to-one-million : iota : expt 2 20 ;; 55 MiB res memory
cons, records and lists added individually to avoid memory interaction:
define results-record : map (λ (x) (apply roll-result (iota 16 x))) up-to-one-million ;; 311 MiB res memory, diff: 256 MiB
define results-cons : map (λ (x) (fold cons x (iota 15 (+ x 1)))) up-to-one-million ;; 440 MiB res memory, diff: 384 MiB
define results-list : map (λ (x) (apply list (iota 16 x))) up-to-one-million ;; 457 MiB res memory, diff: 402 MiB
Let’s try a single vector (but filled with all zeros, for simplicity — I verified that there is no special handling for zero, using different numbers per Element gives the same result):
define 16-million-zeros-vector : make-vector 16000000 0 ;; 179 MiB res memory, diff 124 MiB
Result: From cost-of-records we know that for two-element structures a cons-pair wastes the least amount of space. For 16 element structures however, record wins by a wide margin. For storing 16 million numbers this needs 256 MiB, 268435456 bytes, so each number needs 16.78 bytes.
A plain vector with 16 million times 0 (zero) takes up 124 MiB, 8.13 bytes per number, so if we use records to structure large amounts of data, we have to live with factor 2 overhead compared to packing all values into a single big vector and doing index-magic to retrieve the right values.
You can reduce this to 4.13 bytes per number by explicitly using a u32-vector, accepting the constrain on number-size: less than about 4.3 billion:
define 16-million-zeros-u32vector : make-u32vector 16000000 0 ;; 118 MiB res memory, diff 63 MiB
A hash-table with 16 million x:x key-value pairs takes up 1.3 GiB, 87 bytes per pair.
2d6 + d10, all results
Calculate all possible results for rolling 2d6 and 1d10. This got a bit out of hand while I generalized it to arbitrary dice.
It is absolutely brute-force.
import : srfi srfi-1 define : roll-dice . dice . "Roll arbitrary DICE. Each die is a list of its faces. Example: roll-dice '(1 2 3 4) '(1 2 3 4)" define : roll mod . dice . "Roll DICE with modifier MOD. Example: 1d6+2 is roll 2 '(1 2 3 4 5 6)" cond : null? dice . '() : null? : cdr dice map : λ (pip) : + pip mod car dice else apply append map : λ (pip) : apply roll : cons (+ pip mod) : cdr dice car dice apply roll : cons 0 dice define : frequency results . "Count the frequency of numbers in the results" define counter : make-hash-table define : count value hash-set! counter value + 1 : if (hash-ref counter value) (hash-ref counter value) 0 map count results sort : hash-map->list cons counter λ (x y) : < (car x) (car y) define d6 '(1 2 3 4 5 6) define d10 '(0 1 2 3 4 5 6 7 8 9) frequency : roll-dice d6 d6 d10