UP | HOME

Small Snippets with Wisp

Small snippets from my Wisp REPL.


PDF (drucken)

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

Date: 2020-10-10 Sa 00:00

Author: ArneBab

Validate