LinkedList optmizations

[jeswr]

Noting that the V8 engine has similar optimizations to firefox for up to 50_000 elements, we could do the following (~2x speedup).

export default class LinkedList<V> {
  public length: number = 0;
  private _offset = 0;

  private _head: V[] = [];
  private _tail: V[] = this._head;

  get first()  { return this._head[this._offset]; }
  get last()   { return this._offset > this.length ? undefined : this._tail[this._tail.length - 1]; }
  get empty()  { return this.length === 0; }

  push(value: V) {
    if (this._tail.length === 5_000) {
      (this._tail as any).next = [];
      this._tail = (this._tail as any).next
    }
    this._tail.push(value);
    this.length++;
  }

  shift(): V | undefined {
    if (this._offset === 5_000) {
      // Handle when head.next is not zero
      this._head = (this._head as any).next;
      this._offset = 0;
    }
    if (this._offset > this.length + 1)
      return undefined;
    this.length--;
    return this._head[this._offset++];
  }

  clear() {
    this.length = 0;
    this._head = this._tail = [];
  }
}

console.time('LinkedListNext');
const it3 = new LinkedListNext();

for (let i = 0; i < 50_000_000; i++)
  it3.push(i);

console.timeStamp('LinkedListNext')

for (let i = 0; i < 50_000_000; i++)
  it3.shift(i);

console.timeEnd('LinkedListNext')

console.time('LinkedList');
const it = new LinkedList();

for (let i = 0; i < 50_000_000; i++)
  it.push(i);
for (let i = 0; i < 50_000_000; i++)
  it.shift(i);

console.timeEnd('LinkedList')

Results LinkedListNext: 892.099ms LinkedList: 2.283s

[RubenVerborgh]

Yes—but the test above is benchmarking a situation that should never happen. It tests the pattern:

• 50,000,000 elements in
• 50,000,000 elements out

However, actual patterns will look like this:

• 2 elements in
• 1 element out
• 1 element in
• 2 elements out
• 4 elements in
• 1 element out
• …

So we'd need evidence that the performance gains translate to frequent additions/deletions.

Separately, it's good for V8 to have some warmup runs before measuring.

[RubenVerborgh]

I created a quick example:

// 100 iterators, with 1,000,000 push/read sequences of 0–4 items

console.time('LinkedList');
for (let a = 0; a < 100; a++) {
  const list = new LinkedList();
  for (let i = 0; i < 1_000_000; i++) {
    for (let j = randInt(0, 4); j > 0; j--)
      list.push(i);
    for (let j = randInt(0, 4); j > 0; j--)
      list.shift();
  }
}
console.timeEnd('LinkedList');

console.time('LinkedListNext');
for (let a = 0; a < 100; a++) {
  const list = new LinkedListNext();
  for (let i = 0; i < 1_000_000; i++) {
    for (let j = randInt(0, 4); j > 0; j--)
      list.push(i);
    for (let j = randInt(0, 4); j > 0; j--)
      list.shift();
  }
}
console.timeEnd('LinkedListNext');

function randInt(min: number, max: number) {
  return Math.floor(Math.random() * (max - min + 1)) + min;
}

which yields for me

LinkedList: 6.865s
LinkedListNext: 6.584s

And this includes the fact that LinkedListNext keeps a lot of items in memory.

[RubenVerborgh]

I'll close this for now until new evidence emerges.