Combine match & matcher benchmarks

I'm about to start another round of optimizations in which the current
Match class will go away, becoming an internal implementation detail of
the Matcher class.

As such, the benchmark script needs to be adapted to only interact with
the latter.

This commit makes the necessary adjustments, folding the match
benchmarks into the matcher benchmarks. The overall results continue to
be basically the same.

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Tweak Matcher specs to use OpenStructs instead of stubbing

I'm about to fold the Match specs into the Matcher class (or rather,
I'll be exercising the Match functionality via the Matcher specs, as the
Match class will soon become an internal-only implementation detail of
the Matcher class).

So, this commit tidies up the specs a little by switching to the use of
OpenStructs rather than stubbing. This will enable me to add a bunch of
different specs more easily, as no separate stubbing step will be
required.

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Use one-line `expect` syntax in Matcher specs

These lines are short enough that they can all fit tidily on one line,
so make it so.

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Remove unnecessary instance variables from Matcher specs

Standard local variables are good enough here.

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Make options hash to Matcher#sorted_matches_for truly optional

There was a lying comment in there suggesting that the options parameter
hash was optional, when in fact it was not.

Noticed while writing specs for the method.

In the name of making life as easy as possible for callers, this commit
makes the comment about optionality true.

Included for free is a (cosmetic) typo fix in a nearby code comment.

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Fold Match class specs into Matcher specs

In preparation for the "disappearance" of the Match class, which will
soon become an internal-only implementation detail.

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Enumerate system headers exhaustively in extconf.rb

Let's be explicit about all the different headers we require (although
in practice, the additional headers listed here are much more "standard"
and likely to be present on a system, compared to "ruby.h").

When we add pthread support later on, we'll be adding an additional
check here for "pthread.h", which is another less "standard" header (at
least, on Windows).

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Make it clear that float.h is a system header

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Simplify Match instance initialization

This is a step towards turning the Match class into something that is
pure C and has no Ruby-specific calls in it, which is itself a necessary
prelude to the threaded performance work that I plan on doing later.
(Note, I suspect the reduction of Ruby object allocations that will be a
subsequent step will make this faster even before we get to the
threading bit.)

In a sense, this makes the initialization API strictly worse, replacing
an options hash with two explicit but superficially confusing option
names. Nevertheless, I'm not worried about that right now as the whole
file is going to be reworked as I get rid of the "Ruby-ness" of it.

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Turn CommandTMatcher_matches_for into a private function

This need not be exposed externally, so make it private.

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Make CommandTMatcher_matches_for a "non-Ruby" function

Bypass the normal Ruby method dispatch and just call the function like a
normal C function; it is only used internally.

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Demote Match class to pure-C functions

This is preparatory to being able to do threaded searching, but in the
immediate term, it delivers us a small speed boost as well.

Before:

  pathological        0.000000   0.000000   0.000000 (  0.004766)
  command-t           0.910000   0.000000   0.910000 (  0.913644)
  chromium (subset)   1.260000   0.000000   1.260000 (  1.266127)
  chromium (whole)    3.850000   0.010000   3.860000 (  3.853568)

After:

                          user     system      total        real
  pathological        0.000000   0.000000   0.000000 (  0.004329)
  command-t           0.420000   0.000000   0.420000 (  0.416208)
  chromium (subset)   1.070000   0.000000   1.070000 (  1.071452)
  chromium (whole)    3.680000   0.010000   3.690000 (  3.683207)

The speed-up is likely due to the following:

  - elimination of some Ruby message sends
  - replacement of allocation of N `Match` objects with a single
    allocation of size N * (double + long) (ie. a slab containing a
    double for the score and a long for the path string pointer for each
    path)

Note: this is in addition to some other speedup that comes from previous
commits, starting around 6420a25:

  pathological        0.000000   0.000000   0.000000 (  0.004560)
  command-t           1.030000   0.000000   1.030000 (  1.031469)
  chromium (subset)   1.450000   0.010000   1.460000 (  1.465009)
  chromium (whole)    4.630000   0.010000   4.640000 (  4.664491)

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Annotate float.h include

I like to include a brief hint about why any given system
header is included, but the float.h include was missing the
annotation.

This commit adds it.

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Add basic prototype of threaded searching

The code is pretty ugly, so I'll be looking at cleaning it up in
subsequent commits, as well as adding some configurability (automatic or
otherwise), but nevertheless it gives us a very nice speedup on large
codebases.

Before:
                          user     system      total        real
  pathological        0.000000   0.000000   0.000000 (  0.004329)
  command-t           0.420000   0.000000   0.420000 (  0.416208)
  chromium (subset)   1.070000   0.000000   1.070000 (  1.071452)
  chromium (whole)    3.680000   0.010000   3.690000 (  3.683207)

After:
                          user     system      total        real
  pathological        0.010000   0.030000   0.040000 (  0.018285)
  command-t           0.980000   1.850000   2.830000 (  1.391637)
  chromium (subset)   1.480000   0.020000   1.500000 (  0.551915)
  chromium (whole)    5.150000   0.020000   5.170000 (  1.861232)

Note that the pathological case is actually slightly slower now, but I
suspect that is because of the overhead of invoking a thread which isn't
really needed for the small number of paths (ie. one!) in sample data
set.

The slowdown of the command-t sample data is a little more alarming
though, so I might end up adding a threshold such that only if the
number of paths is greater than, say, 1,000, do we invoke the threading
machinery.

As written in this commit, the threaded support will only be compiled in
if you define USE_THREADS at build time. I'll be making this somewhat
more automatic in a future commit. I've defaulted to it being
effectively inactive so that this commit could, at least in theory, be
merged to the master branch even though I haven't figured out what to do
about Windows support yet.

As Ruby threads are basically useless (even in 1.9, due to the GIL), all
of this is done at a lower-level, using pthreads and avoiding any
interaction with the Ruby runtime (beyond making read-only access of
primitive Ruby objects already in memory). Once the work is done, all
the threads are joined and Ruby and Vim are free to go back to their
usual single-threaded operation.

The division of labor here is fairly crude: given four worker threads,
thread 0 will process paths 0, 4, 8 etc, and thread 1 will process paths
1, 5, 9 etc, and so on. I did it this what instead of dividing the paths
into contiguous chunks because I wanted to increase the likelihood of
each worker getting a similar amount of work (due to the way file
scanners work -- ie. recursively, using a depth-first search -- it is
possible or even likely that the distribution of the search space will
be uneven across the paths array (ie. shorter paths near the beginning
and end, with longer paths in the middle). By "striping" the work across
workers, we make it more likely that they'll all have roughly the same
about of work to do.

Another reason for this simple/crude division of labor is it frees us
from the overhead of having to manage a queue data structure, or a
producer/consumer set-up. Note we don't need to use any locks here as we
effectively have a map-reduce job that slices an array into 4 chunks,
and each thread only ever tries to mutate its own chunk. It is not even
necessary to zero-out the array, as the threads will take care of
filling it out.

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Avoid overhead of threading when search space is small

Don't spawn threads if the search space is small (ie. < 1,000 paths).
Additionally, instead of spawning N threads, spawn N-1 and use the main
thread as the last worker. This allows us to keep the overhead as low as
possible, and also makes things a bit DRY-er.

This brings us back to the unmitigated win territory:

Baseline (no threading):
                          user     system      total        real
  pathological        0.000000   0.000000   0.000000 (  0.004329)
  command-t           0.420000   0.000000   0.420000 (  0.416208)
  chromium (subset)   1.070000   0.000000   1.070000 (  1.071452)
  chromium (whole)    3.680000   0.010000   3.690000 (  3.683207)

With threading (unconditional):
                          user     system      total        real
  pathological        0.010000   0.030000   0.040000 (  0.018285)
  command-t           0.980000   1.850000   2.830000 (  1.391637)
  chromium (subset)   1.480000   0.020000   1.500000 (  0.551915)
  chromium (whole)    5.150000   0.020000   5.170000 (  1.861232)

With threading enabled only for large search spaces:
                          user     system      total        real
  pathological        0.000000   0.000000   0.000000 (  0.004627)
  command-t           0.420000   0.000000   0.420000 (  0.423317)
  chromium (subset)   1.470000   0.020000   1.490000 (  0.551474)
  chromium (whole)    5.050000   0.010000   5.060000 (  1.866479)

It's possible that the threshold should/could be tweaked some more, but
for now 1,000 seems like a reasonable cut-off.

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Dynamically detect presence of pthread.h

This should hopefully do the right thing, even on Windows.
HAVE_PTHREAD_H should not be set if the header can't be found, so the
threading code should degrade to the main-thread-only version.

Note there is some weirdness here, at least on OS X: as soon as you
include ruby.h, you'll end up including:

  /System/Library/Frameworks/Ruby.framework/Versions/2.0/Headers/ruby/config.h

which itself sets HAVE_PTHREAD_H. This is why I moved the:

  #ifdef HAVE_PTHREAD_H
  #include <pthread.h>
  #endif

guard clause down, until after the inclusion of ruby.h (ie. to avoid the
pthread.h header not being included if mkmf couldn't find it, but then
sections further on down the file from being activated thanks to
config.h). It turns out that this works in any case, just with compiler
warnings about use of undeclared functions, but it's better to be safe
than sorry.

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Rename CommandTMatch_initialize -> calculate_match

Now that this is just a C function rather than a Ruby class, we are no
longer bound by the conventions of the Ruby runtime and can use a
shorter name.

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Rename qsort comparison methods

For similarity with the used-nearby strcmp function from the standard
library, let's go with the shorter cmp_* name rather than comp_*.

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Edit a comment for accuracy

Signed-off-by: Wincent Colaiuta <win@wincent.com>
Add a method to detect number of cores on a system

According to Google there are a million different opinions on how best
to do this in cross-platform way. This one looks pretty good.

Signed-off-by: Wincent Colaiuta <win@wincent.com>