🚛

配列操作を覗いてみる

に公開
Go
Ruby
Node.js
配列
tech

はじめに

高級言語で配列をするのは簡単ですが、それに伴うメモリの使用量はどのようになっているかをGoとRubyとNodeで可視化しました。最後にC言語で内部を表現しています。

マシンスペック

MacBook Air M2 arm64

Goで確認

Goでappendで

package main

import (
    "fmt"
    "runtime"
)

func mem(label string, s []int) {
    runtime.GC()
    var m runtime.MemStats
    runtime.ReadMemStats(&m)
    fmt.Printf("%s: len=%d cap=%d Alloc=%d bytes\n", label, len(s), cap(s), m.Alloc)
}

func main() {
    const N = 1_000_000

    s := make([]int, N)

    mem("before append", s)

    s = append(s, 42)
    mem("after  append", s)

    s = s[:len(s)-1]
    mem("after  pop   ", s)
}

実行をして確認します。

before append: len=1000000 cap=1000000 Alloc=8127928 bytes
after  append: len=1000001 cap=1250304 Alloc=10126776 bytes
after  pop   : len=1000000 cap=1250304 Alloc=10128224 bytes

Rubyで確認

# frozen_string_literal: true
require "objspace"

N = 1_000_000

def mem(label, ary)
  GC.start
  size = ObjectSpace.memsize_of(ary)
  puts "#{label}: len=#{ary.length} memsize=#{size}"
end

a = Array.new(N, 0)
mem("before <<", a)

a << 42
mem("after <<", a)

a.pop
mem("after pop", a)

結果は

before <<: len=1000000 memsize=8000040
after <<: len=1000001 memsize=12000048
after pop: len=1000000 memsize=12000048

Nodeで確認

if (typeof global.gc !== "function") {
  console.error("Run with: node --expose-gc exp_node_oneop.mjs");
  process.exit(1);
}

const N = 1_000_000;
let arr = new Array(N).fill(0);

function report(label) {
  global.gc(); 
  const mem = process.memoryUsage().heapUsed;
  console.log(`${label}: len=${arr.length} heapUsed=${mem}`);
}

report("before push");

arr.push(42);
report("after push");

arr.pop();
report("after pop");

結果は

before push: len=1000000 heapUsed=11473728
after push: len=1000001 heapUsed=15826608
after pop: len=1000000 heapUsed=15823496

C言語で中身を模倣してみる

#include <stddef.h> 
#include <stdlib.h> 
#include <string.h>
#include <stdio.h> 

typedef struct {
    size_t len;
    size_t cap;
    int   *data;
} Vec;

void vec_init(Vec *v, size_t len, size_t cap) {
    v->len  = len;
    v->cap  = cap;
    if (cap == 0) {
        v->data = NULL;
        return;
    }
    v->data = malloc(cap * sizeof(int));
    if (!v->data) {
        perror("malloc");
        exit(1);
    }
    if (len > 0) {
        memset(v->data, 0, len * sizeof(int));
    }
}

void vec_free(Vec *v) {
    free(v->data);
    v->data = NULL;
    v->len  = 0;
    v->cap  = 0;
}

void vec_push(Vec *v, int x) {
    if (v->len == v->cap) {
        size_t new_cap = (v->cap == 0) ? 1 : v->cap * 2;
        int *new_data = malloc(new_cap * sizeof(int));
        if (!new_data) {
            perror("malloc");
            exit(1);
        }
        if (v->len > 0 && v->data != NULL) {
            memcpy(new_data, v->data, v->len * sizeof(int));
        }
        free(v->data);
        v->data = new_data;
        v->cap  = new_cap;
    }
    v->data[v->len++] = x;
}

int vec_pop(Vec *v) {
    if (v->len == 0) {
        fprintf(stderr, "vec_pop: empty\n");
        exit(1);
    }
    return v->data[--v->len];
}

void vec_print(const char *label, const Vec *v) {
    printf("%s: len=%zu cap=%zu data=%p buffer_bytes=%zu\n",
           label,
           v->len,
           v->cap,
           (void *)v->data,
           v->cap * sizeof(int));
}

int main(void) {
    const size_t N = 10 * 1000 * 1000;

    printf("=== Case A: 空きありで push 1回 ===\n");
    Vec a;
    vec_init(&a, N, N + 1);
    vec_print("before push (A)", &a);
    vec_push(&a, 42);
    vec_print("after  push (A)", &a);
    vec_free(&a);
    puts("");

    printf("=== Case B: 配列が満たされた状態で push 1回 ===\n");
    Vec b;
    vec_init(&b, N, N);
    vec_print("before push (B)", &b);
    vec_push(&b, 42);
    vec_print("after  push (B)", &b);
    vec_free(&b);
    puts("");

    printf("=== Case C: len=N で pop 1回 ===\n");
    Vec c;
    vec_init(&c, N, N);
    vec_print("before pop  (C)", &c);
    (void)vec_pop(&c);
    vec_print("after  pop  (C)", &c);
    vec_free(&c);

    return 0;
}

結果は

=== Case A: 空きありで push 1回 ===
before push (A): len=10000000 cap=10000001 data=0x130000000 buffer_bytes=40000004
after  push (A): len=10000001 cap=10000001 data=0x130000000 buffer_bytes=40000004

=== Case B: 配列が満たされた状態で push 1回 ===
before push (B): len=10000000 cap=10000000 data=0x130000000 buffer_bytes=40000000
after  push (B): len=10000001 cap=20000000 data=0x132628000 buffer_bytes=80000000

=== Case C: len=N で pop 1回 ===
before pop  (C): len=10000000 cap=10000000 data=0x130000000 buffer_bytes=40000000
after  pop  (C): len=9999999 cap=10000000 data=0x130000000 buffer_bytes=40000000

イメージ図

まとめ

Go, Ruby, Nodeでは、いずれも配列に1回pushすると、内部バッファが拡張されてメモリ使用量が一気に増えることが観測できた。
pop（またはスライスで縮める）だけでは、多くの場合バッファ容量は縮まず、メモリもすぐには減らない。
配列へのpush/popの裏側で起きていることを少し意識しておくと、大きな配列を扱うときの設計やパフォーマンスチューニングのヒントにもなると思います。
今回は、配列の操作について少しだけ観測してみました。
学習の保持になれば幸いです。

Discussion