Added filter groups to speed up "is:" and "ext:"

[sth]

Adds an Ack::Filter::Collection class that can contain filters and internally sort them into groups. The groups can then be optimized for faster filtering.

In this patch, is and ext filters are grouped and replaced by a fast hash lookup. This leads to improved performance when many such filters are active, like when using the --known command line option.

Only is: and ext: filters are affected and usually there aren't enough of them active for these changes to make a difference, but for --known the speedup is quite significant:

$ make ack-standalone && dev/timings.pl --ack 1.96 --ack 2.08 --times 5
make: `ack-standalone' is up to date.
                                          |   1.96 |   2.08 |   HEAD
--------------------------------------------------------------------
           ack foo /home/sth/work/devices |   0.42 |   1.26 |   1.26
      ack foo --cc /home/sth/work/devices |   0.11 |   0.26 |   0.26
    ack foo --rust /home/sth/work/devices |    x_x |   0.26 |   0.26
   ack foo --known /home/sth/work/devices |   0.41 |   1.32 |   0.89
            ack -f /home/sth/work/devices |   0.11 |   0.31 |   0.32
       ack -f --cc /home/sth/work/devices |   0.11 |   0.27 |   0.27
     ack -f --rust /home/sth/work/devices |    x_x |   0.26 |   0.26
    ack -f --known /home/sth/work/devices |   0.11 |   0.80 |   0.38
        ack foo -l /home/sth/work/devices |   0.48 |   0.56 |   0.54
   ack foo -l --cc /home/sth/work/devices |   0.11 |   0.26 |   0.26
 ack foo -l --rust /home/sth/work/devices |    x_x |   0.26 |   0.26
ack foo -l --known /home/sth/work/devices |   0.47 |   0.92 |   0.50
        ack foo -c /home/sth/work/devices |   0.61 |   0.59 |   0.59
   ack foo -c --cc /home/sth/work/devices |   0.11 |   0.26 |   0.26
 ack foo -c --rust /home/sth/work/devices |    x_x |   0.26 |   0.26
ack foo -c --known /home/sth/work/devices |   0.61 |   0.95 |   0.54

The tests also all pass.

[petdance]

Thanks for this. I've posted to ack-dev for discussion.

[sth]

Looks like the Travis tests are failing because I forgot a %{ } in the to_string() functions in IsGroup.pm and ExtensionGroup.pm.

[hoelzro]

Sorry it took so long to look at this; I'm a big fan of this patch. It looks solid, and this is definitely the kind of thing we need in ack. @petdance If it's ok with you, I think we should merge this.

[petdance]

Make it so #1

[hoelzro]

Merged! Thanks for the contribution!

[petdance]

We'd like to credit you in the Changes file and acknowledgements, if you'll give us your name.

[sth]

Thanks for merging the patch! For the changes file, my name is "Stephan Hohe". Sorry for not responding sooner, but I've been away for a while and rather busy at work :).