Deno でキューを実装して性能を【雑に】比較してみた

@mikecat_mixc さんのこの投稿が気になった。

Denoで同じようなベンチを書いて実行してみる。（雑実装注意！）

ソースコード

interface Queue {
  enqueue(value: number): void
  dequeue(): number | undefined
}

class QueueShift implements Queue {
  private queue: number[] = [];

  enqueue(value: number) {
    this.queue.push(value);
  }

  dequeue() {
    return this.queue.shift();
  }
}

class QueueStackSave implements Queue {
  private stack1: number[] = [];
  private stack2: number[] = [];

  enqueue(value: number) {
    while (this.stack1.length > 0) {
      this.stack2.push(this.stack1.pop()??0)
    }
    this.stack1.push(value);
    while (this.stack2.length > 0) {
      this.stack1.push(this.stack2.pop()??0)
    }
  }

  dequeue() {
    return this.stack1.pop();
  }
}

class QueueStack implements Queue {
  private stackPush: number[] = [];
  private stackPop: number[] = [];

  enqueue(value: number) {
    this.stackPush.push(value);
  }

  dequeue() {
    if (this.stackPop.length ===0) {
      while (this.stackPush.length > 0) {
        this.stackPop.push(this.stackPush.pop()??0);
      }
    }
    return this.stackPop.pop();
  }
}

class QueueMap implements Queue {
  private data = new Map<number, number>();
  private nextEnqueueKey = 0;
  private nextDequeueKey = 0;

  enqueue(value: number) {
    this.data.set(this.nextEnqueueKey++, value);
  }

  dequeue() {
    const key = this.nextDequeueKey++;
    const value = this.data.get(key);
    this.data.delete(key);
    return value;
  }
}

class QueueSet implements Queue {
  private q = new Set<number>();

  enqueue(value: number) {
    this.q.add(value);
  }

  dequeue() {
    const value = this.q.values().next().value;
    this.q.delete(value);
    return value;
  }
}

const loop = 1000;
const q: { name: string, q: Queue }[] = [
  { name: 'QueueShift', q: new QueueShift() },
  { name: 'QueueStackSave', q: new QueueStackSave() },
  { name: 'QueueStack', q: new QueueStack() },
  { name: 'QueueMap', q: new QueueMap() },
  { name: 'QueueSet', q: new QueueSet() }
];

q.forEach((v) => {
  Deno.bench({name: v.name, fn: () => {
    const q = v.q;
    let sum = 0;
    for (let i = 0; i < loop; i++) {
      q.enqueue(i);
      sum += i;
    }
  
    let rsum = 0;
    for (let i = 0; i < loop; i++) {
      const r = q.dequeue();
      if (r === undefined) break;
      rsum += r;
    }
   
    if (sum!==rsum) throw new Error();
  }});
});

ベンチマーク

const loop = 1000の部分を変化させて実行速度を見てみる。

loop = 100

deno bench bench.ts 
cpu: Intel(R) Core(TM) i7-10700K CPU @ 3.80GHz
runtime: deno 1.42.3 (x86_64-unknown-linux-gnu)

benchmark           time (avg)        iter/s             (min … max)       p75       p99      p995
-------------------------------------------------------------------- -----------------------------
QueueShift           1.99 µs/iter     501,710.4      (1.9 µs … 2.15 µs) 2.01 µs 2.15 µs 2.15 µs
QueueStackSave      67.08 µs/iter      14,908.0    (63.6 µs … 259.3 µs) 66.4 µs 105 µs 109.4 µs
QueueStack           1.24 µs/iter     807,728.5      (1.2 µs … 1.27 µs) 1.25 µs 1.27 µs 1.27 µs
QueueMap             7.23 µs/iter     138,274.3      (5.1 µs … 1.07 ms) 6.2 µs 15.4 µs 20.6 µs
QueueSet              6.2 µs/iter     161,336.4     (6.04 µs … 6.53 µs) 6.24 µs 6.53 µs 6.53 µs

loop = 1000

deno bench bench.ts 
cpu: Intel(R) Core(TM) i7-10700K CPU @ 3.80GHz
runtime: deno 1.42.3 (x86_64-unknown-linux-gnu)

benchmark           time (avg)        iter/s             (min … max)       p75       p99      p995
-------------------------------------------------------------------- -----------------------------
QueueShift          69.74 µs/iter      14,338.2    (62.7 µs … 238.4 µs) 69.2 µs 131.7 µs 152 µs
QueueStackSave       6.68 ms/iter         149.7     (6.52 ms … 8.58 ms) 6.69 ms 8.58 ms 8.58 ms
QueueStack          12.31 µs/iter      81,248.0    (11.7 µs … 140.4 µs) 12.2 µs 20.5 µs 27.9 µs
QueueMap            63.23 µs/iter      15,815.5     (50.8 µs … 1.08 ms) 56 µs 374.7 µs 832.4 µs
QueueSet           205.64 µs/iter       4,863.0    (191.3 µs … 1.44 ms) 201.5 µs 379.3 µs 603 µs

loop = 10000

deno bench bench.ts 
cpu: Intel(R) Core(TM) i7-10700K CPU @ 3.80GHz
runtime: deno 1.42.3 (x86_64-unknown-linux-gnu)

benchmark           time (avg)        iter/s             (min … max)       p75       p99      p995
-------------------------------------------------------------------- -----------------------------
QueueShift         785.78 µs/iter       1,272.6    (724.8 µs … 1.28 ms) 797.3 µs 1.02 ms 1.25 ms
QueueStackSave     651.48 ms/iter           1.5 (641.46 ms … 668.81 ms) 654.33 ms 668.81 ms 668.81 ms
QueueStack         123.44 µs/iter       8,101.3     (119 µs … 250.8 µs) 122 µs 172.8 µs 187.7 µs
QueueMap             1.03 ms/iter         972.9    (808.1 µs … 2.32 ms) 917.2 µs 2.19 ms 2.21 ms
QueueSet            10.78 ms/iter          92.7   (10.29 ms … 12.35 ms) 10.81 ms 12.35 ms 12.35 ms

結果は？

QueueStackが一番安定して良い！