Mon, 26 Feb 2007
Superlinear Algorithms
A while ago I wrote about the
Email::Address Perl module for parsing addresses
in the e-mail headers (such as To:, Cc:, etc.).
We use it in production system, but on Thursday we have got a problem,
which I narrowed to an inoptimality in this module. The mail delivery daemon
(which - amongst other things - parses the mail message) seemed to be
stuck in an infinite loop.
Later I found out that the message in question contained an overly long
To: header - it had more than 300 mail addresses there.
I have investigated this further, and it seems that the
Email::Address module has complexity far above O(n):
| # of addresses | parsing time |
|---|---|
| 60 | 0.13 s |
| 65 | 0.13 s |
| 70 | 0.29 s |
| 75 | 0.45 s |
| 80 | 0.79 s |
| 85 | 0.58 s |
| 90 | 0.86 s |
| 95 | 1.63 s |
| 100 | 2.38 s |
| 105 | 3.17 s |
| 110 | 4.02 s |
| 115 | 5.97 s |
| 120 | 11.37 s |
| 125 | 230.89 s |
| 130 | 1045.07 s |
So it was definitely impossible for it to parse a header with >300
addresses in a reasonable amount of time.
The alternative module, Mail::Address, is unusable
on this particular message as well - it crashes perl
with SIGSEGV :-(.
As a workaround, I wanted to truncate the header somewhere, but in order to truncate the header exactly between e-mail addresses, I would have to parse the header. Which is what I has been doing, and it took too much time. A nice Catch 22, isn't it? So I have invented a heuristics where I truncate the header after a comma followed by a newline. When this is not enough, I use just a sole comma as a separator, and when even this is not enough, I truncate the header to a fixed number of characters. So far it seems to be sufficient.
3 replies for this story:
Adelton wrote: The scale of the problem?
What was the (repeated) address you've tried this on? I got results that are an order of magnitude better: 100: 0.010125s, 1000: 0.505776s, 2000: 4.809914s even on my aging Celeron. This is with 5.8.8 and Email::Address 1.884.
Yenya wrote: Re: Adelton
I have 1.871. As for the input data, I have used the original To: header from the mail in question, shortening it to several lines as required by the test. I can send you the data, if you are interested.
Adelton wrote:
Yup, send me the example. I just tried my email address, multiplied and joined using ', '. Also, looking at the changelog, there are some performance improvements mentioned, so you might want to give the newer version a try.