jekyll/jekyll — pull request #1983 by jfirebaugh (2014-01-25 01:29:11+00:00)
Title: Optimize Post#{next,previous}

Use object equality for comparisons rather than Comparable#==, which in turn uses Post#<=>, which is slow.

Specifically, the bottleneck call stack is:

```
Jekyll::Post#<=>
Comparable#==
Array#index
Jekyll::Post#{next,previous}
```

Using the block form of `Array#index` and object equality (`equal?`) yielded a 3x performance improvement for `jekyll build` on a large site (1m6.467s -> 0m19.532s).

This assumes that `#next` and `#previous` are only called on Post objects that are actually in `site.posts`. If that's not a safe assumption, I can come up with an alternative fix. However, the one that seemed obvious to me -- defining `Post#==` in terms of `Post#id` -- turned out to actually be slower.

I did some profiling using ruby-prof and stackprof. Both indicated that Post#<=> was an extreme bottleneck.

Excerpts from ruby-prof graph:

```
--------------------------------------------------------------------------------
0.000 0.000 0.000 0.000 59/91042435 Gem::StubSpecification#activated?
684.333 141.914 0.000 542.41991042376/91042435 Array#index
84.49% 17.52% 684.333 141.914 0.000 542.419 91042435 Comparable#==
542.419 308.751 0.000 233.66891042376/91113856 Jekyll::Post#<=>
--------------------------------------------------------------------------------
0.005 0.003 0.000 0.002 773/91113856 Array#sort
0.427 0.247 0.000 0.180 70707/91113856 Array#sort!
542.419 308.751 0.000 233.66891042376/91113856 Comparable#==
67.02% 38.15% 542.851 309.000 0.000 233.851 91113856 Jekyll::Post#<=>
180.840 115.968 0.000 64.87291113856/91113856 Time#<=>
52.907 52.907 0.000 0.00091113856/91310726 Fixnum#==
0.104 0.104 0.000 0.000 138743/138750 String#<=>
--------------------------------------------------------------------------------
...
--------------------------------------------------------------------------------
373.077 0.575 0.000 372.502 85720/85720 Array#map
46.06% 0.07% 373.077 0.575 0.000 372.502 85720 Jekyll::Post#next
372.120 29.587 0.000 342.534 85720/171455 Array#index
0.082 0.082 0.000 0.000 85720/87096 Fixnum#<
0.080 0.080 0.000 0.000 85716/374666 Array#[]
0.079 0.079 0.000 0.000 85720/413908 Fixnum#-
0.071 0.071 0.000 0.000 85716/616276 Fixnum#+
0.070 0.070 0.000 0.000 85720/255886 Array#length
--------------------------------------------------------------------------------
371.819 0.464 0.000 371.354 85720/85720 Array#map
45.90% 0.06% 371.819 0.464 0.000 371.354 85720 Jekyll::Post#previous
371.098 29.299 0.000 341.799 85720/171455 Array#index
0.099 0.099 0.000 0.000 85720/167276 Fixnum#>
0.079 0.079 0.000 0.000 85717/413908 Fixnum#-
0.078 0.078 0.000 0.000 85717/374666 Array#[]
--------------------------------------------------------------------------------
```

Excerpts from stackprof analysis:

```
~/Development/mapbox.github.com $ stackprof stackprof-cpu.dump --text --limit 4
==================================
Mode: cpu(1000)
Samples: 17557 (0.14% miss rate)
GC: 1221 (6.95%)
==================================
TOTAL (pct) SAMPLES (pct) FRAME
9753 (55.6%) 9753 (55.6%) Jekyll::Post#<=>
5760 (32.8%) 946 (5.4%) Jekyll::Post#previous
5866 (33.4%) 928 (5.3%) Jekyll::Post#next
709 (4.0%) 550 (3.1%) Hash#deep_merge
~/Development/mapbox.github.com $ stackprof stackprof-cpu.dump --method 'Jekyll::Post#<=>'
Jekyll::Post#<=> (/Users/john/.gem/ruby/2.1.0/gems/jekyll-1.4.3/lib/jekyll/post.rb:144)
samples: 9753 self (55.6%) / 9753 total (55.6%)
callers:
4938 ( 50.6%) Jekyll::Post#next
4814 ( 49.4%) Jekyll::Post#previous
1 ( 0.0%) block (2 levels) in Jekyll::Site#render
code:
| 144 | def <=>(other)
9016 (51.4%) / 9016 (51.4%) | 145 | cmp = self.date <=> other.date
522 (3.0%) / 522 (3.0%) | 146 | if 0 == cmp
| 147 | cmp = self.slug <=> other.slug
| 148 | end
215 (1.2%) / 215 (1.2%) | 149 | return cmp
| 150 | end
```

Timing data, before and after:

```
~/Development/mapbox.github.com $ time jekyll build
Configuration file: /Users/john/Development/mapbox.github.com/_config.yml
Source: /Users/john/Development/mapbox.github.com
Destination: /Users/john/Development/mapbox.github.com/_site
Generating... done.

real	1m6.467s
user	1m5.889s
sys	0m0.446s
~/Development/mapbox.github.com $ time jekyll build
Configuration file: /Users/john/Development/mapbox.github.com/_config.yml
Source: /Users/john/Development/mapbox.github.com
Destination: /Users/john/Development/mapbox.github.com/_site
Generating... done.

real	0m19.532s
user	0m19.095s
sys	0m0.393s
```