Ruby Compact Internals
Tags: ruby, internals, c, research
Published: 2019-08-11 23:25:04

I encountered a weird phenomenon regarding ruby's `compact` method, and I thought I'd share my findings with you.
When working on "The Grid" dashboard here at [monday.com](https://monday.com), I got to a point where I had an array of hashes, and some of the hashes were empty.
I needed to get rid of those.

---

##Bottom line first
To get the result I wanted I just did `a.reject { |v| v.blank? }` instead of `a.compact`.

---

##Expectation VS Reality.
When I used `compact` on the array I was a bit surprised by the result. 
```ruby
a = [{ key: 'value' }, { key: 'value2' }, {}]

puts a.compact
#[{ key: 'value' }, { key: 'value2' }, {}]
```

I expected the `compact` method to just go over each element in the array, check if it's `present?` and if it is return it.
Something like this:

```ruby
def compact
  select { |value| value.present? }
end
```

So when I had an array with empty hashes that wouldn't go away I had to find the explanation.

---

##The implementations behind the scenes
As usual, I dug deeper for the implementations.

From past research I know ruby's Hash also has a `compact` method and I know it's pretty straightforward, for each key in the hash we check if it's `nil`, if it's not we return it.
Super easy. Similar to what I suggested above, easy to understand, although it wouldn't solve the issue (because we use `nil?` instead of `blank?` or `!present?`)*

_activesupport/lib/active_support/core_ext/hash/compact.rb, line 12_
```ruby
def compact
  select { |_, value| !value.nil? }
end
```


In arrays however the implementation is more complex. It is implemented purely in C.
```c
static VALUE
rb_ary_compact(VALUE ary)
{
  ary = rb_ary_dup(ary);
  rb_ary_compact_bang(ary);
  return ary;
}
```

---

##C is love, C is life
If you don't have any background in C, this next part might be less interesting to you. I'll try to make it as understandable as possible, but I highly recommend learning C if you have the time!

###Pointers background
In case you don't know, the way we access our program's memory (the place where the variables are stored) is by using **pointers**.
These pointers are basically just an address in the memory where we can find the beginning of our variable (each variable takes a different amount of memory, we just get the required number of bytes starting at the pointer's position)

Arrays work similarly (actually, an array is literally a pointer), let's say we have an array of 3 characters, each character consists of one byte, all 3 bytes are stored one after the other in memory.
We can go to the first address in the array (or the pointer to that array), and take 1 byte, that's the first character. Then we take another, that's the second, and then the third.

```c
char arr[3] = {'m', 'i', 'p'}
/*
Behind the scenes it's stored like so:
... 6d 69 70 ...
    ^ arr[0] == *arr
... 6d 69 70 ...
       ^ arr[1] == *(arr + 1)
... 6d 69 70 ...
          ^ arr[2] == *(arr + 2)
*/
```

Another thing to note: in C, if we have a pointer stored in a variable, let's say `ptr`, this variable will contain the address to the value. To get to the value _itself_ we have to use the **"dereference" operator** (an asterisk before the variable name) like so `*ptr`.

###Back to code
Above we saw the C implementation of ruby's array `compact`, we can see a function that receives an array, duplicates it (using the `rb_ary_dup` function), `compact`s it using the `rb_ary_compact_bang` function ("bang" is the same as the "!" symbol, so it basically runs `compact!`), and then returns the duplicated, compacted array.

To find that `rb_ary_compact_bang` function I went to [ruby's source code](https://github.com/ruby/ruby/blob/9d298b9dab831f966ea4bf365c712161118dd631/array.c):

_ruby/array.c, line 5022_
```c
static VALUE
rb_ary_compact_bang(VALUE ary)
{
  VALUE *p, *t, *end;
  long n;

  rb_ary_modify(ary);
  p = t = (VALUE *)RARRAY_CONST_PTR_TRANSIENT(ary); /* WB: no new reference */
  end = p + RARRAY_LEN(ary);

  while (t < end) {
    if (NIL_P(*t)) t++;
    else *p++ = *t++;
  }
  n = p - RARRAY_CONST_PTR_TRANSIENT(ary);
  if (RARRAY_LEN(ary) == n) {
    return Qnil;
  }
  ary_resize_smaller(ary, n);

  return ary;
}
```

Don't close the post! This code isn't friendly for people with no experience in C, but most of it is memory management, some games of allocating memory correctly, resizing arrays to prevent memory leaks etc. I can do a deeper dive in a seperate post if anyone wants.

The interesting part is this one:
```c
while (t < end) {
  if (NIL_P(*t)) t++;
  else *p++ = *t++;
}
```

###Line by line
As I explained above, an array is just a set of variables stored one after the other in our program's memory, so we can get a pointer to the first variable, and then just increase it by 1 every time to get to the next one (`t++` increases `t` by 1)

What we have here is a loop that goes from the beginning of the array, with our current position in the `t` variable (a pointer to the array), and we iterate over every element until we reach the `end` of the array (the address of the beginning of the array + the length of the array)

Every time, we check whether the current value is `nil` (using the `NIL_P` macro defined in _include/ruby/ruby.h line 482_)

If it is `nil` we just increase the pointer, advancing one spot in our array.
If it's not `nil` we put the current value from the original `t` (remember, the `*` dereferences the pointer) into another array we keep stored in the pointer `p`, and then advance the pointer one spot.

##Bottom line
In a nutshell, it's the same as doing `a.reject { |v| v.nil? }` but more memory aware and efficient.

Just to show the difference in efficiency I benchmarked both ways against an array of 20,000,000 elements with alternating integers and `nil`s.
![](https://thepracticaldev.s3.amazonaws.com/i/k9o8p26uqlr0mvuq5l4c.png)
As you can see, array's `compact` method using C null pointer elimination is 6.6 times faster than the `reject` method!

I hope you enjoyed learning a bit about ruby's internal mechanisms!

\* This is the activesupport implementation of Hash `compact`, if you'd like to see the C implementation you can go to _[ruby/hash.c](https://github.com/ruby/ruby/blob/4daff3a603d1a8b2656e82108e2f7d0abf8103c9/hash.c) line 4110_, but it's pretty similar!