GNU bug report logs - #43016
replace-region-contents takes a lot of time when called from json-pretty-print-buffer

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 43016 in the body.
You can then email your comments to 43016 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: ljell <laszlomail <at> protonmail.com>
To: "bug-gnu-emacs <at> gnu.org" <bug-gnu-emacs <at> gnu.org>
Subject: replace-region-contents takes a lot of time when called from
 json-pretty-print-buffer
Date: Mon, 24 Aug 2020 08:25:14 +0000

[Message part 1 (text/plain, inline)]

I have a code which pretty prints data in json:

...
(with-temp-buffer
(insert data)
(json-pretty-print-buffer)
(write-file "data.json"))
...

This code runs for several minutes (I didn't time it, but it's about 1-2 minutes) with Emacs 27.1 It takes several seconds with Emacs 26. Data is about 1MB on disk in pretty printed elisp format.

I tried profiling with this result:

- progn 7486 98%
- json-pretty-print-buffer 7438 98%
- json-pretty-print 7438 98%
- replace-region-contents 7438 98%
+ #<compiled 0x3854909> 198 2%
+ insert 43 0%
+ write-file 5 0%

Apparently, replace-region-contents takes 98% of the CPU time.

Using Windows version from GNU ftp :

GNU Emacs 27.1 (build 1, x86_64-w64-mingw32) of 2020-08-12

[Message part 2 (text/html, inline)]

Message #8 received at 43016 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: ljell <laszlomail <at> protonmail.com>, Tassilo Horn <tsdh <at> gnu.org>
Cc: 43016 <at> debbugs.gnu.org
Subject: Re: bug#43016: replace-region-contents takes a lot of time when called
 from json-pretty-print-buffer
Date: Mon, 24 Aug 2020 13:37:39 +0300

> Date: Mon, 24 Aug 2020 08:25:14 +0000
> From: ljell via "Bug reports for GNU Emacs,
>  the Swiss army knife of text editors" <bug-gnu-emacs <at> gnu.org>
> 
> I have a code which pretty prints data in json:
> 
> ...
>   (with-temp-buffer
>     (insert data)
>     (json-pretty-print-buffer)
>     (write-file "data.json"))
> ...
> 
> This code runs for several minutes (I didn't time it, but it's about 1-2 minutes) with Emacs 27.1  It takes
> several seconds with Emacs 26.  Data is about 1MB on disk in pretty printed elisp format.
> 
> I tried profiling with this result:
> 
>           - progn                                                7486  98%
>            - json-pretty-print-buffer                            7438  98%
>             - json-pretty-print                                  7438  98%
>              - replace-region-contents                           7438  98%
>               + #<compiled 0x3854909>                             198   2%
>            + insert                                                43   0%
>            + write-file                                             5   0%
> 
> Apparently, replace-region-contents  takes 98% of the CPU time.

Thank you for your report and the data.  Is it possible to have the
file with which you've seen this problem?

Tassilo, could you please look into this regression?

Message #11 received at 43016 <at> debbugs.gnu.org (full text, mbox):

From: Tassilo Horn <tsdh <at> gnu.org>
To: ljell <laszlomail <at> protonmail.com>
Cc: Eli Zaretskii <eliz <at> gnu.org>,
 "43016 <at> debbugs.gnu.org" <43016 <at> debbugs.gnu.org>,
 Paul Eggert <eggert <at> cs.ucla.edu>
Subject: Re: bug#43016: replace-region-contents takes a lot of time when
 called from json-pretty-print-buffer
Date: Mon, 24 Aug 2020 19:14:50 +0200

[Message part 1 (text/plain, inline)]

ljell <laszlomail <at> protonmail.com> writes:

Hi all,

>> Thank you for your report and the data. Is it possible to have the
>> file with which you've seen this problem?
>
> Looks like the problem occurs only with accented characters present,
> so I created a json file with them. Attached.

I can easily reproduce the problem using this file.

Back when I introduced that feature, i.e., that json pretty printing
uses replace-region-contents (which in turn uses
replace-buffer-contents), I added a parameter MAX-SECS to those
functions which should restrict the compareseq call's runtime to that
amount of seconds and give up if it takes longer, in which case the
replacement is just a delete + insert (which hasn't the benefit of
retaining point and marks but is fast).  That's controllable via the
variable json-pretty-print-max-secs whose default is 2.0 seconds.

In 975893b2290 Paul (in Cc) improved that change so that the context
struct given to compareseq doesn't store the MAX-SECS but a timespec
time_limit computed beforehand and used later in the
compareseq_early_abort tests later on saving conversions there.  (The
change looks good to me with my very limited C knowledge.)

The actual problem here is that for the specific test file, there are
(only) 321 compareseq_early_abort tests performed and it seems that the
first 320 are executed almost immediately (before MAX-SECS are over),
then no test is performed for minutes, and then a last test is performed
leading to an early_abort of compareseq followed by delete + insert.

This "early_abort if it takes too long" thingy doesn't work if the
compareseq_early_abort tests aren't performed somewhat regularly.  If
there can be minutes between two consecutive tests like here, then this
whole thing doesn't work out.

replace-region-contents and replace-buffer-contents have another
MAX-COSTS parameter which json.el sets to 64 (with a FIXME since I had
no clue what a sensible value was but extracted that value from
edidfns.c where it was hard-coded before).  I've reduced the value in
the json.el call to 16 for testing and indeed it became faster but still
too slow for the very same reason.  Now there were only 65
compareseq_early_abort tests but again 64 occurred almost immediately
whereas the last one aborting the comparison happened after ~40 seconds.

So basically I'd say the problem is in gnulib's compareseq.  If it can't
be fixed there, I see no other possibility than to stop using
replace-buffer/region-contents in json.el (and wherever it might also be
used).  That would be sad because except for the performance in some
cases, it's very nice. :-(

Maybe Paul has some idea (or knows compareseq better)?

I'm attaching a patch adding some printfs which I used to diagnose the
issue.  (Yes, I'm cannot operate GDB without guidance...)

[replace_buffer_contents_debugging.patch (text/x-patch, inline)]

diff --git a/src/editfns.c b/src/editfns.c
index 949f3825a3..2037d1a133 100644
--- a/src/editfns.c
+++ b/src/editfns.c
@@ -2000,6 +2000,7 @@ DEFUN ("replace-buffer-contents", Freplace_buffer_contents,
   else
     CHECK_FIXNUM (max_costs);
 
+  printf("max_secs: %f\n", XFLOAT_DATA (max_secs));
   struct timespec time_limit = make_timespec (0, -1);
   if (!NILP (max_secs))
     {
@@ -2008,7 +2009,11 @@ DEFUN ("replace-buffer-contents", Freplace_buffer_contents,
 			     lisp_time_argument (max_secs)),
 	tmax = make_timespec (TYPE_MAXIMUM (time_t), TIMESPEC_HZ - 1);
       if (timespec_cmp (tlim, tmax) < 0)
-	time_limit = tlim;
+        {
+          time_limit = tlim;
+          printf("time_limit: %lld.%.9ld\n",
+                 (long long)time_limit.tv_sec, time_limit.tv_nsec);
+        }
     }
 
   /* Micro-optimization: Casting to size_t generates much better
@@ -2038,6 +2043,10 @@ DEFUN ("replace-buffer-contents", Freplace_buffer_contents,
      later.  */
   bool early_abort = compareseq (0, size_a, 0, size_b, false, &ctx);
 
+  printf("early_abort: %d\n", early_abort);
+  printf("early_abort_tests: %u\n", ctx.early_abort_tests);
+  printf("size_a: %ld, size_b: %ld\n", size_a, size_b);
+
   if (early_abort)
     {
       del_range (min_a, ZV);
@@ -2186,6 +2195,8 @@ buffer_chars_equal (struct context *ctx,
 static bool
 compareseq_early_abort (struct context *ctx)
 {
+  printf("early_abort_tests\n");
+  ctx->early_abort_tests++;
   if (ctx->time_limit.tv_nsec < 0)
     return false;
   return timespec_cmp (ctx->time_limit, current_timespec ()) < 0;

[Message part 3 (text/plain, inline)]

Bye,
Tassilo

Message #14 received at 43016 <at> debbugs.gnu.org (full text, mbox):

From: ljell <laszlomail <at> protonmail.com>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: "43016 <at> debbugs.gnu.org" <43016 <at> debbugs.gnu.org>,
 Tassilo Horn <tsdh <at> gnu.org>
Subject: Re: bug#43016: replace-region-contents takes a lot of time when
 called from json-pretty-print-buffer
Date: Mon, 24 Aug 2020 12:13:15 +0000

[Message part 1 (text/plain, inline)]

>
> Thank you for your report and the data. Is it possible to have the
> file with which you've seen this problem?
>

Looks like the problem occurs only with accented characters present, so I created a json file with them. Attached.

Warning: Long lines!

After opening the file, just run M-x json-pretty-print-buffer  on it to see how long it takes.


If you run M-x json-pretty-print-buffer on the already pretty file then it's much faster,so maybe it's related to the single long line generated by json-encode.

[test.rar (application/octet-stream, attachment)]

Message #17 received at 43016 <at> debbugs.gnu.org (full text, mbox):

From: ljell <laszlomail <at> protonmail.com>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: "43016 <at> debbugs.gnu.org" <43016 <at> debbugs.gnu.org>,
 Tassilo Horn <tsdh <at> gnu.org>
Subject: Re: bug#43016: replace-region-contents takes a lot of time when
 called from json-pretty-print-buffer
Date: Mon, 24 Aug 2020 12:29:49 +0000

>
> If you run M-x json-pretty-print-buffer on the already pretty file then it's much faster,so maybe it's related to the single long line generated by json-encode.


The json-encode part was missing in my first post, so the relevant code looks like this:

...
  (with-temp-buffer
    (insert (json-encode data))
    (json-pretty-print-buffer)
    (write-file "data.json"))
...


So I insert json encoded lisp data into a temp buffer and then run prettyfing on it, so the json file is more readable and there are no long lines. This code took a few seconds on 26 and it takes much longer with 27.

Message #20 received at 43016 <at> debbugs.gnu.org (full text, mbox):

From: Lars Ingebrigtsen <larsi <at> gnus.org>
To: Tassilo Horn <tsdh <at> gnu.org>
Cc: ljell <laszlomail <at> protonmail.com>,
 "43016 <at> debbugs.gnu.org" <43016 <at> debbugs.gnu.org>,
 Paul Eggert <eggert <at> cs.ucla.edu>
Subject: Re: bug#43016: replace-region-contents takes a lot of time when
 called from json-pretty-print-buffer
Date: Mon, 24 Aug 2020 19:21:24 +0200

Tassilo Horn <tsdh <at> gnu.org> writes:

> That would be sad because except for the performance in some
> cases, it's very nice. :-(

It is indeed very nice.  My guess is that most of the usages of the
function is for shortish JSON structures.  Perhaps we could just
introduce an arbitrary switchover between using replace-region-contents
and plain replacing -- like a hundred K or something?  

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

Message #23 received at 43016 <at> debbugs.gnu.org (full text, mbox):

From: Philipp Stephani <p.stephani2 <at> gmail.com>
To: Lars Ingebrigtsen <larsi <at> gnus.org>
Cc: ljell <laszlomail <at> protonmail.com>,
 "43016 <at> debbugs.gnu.org" <43016 <at> debbugs.gnu.org>,
 Paul Eggert <eggert <at> cs.ucla.edu>, Tassilo Horn <tsdh <at> gnu.org>
Subject: Re: bug#43016: replace-region-contents takes a lot of time when
 called from json-pretty-print-buffer
Date: Mon, 24 Aug 2020 19:25:53 +0200

Am Mo., 24. Aug. 2020 um 19:22 Uhr schrieb Lars Ingebrigtsen <larsi <at> gnus.org>:
>
> Tassilo Horn <tsdh <at> gnu.org> writes:
>
> > That would be sad because except for the performance in some
> > cases, it's very nice. :-(
>
> It is indeed very nice.  My guess is that most of the usages of the
> function is for shortish JSON structures.  Perhaps we could just
> introduce an arbitrary switchover between using replace-region-contents
> and plain replacing -- like a hundred K or something?
>


That's basically what the MAX-SECS and MAX-COST parameters are
supposed to do. We should definitely fix compareseq so that it takes
these costs into account more strictly (e.g. checking at least once
per million iterations or so).

Message #26 received at 43016 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Tassilo Horn <tsdh <at> gnu.org>
Cc: laszlomail <at> protonmail.com, 43016 <at> debbugs.gnu.org, eggert <at> cs.ucla.edu
Subject: Re: bug#43016: replace-region-contents takes a lot of time when
 called from json-pretty-print-buffer
Date: Mon, 24 Aug 2020 20:27:30 +0300

> From: Tassilo Horn <tsdh <at> gnu.org>
> Cc: Eli Zaretskii <eliz <at> gnu.org>,
> 	"43016 <at> debbugs.gnu.org" <43016 <at> debbugs.gnu.org>,
> 	Paul Eggert <eggert <at> cs.ucla.edu>
> Date: Mon, 24 Aug 2020 19:14:50 +0200
> 
> So basically I'd say the problem is in gnulib's compareseq.  If it can't
> be fixed there, I see no other possibility than to stop using
> replace-buffer/region-contents in json.el (and wherever it might also be
> used).  That would be sad because except for the performance in some
> cases, it's very nice. :-(

Could we decide whether to use replace-* functions dynamically, based
on the size of the region/buffer being prettified?

Btw, there's another problem with compareseq, see bug#42931.  I guess
we need to add another criterion for early_abort, based on depth of
recursion?

Thanks.

Message #29 received at 43016 <at> debbugs.gnu.org (full text, mbox):

From: Tassilo Horn <tsdh <at> gnu.org>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: laszlomail <at> protonmail.com, 43016 <at> debbugs.gnu.org, eggert <at> cs.ucla.edu
Subject: Re: bug#43016: replace-region-contents takes a lot of time when
 called from json-pretty-print-buffer
Date: Mon, 24 Aug 2020 21:15:42 +0200

[Message part 1 (text/plain, inline)]

Eli Zaretskii <eliz <at> gnu.org> writes:

>> So basically I'd say the problem is in gnulib's compareseq.  If it
>> can't be fixed there, I see no other possibility than to stop using
>> replace-buffer/region-contents in json.el (and wherever it might also
>> be used).  That would be sad because except for the performance in
>> some cases, it's very nice. :-(
>
> Could we decide whether to use replace-* functions dynamically, based
> on the size of the region/buffer being prettified?

No, the size is just a secondary measure here.  I've successfully and
quickly prettified much larger JSON files.

I've just tried with some other sample json file which is about three
times the size of the file in this report.  That also triggered an
early_abort of compareseq but within MAX-SECS time.  And here I have
almost half a million compareseq_early_abort tests, not just 321.

I've now modified it to approximately the same size as the file of ljell
(the reporter).  Then it doesn't trigger early_abort, is fast, and
slightly below 300.000 early_abort tests are performed.

[sample.json.gz (application/gzip, attachment)]

[Message part 3 (text/plain, inline)]

So the question is why the file in this report with about the same size
and number of changes between minimized and prettified version result in
such strange numbers?

ljell is right, it seems to have to do with the non-ASCII characters.
In my sample.json.gz from above, I've just replaced every "e" with an
"Ê" (except in true/false literals).  When I prettify that, it aborts
early (fast) just after 449 early_abort_tests.

[sample-non-ascii.json.gz (application/gzip, attachment)]

[Message part 5 (text/plain, inline)]

So just replacing "e" with an "Ê" changed "compares in time with 300.000
early_abort_tests" to "doesn't compare in time and makes only 449
early_abort_tests in that time".  The only difference to ljell's test
file is that with mine, there doesn't seem to be a big gap between the
last early_abort_test returning false and the one returning true.

> Btw, there's another problem with compareseq, see bug#42931.  I guess
> we need to add another criterion for early_abort, based on depth of
> recursion?

Ouch, I can also reproduce that.  But as said by Philipp Stephani in
that report, I'd consider protecting against too deep recursion a job of
compareseq, not of its callers.

And I think the issue in that report would also vanish if compareseq
would somehow ensure that its EARLY_ABORT expression would be evaluated
regularly, i.e., there were no long periods without check.  That's the
thing I also observe with the 18 MB file from bug#42931: gazillions of
early_abort_tests early on, then a long phase with no test, and
eventually the segfault.  (Of course it's possible that other files
would result in a quick segfault due to unbounded recursion where that
wouldn't help either...)

Bye,
Tassilo

Message #32 received at 43016 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Tassilo Horn <tsdh <at> gnu.org>
Cc: laszlomail <at> protonmail.com, 43016 <at> debbugs.gnu.org, eggert <at> cs.ucla.edu
Subject: Re: bug#43016: replace-region-contents takes a lot of time when
 called from json-pretty-print-buffer
Date: Mon, 24 Aug 2020 22:36:03 +0300

> From: Tassilo Horn <tsdh <at> gnu.org>
> Cc: laszlomail <at> protonmail.com,  43016 <at> debbugs.gnu.org,  eggert <at> cs.ucla.edu
> Date: Mon, 24 Aug 2020 21:15:42 +0200
> 
> ljell is right, it seems to have to do with the non-ASCII characters.
> In my sample.json.gz from above, I've just replaced every "e" with an
> "Ê" (except in true/false literals).  When I prettify that, it aborts
> early (fast) just after 449 early_abort_tests.
> 
> So just replacing "e" with an "Ê" changed "compares in time with 300.000
> early_abort_tests" to "doesn't compare in time and makes only 449
> early_abort_tests in that time".  The only difference to ljell's test
> file is that with mine, there doesn't seem to be a big gap between the
> last early_abort_test returning false and the one returning true.

I guess it's somehow related to the fact that buffer_chars_equal is
optimized for pure-ASCII buffers, see how we compute a_unibyte and
b_unibyte members of the context struct.

Message #35 received at 43016 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Tassilo Horn <tsdh <at> gnu.org>
Cc: ljell <laszlomail <at> protonmail.com>, Eli Zaretskii <eliz <at> gnu.org>,
 43016 <at> debbugs.gnu.org, Bruno Haible <bruno <at> clisp.org>
Subject: Re: bug#43016: replace-region-contents takes a lot of time when
 called from json-pretty-print-buffer
Date: Mon, 24 Aug 2020 16:35:32 -0700

[Message part 1 (text/plain, inline)]

On 8/24/20 10:14 AM, Tassilo Horn wrote:
> The actual problem here is that for the specific test file, there are
> (only) 321 compareseq_early_abort tests performed and it seems that the
> first 320 are executed almost immediately (before MAX-SECS are over),
> then no test is performed for minutes, and then a last test is performed
> leading to an early_abort of compareseq followed by delete + insert.

This is due to the lineage of diffseq; if memory serves, its EARLY_ABORT macro 
was introduced for approximate string comparison in GNU gettext, where 
NOTE_INSERT and NOTE_DELETE are associated with doing something that can cause 
the comparison to fail. (It's not clear to me why EARLY_ABORT was broken out of 
NOTE_INSERT and NOTE_DELETE.)

Emacs uses diffseq differently, on much-larger vectors; and it can be CPU-bound 
within diag, which never calls EARLY_ABORT. Although we could add some 
EARLY_ABORT calls to diag Emacs doesn't need that, as it can check for CPU time 
exhaustion in XREF_YREF_EQUAL and longjmp out if there's a problem. I did that 
by installing the first attached patch into Emacs master, which fixes the 
problem (at least for me). I installed the second attached patch into Emacs 
master to fix some other minor issues I noticed while in the neighborhood.

I suppose the first attached patch might be a candidate for backporting into 
Emacs 27 if this bug is considered to be serious enough.

I plan to follow up on the diffseq stack-overflow issue in Bug#42931 in a 
separate email.

I am cc'ing this email to Bruno Haible to give him a heads-up, as he did the 
diffseq engineering for gettext. Bruno, the bug report thread is here:

https://bugs.gnu.org/43016

[0001-Fix-replace-region-contents-performance-bug.patch (text/x-patch, attachment)]

[0002-replace-buffer-contents-cleanups.patch (text/x-patch, attachment)]

Message #38 received at 43016 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: laszlomail <at> protonmail.com, 43016 <at> debbugs.gnu.org, bruno <at> clisp.org,
 tsdh <at> gnu.org
Subject: Re: bug#43016: replace-region-contents takes a lot of time when
 called from json-pretty-print-buffer
Date: Tue, 25 Aug 2020 09:10:20 +0300

> Cc: ljell <laszlomail <at> protonmail.com>, Eli Zaretskii <eliz <at> gnu.org>,
>  43016 <at> debbugs.gnu.org, Bruno Haible <bruno <at> clisp.org>
> From: Paul Eggert <eggert <at> cs.ucla.edu>
> Date: Mon, 24 Aug 2020 16:35:32 -0700
> 
> I suppose the first attached patch might be a candidate for backporting into 
> Emacs 27 if this bug is considered to be serious enough.

Yes, please.

Message #41 received at 43016 <at> debbugs.gnu.org (full text, mbox):

From: Tassilo Horn <tsdh <at> gnu.org>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: ljell <laszlomail <at> protonmail.com>, Eli Zaretskii <eliz <at> gnu.org>,
 43016 <at> debbugs.gnu.org, Bruno Haible <bruno <at> clisp.org>
Subject: Re: bug#43016: replace-region-contents takes a lot of time when
 called from json-pretty-print-buffer
Date: Tue, 25 Aug 2020 19:30:26 +0200

Paul Eggert <eggert <at> cs.ucla.edu> writes:

> by installing the first attached patch into Emacs master, which fixes
> the problem (at least for me). I installed the second attached patch
> into Emacs master to fix some other minor issues I noticed while in
> the neighborhood.

Seems to work fine for me too with all three files of this report and
the large one from bug#42931.  It seems like the early abort will now
happen shortly after MAX-SECS bounds.

Bye,
Tassilo

Message #46 received at 43016-done <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Tassilo Horn <tsdh <at> gnu.org>
Cc: ljell <laszlomail <at> protonmail.com>, Eli Zaretskii <eliz <at> gnu.org>,
 Bruno Haible <bruno <at> clisp.org>, 43016-done <at> debbugs.gnu.org
Subject: Re: bug#43016: replace-region-contents takes a lot of time when
 called from json-pretty-print-buffer
Date: Tue, 25 Aug 2020 11:19:47 -0700

On 8/25/20 10:30 AM, Tassilo Horn wrote:

> Seems to work fine for me too with all three files of this report and
> the large one from bug#42931.  It seems like the early abort will now
> happen shortly after MAX-SECS bounds.

Thanks for checking; closing the Emacs bug report.

Message #49 received at 43016 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: laszlomail <at> protonmail.com, 43016 <at> debbugs.gnu.org, bruno <at> clisp.org,
 tsdh <at> gnu.org
Subject: Re: bug#43016: replace-region-contents takes a lot of time when
 called from json-pretty-print-buffer
Date: Tue, 25 Aug 2020 11:26:23 -0700

On 8/24/20 11:10 PM, Eli Zaretskii wrote:

>> I suppose the first attached patch might be a candidate for backporting into
>> Emacs 27 if this bug is considered to be serious enough.
> 
> Yes, please.

OK, I installed the backported patch into the emacs-27 branch.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.