[Cscope-devel] Performance improvements

[Elad L. <e2...@gm...>]

I was made aware that the sorting code I wrote for min-cscope a few years
ago (primarily targeted at Windows) was not performing very well on Linux
and FreeBSD. I re-wrote the code which now runs faster than GNU sort (at
least for the postings list produced by Cscope and compared with the sort
version on Ubuntu 12.04). The code is also much more compact and fits
nicely within a single source file. Consequently, I would like to propose
its inclusion in the main Cscope code. The attached patch provides the new
sort.c and sort.h files, the necessary changes to build.c, crossref.c,
invlib.c and Makefile.am. It also replaces a linear search within invmake()
with a binary search, which gives an additional performance boost.

Performance results:
Ran a clean Cscope build on the Linux 3.13.7 tree (~35K files) with a warm
cache (i.e., ran a clean build first and discarded the results).

Vanilla Cscope:
elahav@elahav-mbp:~/src/linux-3.13.7$ time /usr/bin/cscope -b -k -q

real    0m52.349s
user    1m13.193s
sys     0m2.680s

Modified Cscope:
elahav@elahav-mbp:~/src/linux-3.13.7$ time ~/tmp/cscope/src/cscope -b -k -q

real    0m33.800s
user    0m30.874s
sys     0m1.224s

Verified that the generated DB is sane by running a query for all
references to '.*kernel.*' (there are 7647 of those) and made sure the
vanilla and modified versions produced the same results.

Note: after applying the patch, you need to run autoreconf to update the
various build configuration files.

--Elad

P.S.,
There are annoying inconsistencies in indentation throughout the code, with
a mixture of tabs and spaces, even within single files. Should probably be
cleaned-up at some point.