array search vs LLRB

test.ts

const enum AttributeEntry {
  FG = 0,
  BG = 1
}

const enum FLAGS {
  BOLD = 1,
  UNDERLINE = 2,
  BLINK = 4,
  INVERSE = 8,
  INVISIBLE = 16,
  DIM = 32,
  ITALIC = 64
}

interface IColorsRef {
  indexed: number;
  R: number;
  G: number;
  B: number;
}

interface ITextAttributes {
  bold: number;
  underline: number;
  blink: number;
  inverse: number;
  invisible: number;
  dim: number;
  italic: number;
  fgRGB: number;
  bgRGB: number;
  fgRef: IColorsRef;
  bgRef: IColorsRef;
  flags: number;
  fg: number;
  bg: number;
  updateColors(fg: number, bg: number): void;
}

class TextAttributes implements ITextAttributes {
  private _fgRef: IColorsRef;
  private _bgRef: IColorsRef;
  constructor(public flags: number, public fg: number, public bg: number) {
    this._fgRef = {R: 0, G: 0, B: 0, indexed: 0};
    this._getColors(this.fg, this._fgRef, this.fgRGB);
    this._bgRef = {R: 0, G: 0, B: 0, indexed: 0};
    this._getColors(this.bg, this._bgRef, this.bgRGB);
  }
  updateColors(fg: number, bg: number): void {
    this.fg = fg;
    this._getColors(this.fg, this._fgRef, this.fgRGB);
    this.bg = bg;
    this._getColors(this.bg, this._bgRef, this.bgRGB);
  }
  get fgRGB(): number {
    return this.fg & 0x80000000;
  }
  set fgRGB(value: number) {
    if (value) this.fg | 0x80000000;
    else this.fg &= ~0x80000000;
  }
  get bgRGB(): number {
    return this.bg & 0x80000000;
  }
  set bgRGB(value: number) {
    if (value) this.bg | 0x80000000;
    else this.bg &= ~0x80000000;
  }
  private _getColors(value: number, colors: IColorsRef, isRGB: number): void {
    if (isRGB) {
      colors.R = (value >> 16) & 0xFF;
      colors.G = (value >> 8) & 0xFF;
      colors.B = value & 255;
      colors.indexed = 0;
    } else {
      colors.R = 0;
      colors.G = 0;
      colors.B = 0;
      colors.indexed = value & 255;
    }
  }
  private _setColors(colors: IColorsRef, isRGB: number): number {
    if (isRGB) return (colors.R << 16) | (colors.G << 8) | colors.B | 0x80000000;
    return colors.indexed & 255;
  }
  get fgRef(): IColorsRef {
    return this._fgRef;
  }
  set fgRef(colors: IColorsRef) {
    this.fg = this._setColors(colors, this.fgRGB);
    this._getColors(this.fg, this._fgRef, this.fgRGB);
  }
  get bgRef(): IColorsRef {
    return this._bgRef;
  }
  set bgRef(colors: IColorsRef) {
    this.bg = this._setColors(colors, this.bgRGB);
    this._getColors(this.bg, this._bgRef, this.bgRGB);
  }
  get bold(): number {
    return this.flags & FLAGS.BOLD;
  }
  set bold(value: number) {
    if (value) this.flags |= FLAGS.BOLD;
    else this.flags &= ~FLAGS.BOLD;
  }
  get underline(): number {
    return this.flags & FLAGS.UNDERLINE;
  }
  set underline(value: number) {
    if (value) this.flags |= FLAGS.UNDERLINE;
    else this.flags &= ~FLAGS.UNDERLINE;
  }
  get blink(): number {
    return this.flags & FLAGS.BLINK;
  }
  set blink(value: number) {
    if (value) this.flags |= FLAGS.BLINK;
    else this.flags &= ~FLAGS.BLINK;
  }
  get inverse(): number {
    return this.flags & FLAGS.INVERSE;
  }
  set inverse(value: number) {
    if (value) this.flags |= FLAGS.INVERSE;
    else this.flags &= ~FLAGS.INVERSE;
  }
  get invisible(): number {
    return this.flags & FLAGS.INVISIBLE;
  }
  set invisible(value: number) {
    if (value) this.flags |= FLAGS.INVISIBLE;
    else this.flags &= ~FLAGS.INVISIBLE;
  }
  get dim(): number {
    return this.flags & FLAGS.DIM;
  }
  set dim(value: number) {
    if (value) this.flags |= FLAGS.DIM;
    else this.flags &= ~FLAGS.DIM;
  }
  get italic(): number {
    return this.flags & FLAGS.ITALIC;
  }
  set italic(value: number) {
    if (value) this.flags |= FLAGS.ITALIC;
    else this.flags &= ~FLAGS.ITALIC;
  }
}

class AttributeStorage {
  public data: Uint32Array;
  public refs: Uint32Array;
  constructor(initial: number) {
    this.data = new Uint32Array(initial * 2);
    this.refs = new Uint32Array(initial);
  }
  private _getSlot(attrs: ITextAttributes): number {
    // search in O(n) :(
    for (let i = 0; i < this.refs.length; i++) {
      if (!this.refs[i]) {
        this.data[i * 2 + AttributeEntry.FG] = attrs.fg;
        this.data[i * 2 + AttributeEntry.BG] = attrs.bg;
        return i;
      }
      if (this.data[i * 2 + AttributeEntry.FG] === attrs.fg
          && this.data[i * 2 + AttributeEntry.BG] === attrs.bg) return i;
    }
    // mem exhausted - resize
    const idx = this.refs.length;
    const data = new Uint32Array(this.data.length * 2);
    for (let i = 0; i < this.data.length; ++i) data[i] = this.data[i];
    this.data = data;
    const refs = new Uint32Array(this.refs.length * 2);
    for (let i = 0; i < this.refs.length; ++i) refs[i] = this.refs[i];
    this.refs = refs;
    return idx;
  }
  ref(slot: number): void {
    if (slot < 0) this.refs[slot & 0xFFFFFF]++;
  }
  unref(slot: number): void {
    if (slot < 0 && this.refs[slot & 0xFFFFFF]) this.refs[slot & 0xFFFFFF]--;
  }
  loadAttrs(slot: number, attrs: ITextAttributes): void {
    if (slot < 0) {
      attrs.flags = slot >> 24 & 7;
      const idx = slot << 1 & 0xFFFFFF;
      attrs.updateColors(this.data[idx + AttributeEntry.FG], this.data[idx + AttributeEntry.BG]);
    } else {
      attrs.flags = slot >> 24;
      attrs.updateColors(slot >> 16 & 0xFF, slot >> 8 & 0xFF);
    }
  }
  storeAttrs(attrs: ITextAttributes): number {
    if (attrs.fgRGB || attrs.bgRGB) {
      const idx = this._getSlot(attrs);
      return idx | attrs.flags << 24 | 2147483648;
    }
    return attrs.flags << 24 | attrs.fg << 16 | attrs.bg << 8;
  }
}


class PoolAllocatorU32 {
  public HEAP: Uint32Array;
  public entrySize: number;
  public head: number;
  public numSlots: number;
  constructor(public initialSlots: number, public maxSlots: number, public slotSize: number) {    
    // adjust slotSize to multiple of 4 (must be at least 4 bytes to hold list address)
    this.entrySize = slotSize;

    // check for address overflow
    if ((initialSlots + 1) * this.entrySize > 0xFFFFFFFF) throw new Error('initial address space exceeds 2^32');
    if ((maxSlots + 1) * this.entrySize > 0xFFFFFFFF) throw new Error('max address space exceeds 2^32');

    // create storage, reserve first slot as NULL
    this.HEAP = new Uint32Array(this.entrySize * (this.initialSlots + 1));

    // insert free list pointers
    // last slot gets NULL pointer
    // head points to first slot at entrySize
    for (let i = this.entrySize; i < this.HEAP.length; i += this.entrySize) this.HEAP[i] = i + this.entrySize;
    this.HEAP[this.HEAP.length - this.entrySize] = 0;
    this.head = this.entrySize;
    this.numSlots = this.initialSlots;
  }
  alloc(): number {
    if (!this.head) {
      // out of memory, try to resize
      let newSlots = this.numSlots * 2;
      if (newSlots > this.maxSlots) newSlots = this.maxSlots;
      if (newSlots === this.numSlots) throw new Error('out of memory');

      // alloc new storage and copy values over
      const HEAP = new Uint32Array(this.entrySize * (newSlots + 1));
      for (let i = 0; i < this.HEAP.length; ++i) HEAP[i] = this.HEAP[i];
      HEAP[HEAP.length - this.entrySize] = 0;
      for (let i = this.HEAP.length; i < HEAP.length; i += this.entrySize) HEAP[i] = i + this.entrySize;
      HEAP[HEAP.length - this.entrySize] = 0;
      this.head = this.HEAP.length;
      this.numSlots = newSlots;
      this.HEAP = HEAP;
    }
    const idx = this.head;
    this.head = this.HEAP[idx];
    return idx;
  }
  free(idx: number) {
    this.HEAP[idx] = this.head;
    this.head = idx;
  }
}




// LLRB
interface INode {
  key: number;
  value: number;
  red: number;
  left: PNode;
  right: PNode;
}
const enum ENode {
  KEY = 0,
  VALUE = 1,
  RED = 2,
  LEFT = 3,
  RIGHT = 4
}

type PNode = number;
const nullptr = 0;

class LLRB {
  //public memory: PoolAllocator;
  public memory: PoolAllocatorU32;
  public M: Uint32Array;
  public root: PNode;
  public bottom: PNode;
  public alloc: () => PNode;
  constructor(initialSlots: number, maxSlots: number) {
    //this.memory = new PoolAllocator(initialSlots, maxSlots, 20);
    //this.M = this.memory.HEAP32;
    this.memory = new PoolAllocatorU32(initialSlots, maxSlots, 5);
    this.M = this.memory.HEAP;
    this.alloc = this.memory.alloc.bind(this.memory);
    this.bottom = nullptr;
    this.root = this.bottom;
  }
  //alloc() {
  //  return this.memory.alloc() >> 2;
  //}
  compare(a: number, b: number): number {
    return a < b ? -1 : a > b ? 1 : 0;
  }
  find(key: number): PNode {
    const M = this.M;
    let n = this.root;
    while (n !== this.bottom) {
      let c = this.compare(key, M[n + ENode.KEY]);
      if (c === 0) return n;
      n = c < 0 ? M[n + ENode.LEFT] : M[n + ENode.RIGHT];
    }
    return nullptr;
  }
  insert(key: number, value: number) {
    this.root = this._insert(this.root, key, value, this.M);
    this.M[this.root + ENode.RED] = 0;
  }
  removeMin() {
    if (this.root === this.bottom) return;
    const M = this.M;
    const root_left = M[this.root + ENode.LEFT];
    const root_right = M[this.root + ENode.RIGHT];
    if (!M[root_left + ENode.RED] && !M[root_right + ENode.RED]) M[this.root + ENode.RED] = 1;
    this.root = this._removeMin(this.root, M);
    M[this.root + ENode.RED] = 0;
  }
  remove(key: number) {
    if (!this.find(key)) return;
    const M = this.M;
    if (!M[M[this.root + ENode.LEFT] + ENode.RED] && !M[M[this.root + ENode.RIGHT] + ENode.RED]) M[this.root + ENode.RED] = 1;
    this.root = this._remove(this.root, key, M);
    M[this.root + ENode.RED] = 0;
  }
  private _insert(h: PNode, key: number, value: number, M: Uint32Array): PNode {
    if (h === this.bottom) {
      const idx = this.alloc();
      this.M = this.memory.HEAP;
      M = this.M;
      M[idx + ENode.KEY] = key;
      M[idx + ENode.VALUE] = value;
      M[idx + ENode.RED] = 1;
      M[idx + ENode.LEFT] = this.bottom;
      M[idx + ENode.RIGHT] = this.bottom;
      return idx;
    }
    const c = this.compare(key, M[h + ENode.KEY]);
    if (c < 0) this.M[h + ENode.LEFT] = this._insert(M[h + ENode.LEFT], key, value, M);
    else if (c > 0) this.M[h + ENode.RIGHT] = this._insert(M[h + ENode.RIGHT], key, value, M);
    else this.M[h + ENode.VALUE] = value;
    M = this.M;
    if (M[M[h + ENode.RIGHT] + ENode.RED] && !M[M[h + ENode.LEFT] + ENode.RED]) h = this._rotateLeft(h, M);
    if (M[M[h + ENode.LEFT] + ENode.RED] && M[M[M[h + ENode.LEFT] + ENode.LEFT] + ENode.RED]) h = this._rotateRight(h, M);
    if (M[M[h + ENode.LEFT] + ENode.RED] && M[M[h + ENode.RIGHT] + ENode.RED]) this._flipColors(h, M);
    return h;
  }
  private _remove(h: PNode, key: number, M: Uint32Array) {
    if (this.compare(key, M[h + ENode.KEY]) < 0)  {
      const left = M[h + ENode.LEFT];
      if (!M[left + ENode.RED] && !M[M[left + ENode.LEFT] + ENode.RED]) h = this._moveRedLeft(h, M);
      M[h + ENode.LEFT] = this._remove(M[h + ENode.LEFT], key, M);
    } else {
      if (M[M[h + ENode.LEFT] + ENode.RED]) h = this._rotateRight(h, M);
      if (this.compare(key, M[h + ENode.KEY]) === 0 && (M[h + ENode.RIGHT] === this.bottom)) return this.bottom;
      const right = M[h + ENode.RIGHT];
      if (!M[right + ENode.RED] && !M[M[right + ENode.LEFT] + ENode.RED]) h = this._moveRedRight(h, M);
      if (this.compare(key, M[h + ENode.KEY]) === 0) {
        const x = this._min(M[h + ENode.RIGHT], M);
        M[h + ENode.KEY] = M[x + ENode.KEY];
        M[h + ENode.VALUE] = M[x + ENode.VALUE];
        M[h + ENode.RIGHT] = this._removeMin(M[h + ENode.RIGHT], M);
      } else M[h + ENode.RIGHT] = this._remove(M[h + ENode.RIGHT], key, M);
    }
    return this._balance(h, M);
  }
  private _min(h: PNode, M: Uint32Array): PNode {
    if (M[h + ENode.LEFT] === this.bottom) return h;
    return this._min(M[h + ENode.LEFT], M);
  }
  private _removeMin(h: PNode, M: Uint32Array) {
    const left = M[h + ENode.LEFT];
    if (left === this.bottom) return this.bottom;
    if (!M[left + ENode.RED] && !M[M[left + ENode.LEFT] + ENode.RED]) h = this._moveRedLeft(h, M);
    M[h + ENode.LEFT] = this._removeMin(left, M);
    return this._balance(h, M);
  }
  private _balance(h: PNode, M: Uint32Array) {
    if (M[M[h + ENode.RIGHT] + ENode.RED]) h = this._rotateLeft(h, M);
    const left = M[h + ENode.LEFT];
    if (M[left + ENode.RED] && M[M[left + ENode.LEFT] + ENode.RED]) h = this._rotateRight(h, M);
    if (M[M[h + ENode.LEFT] + ENode.RED] && M[M[h + ENode.RIGHT] + ENode.RED]) this._flipColors(h, M);
    return h;
  }
  private _moveRedLeft(h: PNode, M: Uint32Array) {
    this._flipColors(h, M);
    const right = M[h + ENode.RIGHT];
    if (M[M[right + ENode.LEFT] + ENode.RED]) {
        M[h + ENode.RIGHT] = this._rotateRight(right, M);
        h = this._rotateLeft(h, M);
    }
    return h;
  }
  private _moveRedRight(h: PNode, M: Uint32Array) {
    this._flipColors(h, M);
    if (M[M[M[h + ENode.LEFT] + ENode.LEFT] + ENode.RED]) h = this._rotateRight(h, M);
    return h;
  }
  private _rotateRight(h: PNode, M: Uint32Array) {
    const x = M[h + ENode.LEFT];
    M[h + ENode.LEFT] = M[x + ENode.RIGHT];
    M[x + ENode.RIGHT] = h;
    M[x + ENode.RED] = M[h + ENode.RED];
    M[h + ENode.RED] = 1;
    return x;
  }
  private _rotateLeft(h: PNode, M: Uint32Array) {
    const x = M[h + ENode.RIGHT];
    M[h + ENode.RIGHT] = M[x + ENode.LEFT];
    M[x + ENode.LEFT] = h;
    M[x + ENode.RED] = M[h + ENode.RED];
    M[h + ENode.RED] = 1;
    return x;
  }
  private _flipColors(h: PNode, M: Uint32Array) {
    M[h + ENode.RED] ^= 1;
    M[M[h + ENode.LEFT] + ENode.RED] ^= 1;
    M[M[h + ENode.RIGHT] + ENode.RED] ^= 1;
  }
}

class LLRBIterator {
  private _stack: number[];
  constructor(private _llrb: LLRB, private _reverse=false) {
    this._stack = [];
    this._load(this._llrb.root, (this._reverse) ? ENode.RIGHT : ENode.LEFT);
  }
  private _load(node: PNode, direction: ENode) {
    while (node) {
      this._stack.push(node);
      node = this._llrb.M[node + direction];
    }
  }
  next(): PNode {
    const node = this._stack.pop();
    if (this._reverse) this._load(this._llrb.M[node + ENode.LEFT], ENode.RIGHT);
    else this._load(this._llrb.M[node + ENode.RIGHT], ENode.LEFT);
    return node;
  }
  hasNext(): boolean {
    return !!this._stack.length;
  }
  toArray(): PNode[] {
    const res = [];
    while (this.hasNext()) res.push(this.next());
    return res;
  }
}



function test(n: number, scale: number) {
  let sum = [0, 0];
  for (let k = 0; k < scale; ++k) {
    const llrb = new LLRB(1, 20000000);
    for (let i = 0; i < n; ++i) llrb.insert(n, n);
    const start = process.hrtime();
    for (let i = n; i < n+10000; ++i) llrb.insert(Math.random() * Math.pow(2, 24) >>> 0, 0);
    const end = process.hrtime(start);
    sum[0] += end[0];
    sum[1] += end[1];
  }
  return [sum[0], sum[1]/1000000];
}


for (let i = 0; i < 5; ++i) console.log('100,', test(100, 100)[1]);
//for (let i = 0; i < 5; ++i) console.log('250,', test(100, 100)[1]);
//for (let i = 0; i < 5; ++i) console.log('500,', test(100, 100)[1]);
//for (let i = 0; i < 5; ++i) console.log('750,', test(100, 100)[1]);
for (let i = 0; i < 5; ++i) console.log('1000,', test(1000, 100)[1]);
//for (let i = 0; i < 5; ++i) console.log('2500,', test(1000, 100)[1]);
//for (let i = 0; i < 5; ++i) console.log('5000,', test(1000, 100)[1]);
//for (let i = 0; i < 5; ++i) console.log('7500,', test(1000, 100)[1]);
for (let i = 0; i < 5; ++i) console.log('10000,', test(10000, 100)[1]);
//for (let i = 0; i < 5; ++i) console.log('25000,', test(10000, 100)[1]);
//for (let i = 0; i < 5; ++i) console.log('50000,', test(10000, 100)[1]);
//for (let i = 0; i < 5; ++i) console.log('75000,', test(10000, 100)[1]);
for (let i = 0; i < 5; ++i) console.log('100000,', test(100000, 100)[1]);
//for (let i = 0; i < 5; ++i) console.log('250000,', test(100000, 100)[1]);
//for (let i = 0; i < 5; ++i) console.log('500000,', test(100000, 100)[1]);
//for (let i = 0; i < 5; ++i) console.log('750000,', test(100000, 100)[1]);
for (let i = 0; i < 5; ++i) console.log('1000000,', test(1000000, 100)[1]);
//for (let i = 0; i < 5; ++i) console.log('2500000,', test(1000000, 100)[1]);
//for (let i = 0; i < 5; ++i) console.log('5000000,', test(1000000, 100)[1]);
//for (let i = 0; i < 5; ++i) console.log('7500000,', test(1000000, 100)[1]);
for (let i = 0; i < 5; ++i) console.log('10000000,', test(10000000, 100)[1]);


function test2(n: number, scale: number) {
  let sum = [0, 0];
  const attr = new TextAttributes(0, 0, 0);
  for (let k = 0; k < scale; ++k) {
    const stor = new AttributeStorage(1);
    for (let i = 0; i < n; ++i) {
      attr.fg = i;
      let p = stor.storeAttrs(attr);
      stor.ref(p);
    }
    const start = process.hrtime();
    for (let i = n; i < n+10000; ++i) {
      //attr.fg = i;
      attr.fg = Math.random() * Math.pow(2, 24) >>> 0;
      let p = stor.storeAttrs(attr);
      stor.ref(p);
    }
    const end = process.hrtime(start);
    sum[0] += end[0];
    sum[1] += end[1];
  }
  return [sum[0], sum[1]/1000000];
}


for (let i = 0; i < 5; ++i) console.log('100,', test2(100, 100)[1]);
//for (let i = 0; i < 5; ++i) console.log('250,', test2(100, 100)[1]);
//for (let i = 0; i < 5; ++i) console.log('500,', test2(100, 100)[1]);
//for (let i = 0; i < 5; ++i) console.log('750,', test2(100, 100)[1]);
for (let i = 0; i < 5; ++i) console.log('1000,', test2(1000, 100)[1]);
//for (let i = 0; i < 5; ++i) console.log('2500,', test2(1000, 100)[1]);
//for (let i = 0; i < 5; ++i) console.log('5000,', test2(1000, 100)[1]);
//for (let i = 0; i < 5; ++i) console.log('7500,', test2(1000, 100)[1]);
for (let i = 0; i < 5; ++i) console.log('10000,', test2(10000, 100)[1]);
//for (let i = 0; i < 5; ++i) console.log('25000,', test2(10000, 100)[1]);
//for (let i = 0; i < 5; ++i) console.log('50000,', test2(10000, 100)[1]);
//for (let i = 0; i < 5; ++i) console.log('75000,', test2(10000, 100)[1]);
for (let i = 0; i < 5; ++i) console.log('100000,', test2(100000, 100)[1]);
//for (let i = 0; i < 5; ++i) console.log('250000,', test2(100000, 100)[1]);
//for (let i = 0; i < 5; ++i) console.log('500000,', test2(100000, 100)[1]);
//for (let i = 0; i < 5; ++i) console.log('750000,', test2(100000, 100)[1]);
for (let i = 0; i < 5; ++i) console.log('1000000,', test2(1000000, 100)[1]);
//for (let i = 0; i < 5; ++i) console.log('2500000,', test2(1000000, 100)[1]);
//for (let i = 0; i < 5; ++i) console.log('5000000,', test2(1000000, 100)[1]);
//for (let i = 0; i < 5; ++i) console.log('7500000,', test2(1000000, 100)[1]);
for (let i = 0; i < 5; ++i) console.log('10000000,', test2(10000000, 100)[1]);