Programming Languages (7) --- Observing and measuring memory management

NOTE: There were errors in OCaml and Rust programs.

• The issue was that the OCaml and Rust programs I gave to you allocated arrays of 32-bit integers, where it should allocate arrays of 64-bit integers

• Thanks to 蒋知睿 君 for letting me know

• Specifically,

• In OCaml,

let b = Array.make s 0 in   (* *** WRONG *** *)

should have been

let b = Array.make s 0L in   (* *** ERROR CORRECTED *** *)

• In Rust,

let b = Box::new(vec![0; s]);    // *** WRONG ***

should have been

let b = Box::new(vec![0i64; s]); // *** ERROR CORRECTED ***

• Please fix them by modifying programs in your Jupyter notebook
  • There were two lines that have to be fixed in each OCaml/Rust program
  • Three slightly different programs were given for each language
    • OCaml in section 3-3, 5-3, and 6-3
    • Rust in section 3-4, 5-4, and 6-4
  • Therefore, you should fix 6 lines in total
• This page contains the corrected programs and is given for your reference, with apologies
• Corrected lines have comments *** ERROR CORRECTED ***

Enter your name and student ID.

• Name:
• Student ID:

1. Say your language

Say the language you are assigned to. I am working on

BEGIN SOLUTION END SOLUTION Go Julia OCaml Rust

2. Roadmap

• in this notebook, you are going to observe, measure, and tune memory management
• I have given you a benchmark program that stresses memory allocator in the four programming languages
• you collaborate with members in your team to measure and compare the performance of the four languages from several angles
  • speed
  • memory consumption
  • pause time
• you also investigate performance knobs of your language (e.g., heap size) and try to improve a performance criteria if possible

3. Benchmark program

• You are given a program that performs the following

1. allocate an array $A$ of $M$ elements, each element of which is a reference to an array of $S$ 64-bit integers (that is, $A$ is an array of array of 64-bit integers)
2. repeat $N$ times allocating $S$-element array of 64-bit integers and put it in one of the elements of $A$

• default values for $S$, $M$, and $N$ are as follows (they can be specified by the command line)
  • $S$ : $1000 \times 1000$
  • $M$ : $100$
  • $N$ : $M \times 10$

3-1. Go

Note: you do not have to execute the following cell

package main
import (
    "os"
    "strconv"
    "fmt"
)

func get_int64(args []string, i int, def_val int64) int64 {
	if i < len(args)  {
		x, _ := strconv.Atoi(args[i])
		return int64(x)
	} else {
		return def_val
	}
}


func main() {
	s := get_int64(os.Args, 1, int64(1000 * 1000))
	m := get_int64(os.Args, 2, int64(100))
	n := get_int64(os.Args, 3, m * 10)
    sizeof_elem := int64(8)
    if sizeof_elem * s * m > (1 << 30) {
        fmt.Printf("you'd better not allocate that much memory\n")
        fmt.Printf("sizeof_element(8) * s(%d) * m(%d) = %d > 1GB\n", s, m, sizeof_elem * s * m)
        os.Exit(1)
    }
    a := make([][]int64, m)
    for i := int64(0); i < n; i++ {
        b := make([]int64, s)
        a[i % m] = b
    }
}

3-2. Julia

Note: you do not have to execute the following cell

import Printf

function main()
    argc = length(ARGS)
    s = if argc >= 1 parse(Int64, ARGS[1]) else 1000 * 1000 end
    m = if argc >= 2 parse(Int64, ARGS[2]) else 100 end
    n = if argc >= 3 parse(Int64, ARGS[3]) else m * 10 end
    if sizeof(Int64) * s * m > (1 << 30)
        Printf.@printf("you'd better not allocate that much memory")
        Printf.@printf("sizeof element(8) * s(%d) * m(%d) = %d > 1GB\n", s, m, sizeof(Int64) * s * m)
        exit(1)
    end
    a = Vector{Vector{Int64}}(undef, m)
    for i = 1:n
        b = fill(0, s)
        a[(i - 1) % m + 1] = b
    end
end

main()

3-3. OCaml

Note: you do not have to execute the following cell

let main () = 
  let argv = Sys.argv in
  let argc = Array.length argv in
  let s = if argc > 1 then int_of_string argv.(1) else 1000 * 1000 in
  let m = if argc > 2 then int_of_string argv.(2) else 100 in
  let n = if argc > 3 then int_of_string argv.(3) else m * 10 in
  let sizeof_elem = 8 in
  let _ = if sizeof_elem * s * m > (1 lsl 30) then
            (Printf.printf "you'd better not allocate that much memory\n" ;
             Printf.printf "sizeof element(8) * s(%d) * m(%d) = %d > 1GB\n" s m (sizeof_elem * s * m);
             exit 1) in
  let b = Array.make s 0L in    (* *** ERROR CORRECTED *** *)
  let a = Array.make m b in
  let rec allocate_loop i =
    if i < n then
      let b = Array.make s 0L in (* *** ERROR CORRECTED *** *)
      let _ = a.(i mod m) <- b in
      allocate_loop (i + 1)
  in
  allocate_loop 0
;;

main ()

3-4. Rust

Note: you do not have to execute the following cell

fn main() {
    let args : Vec<String> = std::env::args().collect();
    let argc = args.len();
    let s = if argc > 1 { args[1].parse::<usize>().unwrap() } else { 1_000_000 };
    let m = if argc > 2 { args[2].parse::<usize>().unwrap() } else { 100 };
    let n = if argc > 3 { args[3].parse::<usize>().unwrap() } else { m * 10 };
    let sizeof_elem = 8;
    if sizeof_elem * s * m > (1 << 30) {
        println!("you'd better not allocate that much memory");
        println!("sizeof element(8) * s({}) * m({}) = {} > 1GB", s, m, sizeof_elem * s * m);
        std::process::exit(1)
    }
    let b = Box::new(vec![0i64; s]);     // *** ERROR CORRECTED ***
    let mut a = Box::new(vec![b; m]);
    for i in 0..n {
        let b = Box::new(vec![0i64; s]); // *** ERROR CORRECTED ***
        a[i % m] = b;
    }
}

Problem 1 : Discuss this program

• Discuss these programs with your team members and confirm they are doing what I said they do
• Q1: Assuming the memory management system is "perfect" in the sense it retains only those objects that are reachable from the root, what is the minimum amount of memory this program requires for those arrays? Express it in terms of $S$, $M$, and $N$
• Write your team's answer in the Excel book I gave to each team on OneDrive

4. A C program that leaks

• Before looking at Go/Julia/OCaml/Rust, let's look at C version that does not free allocated memory and see what happens
• To observe "what happens," we print the address of each allocated array
• In C, a pointer is actually an address; you can print it just by casting it into an integer of an appropriate size (e.g., printf("%p", (long)p))

• Prepare a working directory

mkdir -p ~/notebooks/pl07_memory_management/p2/cc/show_addr_no_gc

• Write the souce file

%%writefile p2/cc/show_addr_no_gc/show_addr_no_gc.cc
#include <stdio.h>
#include <stdlib.h>
#include <time.h>


typedef long T;

int main(int argc, char ** argv) {
  long s = (1 < argc ? atol(argv[1]) : 1000 * 1000);
  long m = (2 < argc ? atol(argv[2]) : 100);
  long n = (3 < argc ? atol(argv[3]) : m * 10);
  if (sizeof(T) * s * n > (1L << 31)) {
      fprintf(stderr, "you'd better not allocate that much memory\n");
      fprintf(stderr, "sizeof element(8) * s(%ld) * n(%ld) > 2GB\n", s, n);
      exit(1);
  }
  T ** a = (T **)malloc(sizeof(T *) * m);
  for (long i = 0; i < n; i++) {
    T * b = (T *)malloc(sizeof(T) * s);
    a[i % m] = b;
    printf("%ld\t%ld\n", i, (long)&b[0]);
  }
  return 0;
}

• Compile it

cd ~/notebooks/pl07_memory_management/p2/cc/show_addr_no_gc
gcc -O3 -Wall -Wextra -o show_addr_no_gc show_addr_no_gc.cc

• Execute it
• The following command prints N lines; be careful not to make it too large

cd ~/notebooks/pl07_memory_management/p2/cc/show_addr_no_gc
S=$((1000 * 1000))
M=10
N=$((M * 10))
/usr/bin/time ./show_addr_no_gc ${S} ${M} ${N}

Problem 2 : Observe leak

• Visualize these addresses in the Excel book I made for each team on OneDrive
  • The x-axis: the number of times you allocated (iteration number)
  • The y-axis: the address offset (see below)
• In order to easily grasp how many bytes they are spread across, show addresses as their offsets from the minimum of all addresses (so that the minimum address is shown as zero)
• e.g., if the result is

0,100000000
1,100010000
2,100020000
3,100030000

you should visualize it as follows

0,0
1,10000
2,20000
3,30000

• You can perform this conversion to offsets either with Excel formula or by a program
• To put data in the Excel book, copy-and-paste from Jupyter is not recommended; you instead redirect the output of the program into a file (e.g., command > out.csv) and download it. Open it in the text editor or Excel and copy it in the Excel book on OneDrive
• Hint : use scatter-plot
• Discuss the visualized data and understand what it means
  • Q2: : what is the sign that memory is "leaked"?
  • Q3: : how many bytes two consecutive arrays are apart? How it relates to $S$, $M$, or $N$?

5. Automatic memory management (reclamation)

• Now let's see what happens in languages doing automatic memory management
• We do what we did for C in each of the four languages; print the addresses of allocated arrays
• Execute the program of the language you are assigned to

5-1. Go

• In Go, you can simply print an address of an array b by something like

fmt.Printf("%d\n", &b[0])

• check if you can run go command

go version

• if it raises an error indicating go command is not found, add ~/go/bin to your PATH environment variable

export PATH=~/go/bin:$PATH

mkdir -p ~/notebooks/pl07_memory_management/p3/go/show_addr
cd ~/notebooks/pl07_memory_management/p3/go/show_addr
go mod init show_addr

%%writefile p3/go/show_addr/show_addr.go
package main
import (
    "os"
    "strconv"
    "fmt"
)

func get_int64(args []string, i int, def_val int64) int64 {
	if i < len(args)  {
		x, _ := strconv.Atoi(args[i])
		return int64(x)
	} else {
		return def_val
	}
}


func main() {
	s := get_int64(os.Args, 1, int64(1000 * 1000))
	m := get_int64(os.Args, 2, int64(100))
	n := get_int64(os.Args, 3, m * 10)
    sizeof_elem := int64(8)
    if sizeof_elem * s * m > (1 << 30) {
        fmt.Printf("you'd better not allocate that much memory\n")
        fmt.Printf("sizeof_element(8) * s(%d) * m(%d) = %d > 1GB\n", s, m, sizeof_elem * s * m)
        os.Exit(1)
    }
    a := make([][]int64, m)
    for i := int64(0); i < n; i++ {
        b := make([]int64, s)
        a[i % m] = b
        fmt.Printf("%d\t%d\n", i, &b[0])
    }
}

cd ~/notebooks/pl07_memory_management/p3/go/show_addr
go build

cd ~/notebooks/pl07_memory_management/p3/go/show_addr
S=$((1000 * 1000))
M=100
N=$((M * 10))
/usr/bin/time ./show_addr ${S} ${M} ${N}

5-2. Julia

• In Julia, to print an address of an array b, you first get a pointer by p = pointer(b) and cast it into an integer by Int64(p)
• Check if you can run julia command

julia --version

• If it raises an error indicating julia command is not found, add ~/.juliaup/bin to your PATH environment variable

export PATH=~/.juliaup/bin:$PATH

mkdir -p ~/notebooks/pl07_memory_management/p3/jl/show_addr

%%writefile p3/jl/show_addr/show_addr.jl
import Printf

function main()
    argc = length(ARGS)
    s = if argc >= 1 parse(Int64, ARGS[1]) else 1000 * 1000 end
    m = if argc >= 2 parse(Int64, ARGS[2]) else 100 end
    n = if argc >= 3 parse(Int64, ARGS[3]) else m * 10 end
    if sizeof(Int64) * s * m > (1 << 30)
        Printf.@printf("you'd better not allocate that much memory")
        Printf.@printf("sizeof element(8) * s(%d) * m(%d) = %d > 1GB\n", s, m, sizeof(Int64) * s * m)
        exit(1)
    end
    a = Vector{Vector{Int64}}(undef, m)
    for i = 1:n
        b = fill(0, s)
        p = pointer(b)
        a[(i - 1) % m + 1] = b
        Printf.@printf("%ld\t%ld\n", i, Int64(p))
    end
end

main()

cd ~/notebooks/pl07_memory_management/p3/jl/show_addr
S=$((1000 * 1000))
M=100
N=$((M * 10))
/usr/bin/time julia ./show_addr.jl ${S} ${M} ${N}

5-3. OCaml

• In OCaml, to print an address of an array b, Obj.magic (Obj.repr b) does the trick
• Check if you can run ocamlc command

ocamlc --version

• if it raises an error indicating ocamlc command is not found, execute the following in your shell

eval $(opam env)

mkdir -p ~/notebooks/pl07_memory_management/p3/ml
cd ~/notebooks/pl07_memory_management/p3/ml
dune init project show_addr

%%writefile p3/ml/show_addr/bin/main.ml
let main () = 
  let argv = Sys.argv in
  let argc = Array.length argv in
  let s = if argc > 1 then int_of_string argv.(1) else 1000 * 1000 in
  let m = if argc > 2 then int_of_string argv.(2) else 100 in
  let n = if argc > 3 then int_of_string argv.(3) else m * 10 in
  let sizeof_elem = 8 in
  let _ = if sizeof_elem * s * m > (1 lsl 30) then
            (Printf.printf "you'd better not allocate that much memory\n" ;
             Printf.printf "sizeof element(8) * s(%d) * m(%d) = %d > 1GB\n" s m (sizeof_elem * s * m);
             exit 1) in
  let b = Array.make s 0L in    (* *** ERROR CORRECTED *** *)
  let a = Array.make m b in
  let rec allocate_loop i =
    if i < n then
      let b = Array.make s 0L in (* *** ERROR CORRECTED *** *)
      let p = Obj.magic (Obj.repr b) in
      let _ = a.(i mod m) <- b in
      let _ = Printf.printf "%d\t%d\n" i p in
      allocate_loop (i + 1)
  in
  allocate_loop 0
;;

main ()

cd ~/notebooks/pl07_memory_management/p3/ml/show_addr
dune build --profile release

cd ~/notebooks/pl07_memory_management/p3/ml/show_addr
S=$((1000 * 1000))
M=100
N=$((M * 10))
/usr/bin/time ./_build/default/bin/main.exe ${S} ${M} ${N}

5-4. Rust

• In Rust, for an array b, b.as_ptr() as usize is the address of it cast into an integer (usize)
• check if you can run rustc command

rustc --version

• if it raises an error indicating rustc command is not found, execute the following in your shell

. ~/.cargo/env

mkdir -p ~/notebooks/pl07_memory_management/p3/rs
cd ~/notebooks/pl07_memory_management/p3/rs
cargo new show_addr

%%writefile p3/rs/show_addr/src/main.rs
fn main() {
    let args : Vec<String> = std::env::args().collect();
    let argc = args.len();
    let s = if argc > 1 { args[1].parse::<usize>().unwrap() } else { 1_000_000 };
    let m = if argc > 2 { args[2].parse::<usize>().unwrap() } else { 100 };
    let n = if argc > 3 { args[3].parse::<usize>().unwrap() } else { m * 10 };
    let sizeof_elem = 8;
    if sizeof_elem * s * m > (1 << 30) {
        println!("you'd better not allocate that much memory");
        println!("sizeof element(8) * s({}) * m({}) = {} > 1GB", s, m, sizeof_elem * s * m);
        std::process::exit(1)
    }
    let b = Box::new(vec![0i64; s]);     // *** ERROR CORRECTED ***
    let mut a = Box::new(vec![b; m]);
    for i in 0..n {
        let b = Box::new(vec![0i64; s]); // *** ERROR CORRECTED ***
        let p = b.as_ptr() as usize;
        a[i % m] = b;
        println!("{}\t{}", i, p);
    }
}

cd ~/notebooks/pl07_memory_management/p3/rs/show_addr
cargo build --release

cd ~/notebooks/pl07_memory_management/p3/rs/show_addr
S=$((1000 * 1000))
M=100
N=$((M * 10))
/usr/bin/time ./target/release/show_addr ${S} ${M} ${N}

5-5. C + conservative GC library

• Boehm + Weiser Conservative GC is a library that you can plug into your C/C++ programs
• On Ubuntu, installation only takes

sudo apt install libgc-dev

• All you need to do is
  • #include <gc/gc.h>
  • replace malloc and calloc to GC_MALLOC
  • you don't have to free
  • link with -lgc (add this when you produce the executable, like

gcc -o foo.exe foo.c -lgc

mkdir -p ~/notebooks/pl07_memory_management/p3/cc/show_addr

%%writefile p3/cc/show_addr/show_addr.cc
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <gc/gc.h>


typedef long T;

int main(int argc, char ** argv) {
  long s = (1 < argc ? atol(argv[1]) : 1000 * 1000);
  long m = (2 < argc ? atol(argv[2]) : 100);
  long n = (3 < argc ? atol(argv[3]) : m * 10);
  if (sizeof(T) * s * m > (1L << 30)) {
      fprintf(stderr, "you'd better not allocate that much memory\n");
      fprintf(stderr, "sizeof(T)(8) * s(%ld) * m(%ld) > 1GB\n", s, m);
      exit(1);
  }
  T ** a = (T **)GC_MALLOC(sizeof(T *) * m);
  for (long i = 0; i < n; i++) {
    T * b = (T *)GC_MALLOC_ATOMIC(sizeof(T) * s);
    a[i % m] = b;
    printf("%ld\t%ld\n", i, (long)&b[0]);
  }
  return 0;
}

cd ~/notebooks/pl07_memory_management/p3/cc/show_addr
gcc -O3 -Wall -Wextra -o show_addr show_addr.cc -lgc

cd ~/notebooks/pl07_memory_management/p3/cc/show_addr
S=$((1000 * 1000))
M=100
N=$((M * 10))
/usr/bin/time ./show_addr ${S} ${M} ${N}

Problem 3 : Observe memory management at work

• Visualize these addresses in the Excel book I made for each team on OneDrive
  • The x-axis: the number of times you allocated (iteration number)
  • The y-axis: the address offset (see below)
• As you did for the C program, addresses should be shown as offsets from the minimum address (the minimum taken over addresses in a particular language)
• As you did for the C program, redirect the result into a file (e.g., out.csv) rather than copy-pasting from Jupyter
• Addresses are typically contiguous (they are densely packed in a contiguous region), but in some languages they may be split into two (or a few) clusters, making it becomes difficult to grasp how much memory they actually occupy
• If that happens, exclude all but one largest cluster from the visualization (only show addresses in the largest cluster)
• Discuss the visualized data and understand what it means; in particular,
  • Q4: From the visualization, how do you know the memory management is "working"
  • Q5: Deduce from the visualization the amount of memory each language requires for these arrays
  • Q6: Count the number of distinct addresses; write a shell command that takes the output (e.g., out.csv) and counts the number of distinct addresses (hint: combine sort, uniq, and wc)
  • Q7: Confirm the former is close to "the number of distinct addresses x the array size"
  • Q8: How large is it relative to the "minimum" amount of memory required you calculated in Problem 1?
• Change the values of $S$, $M$, and $N$ and how the behavior changes (or does not change); you can copy the sheet in Excel book to record experimental results with different parameters

6. Measuring allocation (pause) time

• In this experiment, we measure the time taken for each allocation
• In garbage-collected languages, an allocation occasionally takes much time than usual
• The maximum allocation time is essentially a "pause time" experienced by the user program, so a large spike in allocation time is a significant deal even if it is infrequent
• Average time is important, too, as it indicates the basic performance of the language

6-1. Go

mkdir -p ~/notebooks/pl07_memory_management/p4/go/measure_time
cd ~/notebooks/pl07_memory_management/p4/go/measure_time
go mod init measure_time

%%writefile p4/go/measure_time/measure_time.go
package main
import (
    "os"
    "strconv"
    "fmt"
    "github.com/loov/hrtime"
)

func get_int64(args []string, i int, def_val int64) int64 {
	if i < len(args)  {
		x, _ := strconv.Atoi(args[i])
		return int64(x)
	} else {
		return def_val
	}
}

func time_ns() int64 {
	return int64(hrtime.Now())
}

func main() {
	s := get_int64(os.Args, 1, int64(1000 * 1000))
	m := get_int64(os.Args, 2, int64(100))
	n := get_int64(os.Args, 3, m * 10)
    sizeof_elem := int64(8)
    if sizeof_elem * s * m > (1 << 30) {
        fmt.Printf("you'd better not allocate that much memory\n")
        fmt.Printf("sizeof_element(8) * s(%d) * m(%d) = %d > 1GB\n", s, m, sizeof_elem * s * m)
        os.Exit(1)
    }
    a := make([][]int64, m)
    for i := int64(0); i < n; i++ {
        t0 := time_ns()
        b := make([]int64, s)
        a[i % m] = b
        t1 := time_ns()
        fmt.Printf("%d\t%d\t%d\n", i, &b[0], t1 - t0)
    }
}

• you will be complained when executing the following cell, and instructed to execute

go get github.com/loov/hrtime

• just do it when it happens

cd ~/notebooks/pl07_memory_management/p4/go/measure_time
go build

cd ~/notebooks/pl07_memory_management/p4/go/measure_time
S=$((1000 * 1000))
M=100
N=$((M * 10))
/usr/bin/time ./measure_time ${S} ${M} ${N}

6-2. Julia

mkdir -p ~/notebooks/pl07_memory_management/p4/jl/measure_time

%%writefile p4/jl/measure_time/measure_time.jl
import Printf

function main()
    argc = length(ARGS)
    s = if argc >= 1 parse(Int64, ARGS[1]) else 1000 * 1000 end
    m = if argc >= 2 parse(Int64, ARGS[2]) else 100 end
    n = if argc >= 3 parse(Int64, ARGS[3]) else m * 10 end
    if sizeof(Int64) * s * m > (1 << 30)
        Printf.@printf("you'd better not allocate that much memory")
        Printf.@printf("sizeof element(8) * s(%d) * m(%d) = %d > 1GB\n", s, m, sizeof(Int64) * s * m)
        exit(1)
    end
    a = Vector{Vector{Int64}}(undef, m)
    for i = 1:n
        t0 = time_ns()
        b = fill(0, s)
        p = pointer(b)
        a[(i - 1) % m + 1] = b
        t1 = time_ns()
        Printf.@printf("%ld\t%ld\t%ld\n", i, Int64(p), t1 - t0)
    end
end

main()

cd ~/notebooks/pl07_memory_management/p4/jl/measure_time
S=$((1000 * 1000))
M=100
N=$((M * 10))
/usr/bin/time julia ./measure_time.jl ${S} ${M} ${N}

6-3. OCaml

mkdir -p ~/notebooks/pl07_memory_management/p4/ml
cd ~/notebooks/pl07_memory_management/p4/ml
dune init project measure_time

%%writefile p4/ml/measure_time/bin/main.ml
(* get current time in ns *)
exception Couldnt_get_time
;;

let time_ns () = 
  match Base.Int63.to_int (Time_now.nanoseconds_since_unix_epoch()) with
    Some(t) -> t
  | None -> raise Couldnt_get_time
;;
let main () = 
  let argv = Sys.argv in
  let argc = Array.length argv in
  let s = if argc > 1 then int_of_string argv.(1) else 1000 * 1000 in
  let m = if argc > 2 then int_of_string argv.(2) else 100 in
  let n = if argc > 3 then int_of_string argv.(3) else m * 10 in
  let sizeof_elem = 8 in
  let _ = if sizeof_elem * s * m > (1 lsl 30) then
            (Printf.printf "you'd better not allocate that much memory\n" ;
             Printf.printf "sizeof element(8) * s(%d) * m(%d) = %d > 1GB\n" s m (sizeof_elem * s * m);
             exit 1) in
  let b = Array.make s 0L in    (* *** ERROR CORRECTED *** *)
  let a = Array.make m b in
  let rec allocate_loop i =
    if i < n then
      let t0 = time_ns() in
      let b = Array.make s 0L in (* *** ERROR CORRECTED *** *)
      let p = Obj.magic (Obj.repr b) in
      let _ = a.(i mod m) <- b in
      let t1 = time_ns() in
      let _ = Printf.printf "%d\t%d\t%d\n" i p (t1 - t0) in
      allocate_loop (i + 1)
  in
  allocate_loop 0
;;

main ()

• You will be complained when executing the following cell
• execute

opam install time_now

in the terminal (it takes a while and ask you if you want to go ahead)

• and add time_now in the p4/ml/measure_time/bin/dune file, as follows

(executable
 ( ... )
 ( ...
 (libraries measure_time time_now))

cd ~/notebooks/pl07_memory_management/p4/ml/measure_time
dune build --profile release

cd ~/notebooks/pl07_memory_management/p4/ml/measure_time
S=$((1000 * 1000))
M=100
N=$((M * 10))
/usr/bin/time ./_build/default/bin/main.exe ${S} ${M} ${N}

6-4. Rust

mkdir -p ~/notebooks/pl07_memory_management/p4/rs
cd ~/notebooks/pl07_memory_management/p4/rs
cargo new measure_time

%%writefile p4/rs/measure_time/src/main.rs
fn time_ns(now : &std::time::Instant) -> i64 {
    now.elapsed().as_nanos() as i64
}
fn main() {
    let args : Vec<String> = std::env::args().collect();
    let argc = args.len();
    let s = if argc > 1 { args[1].parse::<usize>().unwrap() } else { 1_000_000 };
    let m = if argc > 2 { args[2].parse::<usize>().unwrap() } else { 100 };
    let n = if argc > 3 { args[3].parse::<usize>().unwrap() } else { m * 10 };
    let sizeof_elem = 8;
    if sizeof_elem * s * m > (1 << 30) {
        println!("you'd better not allocate that much memory");
        println!("sizeof element(8) * s({}) * m({}) = {} > 1GB", s, m, sizeof_elem * s * m);
        std::process::exit(1)
    }
    let b = Box::new(vec![0i64; s]);     // *** ERROR CORRECTED ***
    let mut a = Box::new(vec![b; m]);
    let ts = std::time::Instant::now();
    for i in 0..n {
        let t0 = time_ns(&ts);
        let b = Box::new(vec![0i64; s]); // *** ERROR CORRECTED ***
        let p = b.as_ptr() as usize;
        a[i % m] = b;
        let t1 = time_ns(&ts);
        println!("{}\t{}\t{}", i, p, t1 - t0);
    }
}

cd ~/notebooks/pl07_memory_management/p4/rs/measure_time
cargo build --release

cd ~/notebooks/pl07_memory_management/p4/rs/measure_time
S=$((1000 * 1000))
M=100
N=$((M * 10))
/usr/bin/time ./target/release/measure_time ${S} ${M} ${N}

Problem 4 : Observe pause time

• Visualize allocation time
  • The x-axis: the number of times you allocated (iteration number)
  • The y-axis: the time taken on that allocation
• Discuss the visualized data and compare languages
  • Q9: What is the maximum pause time of each language? What makes the pause time longer for garbage-collected languages?
  • Q10: What is the pause time of "average cases" in each language (i.e., when GC does not happen in garbage collected languages)?
• Change the values of $S$, $M$, and $N$ and how the behavior changes (or does not change); you can copy the sheet in Excel book to record experimental results with different parameters

Problem 5 : Show the tail of cumulative distribution

• Visualize allocation time
  • The x-axis: the fraction (0 ≤ x &le 1) of allocations that finished within the specified $y$
  • The y-axis: allocation (pause) time
  • for example, point (x, y) = (0.87, 2000) in the graph indicates 87% of allocations finish within 2000 nsec
• Hint:
  • Sort all pause times and scatter-plot $(i / N, y[i])$ for each $i = 1, 2, ..., N$

Problem 6 : (Optional)

• Languages typically support a few knobs to control memory usage (and frequency of garbage collections) and to report when GC happens
• Consult the manual of your language and play with them. In particular,
  • try to control GC less frequenty by using more memory
  • try to shorten pause time of GCs if there is any such option