Update stats processing

This is a large patch, sorry. It probably doesn`t make sense to review this in detail - some polishing is certainly possible but this isn`t really critical. At least I tried to comply with PEP 8 this time :). However, it would be great if you could verify the general approach. Also, anything that can speed up log processing would be appreciated. In general, currently there are three steps executed daily: 1) Mirror servers process their logs and save the result in a temporary file. 2) Stats master retrieves these files and merges them into the existing data. 3) Stats master produces static HTML pages for the data. We probably want to move 1) off the mirrors to the stats master but right now we have too many logs to process them on a single server. Also, we probably don`t want to rebuild all pages in 3) but only do it if the data changed.

[Sebastian Noack, 2013-08-26 16:05:22]

Also you use a lot of inline regular expressions. So if performance is an issue,
you should replace them with pre-compiled regular expressions. See re.compile().

http://codereview.adblockplus.org/11481051/diff/1/sitescripts/stats/bin/datam...
File sitescripts/stats/bin/datamerger.py (right):

http://codereview.adblockplus.org/11481051/diff/1/sitescripts/stats/bin/datam...
sitescripts/stats/bin/datamerger.py:18: import os, sys, re, codecs, subprocess,
urllib, simplejson, traceback
Since Python 2.6, you can use the built-in module "json", instead of the
third-party "simplejson" module.

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/da...
File sitescripts/stats/bin/datamerger.py (right):

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/da...
sitescripts/stats/bin/datamerger.py:18: import os, sys, re, codecs, subprocess,
urllib, simplejson, traceback
Since Python 2.6 you can use the built-in "json" module, and don't need to rely
on the third-party "simplejson" module anymore.

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/da...
sitescripts/stats/bin/datamerger.py:49: yield re.split(r"\s+", value, 1)
Did you know that value.split(None, 1) would do the same, just more efficient
because no regular expression is involved.

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/lo...
File sitescripts/stats/bin/logprocessor.py (right):

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/lo...
sitescripts/stats/bin/logprocessor.py:44: match = re.search(r"\b%s/(\d+\.\d+)" %
appName, ua)
Instead of iterating over the list of browsers and generate a regex for each, I
would suggest to use a single regex that matches all:

\b(Fennec|Thunderbird|SeaMonkey|Songbird|K-Meleon|Prism|Firefox)/(\d+\.\d+)

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/lo...
sitescripts/stats/bin/logprocessor.py:54: return "Gecko", "%s.%s.%s" %
(match.group(1), match.group(2), match.group(3))
You could just just call match.groups(), which already returns a tuple with all
3 groups in it.

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/pa...
File sitescripts/stats/bin/pagegenerator.py (right):

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/pa...
sitescripts/stats/bin/pagegenerator.py:24: @cached(())
You passed an empty tuple as timeout. Obviously you want to make the timeout
forever, but this isn't the right way to do it. It though works in at least
recent versions of CPython, but that is just luck, since the Python language
specs, don't specify that a tuple is always larger than an int/float, as far as
I know. So it might fail with other Python implementations or future versions of
CPython. However why don't you just use float('Inf')?

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/pa...
sitescripts/stats/bin/pagegenerator.py:53: def ensure_dir(path):
Instead of checking if the dir exist and creating it if not, I would rather just
create it and catch the OSError. This will be faster since the FS must be
queried only once and you get around the theoretical condition that the dir
doesn't exist when you check for its presence but suddenly was created by
somebody else when actually try to create it a (few) ms later.

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/pa...
sitescripts/stats/bin/pagegenerator.py:116: if filter(lambda k: k not in
("hits", "bandwidth"), value.keys()):
No need to create a new list with the keys first. Just call filter(..., value).
If value is a dict, it is iterable, and produces its keys on iteration. Also you
might want to use itertools.ifilter instead of filter, which doesn't returns a
pre-computed list, but a generator that is evaluated on the fly.

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/pa...
sitescripts/stats/bin/pagegenerator.py:142: month_url =
(common.filename_encode(month) + "/" +
You should use os.path.join() here as well.

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/utils.py
File sitescripts/utils.py (right):

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/utils.py#new...
sitescripts/utils.py:151: env =
jinja2.Environment(loader=jinja2.FileSystemLoader(siteScriptsPath),
autoescape=True, extensions=['jinja2.ext.autoescape'])
You don't need to add the autoescape extesnion to enable autescaping. You only
need that extension if you want to enable or disable autoescaping for a template
fragment with the {% autoescape on|off %} tag, which you don't use.

[Wladimir Palant, 2013-08-27 07:34:28]

On 2013/08/26 16:05:22, sebastian wrote:
> Also you use a lot of inline regular expressions. So if performance is an
issue,
> you should replace them with pre-compiled regular expressions. See
re.compile().

I did a few tests and the variant with re.compile() was consistently slower.
This matches what I know from other programming languages - precompiling regular
expressions doesn't actually make things faster. There is a nice Stack Overflow
answer on this: http://stackoverflow.com/a/452143/785541

All the issues should be fixed unless noted otherwise. Also, I fixed an issue
with wrong URLs to filtered stats pages.

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/da...
File sitescripts/stats/bin/datamerger.py (right):

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/da...
sitescripts/stats/bin/datamerger.py:18: import os, sys, re, codecs, subprocess,
urllib, simplejson, traceback
On 2013/08/26 16:05:22, sebastian wrote:
> Since Python 2.6 you can use the built-in "json" module, and don't need to
rely
> on the third-party "simplejson" module anymore.

I am aware of that of course. However, simplejson is around 40% faster than the
built-in json module.

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/da...
sitescripts/stats/bin/datamerger.py:49: yield re.split(r"\s+", value, 1)
On 2013/08/26 16:05:22, sebastian wrote:
> Did you know that value.split(None, 1) would do the same, just more efficient
> because no regular expression is involved.

No, I didn't. Fixed.

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/lo...
File sitescripts/stats/bin/logprocessor.py (right):

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/lo...
sitescripts/stats/bin/logprocessor.py:44: match = re.search(r"\b%s/(\d+\.\d+)" %
appName, ua)
On 2013/08/26 16:05:22, sebastian wrote:
> Instead of iterating over the list of browsers and generate a regex for each,
I
> would suggest to use a single regex that matches all:
> 
> \b(Fennec|Thunderbird|SeaMonkey|Songbird|K-Meleon|Prism|Firefox)/(\d+\.\d+)

This was done like that intentionally - quite a few browsers will claim being
Firefox. However, we can indeed handle all but Firefox in one go, done that now.

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/lo...
sitescripts/stats/bin/logprocessor.py:54: return "Gecko", "%s.%s.%s" %
(match.group(1), match.group(2), match.group(3))
On 2013/08/26 16:05:22, sebastian wrote:
> You could just just call match.groups(), which already returns a tuple with
all
> 3 groups in it.

I think I rather keep this as is for consistency with the variant two lines
below. Besides, I prefer listing the groups explicitly - regexps commonly have
groups that aren't meant to be used (I avoid this here by using (?:...) but
still).

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/pa...
File sitescripts/stats/bin/pagegenerator.py (right):

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/pa...
sitescripts/stats/bin/pagegenerator.py:24: @cached(())
This behavior is somewhat specified as described here:
http://stackoverflow.com/a/3270689/785541

Anyway, float("inf") was introduced in Python 2.6, this code is older however. I
followed the advice to use an empty tuple because I liked it better than using
an arbitrary number like 1e400. Fixed.

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/pa...
sitescripts/stats/bin/pagegenerator.py:56: os.makedirs(dir)
Fixed. However, this is a common pattern in our code base and will have to be
fixed consistently everywhere.

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/pa...
sitescripts/stats/bin/pagegenerator.py:116: if filter(lambda k: k not in
("hits", "bandwidth"), value.keys()):
On 2013/08/26 16:05:22, sebastian wrote:
> No need to create a new list with the keys first. Just call filter(...,
value).
> If value is a dict, it is iterable, and produces its keys on iteration. Also
you
> might want to use itertools.ifilter instead of filter, which doesn't returns a
> pre-computed list, but a generator that is evaluated on the fly.

I rather use value.iterkeys() here - it's obvious what's meant then, with Python
dictionaries I'm frequently confused what I am iterating on.

As to itertools.ifilter(), I would rather not complicate the code here since
this spot isn't performance-critical.

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/pa...
sitescripts/stats/bin/pagegenerator.py:142: month_url =
(common.filename_encode(month) + "/" +
On 2013/08/26 16:05:22, sebastian wrote:
> You should use os.path.join() here as well.

No, definitely not going to use os.path.join() for URLs - this would produce
wrong URLs on Windows for example. And urlparse.urljoin() won't make the logic
here more obvious.

[Sebastian Noack, 2013-08-27 10:05:50]

On 2013/08/27 07:34:28, Wladimir Palant wrote:
> On 2013/08/26 16:05:22, sebastian wrote:
> > Also you use a lot of inline regular expressions. So if performance is an
> issue,
> > you should replace them with pre-compiled regular expressions. See
> re.compile().
> 
> I did a few tests and the variant with re.compile() was consistently slower.
> This matches what I know from other programming languages - precompiling
regular
> expressions doesn't actually make things faster. There is a nice Stack
Overflow
> answer on this: http://stackoverflow.com/a/452143/785541

Precompiled reular expressions actually can not be slower, because of CPython
uses the same code to compile them on the fly otherwise. However it caches up to
100 regular expressions, internally. But instead of using a proper LRU cache, it
just flushes the entire cache wenn the 101st regex is compiled. So the
difference is barely measurable when your entire process uses up to 100
different regular expressions, but will become notable faster when you use more
than 100 regular expressions.

>
http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/da...
> File sitescripts/stats/bin/datamerger.py (right):
> 
>
http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/da...
> sitescripts/stats/bin/datamerger.py:18: import os, sys, re, codecs,
subprocess,
> urllib, simplejson, traceback
> On 2013/08/26 16:05:22, sebastian wrote:
> > Since Python 2.6 you can use the built-in "json" module, and don't need to
> rely
> > on the third-party "simplejson" module anymore.
> 
> I am aware of that of course. However, simplejson is around 40% faster than
the
> built-in json module.

That is strange since the original simplejson module was just merged into
upstream Python and became the built-in json module. However, it might be that
they have added some performance improvements to simplejson afterwards, that
aren't merged into upstream Python yet. You might also want to look at cjson,
which is known to be even faster, if performance is an issue.

>
http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/pa...
> sitescripts/stats/bin/pagegenerator.py:116: if filter(lambda k: k not in
> ("hits", "bandwidth"), value.keys()):
> On 2013/08/26 16:05:22, sebastian wrote:
> > No need to create a new list with the keys first. Just call filter(...,
> value).
> > If value is a dict, it is iterable, and produces its keys on iteration. Also
> you
> > might want to use itertools.ifilter instead of filter, which doesn't returns
a
> > pre-computed list, but a generator that is evaluated on the fly.
> 
> I rather use value.iterkeys() here - it's obvious what's meant then, with
Python
> dictionaries I'm frequently confused what I am iterating on.

It does the same, but isn't actually necessary, because the dict object itself
is iterable and will produce it keys on iteration.

>
http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/pa...
> sitescripts/stats/bin/pagegenerator.py:142: month_url =
> (common.filename_encode(month) + "/" +
> On 2013/08/26 16:05:22, sebastian wrote:
> > You should use os.path.join() here as well.
> 
> No, definitely not going to use os.path.join() for URLs - this would produce
> wrong URLs on Windows for example. And urlparse.urljoin() won't make the logic
> here more obvious.

Oh, didn't noted, it was an url. In that case hardcoded slashes are ok, of
course. But I would rather use a format string here, with all the literal parts
already included, instead the plus operator. This is Python, not JS. ;) I only
use the plus operator to concatenate two strings. If you have more strings to
concatenate into a single string, it is more readable and faster to either use
format strings or str.join().

[Wladimir Palant, 2013-08-27 11:59:47]

Sebastian, I merely copied your reply to the right comment threads here.

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/da...
File sitescripts/stats/bin/datamerger.py (right):

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/da...
sitescripts/stats/bin/datamerger.py:18: import os, sys, re, codecs, subprocess,
urllib, simplejson, traceback
Reply by Sebastian:

That is strange since the original simplejson module was just merged into
upstream Python and became the built-in json module. However, it might be that
they have added some performance improvements to simplejson afterwards, that
aren't merged into upstream Python yet. You might also want to look at cjson,
which is known to be even faster, if performance is an issue.

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/pa...
File sitescripts/stats/bin/pagegenerator.py (right):

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/pa...
sitescripts/stats/bin/pagegenerator.py:116: if filter(lambda k: k not in
("hits", "bandwidth"), value.keys()):
Reply by Sebastian:

It does the same, but isn't actually necessary, because the dict object itself
is iterable and will produce it keys on iteration.

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/pa...
sitescripts/stats/bin/pagegenerator.py:142: month_url =
(common.filename_encode(month) + "/" +
Reply by Sebastian:

Oh, didn't noted, it was an url. In that case hardcoded slashes are ok, of
course. But I would rather use a format string here, with all the literal parts
already included, instead the plus operator. This is Python, not JS. ;) I only
use the plus operator to concatenate two strings. If you have more strings to
concatenate into a single string, it is more readable and faster to either use
format strings or str.join().

[Wladimir Palant, 2013-08-27 12:42:01]

On 2013/08/27 10:05:50, sebastian wrote:
> Precompiled reular expressions actually can not be slower, because of CPython
> uses the same code to compile them on the fly otherwise.

I'm just telling you what a quick test has shown. Maybe that's because the code
couldn't be optimized just as well with an additional variable, I don't know.
But precompiled regexps definitely don't have any advantage for us here.

New patchset changing string concatenation uploaded.

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/da...
File sitescripts/stats/bin/datamerger.py (right):

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/da...
sitescripts/stats/bin/datamerger.py:18: import os, sys, re, codecs, subprocess,
urllib, simplejson, traceback
On 2013/08/27 11:59:47, Wladimir Palant wrote:
> You might also want to look at cjson,
> which is known to be even faster, if performance is an issue.

I did. However, looking at
http://www.tablix.org/~avian/blog/archives/2011/07/a_case_for_cjson/ we probably
don't want to use it - an unmaintained project with a known security
vulnerability isn't a good solution for performance issues.

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/pa...
File sitescripts/stats/bin/pagegenerator.py (right):

http://codereview.adblockplus.org/11481051/diff/4002/sitescripts/stats/bin/pa...
sitescripts/stats/bin/pagegenerator.py:116: if filter(lambda k: k not in
("hits", "bandwidth"), value.keys()):
On 2013/08/27 11:59:47, Sebasitian wrote:
> It does the same, but isn't actually necessary, because the dict object itself
> is iterable and will produce it keys on iteration.

See my reply - I already know that. But I prefer it to be obvious that we are
iterating over keys and not items here.

[Sebastian Noack, 2013-08-27 12:44:41]

lgtm

[Felix Dahlke, 2013-08-28 17:25:32]

I only focused on the notification parsing changes here, and optimising that in
particular.

I didn't spot anything wasteful we're doing, assuming we need all the fields of
the info object.

I optimised a few things here and there, mostly using dynamic programming, and
ended up speeding things up by about 22% in total. I added inline comments for
all these things.

After looking at the code, it looks like most of this is really CPU bound,
probably mostly caused by regex matching and string manipulation. Memory usage
should be relatively stable even with huge files. So switching to a faster
runtime will probably be the only thing that provides really significant
speedups.

I ran this with PyPy, which does JIT compilation and GC, and that sped things up
by 16%, which, together with my modifications above, results in a 40% speedup.
Without my modifications, PyPy speeds things up by 23%.

All the tests so far (the numbers above and the numbers for the micro
optimisations below) where with a very small notification log, only 10,000
lines. I've run some tests with a notification log containing 1,000,000, and at
this size, it seems to make a real difference:

CPython, no optimisations: 10:40 minutes
PyPy, no optimisations: 3:25 minutes
PyPy, all optimisations: 2:30 minutes

That's a 77% speedup. If that scales up to the real logs, which have around
10,000,000 lines, it'd be great.

I believe we still have more potential, if we want to invest more time:

1. Parallelisation - but that doesn't make sense right now, because the
notification servers only have a single core, and the code is CPU bound
2. Rewrite in native code or use a considerably faster runtime (e.g. the JVM) -
that's essentially a full rewrite

But frankly, 77% seems good enough for now.

http://codereview.adblockplus.org/11481051/diff/23002/sitescripts/stats/bin/l...
File sitescripts/stats/bin/logprocessor.py (right):

http://codereview.adblockplus.org/11481051/diff/23002/sitescripts/stats/bin/l...
sitescripts/stats/bin/logprocessor.py:29: match =
re.search(r"\bOpera/([\d\.]+)", ua)
Memoization helped save around 5% here. In an access log with 10k lines, I had
only 435 unique user agents.

Here's the approach I used:

ua_mem_table = {}

def parse_ua_mem(ua):
  hash_code = hash(ua)
  if not hash_code in ua_mem_table:
    ua_mem_table[hash_code] = {}
  if ua in ua_mem_table[hash_code]:
    return ua_mem_table[hash_code][ua]
  browser = parse_ua(ua)
  ua_mem_table[hash_code][ua] = browser
  return browser

Then I called parse_ua_mem instead of parse_ua below.

This is relatively easy on the memory and avoids collisions. Would be a tad bit
faster to just use a single flat hash table with the ua as the key, but that'd
also blow up memory usage.

http://codereview.adblockplus.org/11481051/diff/23002/sitescripts/stats/bin/l...
sitescripts/stats/bin/logprocessor.py:120: def parse_time(timestr, tz_hours,
tz_minutes):
Memoization saved round 6% for me here.

http://codereview.adblockplus.org/11481051/diff/23002/sitescripts/stats/bin/l...
sitescripts/stats/bin/logprocessor.py:125: def parse_path(path):
Memoization saved around 1.5% for me here.

http://codereview.adblockplus.org/11481051/diff/23002/sitescripts/stats/bin/l...
sitescripts/stats/bin/logprocessor.py:134: params =
urlparse.parse_qs(info["query"])
Looks like this is quite heavy, memoization saved around 2.5%.

http://codereview.adblockplus.org/11481051/diff/23002/sitescripts/stats/bin/l...
sitescripts/stats/bin/logprocessor.py:163: last_update =
datetime.strptime(last_version, "%Y%m%d%H%M")
Memoization saved around 3% for me here.

http://codereview.adblockplus.org/11481051/diff/23002/sitescripts/stats/bin/l...
sitescripts/stats/bin/logprocessor.py:179: if last_update.isocalendar()[0:2] !=
info["time"].isocalendar()[0:2]:
Doing this a bit lengthier saves me 6%:
if last_update.year != info["time"].year and last_update.month !=
info["time"].month:

http://codereview.adblockplus.org/11481051/diff/23002/sitescripts/stats/bin/l...
sitescripts/stats/bin/logprocessor.py:283: if "addonName" in info:
According to my tests, this block causes a runtime overhead of around 25%. It
looks like the concatenation is at fault (even 10000 concatenations of two 3
byte strings take more than a second), but I couldn't find a way to speed things
up.

Join appears to be a little bit faster, and I think it's nicer anyway:

info["fullAddon"] = " ".join((info["addonName"], info["addonVersion"]))

But I don't see how we can safe a significant amount of time here.

[Sebastian Noack, 2013-08-29 10:18:05]

On 2013/08/28 17:25:32, Felix H. Dahlke wrote:
> I ran this with PyPy, which does JIT compilation and GC, and that sped things
up
> by 16%, which, together with my modifications above, results in a 40% speedup.
> Without my modifications, PyPy speeds things up by 23%.

Using PyPy is a pretty good idea. But you should note that CPython also has a GC
in addition to reference counting. However CPython only uses the GC to resolve
circular references and to dispose objects that have a __del__ method. I don't
know whether and in which way PyPy's GC works different from that. But I doubt,
that a GC only approach (without any reference counting) would be faster. PyPy
is faster than CPython, mainly because of JIT compilation and runtime
optimization.

> All the tests so far (the numbers above and the numbers for the micro
> optimisations below) where with a very small notification log, only 10,000
> lines. I've run some tests with a notification log containing 1,000,000, and
at
> this size, it seems to make a real difference:
> 
> CPython, no optimisations: 10:40 minutes
> PyPy, no optimisations: 3:25 minutes
> PyPy, all optimisations: 2:30 minutes
> 
> That's a 77% speedup. If that scales up to the real logs, which have around
> 10,000,000 lines, it'd be great.

Good job.

http://codereview.adblockplus.org/11481051/diff/23002/sitescripts/stats/bin/l...
File sitescripts/stats/bin/logprocessor.py (right):

http://codereview.adblockplus.org/11481051/diff/23002/sitescripts/stats/bin/l...
sitescripts/stats/bin/logprocessor.py:29: match =
re.search(r"\bOpera/([\d\.]+)", ua)
On 2013/08/28 17:25:32, Felix H. Dahlke wrote:
> Memoization helped save around 5% here. In an access log with 10k lines, I had
> only 435 unique user agents.
> 
> Here's the approach I used:
> 
> ua_mem_table = {}
> 
> def parse_ua_mem(ua):
>   hash_code = hash(ua)
>   if not hash_code in ua_mem_table:
>     ua_mem_table[hash_code] = {}
>   if ua in ua_mem_table[hash_code]:
>     return ua_mem_table[hash_code][ua]
>   browser = parse_ua(ua)
>   ua_mem_table[hash_code][ua] = browser
>   return browser
> 
> Then I called parse_ua_mem instead of parse_ua below.
> 
> This is relatively easy on the memory and avoids collisions. Would be a tad
bit
> faster to just use a single flat hash table with the ua as the key, but that'd
> also blow up memory usage.

Python dicts are already hashtables. So when you get or set an item in a dict,
hash() is already called to determine the bucket, and then the key of each item
in the bucket will be compared directly to the requested key. So following
implementation would be even slightly faster and prevents collisions as well:

def parse_ua_mem(ua):
  try:
    browser = ua_mem_table[ua]
  except KeyError:
    browser = ua_mem_table[ua] = parse_ua(ua)
  return browser

http://codereview.adblockplus.org/11481051/diff/23002/sitescripts/stats/bin/l...
sitescripts/stats/bin/logprocessor.py:283: if "addonName" in info:
On 2013/08/28 17:25:32, Felix H. Dahlke wrote:
> According to my tests, this block causes a runtime overhead of around 25%. It
> looks like the concatenation is at fault (even 10000 concatenations of two 3
> byte strings take more than a second), but I couldn't find a way to speed
things
> up.
> 
> Join appears to be a little bit faster, and I think it's nicer anyway:
> 
> info["fullAddon"] = " ".join((info["addonName"], info["addonVersion"]))
> 
> But I don't see how we can safe a significant amount of time here.

In [8]: %timeit '%s %s' % (a,b)
1000000 loops, best of 3: 417 ns per loop

In [9]: %timeit ' '.join([a, b])
1000000 loops, best of 3: 480 ns per loop

In [10]: %timeit '%s %s' % (a,b)
1000000 loops, best of 3: 416 ns per loop

In [11]: %timeit ' '.join([a, b])
1000000 loops, best of 3: 484 ns per loop

My test showed that format strings are slightly faster. And I find them nicer
here. ;P

[Felix Dahlke, 2013-08-29 10:29:56]

On 2013/08/29 10:18:05, sebastian wrote:
> Using PyPy is a pretty good idea. But you should note that CPython also has a
GC
> in addition to reference counting. However CPython only uses the GC to resolve
> circular references and to dispose objects that have a __del__ method. I don't
> know whether and in which way PyPy's GC works different from that. But I
doubt,
> that a GC only approach (without any reference counting) would be faster.

I don't think so, reference counting has runtime overhead whereas GC has none.
Not really worth digging deeply into I guess, but GC is even faster than manual
memory management when there's a lot of memory available and a reasonable GC
algorithm is used (and when GC pauses are not an issue of course). That's
probably why modern JS runtimes, the JVM and PyPy go for it.

No matter what causes the speedup though, it's very evident. I think switching
to PyPy is what we should do first, considering my micro optimisations
afterwards.

[Felix Dahlke, 2013-08-29 10:30:09]

http://codereview.adblockplus.org/11481051/diff/23002/sitescripts/stats/bin/l...
File sitescripts/stats/bin/logprocessor.py (right):

http://codereview.adblockplus.org/11481051/diff/23002/sitescripts/stats/bin/l...
sitescripts/stats/bin/logprocessor.py:29: match =
re.search(r"\bOpera/([\d\.]+)", ua)
On 2013/08/29 10:18:05, sebastian wrote:
> On 2013/08/28 17:25:32, Felix H. Dahlke wrote:
> > Memoization helped save around 5% here. In an access log with 10k lines, I
had
> > only 435 unique user agents.
> > 
> > Here's the approach I used:
> > 
> > ua_mem_table = {}
> > 
> > def parse_ua_mem(ua):
> >   hash_code = hash(ua)
> >   if not hash_code in ua_mem_table:
> >     ua_mem_table[hash_code] = {}
> >   if ua in ua_mem_table[hash_code]:
> >     return ua_mem_table[hash_code][ua]
> >   browser = parse_ua(ua)
> >   ua_mem_table[hash_code][ua] = browser
> >   return browser
> > 
> > Then I called parse_ua_mem instead of parse_ua below.
> > 
> > This is relatively easy on the memory and avoids collisions. Would be a tad
> bit
> > faster to just use a single flat hash table with the ua as the key, but
that'd
> > also blow up memory usage.
> 
> Python dicts are already hashtables. So when you get or set an item in a dict,
> hash() is already called to determine the bucket, and then the key of each
item
> in the bucket will be compared directly to the requested key. So following
> implementation would be even slightly faster and prevents collisions as well:
> 
> def parse_ua_mem(ua):
>   try:
>     browser = ua_mem_table[ua]
>   except KeyError:
>     browser = ua_mem_table[ua] = parse_ua(ua)
>   return browser

I'm aware that dicts are hash tables. However, hash tables save the key as well
as the hash, and since the key is rather large, we'd use considerably more
memory using a single flat hash table, like I said. With this approach, we keep
only the unique keys. In both cases, memory usage goes up with the number of
lines, which is not ideal. But we shouldn't have it go up linearly.

http://codereview.adblockplus.org/11481051/diff/23002/sitescripts/stats/bin/l...
sitescripts/stats/bin/logprocessor.py:283: if "addonName" in info:
On 2013/08/29 10:18:05, sebastian wrote:
> On 2013/08/28 17:25:32, Felix H. Dahlke wrote:
> > According to my tests, this block causes a runtime overhead of around 25%.
It
> > looks like the concatenation is at fault (even 10000 concatenations of two 3
> > byte strings take more than a second), but I couldn't find a way to speed
> things
> > up.
> > 
> > Join appears to be a little bit faster, and I think it's nicer anyway:
> > 
> > info["fullAddon"] = " ".join((info["addonName"], info["addonVersion"]))
> > 
> > But I don't see how we can safe a significant amount of time here.
> 
> In [8]: %timeit '%s %s' % (a,b)
> 1000000 loops, best of 3: 417 ns per loop
> 
> In [9]: %timeit ' '.join([a, b])
> 1000000 loops, best of 3: 480 ns per loop
> 
> In [10]: %timeit '%s %s' % (a,b)
> 1000000 loops, best of 3: 416 ns per loop
> 
> In [11]: %timeit ' '.join([a, b])
> 1000000 loops, best of 3: 484 ns per loop
> 
> My test showed that format strings are slightly faster. And I find them nicer
> here. ;P

Fair enough :)

[Sebastian Noack, 2013-08-29 10:54:30]

On 2013/08/29 10:29:56, Felix H. Dahlke wrote:
> On 2013/08/29 10:18:05, sebastian wrote:
> > Using PyPy is a pretty good idea. But you should note that CPython also has
a
> GC
> > in addition to reference counting. However CPython only uses the GC to
resolve
> > circular references and to dispose objects that have a __del__ method. I
don't
> > know whether and in which way PyPy's GC works different from that. But I
> doubt,
> > that a GC only approach (without any reference counting) would be faster.
> 
> I don't think so, reference counting has runtime overhead whereas GC has none.
> Not really worth digging deeply into I guess, but GC is even faster than
manual
> memory management when there's a lot of memory available and a reasonable GC
> algorithm is used (and when GC pauses are not an issue of course). That's
> probably why modern JS runtimes, the JVM and PyPy go for it.

I don't see how a GC can have no runtime overhead. It usually has even more
overhead, than reference counting. But while reference counting is done inline,
garbage collection can be deferred. This is an advantage in asynchronous and
IO-bound applications (which are most applications), where the garbage collector
can run while the application would just idle otherwise. But in an CPU-bound
application, it might be way slower than reference counting.

http://codereview.adblockplus.org/11481051/diff/23002/sitescripts/stats/bin/l...
File sitescripts/stats/bin/logprocessor.py (right):

http://codereview.adblockplus.org/11481051/diff/23002/sitescripts/stats/bin/l...
sitescripts/stats/bin/logprocessor.py:29: match =
re.search(r"\bOpera/([\d\.]+)", ua)
On 2013/08/29 10:30:09, Felix H. Dahlke wrote:
> On 2013/08/29 10:18:05, sebastian wrote:
> > On 2013/08/28 17:25:32, Felix H. Dahlke wrote:
> > > Memoization helped save around 5% here. In an access log with 10k lines, I
> had
> > > only 435 unique user agents.
> > > 
> > > Here's the approach I used:
> > > 
> > > ua_mem_table = {}
> > > 
> > > def parse_ua_mem(ua):
> > >   hash_code = hash(ua)
> > >   if not hash_code in ua_mem_table:
> > >     ua_mem_table[hash_code] = {}
> > >   if ua in ua_mem_table[hash_code]:
> > >     return ua_mem_table[hash_code][ua]
> > >   browser = parse_ua(ua)
> > >   ua_mem_table[hash_code][ua] = browser
> > >   return browser
> > > 
> > > Then I called parse_ua_mem instead of parse_ua below.
> > > 
> > > This is relatively easy on the memory and avoids collisions. Would be a
tad
> > bit
> > > faster to just use a single flat hash table with the ua as the key, but
> that'd
> > > also blow up memory usage.
> > 
> > Python dicts are already hashtables. So when you get or set an item in a
dict,
> > hash() is already called to determine the bucket, and then the key of each
> item
> > in the bucket will be compared directly to the requested key. So following
> > implementation would be even slightly faster and prevents collisions as
well:
> > 
> > def parse_ua_mem(ua):
> >   try:
> >     browser = ua_mem_table[ua]
> >   except KeyError:
> >     browser = ua_mem_table[ua] = parse_ua(ua)
> >   return browser
> 
> I'm aware that dicts are hash tables. However, hash tables save the key as
well
> as the hash, and since the key is rather large, we'd use considerably more
> memory using a single flat hash table, like I said. With this approach, we
keep
> only the unique keys. In both cases, memory usage goes up with the number of
> lines, which is not ideal. But we shouldn't have it go up linearly.

Keys in python dicts are already unique. So when you add multiple items with the
same key (key1 == key2 == True), into a dict, only the most recent added
key-value-pair is kept. Just like with your approach. Or what do you mean?

If you don't want to grow the cache infinitely, you might want to use an LRU
cache.

[Felix Dahlke, 2013-08-29 12:38:19]

On 2013/08/29 10:54:30, sebastian wrote:
> I don't see how a GC can have no runtime overhead. It usually has even more
> overhead, than reference counting.

It has no overhead at all at allocation/deallocation time, I think that's mainly
what makes GC more efficient if (and AFAIK only if) there is considerably more
memory available than needed. The JVM e.g. uses concurrent mark sweep, so it's
even faster if multiple cores are available.

[Felix Dahlke, 2013-08-29 12:38:26]

http://codereview.adblockplus.org/11481051/diff/23002/sitescripts/stats/bin/l...
File sitescripts/stats/bin/logprocessor.py (right):

http://codereview.adblockplus.org/11481051/diff/23002/sitescripts/stats/bin/l...
sitescripts/stats/bin/logprocessor.py:29: match =
re.search(r"\bOpera/([\d\.]+)", ua)
On 2013/08/29 10:54:30, sebastian wrote:
> On 2013/08/29 10:30:09, Felix H. Dahlke wrote:
> > On 2013/08/29 10:18:05, sebastian wrote:
> > > On 2013/08/28 17:25:32, Felix H. Dahlke wrote:
> > > > Memoization helped save around 5% here. In an access log with 10k lines,
I
> > had
> > > > only 435 unique user agents.
> > > > 
> > > > Here's the approach I used:
> > > > 
> > > > ua_mem_table = {}
> > > > 
> > > > def parse_ua_mem(ua):
> > > >   hash_code = hash(ua)
> > > >   if not hash_code in ua_mem_table:
> > > >     ua_mem_table[hash_code] = {}
> > > >   if ua in ua_mem_table[hash_code]:
> > > >     return ua_mem_table[hash_code][ua]
> > > >   browser = parse_ua(ua)
> > > >   ua_mem_table[hash_code][ua] = browser
> > > >   return browser
> > > > 
> > > > Then I called parse_ua_mem instead of parse_ua below.
> > > > 
> > > > This is relatively easy on the memory and avoids collisions. Would be a
> tad
> > > bit
> > > > faster to just use a single flat hash table with the ua as the key, but
> > that'd
> > > > also blow up memory usage.
> > > 
> > > Python dicts are already hashtables. So when you get or set an item in a
> dict,
> > > hash() is already called to determine the bucket, and then the key of each
> > item
> > > in the bucket will be compared directly to the requested key. So following
> > > implementation would be even slightly faster and prevents collisions as
> well:
> > > 
> > > def parse_ua_mem(ua):
> > >   try:
> > >     browser = ua_mem_table[ua]
> > >   except KeyError:
> > >     browser = ua_mem_table[ua] = parse_ua(ua)
> > >   return browser
> > 
> > I'm aware that dicts are hash tables. However, hash tables save the key as
> well
> > as the hash, and since the key is rather large, we'd use considerably more
> > memory using a single flat hash table, like I said. With this approach, we
> keep
> > only the unique keys. In both cases, memory usage goes up with the number of
> > lines, which is not ideal. But we shouldn't have it go up linearly.
> 
> Keys in python dicts are already unique. So when you add multiple items with
the
> same key (key1 == key2 == True), into a dict, only the most recent added
> key-value-pair is kept. Just like with your approach. Or what do you mean?
> 
> If you don't want to grow the cache infinitely, you might want to use an LRU
> cache.

Now I see why you're asking, the implementation I provided is actually complete
rubbish. What I had in mind is something along these lines:

    if not key in big_map:
      big_map[key] = []
    big_map[key].append(value)

However, I just tested this and it doesn't help at all. Simple hash table
implementations generally store the key as part of each object, not each bucket,
and I thought this is what Python does. In that case my approach would have
helped. However, each unique key is being stored only once already, so the flat
map approach is in fact the most memory efficient one.

[Sebastian Noack, 2013-08-29 13:33:46]

On 2013/08/29 12:38:19, Felix H. Dahlke wrote:
> On 2013/08/29 10:54:30, sebastian wrote:
> > I don't see how a GC can have no runtime overhead. It usually has even more
> > overhead, than reference counting.
> 
> It has no overhead at all at allocation/deallocation time, I think that's
mainly
> what makes GC more efficient if (and AFAIK only if) there is considerably more
> memory available than needed. The JVM e.g. uses concurrent mark sweep, so it's
> even faster if multiple cores are available.

The garbage collector actually have to know which objects exist, in order to
figure out which of them it can destroy. Dependent on the implementation details
of your runtime those information already exist, or otherwise would require a
little overhead on allocation. But yes, the actual work moves from the time of
allocation/deallocation to the time of garbage collection. In cases where
garbage collection can be deferred until the application would idle otherwise,
this can speed up things. But in a CPU-bound application the GC has to interrupt
the execution of the application, and slow it down. Yes, you could also move the
GC to background threads. But as you already noted, that only gives an advantage
on multi core machines. And even then, data must be shared between the runtime
and the GC threads, and therefore locks are required, that might still interrupt
execution.

[Felix Dahlke, 2013-08-29 13:41:31]

On 2013/08/29 13:33:46, sebastian wrote:
> this can speed up things. But in a CPU-bound application the GC has to
interrupt
> the execution of the application, and slow it down.

True, but that's all at one time, running the same code again and again means
there's not that much swapping at the CPU level, and various other things at
that level I don't fully comprehend yet :)

[Wladimir Palant, 2013-08-29 13:42:42]

I added memoization in the places noted by Felix, this caused a 16% performance
improvement for me.

However, using PyPy is non-trivial to say the least, finding the right packages
for it is difficult. This affects GeoIP in particular.

[Felix Dahlke, 2013-08-29 13:58:57]

LGTM

[Felix Dahlke, 2013-08-29 15:06:16]

On 2013/08/29 13:42:42, Wladimir Palant wrote:
> However, using PyPy is non-trivial to say the least, finding the right
packages
> for it is difficult. This affects GeoIP in particular.

For the record, there are three packages in PyPI we could use:

- pygeoip (pure Python implementation)
- OL-GeoIP (fork of the module we use, possibly unmaintained)
- GeoIP2 (new version of the module we use, apparently beta)

Out of these, pygeoip looks like the best option, but it might just be slower. I
tested this and the speedup we get from PyPy is still significant.

I tested with 10,000,000 entries and without any optimisations:

CPython, no GeoIP: 10:40 minutes
PyPy, no GeoIP: 3:25 minutes
PyPy, pygeoip: 4:21 minutes

So, while using pygeoip takes 21% longer than not using GeoIP at all (I couldn't
get the module we use for OSX, so I can't compare), it's still more than twice
as fast as CPython without using GeoIP. So, looks like it's more than worth it.

[Felix Dahlke, 2013-08-29 15:13:36]

On 2013/08/29 15:06:16, Felix H. Dahlke wrote:
> I tested with 10,000,000 entries and without any optimisations:

Um, overenthusiastic typo there, I tested with 1,000,000 lines. The numbers are
correct though.

[Wladimir Palant, 2013-08-29 19:40:28]

Ok, you got me convinced. See http://codereview.adblockplus.org/11577044/.