Memento: Speed improvements.

Avoid searching the linked list of blocks in order to remove a
block by moving to a doubly linked list. This can be done
without increasing the amount of memory in use by making better
use of the 'parent' pointer that is only used when displaying
nested blocks.

Also store magic values in the 'child' and 'sibling' pointers
(again only used when displaying nested blocks) so that we
can quickly verify that a block is real before doing too much
with it.

Those changes drastically reduce the time required for
MEMENTO_LEAKONLY runs (now the same order of magnitude as non
memento runs).

Normal memento runs are still very slow when the numbers of
blocks increase due to the paranoid checking taking time.

To ameliorate this a bit, we try 2 other things.

Firstly, we optimise the searching of blocks by making use of
int aligned tests. This still doesn't make much difference.

Secondly, we introduce a new mechanism for the 'paranoia'
levels. If a negative number is given for the paranoia level
(say -n) then we first perform our overwrite checks after n events.
We next test after 2n events, then 4n, then 8n etc.

The new default paranoia level is set to be -1024.

This makes a huge difference, and brings normal memento runs
down to be comparable with debug runs.

1 files changed, 9 insertions, 5 deletions

diff --git a/include/mupdf/memento.h b/include/mupdf/memento.h
index 90f9285e..0a1978a6 100644
--- a/include/mupdf/memento.h
+++ b/include/mupdf/memento.h
@@ -1,4 +1,4 @@
-/* Copyright (C) 2009-2015 Artifex Software, Inc.
+/* Copyright (C) 2009-2016 Artifex Software, Inc.
    All Rights Reserved.
 
    This software is provided AS-IS with no warranty, either express or
@@ -29,10 +29,14 @@
  *    On each event Memento increments a counter. Every block is tagged with
  *    the current counter on allocation. Every so often during program
  *    execution, the heap is checked for consistency. By default this happens
- *    every 1024 events. This can be changed at runtime by using
- *    Memento_setParanoia(int level). 0 turns off such checking, 1 sets
- *    checking to happen on every event, any other number n sets checking to
- *    happen once every n events.
+ *    after 1024 events, then after 2048 events, then after 4096 events, etc.
+ *    This can be changed at runtime by using Memento_setParanoia(int level).
+ *    0 turns off such checking, 1 sets checking to happen on every event,
+ *    any positive number n sets checking to happen once every n events,
+ *    and any negative number n sets checking to happen after -n events, then
+ *    after -2n events etc.
+ *
+ *    The default paranoia level is therefore -1024.
  *
  *    Memento keeps blocks around for a while after they have been freed, and
  *    checks them as part of these heap checks to see if they have been