Yakov Lerner wrote:
From two experiments below, it follows that vimgrep time
is dominated (75-99%) by some overhead of file opening, while
while searching is small fraction of [current] vimgrep time (1-15%)
Here are two experiments by which I tried to tell apart
two parts of vimgrep,
(1) the pattern searching part without file opening part
(2) the files opening without pattern searching
1. To test searching times separately from file loading time, I did this:
- I computed average file size under $VIMRUNTIME. ....snip
The search time greately depends on pattern (filesize is 14kb).
If pattern is 'a' (NB: file consists of all 'x'), then total search
time is
0.31 sec ! (that's 1274 times!). If pattern is 'xxxj' then search time
is 7.4 sec.
This is small part of 46 sec of vimgrep.
This is the portion due to the algorithms involved. A single non-magic
character avoids all the regular-expression backtracking typical with
wildcards.
The "xxxj" pattern is essentially matched with a brute force via the
regular expression s/w.
T: xxxxxxxxxxxxxxxxxxx
P xxxj
P xxxj
P xxxj
...
whereas the Boyer-Moore algorithm, which grep would likely use for
this no-magic pattern, would be
T: xxxxxxxxxxxxxxxxxxx
P: j
P: j
P: j
So you can see that the B-M approach would yield a lot less work.
2. To test file opening time separately from pattern searching time,
I created copy of $VIMRUNTIME, but with all files empty (see script
populate.sh below). vimgrep through this tree took 29 sec:
% sh populate.sh
% vim -u NONE
:TIM vimgrep aklsjlakj /tmp/aaa/
3. Note that 29+(1..7) sec is still not 46. I speculate that remaining
10-15 sec is file contents loading time. (Note that file loading time
does not happen neither in (1) nor in (2)).
If grep simply read lines into a buffer (that grows only to the max size
required
of a line), grep wouldn't need to do much memory allocating. Vim is
doing all
sorts of allocations, etc. Each of those is a system call. If you were
able to measure
system time, I suspect you'd find much of it the time use there.
Regards,
Chip Campbell
