Minimize cache misshit to gain optimal speed

# Cachelined: A ruby improvement

### Abstract

![](https://raw.github.com/shyouhei/sandbox/master/cachelined/banner.png)

It's faster, even compared to 2.1.

### Introduction

Ruby is an object oriented language.  Although it is normal these days, "everything is an object" has been a key characteristic of this language.

The "object", in practice, is stored as a C struct named `struct RVALUE` (with a few exceptions such as `true`, `false`).  This struct is a 5 machine-word sized structure.  Its first word is management area mainly for flags, the next word is a pointer to that object's class if any, and the remaining 3 words are dedicated for each classes.

```c
struct RBasic {
    VALUE flags;
    const VALUE klass;
};

typedef struct RVALUE {
    union {
        struct {
            struct RBasic basic;
            VALUE v1;
            VALUE v2;
            VALUE v3;
        } values;
        …
    } as;
} RVALUE;
```

The problem is, 5 is a prime number.  So cache mechanisms of any size cannot store this struct efficiently.  Most notably, CPUs have been equipped with data caches since their mid age; Ruby's objects do not suit there.  That does not always mean a breakage but significant slowdown is happening.

Today I'd like to propose a fix around this; to make objects power-of-two sized.  What I did was to make objects 8 words length instead of 5.  By doing so an object, most importantly its `struct RBasic` part, is forced to fit in a same cache line.

A side effect is that the extended areas of each objects can be used to store additional info.  For instance strings can hold up to 48 bytes inside their objects;  most short strings are now embedded, which reduces memory allocations.

### Cache Lines

It is not the recent development.  At least, Intel i386 could use upto 64KiB L1 cache.  But since CPUs get faster and faster, the importance of cache is rising rapidly.

When CPU tries to retrieve an area of memory, no matter how many bytes it requested, a bunch of memory regions are loaded anyway for later uses.  This bunch is called "cache line".  The size of that line vary from model to model, but most recent CPUs use 64 bytes.  So whenever you poke a memory, 64 bytes are concerned at once.

Like I mentioned above ruby objects are (were) 5 words width, or 40 bytes.  Objects are tightly arranged inside memory.  If an object starts from 0 byte offset from cache line, the next object is 24 bytes on the current cache, but remaining 16 bytes are not.  As 5 is a prime, the size of an object and the cache line size are pairwise disjoint.  This means every patterns of placements are possible.  Only 3 out of 8 possible arrangement holds entire object at once in a cache line.  All other cases need to access real memory twice.

### Our Approach

To fix this issue is simple; just make ruby objects large enough so that they can tightly fit into each cache lines.  By carefully aligning initial allocation, we can force every objects to be cache line aligned.  By dong so every access to an object is guaranteed to have at most one physical memory access.

### Embedding Others

Interesting side effect of expanding object width, is that it eliminates some memory allocations.

Several ruby objects "embeds" their contents when possible.  These objects include strings, arrays, hashes, and instances of pure-ruby classes; that is, a wide range of popular objects do so.  Now, the width of an object is extended.  This means there are much more rooms for those embedding objects.  For instance arrays can now embed upto 6 elements.  Hashes can hold upto 3 key-value pairs.  Strings can hold upto 48 bytes.  These relatively small objects are now self-contained.  They can avoid extra cost of allocations.

### Experiments

To determine effectiveness of this approach I took several experiments on my vaio pro laptop.  This machine is 2 physical / 4 logical core Haswell equipped, running Linux 3.12.0 (3.12.0 was needed for Linux to support Intel p-state on this chip).

#### Results of `make benchmark`

Here is the result of `make benchmark`, against ruby 2.1.1p2, 2.0.0p376, 1.9.3p488, and ours (trunk r44485 + our patch); all compiled from source, same compiler (clang 3.2), same options.

![](https://raw.github.com/shyouhei/sandbox/master/cachelined/benchmark.png)

The result of proposed approach is very similar to 2.1.1p2.  It seems they are virtually identical.  But our approach is the fastest for most cases.  Most are few % faster than 2.1.1p2; which is typical to cache optimizations.  Several cases earn more speedup because of side effect mentioned above, most notably is `bm_vm3_gc`; which in fact used most if its time around hash allocations.

#### Results of `make rdoc`

To measure impacts of our approach to a real-world program, `make rdoc XRUBY=${target}` is tested against the set of ruby versions mentioned above.  However, 1.9.3 was not able to make it through due to the version RDoc supports.  So it is not on the graph.

![](https://raw.github.com/shyouhei/sandbox/master/cachelined/rdoc.png)

Here again, our approach is the fastest.  RDoc is almost 100% pure-ruby, so hash optimizations benefit it very much.

#### Memory usage

One key concern about our approach is the increasing size of objects; that can impact on memory footprint.  Though at the same time many small memory regions (notably hashes) are packed into one, which can partially reduce memory usages.  How much is used in fact?

To measure memory usages I used valgrind memory profiler.  It can profile memory usage in non-disruptive manner.  Here are memory footprints of rdoc generation:

![](https://raw.github.com/shyouhei/sandbox/master/cachelined/massif.211p2.png)<br>![](https://raw.github.com/shyouhei/sandbox/master/cachelined/massif.cachelined.png)

Two graphs above are the memory profiles for both ours and 2.1.1p2.  It shows that the memory footprint does blow up.  However I also have to note that the blew up ratio is  260.5 / 207.4 == 1.256, which is below what is expected from the object size (8 words / 5 words == 1.6 times bigger).  If you take a closer look at them, you see the amount acquired by `heap_assign_page()` is increasing, while that of `objspace_xmalloc()` is decreasing.  This means some part of memories originally taken externally are now embedded into objects; which clearly describes the side effect we expected.

#### Cache profile

Valgrind can also profile cache misshits.  However this feature is ultra slow, not suitable for real-world programs like RDoc.  So I tested `ruby --disable-gems -e"0x400000.times { Object.new }"`.  The output below is cache misshit delta between ours versus 2.1.1p2.

```
zsh % cg_diff cachegrind.out.cachelined cachegrind.out.211p2 | cg_annotate /dev/stdin
--------------------------------------------------------------------------------
Files compared:   cachegrind.out.cachelined; cachegrind.out.211p2
Command:          ./ruby --disable-gems -e0x400000.times { Object.new }; /home/shyouhei/data/target/ruby_2_1/bin/ruby --disable-gems -e0x400000.times { Object.new }
Data file:        /dev/stdin
Events recorded:  Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
Events shown:     Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
Event sort order: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
Thresholds:       0.1 100 100 100 100 100 100 100 100
Include dirs:     
User annotated:   
Auto-annotation:  off

--------------------------------------------------------------------------------
        Ir  I1mr ILmr      Dr       D1mr DLmr      Dw    D1mw    DLmw 
--------------------------------------------------------------------------------
12,772,600 3,381  -36 742,954 -1,725,002    2 222,942 -30,220 -14,810  PROGRAM TOTALS

--------------------------------------------------------------------------------
       Ir  I1mr ILmr      Dr       D1mr DLmr        Dw    D1mw    DLmw  file:function
--------------------------------------------------------------------------------
8,490,879    13   -1 -65,345 -1,553,377    0  -102,802 -19,959       0  gc.c:gc_heap_lazy_sweep
1,435,366   -12    1 247,409     -1,476    0   144,589     436       0  gc.c:gc_mark
  938,264     4    1  42,615     -3,114    0    32,188    -328       0  gc.c:gc_marks_body
  732,366   -23   -2 180,170     23,350    0    91,665      22       0  gc.c:gc_mark_children
  544,747    -1    2  72,222        -68    0     1,826       0       0  gc.c:mark_current_machine_context
  516,747   -11    0 167,970     21,331    0    54,456      59       0  st.c:st_foreach
  226,596  -368    0  78,816     10,844    0    39,408    -353       0  gc.c:mark_method_entry_i
 -204,979   -33    1 -45,053   -152,686    0   -38,672  12,178       2  gc.c:newobj_of
  119,003  -365    0  36,875      5,999    0     3,186       0       0  st.c:st_foreach_check
 -100,022   -93    1 -11,628       -556    0   -37,545 -15,310 -14,791  gc.c:heap_assign_page
  -95,217   -37    0 -34,943       -125    0         0       0       0  gc.c:rb_gc_mark_maybe
   76,464     0    0  33,453      2,771    0    23,895       0       0  gc.c:mark_const_entry_i
   34,515     5    0  10,620          7    0     5,310       0       0  hash.c:foreach_safe_i
   29,571    21    0   3,942        296    0     4,854       0       0  gc.c:rb_gc_mark_locations
   29,205     0    0  15,930      1,177    0     5,310       0       0  variable.c:mark_global_entry
   27,317   -42    0   4,897        708    0       944       0       0  vm.c:rb_vm_mark
   22,656    -1    0   7,552          0    0         0       0       0  gc.c:rb_gc_mark
  -20,253     0    0  -2,421     -7,125    0       -27       1       0  gc.c:rb_gc_call_finalizer_at_exit
  -19,602    21    0  -4,340     -1,669    0    -5,874  -6,707       0  gc.c:garbage_collect_body
  -18,335   134    0  -9,156         -7    0    -3,061      -3       0  parse.y:rb_intern2
  -18,131   -33   -2  -5,163       -229    0    -2,464     -44       3  /build/buildd/eglibc-2.17/malloc/malloc.c:_int_free
  -16,541    60    0  -2,080       -281    0    -2,300     -65      83  /build/buildd/eglibc-2.17/malloc/malloc.c:_int_malloc
   16,284     8    0   8,142          0    0     5,428      -1       0  gc.c:mark_entry
   14,809  -377    0   4,189        881    0     2,773     118       0  vm.c:rb_thread_mark
   14,342  -119   -1   3,611        474    0     1,892      59       0  gc.c:gc_mark_roots
```

It shows that data read ("Dr") is increasing, while cache misshit ("D1mr") is decreasing.  This conforms very much with the memory profile;  the footprint increases so data read counts up, while cache misshit decreases as designed to be.

### Conclusion

Proposed is a way optimize cache misshits in ruby's object system.  It speeds up both benchmarks and real-world programs, by sacrificing memory footprint a bit.