benchmark.out.txt

> lru_map@0.4.1 benchmark /Users/rsms/src/js-lru
> node --expose-gc benchmark.js

N = 10000, Iterations = 1000

----------
  function(){
    // 1. put
    //    Simply append a new entry.
    //    There will be no reordering since we simply append to the tail.
    for (var i=N; --i;)
      c.set('key'+i, i);
  }
   rss:        +7,164 kB -- (19,944 kB -> 27,108 kB)
   heap total: +3,576 kB -- (5,128 kB -> 8,704 kB)
   heap used:  +1,504 kB -- (2,052 kB -> 3,556 kB)

  -- 0.798 ms avg per iteration --

----------
  function(){
    // 2. get recent -> old
    //    Get entries starting with newest, effectively reversing the list.
    //
    // a. For each get, a find is first executed implemented as a native object with
    //    keys mapping to entries, so this should be reasonably fast as most native
    //    objects are implemented as hash maps.
    //
    // b. For each get, the aquired item will be moved to tail which includes a
    //    maximum of 7 assignment operations (minimum 3).
    for (var i=1,L=N+1; i<L; ++i)
      c.get('key'+i, i);
  }
   rss:        +300 kB -- (27,180 kB -> 27,480 kB)
   heap total: +0 kB -- (8,704 kB -> 8,704 kB)
   heap used:  +11 kB -- (3,552 kB -> 3,563 kB)

  -- 0.858 ms avg per iteration --

----------
  function(){
    // 3. get old -> recent
    //    Get entries starting with oldest, effectively reversing the list.
    //
    //  - Same conditions apply as for test 2.
    for (var i=1,L=N+1; i<L; ++i)
      c.get('key'+i);
  }
   rss:        +724 kB -- (27,480 kB -> 28,204 kB)
   heap total: +0 kB -- (8,704 kB -> 8,704 kB)
   heap used:  +5 kB -- (3,557 kB -> 3,562 kB)

  -- 0.753 ms avg per iteration --

----------
  function(){
    // 4. get missing
    //    Get try to get entries not in the cache.
    //  - Same conditions apply as for test 2, section a.
    for (var i=1,L=N+1; i<L; ++i)
      c.get('xkey'+i);
  }
   rss:        +612 kB -- (28,252 kB -> 28,864 kB)
   heap total: +0 kB -- (8,704 kB -> 8,704 kB)
   heap used:  +8 kB -- (3,555 kB -> 3,562 kB)

  -- 0.63 ms avg per iteration --

----------
  function(){
    // 5. put overflow
    //    Overflow the cache with N more items than it can hold.
    // a. The complexity of put in this case should be:
    //    ( <get whith enough space> + <shift> )
    for (var i=N; --i;)
      c.set('key2_'+i, i);
  }
   rss:        +5,384 kB -- (28,868 kB -> 34,252 kB)
   heap total: +5,312 kB -- (8,704 kB -> 14,016 kB)
   heap used:  +531 kB -- (3,555 kB -> 4,086 kB)

  -- 0.757 ms avg per iteration --

----------
  function(){
    // 6. shift head -> tail
    //    Remove all entries going from head to tail
    for (var i=1,L=N+1; i<L; ++i)
      c.shift();
  }
   rss:        +920 kB -- (34,260 kB -> 35,180 kB)
   heap total: -1,668 kB -- (14,016 kB -> 12,348 kB)
   heap used:  -1,746 kB -- (4,078 kB -> 2,332 kB)

  -- 0.021 ms avg per iteration --

----------
  function(){
    // 7. put
    //    Simply put N new items into an empty cache with exactly N space.
    for (var i=N; --i;)
      c.set('key'+i, i);
  }
   rss:        +1,132 kB -- (32,760 kB -> 33,892 kB)
   heap total: +1,732 kB -- (11,836 kB -> 13,568 kB)
   heap used:  +1,240 kB -- (2,324 kB -> 3,564 kB)

  -- 0.827 ms avg per iteration --

----------
  function(){
    // 8. delete random
    // a. Most operations (which are not entries at head or tail) will cause closes
    //    siblings to be relinked.
    for (var i=shuffledKeys.length, key; key = shuffledKeys[--i]; ) {
      c.delete('key'+i, i);
    }
  }
   rss:        +300 kB -- (33,956 kB -> 34,256 kB)
   heap total: -452 kB -- (13,568 kB -> 13,116 kB)
   heap used:  -985 kB -- (3,650 kB -> 2,665 kB)

  -- 0.502 ms avg per iteration --