News for hackers. Stuff that matters.
Re:How F5Bot Slurps All of Reddit by saagarjha on Monday July 30, 2018 @04:26PM (#17647703)
Aho-Corasick is really great. It’s a bit complicated to set up, but once you have the modified true set up it’s really fast. By the way,

> Basically I use the selftext, subreddit, permalink, url and title. The other 95% of it is just wasted bandwidth.

It’d probably be better for Reddit if they allowed for specifying the fields we care about rather than just returning the whole thing…

Re:How F5Bot Slurps All of Reddit by cxseven on Monday July 30, 2018 @05:11PM (#17648081)
Also, imagine the joules saved worldwide if known key names didn't have to be sent each time, or, better yet, data was packed in a format that optimized for size and processing speed rather than readability.

I mean, I enjoy the idea of human readability as much as Jon Postel, but at certain scales you have to wonder about the hidden cost of petabytes of human-readable data flying over the wire, never to be seen by anything but computers.

Re:How F5Bot Slurps All of Reddit by wvenable on Monday July 30, 2018 @05:23PM (#17648171)
Except that the data stream is, I should hope, compressed so that the data is actually packed into a format optimized for size.
Re:How F5Bot Slurps All of Reddit by yitosda on Monday July 30, 2018 @05:49PM (#17648414)
Not necessarily, and even so not for free.

(Client must specify compression support)

Re:How F5Bot Slurps All of Reddit by wvenable on Monday July 30, 2018 @06:00PM (#17648520)
Most clients support it implicitly; you probably have to go out of your way to get an uncompressed stream. Now compressing a verbose text string is not optimal but given the past attempts I'd hesitate against using a pre-packed format. Historically that has not worked out well. Compressing the text format is ultimately the worse-is-better solution.
Re:How F5Bot Slurps All of Reddit by jwilk on Monday July 30, 2018 @06:14PM (#17648636)
They are using libcurl, for which you need to request compression explicitly:

https://curl.haxx.se/libcurl/c/CURLOPT_ACCEPT_ENCODING.html

Re:How F5Bot Slurps All of Reddit by bmn__ on Tuesday July 31, 2018 @08:55AM (#17652741)
> It’s a bit complicated to set up […] it’s really fast

Sigh, just use Perl. Writing code with the general regex engine took me only one minute of effort, but it runs already nearly 500× faster than codeplea's optimised special purpose code.

Why 100000 loops and not 10 like in the original code? Otherwise Benchmark.pm will show "(warning: too few iterations for a reliable count)".

----

benchmark.php 100000 loops:

    Loaded 3000 keywords to search on a text of 19377 characters.

    Searching with aho corasick...
    time: 329.3522541523
----

benchmark.pl 100000 loops:

    Benchmark: timing 100000 iterations of regex...
    regex: 0.691561 wallclock secs ( 0.69 usr +  0.00 sys =  0.69 CPU) @ 144927.54/s (n=100000)
----

benchmark.pl (fill in the abbreviated ... parts from benchmark_setup.php):

    #!/usr/bin/env perl
    use Benchmark qw(timethese :hireswallclock);
    require Time::HiRes;
    my @needles = qw(
    abandonment abashed abashments abduction ...
    );
    my $haystack = 'unscathed grampus ...
    heroically';
    my $n = join '|', @needles;
    timethese 100000, {
        regex => sub {
            my @found;
            while ($haystack =~ /($n)/cg) {
                push @found, [$1, pos $haystack];
            }
            return @found;
        },
        index => sub {
            my @found;
            for (@needles) {
                my $pos = index $haystack, $_;
                push @found, [$_, $pos] if -1 < $pos;
            }
            return @found;
        }
    };
Re:How F5Bot Slurps All of Reddit by codeplea on Tuesday July 31, 2018 @10:39AM (#17653505)
Is your solution broken for the cases where keywords are prefixes or suffixes of each other? This situation is very common in my use-case. Also, does your solution work if a keyword appears multiple times?

I get what you're saying, but it's not quite as easy as you imply.

Pulling in an entire programming language is a much bigger dependency and maintenance cost than spending a couple hours writing an algorithm. It would make more sense to just use a C extension.

I did try PHP's regex. It was much, much slower.

Re:How F5Bot Slurps All of Reddit by bmn__ on Wednesday August 01, 2018 @02:26PM (#17665406)
You are right, the solution is broken. I can't make it work, so I take back what I said.

I learnt something valuable, thank you for that.

Re:How F5Bot Slurps All of Reddit by chillee on Monday July 30, 2018 @05:32PM (#17648251)
I only took a quick skim, but it doesn't look like they do the optimization to aho-corasick where you store connections directly to "leaf" nodes (ie: nodes where you can have a finished match).

If I'm right, that would probably speed things up significantly.

Re:How F5Bot Slurps All of Reddit by saagarjha on Monday July 30, 2018 @07:39PM (#17649250)
Sorry, what optimization are you talking about? If you're just path compression, then I don't think this works because you miss out on generating failure links as you go along.
Re:How F5Bot Slurps All of Reddit by chillee on Sunday August 12, 2018 @07:27PM (#17747049)
It basically is path compression. You still need to maintain failure links, but at every step, when you step up your parents to find all matches, you jump directly to leaves.