Re: roff.c question

[Ingo Schwarze <schwarze@usta.de>]

Hi Kristaps,

Kristaps Dzonsons wrote on Fri, Dec 10, 2010 at 10:40:52AM +0100:
>>> Ingo wrote:

>>>> 1) roff_res() should not expand \\* or \\\\*,
>>>>    but it should expand \* and \\\*.

> I worry a bit about performance, as this is an
> often-called function:

Yes, the function is called L+E times,
where L is the number of input lines and E is the number
of expanded strings and user-defined roff macro invocations.

But my algorithm is still O(N), where N is the number of
characters on the line, as long as no expansion is done.
So, if C is the total number of characters in the input file,
and e is the mean number of expansions per line,
then the total order of the search algorithm (without
doing the actual expansions) is O(C*(1+e)).

The work to do for the expansions is O(C*e), but that
didn't change.

All that is still nearly linear, which is hardly a bad order.

> why the funny business looking for three
> non-nils then the escaped asterisk?
> 
> Seems (it pseudo-C)
> 
>   for (cp = buf + pos; cpp = strstr(cp, "\\*"); cp++)
>      if ('\0' == cpp[2]) continue;
>      ...
> 
> would be much clearer and faster.  No?

No.

Faster, no.  That's O(C*(1+e)) as well.
So we are talking about constant factors here.
Maybe you are economizing two char comparisons
per loop cycle.  Assuming e=1, that will buy you
perhaps 400k char comparisons on a 100k input file.
That might be about a millisecond on a very old PC.

Clearer, no.  It's incorrect.  You cannot use strstr().
The number of backslashes before "\\*" is relevant.
It must be even, or you don't want to substitute.

If we want to go into micro-optimization, we could do this:

        for (cp = *bufp + pos; *cp; cp++) {
                if ('\\' != *cp)
                        continue;
                stesc = cp;
		if ('\0' == *(++cp))
			break;
		if ('*' != *cp)
			continue;
		if ('\0' == *(++cp))
			break;
		switch (*cp) {

deferring the tests until they are really needed (untested).
That's fewer tests because most of the time, the
continue branches will be taken.

But is that really better?  It is more code, and harder
to understand.

Yours,
  Ingo
--
 To unsubscribe send an email to tech+unsubscribe@mdocml.bsd.lv