Path: utzoo!utgpu!water!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!mailrus!ames!pasteur!ucbvax!decwrl!sun!pitstop!sundc!seismo!uunet!mcvax!ukc!dcl-cs!nott-cs!anw
From: anw@nott-cs.UUCP
Newsgroups: comp.editors
Subject: Re: Vi question
Message-ID: <561@tuck.nott-cs.UUCP>
Date: 18 May 88 14:31:11 GMT
References: <37200004@uiucdcsm> <727@sjoerd.cs.vu.nl> <7549@boring.cwi.nl>
Reply-To: anw@maths.nott.ac.uk (Dr A. N. Walker)
Organization: Department of Mathematics, The University, NOTTINGHAM, NG7 2RD, UK.
Lines: 45

In article <7549@boring.cwi.nl> dik@cwi.nl (Dik T. Winter) writes:
>In article <727@sjoerd.cs.vu.nl> sjoerd@cs.vu.nl (Sjoerd Mullender) writes:
> >	[direct substitute v. global version]
> > But on the whole the forms are similar enough so that you can use either.
>All very true, but there is another difference: performance.  Try a 8192
>line file were all lines contain the text pattern only; time the two
>commands.  On a VAX 780 the :%s form will do it in about 6 seconds; the
>:g form needs more than 3 minutes.

	There is obviously scope for an interesting benchmark here.  I *did*
try it -- PDP 11/44 running a much-hacked V7, file == 8192*"qwertyuiop",
and substituting "/qwertyuiop/fred/" -- and it took 18 seconds for the s
form and just over 16 minutes for the g form.  (Ed, not vi, which we don't
have on this machine.)  Reasons for the *relatively* poor performance are
solicited!

>The reason:
>	[for :g]      the searching is a n squared process, each and
>	every time the file will be searched from the first line to find
>	the next marked line.  the reason is obvious: all kinds of
>	commands may follow that disrupt the order of the file.

	Yes, but there is a relatively easy hack:  keep track of the
next-possibly-marked-line;  the search can then run from this line,
stopping on reaching the last line.  Usually, the n-p-m-line is the
line after the previous marked line (or initially line 1), but it
will be updated in a reasonably obvious way by deletions, insertions
or moves.  The search will then be linear in most cases, including

		g/pattern/d
		g/pattern/s//fred/
		g/pattern/.,+5m-5
		g/^/m0			# "reverse" a file

and be quadratic only in cases such as

		g/pattern/$m0

(in these last two cases, the run-time behaviour will be respectively
quadratic and cubic in vanilla ed/vi, 'cos the move takes longer as
the "range" gets longer).

-- 
Andy Walker, Maths Dept, Nott'm Univ, UK.
anw@maths.nott.ac.uk