z, ?	toggle help (this)
space, →	next slide
shift-space, ←	previous slide
d	toggle debug mode
## <ret>	go to slide #
r	reload slides
n	toggle notes

loading presentation...

Hello everyone! In this presentation, I will be discussing how the Set class was reimplemented as a core class in Ruby 4.0.

Implementing

Core Set

RubyKaigi 2026

My name is Jeremy Evans. I am a Ruby committer. I am also the maintainer of Sequel, Roda, Rodauth, and many other gems.

GitHub: jeremyevans

Twitter: @jeremyevans0

I work at Ubicloud as a Principal Software Engineer. We are building an open source alternative to Amazon Web Services.

@

Let me first give a brief history of the Set class.

History

Set was added as a standard library in Ruby 1.8.0.

Added

in Ruby 1.8.0

When Set was added, it used a hash for storage, where each element of the set is a key in the hash,

Elements

Are Hash Keys

and all of the hash values are true.

All Hash Values

Are true

In Ruby 3.2, Set became an autoloaded constant. So while the Set standard library was not loaded by default, you could use Set without requiring it, so from a user perspective, it appeared to be a core class.

Autoloaded

in Ruby 3.2

Set's basic design did not change between when it was introduced in Ruby 1.8.0 and Ruby 3.4, though there have been some methods added to set over the years.|Considering the constraints that Set needed to operate within, I do not think it could have been designed better. However, there were a couple issues with it.

Design

Unchanged

The first was that set used more memory than was theoretically necessary.

Excessive

Memory Use

This is due to the fact that for each element in the set, there is space taken to store a true value in the hash, even though this value is the same for all elements. |While true itself is an immediate object and does not take space by itself, the hash entry must reserve space for the hash value. This reserved space is wasted for set elements.

All Hash Values

Are true

The second issue was that certain set methods could return incorrect values if called concurrently by multiple threads.

Thread

Safety

Here is an definition of one such method, add predicate, which has been functionally the same since Ruby 1.8.0.

  def add?(o)
    add(o) unless include?(o)
  end

The sole reason that add predicate exists is so that the caller can tell the difference between adding a new element to the set, or making no change to the set as the element was already in the set.

  def add?(o)
    add(o) unless include?(o)
  end

The method first checks whether the set already includes the element.

  def add?(o)
    add(o) unless include?(o)
  end

If the element is already included in the set, include returns true, so the unless conditional results in the method returning nil and making no changes.

  def add?(o)
    add(o) unless include?(o)
  end

If the set does not already include the element, it adds the element to the set. add returns the set itself, so the caller can know whether a new element was added to the set.

  def add?(o)
    add(o) unless include?(o)
  end

Unfortunately, this code has an issue if the set is being updated concurrently by multiple threads.|If two threads call add predicate concurrently with the same element, both could check whether the element is already included in the set, which could be false for both threads.

  def add?(o)
    add(o) unless include?(o)
  end

Then, both threads call add and both return the set. This is a thread safety issue, since the method should return nil for one of the threads.

  def add?(o)
    add(o) unless include?(o)
  end

Unfortuantely, there is no way to avoid this issue, because Ruby's hash does not provide a method that allows for thread safe behavior in this case.|There have been multiple proposals to add such a method to hash, in some cases specifically to allow for a thread safe version of this method, but they were never merged.

  def add?(o)
    add(o) unless include?(o)
  end

Note that this method also has a minor performance issue, because it does two separate hash lookups instead of a single hash lookup, which makes the method slower.

  def add?(o)
    add(o) unless include?(o)
  end

Now that you know about the issues with the previous standard library implementation, I can discuss the new implementation of Set in Ruby 4.0.|Note that while the implementation changed completely,

New

Implementation

the underlying design of the library remains the same.

Using

Same

Design

One of the primary goals of the new implementation is to reduce the memory usage for large sets.|As I mentioned, the excessive memory use is because we are storing an unnecessary true value for each set element.

Reduce

Memory

Usage

Each entry you store in a Ruby hash actually stores three separate values.

struct st_table_entry {
    st_hash_t hash;
    st_data_t key;
    st_data_t record;
};

The first value stored is the hash code for the entry. This would be based on the integer returned by calling the hash method on the key.

struct st_table_entry {
    st_hash_t hash;
    st_data_t key;
    st_data_t record;
};

The key is stored separately from the hash code, because multiple keys may have the same hash code.

struct st_table_entry {
    st_hash_t hash;
    st_data_t key;
    st_data_t record;
};

Finally, the value for the hash entry is stored in the record member. For the standard library set implementation, this member is always true.

struct st_table_entry {
    st_hash_t hash;
    st_data_t key;
    st_data_t record;
};

Of the three members, only the first two are needed for sets.

struct st_table_entry {
    st_hash_t hash;
    st_data_t key;
    st_data_t record;
};

The record member is not needed, and this is what resulted in large sets taking 1/3 more memory than they actually need.

struct st_table_entry {
    st_hash_t hash;
    st_data_t key;
    st_data_t record;
};

We can fix this issue for sets by removing this member.

struct st_table_entry {
    st_hash_t hash;
    st_data_t key;
                     
};

Obviously, we need a different struct for set table entries than we use for hash table entries, so we will change the prefix from st

struct st_table_entry {
    st_hash_t hash;
    st_data_t key;

};

to set. Now, that we have have the new data structure for set elements, we need to start using it. So we need to create a data structure for the entire set.

struct set_table_entry {
    st_hash_t hash;
    st_data_t key;

};

We will base that on the data structure used for hashes, named st_table. When copying and modifying this structure for sets, only two changes are needed.


struct st_table {
    unsigned char entry_power, bin_power, size_ind;
    unsigned int rebuilds_num;
    const struct st_hash_type *type;
    st_index_t num_entries;
    st_index_t *bins;
    st_index_t entries_start, entries_bound;
    st_table_entry *entries;
};

First, we change the name of the struct from st_table to set_table.


struct set_table {
    unsigned char entry_power, bin_power, size_ind;
    unsigned int rebuilds_num;
    const struct st_hash_type *type;
    st_index_t num_entries;
    st_index_t *bins;
    st_index_t entries_start, entries_bound;
    st_table_entry *entries;
};

Second, we change the type of the entries from st_table_entry to set_table_entry. Those are the only changes needed to convert the data structure from storing hash information to storing set information.


struct set_table {
    unsigned char entry_power, bin_power, size_ind;
    unsigned int rebuilds_num;
    const struct st_hash_type *type;
    st_index_t num_entries;
    st_index_t *bins;
    st_index_t entries_start, entries_bound;
    set_table_entry *entries;
};

The data structures are the easiest part of the change. Much of the work requires copying the functions that operate on the hash data structure, and modifying them to work on the set data structure. Now, some functions are easy.

Functions

Consider this function, named st_free_table. This is used for freeing memory after the hash table is no longer used. This also only takes two simple changes to modify for use in sets.


void
st_free_table(st_table *tab)
{
    free(tab->bins);
    free(tab->entries);
    free(tab);
}

First, we change the prefix in the function name.


void
set_free_table(st_table *tab)
{
    free(tab->bins);
    free(tab->entries);
    free(tab);
}

Next, we change the type of the argument. However, note that the body of the function does not change in this case.|There are actually a significant number of hash table functions that only take minimal changes like these to convert to set table functions.


void
set_free_table(set_table *tab)
{
    free(tab->bins);
    free(tab->entries);
    free(tab);
}

Another piece of good news is that not all hash table functions need to be copied and modified. For example, a hash table function like this does not need to be converted.


st_index_t
rb_st_values(st_table *table,
             st_data_t *values,
             st_index_t size);

That is because this function deals with the hash entry values, and set entries have no values. So the equivalent function is not needed for set tables. Unfortunately, not all hash functions are trivial to convert or can be ignored.


st_index_t
rb_st_values(st_table *table,
             st_data_t *values,
             st_index_t size);

This function is a general function used for iterating over a Ruby hash table in C. A number of other C functions call this function internally.


static inline int
st_general_foreach(st_table *tab,
                   st_foreach_check_callback_func *func,
                   st_update_callback_func *replace,
                   st_data_t arg, int check_p);

All of these types are specific to hash tables and need to be updated for set tables.


static inline int
st_general_foreach(st_table *tab,
                   st_foreach_check_callback_func *func,
                   st_update_callback_func *replace,
                   st_data_t arg, int check_p);

Changing the name of the function and the argument types is the simple part of the change.


static inline int
set_general_foreach(set_table *tab,
                    set_foreach_check_callback_func *func,
                    set_update_callback_func *replace,
                    st_data_t arg, int check_p);

Here is an example where code needs to be updated inside the body of the function to make it work correctly with sets.


hash = curr_entry_ptr->hash;
retval = (*func)(key, curr_entry_ptr->record, arg, 0);

if (retval == ST_REPLACE && replace) {
    st_data_t value;
    value = curr_entry_ptr->record;
    retval = (*replace)(&key, &value, arg, TRUE);
    curr_entry_ptr->key = key;
    curr_entry_ptr->record = value;
}

Our first problem in this code is here. This references the record member of the hash table entry, which does not exist for set table entries.


hash = curr_entry_ptr->hash;
retval = (*func)(key, curr_entry_ptr->record, arg, 0);

if (retval == ST_REPLACE && replace) {
    st_data_t value;
    value = curr_entry_ptr->record;
    retval = (*replace)(&key, &value, arg, TRUE);
    curr_entry_ptr->key = key;
    curr_entry_ptr->record = value;
}

As set entries do not have values, we do not need this argument, and we would like to eliminate it.


hash = curr_entry_ptr->hash;
retval = (*func)(key,                         arg, 0);

if (retval == ST_REPLACE && replace) {
    st_data_t value;
    value = curr_entry_ptr->record;
    retval = (*replace)(&key, &value, arg, TRUE);
    curr_entry_ptr->key = key;
    curr_entry_ptr->record = value;
}

However, eliminating this argument requires changing the definition of the function pointer type.


hash = curr_entry_ptr->hash;
retval = (*func)(key, arg, 0);

if (retval == ST_REPLACE && replace) {
    st_data_t value;
    value = curr_entry_ptr->record;
    retval = (*replace)(&key, &value, arg, TRUE);
    curr_entry_ptr->key = key;
    curr_entry_ptr->record = value;
}

If we go back to the prototype, we can see the function pointer type is set_foreach_callback_func.


static inline int
set_general_foreach(set_table *tab,
                   set_foreach_check_callback_func *func,
                   set_update_callback_func *replace,
                   st_data_t arg, int check_p);

The type definition for the equivalent function pointer for hash tables takes 4 arguments.


typedef int
st_foreach_check_callback_func(st_data_t, st_data_t,
                               st_data_t, int);

The second argument is the value of the hash table entry.


typedef int
st_foreach_check_callback_func(st_data_t, st_data_t,
                               st_data_t, int);

When converting the function pointer type for sets, in addition to changing the type name, we need to eliminate that argument as one of the function's arguments.


typedef int
set_foreach_check_callback_func(st_data_t,          
                               st_data_t, int);

If that callback function returns ST_REPLACE, that indicates the entry should be replaced with a different entry.


hash = curr_entry_ptr->hash;
retval = (*func)(key, arg, 0);

if (retval == ST_REPLACE && replace) {
    st_data_t value;
    value = curr_entry_ptr->record;
    retval = (*replace)(&key, &value, arg, TRUE);
    curr_entry_ptr->key = key;
    curr_entry_ptr->record = value;
}

In this case, the code gets the current value of the hash table entry.


hash = curr_entry_ptr->hash;
retval = (*func)(key, arg, 0);

if (retval == ST_REPLACE && replace) {
    st_data_t value;
    value = curr_entry_ptr->record;
    retval = (*replace)(&key, &value, arg, TRUE);
    curr_entry_ptr->key = key;
    curr_entry_ptr->record = value;
}

Then it calls the other callback function, which is designed to be called when the key or value of a hash entry changes.


hash = curr_entry_ptr->hash;
retval = (*func)(key, arg, 0);

if (retval == ST_REPLACE && replace) {
    st_data_t value;
    value = curr_entry_ptr->record;
    retval = (*replace)(&key, &value, arg, TRUE);
    curr_entry_ptr->key = key;
    curr_entry_ptr->record = value;
}

After that, we update the values inside the hash entry.


hash = curr_entry_ptr->hash;
retval = (*func)(key, arg, 0);

if (retval == ST_REPLACE && replace) {
    st_data_t value;
    value = curr_entry_ptr->record;
    retval = (*replace)(&key, &value, arg, TRUE);
    curr_entry_ptr->key = key;
    curr_entry_ptr->record = value;
}

When converting this code to work with set tables, all of the code that deals with hash entry values is no longer necessary,


hash = curr_entry_ptr->hash;
retval = (*func)(key, arg, 0);

if (retval == ST_REPLACE && replace) {
    st_data_t value;
    value = curr_entry_ptr->record;
    retval = (*replace)(&key, &value, arg, TRUE);
    curr_entry_ptr->key = key;
    curr_entry_ptr->record = value;
}

and we can just delete it. Pretty much all of the conversions of hash table functions to set table functions followed one of the patterns shown earlier. Rename the function, update the data types from hash table types to set table types, and remove any code related to hash entry values.


hash = curr_entry_ptr->hash;
retval = (*func)(key, arg, 0);

if (retval == ST_REPLACE && replace) {
                    
                                      
    retval = (*replace)(&key,             arg, TRUE);
    curr_entry_ptr->key = key;
                                      
}

Copying and modifying the hash table data structures and functions accounts for about a third of the changes need for core set.

⅓

So what about the other 2/3?

⅔

Well, the other 2/3 was spent reimplementing Set methods, so that instead of storing data in a hash, it directly accessed a set_table, similar to how hash works.

Implementing

Set Methods

There were two basic approaches I considered for converting the standard library set methods into core set methods.

2 Approaches

One approach is keeping the existing Ruby implementation, but changing methods that access the hash instance variable to instead call an internal function that accesses the set_table using Primitive.|This is generally a better approach for methods with keyword arguments and methods that use rescue or ensure, as Ruby can use optimizations in these cases that are not available in C functions.|It can also result in more optimized calls to other Ruby methods, by using inline method call caches.

Ruby with

Primitive

The alternative approach is to write the methods in C using Ruby's C-API. To avoid the performance issues with methods calling other methods, methods written in C generally call the underlying C functions directly instead of calling methods. This is how most methods for array and hash are implemented.|I chose this approach when implementing core Set, as I expected it would result in the best performance and make it easier to avoid thread safety problems.

C-API

Methods

If you remember back to the add predicate method I discussed earlier, the one with the thread safety issues, let me go over how this is implemented in C.

  def add?(o)
    add(o) unless include?(o)
  end

Here is what that implementation of that method looks like in C. It is significantly more complex than the Ruby version, but I will walk through most of it.

static VALUE
set_i_add_p(VALUE set, VALUE item)
{
    rb_check_frozen(set);
    if (set_iterating_p(set)) {
        if (!set_table_lookup(RSET_TABLE(set), (st_data_t)item)) {
            no_new_item();
        }
        return Qnil;
    }
    else {
        return set_insert_wb(set, item, NULL) ? Qnil : set;
    }
}

The first thing the function does is check whether the set is frozen. This check did not exist in the Ruby implementation, because it would ultimately be handled when the trying to update the underlying hash, which would be frozen for a frozen set.|There is actually a behavior difference here. The add predicate method in core set will always raise a FrozenError if the set is frozen, while in standard library set, the add predicate method only raises a FrozenError if you call it with an element not already in the set.

static VALUE
set_i_add_p(VALUE set, VALUE item)
{
    rb_check_frozen(set);
    if (set_iterating_p(set)) {
        if (!set_table_lookup(RSET_TABLE(set), (st_data_t)item)) {
            no_new_item();
        }
        return Qnil;
    }
    else {
        return set_insert_wb(set, item, NULL) ? Qnil : set;
    }
}

We then call the set_iterating_p function, which determines whether this set is currently being iterated over. If the set is currently being iterated over, you cannot safely add an element to it. Many of Ruby's hash methods have a similar check.

static VALUE
set_i_add_p(VALUE set, VALUE item)
{
    rb_check_frozen(set);
    if (set_iterating_p(set)) {
        if (!set_table_lookup(RSET_TABLE(set), (st_data_t)item)) {
            no_new_item();
        }
        return Qnil;
    }
    else {
        return set_insert_wb(set, item, NULL) ? Qnil : set;
    }
}

If we are currently iterating over the set, we can still lookup elements in it, just not insert elements. This looks up the element in the set.

static VALUE
set_i_add_p(VALUE set, VALUE item)
{
    rb_check_frozen(set);
    if (set_iterating_p(set)) {
        if (!set_table_lookup(RSET_TABLE(set), (st_data_t)item)) {
            no_new_item();
        }
        return Qnil;
    }
    else {
        return set_insert_wb(set, item, NULL) ? Qnil : set;
    }
}

If the element is already in the set, it returns Qnil, which is how nil is represented in Ruby's C-API.

static VALUE
set_i_add_p(VALUE set, VALUE item)
{
    rb_check_frozen(set);
    if (set_iterating_p(set)) {
        if (!set_table_lookup(RSET_TABLE(set), (st_data_t)item)) {
            no_new_item();
        }
        return Qnil;
    }
    else {
        return set_insert_wb(set, item, NULL) ? Qnil : set;
    }
}

However, if the element is not already in the set, it cannot be safely added. So the method calls the no_new_item function, which raises a RuntimeError.

static VALUE
set_i_add_p(VALUE set, VALUE item)
{
    rb_check_frozen(set);
    if (set_iterating_p(set)) {
        if (!set_table_lookup(RSET_TABLE(set), (st_data_t)item)) {
            no_new_item();
        }
        return Qnil;
    }
    else {
        return set_insert_wb(set, item, NULL) ? Qnil : set;
    }
}

If the set is not being iterated over, which will be the typical case when calling the add predicate method, it calls the set_insert_wb function.|This will insert the element into the set, and return 1 if the element was already in the set, or 0 if the element was not in the set.

static VALUE
set_i_add_p(VALUE set, VALUE item)
{
    rb_check_frozen(set);
    if (set_iterating_p(set)) {
        if (!set_table_lookup(RSET_TABLE(set), (st_data_t)item)) {
            no_new_item();
        }
        return Qnil;
    }
    else {
        return set_insert_wb(set, item, NULL) ? Qnil : set;
    }
}

If the element was already in the set, the method returns nil.

static VALUE
set_i_add_p(VALUE set, VALUE item)
{
    rb_check_frozen(set);
    if (set_iterating_p(set)) {
        if (!set_table_lookup(RSET_TABLE(set), (st_data_t)item)) {
            no_new_item();
        }
        return Qnil;
    }
    else {
        return set_insert_wb(set, item, NULL) ? Qnil : set;
    }
}

If the element was not already in the set, the method returns the set.

static VALUE
set_i_add_p(VALUE set, VALUE item)
{
    rb_check_frozen(set);
    if (set_iterating_p(set)) {
        if (!set_table_lookup(RSET_TABLE(set), (st_data_t)item)) {
            no_new_item();
        }
        return Qnil;
    }
    else {
        return set_insert_wb(set, item, NULL) ? Qnil : set;
    }
}

Now that I've gone over the implementation, I'd like to point out the two significant advantages of this code compared to the previous Ruby code.

static VALUE
set_i_add_p(VALUE set, VALUE item)
{
    rb_check_frozen(set);
    if (set_iterating_p(set)) {
        if (!set_table_lookup(RSET_TABLE(set), (st_data_t)item)) {
            no_new_item();
        }
        return Qnil;
    }
    else {
        return set_insert_wb(set, item, NULL) ? Qnil : set;
    }
}

The first is that the thread safety issue has been fixed. Instead of a 2 accesses to the underlying hash table, where a separate thread could change the underlying table between the two calls, there is a single access to the underlying set table in this function call.|Because this function is written in C, and does not release the global VM lock, the only thread that could be operating on the set during the execution of this function is the current thread.|This also fixes the performance issue. Instead of 2 hash table accesses, there is only a single set table access, so the method is significantly faster in addition to being more thread safe.

static VALUE
set_i_add_p(VALUE set, VALUE item)
{
    rb_check_frozen(set);
    if (set_iterating_p(set)) {
        if (!set_table_lookup(RSET_TABLE(set), (st_data_t)item)) {
            no_new_item();
        }
        return Qnil;
    }
    else {
        return set_insert_wb(set, item, NULL) ? Qnil : set;
    }
}

Now that you've seen how the add predicate method is defined, let me go over how sets are initialized in C.|Here is the function that implements Set.allocate. As you can see, it is fairly simple.

static VALUE
set_s_alloc(VALUE klass)
{
    return set_alloc_with_size(klass, 0);
}

It calls a set_alloc_with_size function, passing the underlying class, which may be Set or a subclass of Set.

static VALUE
set_s_alloc(VALUE klass)
{
    return set_alloc_with_size(klass, 0);
}

The second argument specifies the initial capacity for the set. Since Set.allocate does not provide any hint as to the desired size of the set, we call the function with 0, creating the smallest possible set.|Other code that needs to allocate a new set may know the expected size of the set up front, and can specify a larger number.

static VALUE
set_s_alloc(VALUE klass)
{
    return set_alloc_with_size(klass, 0);
}

Here is the implementation of the set_alloc_with_size function. There are a few interesting parts here, so I will walk through this.

static VALUE
set_alloc_with_size(VALUE klass, st_index_t size)
{
    VALUE set;
    struct set_object *sobj;

    set = TypedData_Make_Struct(klass, struct set_object,
                                &set_data_type, sobj);
    set_init_table_with_size(&sobj->table, &objhash, size);

    return set;
}

First is this line, which defines a local variable for the underlying C structure containing the data for the set.

static VALUE
set_alloc_with_size(VALUE klass, st_index_t size)
{
    VALUE set;
    struct set_object *sobj;

    set = TypedData_Make_Struct(klass, struct set_object,
                                &set_data_type, sobj);
    set_init_table_with_size(&sobj->table, &objhash, size);

    return set;
}

In this case, the C structure only wraps the underlying set table and no other data. We might be able to use the set_table directly, but this makes it easier to add data for Ruby set objects without affecting the underlying set_table implementation, which may be used for things other than Ruby objects.


struct set_object {
    set_table table;
};

The next interesting thing is this call to TypedData_Make_Struct. This is a C function that creates a new Ruby instance of

static VALUE
set_alloc_with_size(VALUE klass, st_index_t size)
{
    VALUE set;
    struct set_object *sobj;

    set = TypedData_Make_Struct(klass, struct set_object,
                                &set_data_type, sobj);
    set_init_table_with_size(&sobj->table, &objhash, size);

    return set;
}

a given class,

static VALUE
set_alloc_with_size(VALUE klass, st_index_t size)
{
    VALUE set;
    struct set_object *sobj;

    set = TypedData_Make_Struct(klass, struct set_object,
                                &set_data_type, sobj);
    set_init_table_with_size(&sobj->table, &objhash, size);

    return set;
}

which stores the information for the instance using the given C type.

static VALUE
set_alloc_with_size(VALUE klass, st_index_t size)
{
    VALUE set;
    struct set_object *sobj;

    set = TypedData_Make_Struct(klass, struct set_object,
                                &set_data_type, sobj);
    set_init_table_with_size(&sobj->table, &objhash, size);

    return set;
}

The third argument here provides information about the type.

static VALUE
set_alloc_with_size(VALUE klass, st_index_t size)
{
    VALUE set;
    struct set_object *sobj;

    set = TypedData_Make_Struct(klass, struct set_object,
                                &set_data_type, sobj);
    set_init_table_with_size(&sobj->table, &objhash, size);

    return set;
}

Here is what that information looks like.

static const rb_data_type_t set_data_type = {
    .wrap_struct_name = "set",
    .function = {
        .dmark = set_mark,
        .dfree = set_free,
        .dsize = set_size,
        .dcompact = set_update_references,
    },
    .flags = RUBY_TYPED_EMBEDDABLE |
             RUBY_TYPED_FREE_IMMEDIATELY |
             RUBY_TYPED_WB_PROTECTED |
             RUBY_TYPED_FROZEN_SHAREABLE
};

This sets an internal name for the wrapped struct.

static const rb_data_type_t set_data_type = {
    .wrap_struct_name = "set",
    .function = {
        .dmark = set_mark,
        .dfree = set_free,
        .dsize = set_size,
        .dcompact = set_update_references,
    },
    .flags = RUBY_TYPED_EMBEDDABLE |
             RUBY_TYPED_FREE_IMMEDIATELY |
             RUBY_TYPED_WB_PROTECTED |
             RUBY_TYPED_FROZEN_SHAREABLE
};

These are callback functions related to the struct, mostly related to integration with the garbage collector.|This lets the garbage collector know which elements this set is referencing, so it does not free the elements while the set still contains them.

static const rb_data_type_t set_data_type = {
    .wrap_struct_name = "set",
    .function = {
        .dmark = set_mark,
        .dfree = set_free,
        .dsize = set_size,
        .dcompact = set_update_references,
    },
    .flags = RUBY_TYPED_EMBEDDABLE |
             RUBY_TYPED_FREE_IMMEDIATELY |
             RUBY_TYPED_WB_PROTECTED |
             RUBY_TYPED_FROZEN_SHAREABLE
};

These are flags related to the data type, which changes how Ruby will interact with it.

static const rb_data_type_t set_data_type = {
    .wrap_struct_name = "set",
    .function = {
        .dmark = set_mark,
        .dfree = set_free,
        .dsize = set_size,
        .dcompact = set_update_references,
    },
    .flags = RUBY_TYPED_EMBEDDABLE |
             RUBY_TYPED_FREE_IMMEDIATELY |
             RUBY_TYPED_WB_PROTECTED |
             RUBY_TYPED_FROZEN_SHAREABLE
};

For example, the frozen shareable flag allows frozen instances to be shared between ractors. I will discuss a couple of these other flags later.

static const rb_data_type_t set_data_type = {
    .wrap_struct_name = "set",
    .function = {
        .dmark = set_mark,
        .dfree = set_free,
        .dsize = set_size,
        .dcompact = set_update_references,
    },
    .flags = RUBY_TYPED_EMBEDDABLE |
             RUBY_TYPED_FREE_IMMEDIATELY |
             RUBY_TYPED_WB_PROTECTED |
             RUBY_TYPED_FROZEN_SHAREABLE
};

Going back to set_alloc_with_size, the fourth argument is the local variable pointer that should be updated to point to the C structure for the created object.

static VALUE
set_alloc_with_size(VALUE klass, st_index_t size)
{
    VALUE set;
    struct set_object *sobj;

    set = TypedData_Make_Struct(klass, struct set_object,
                                &set_data_type, sobj);
    set_init_table_with_size(&sobj->table, &objhash, size);

    return set;
}

The TypedData_Make_Struct function returns the allocated set. At this point, memory for the set has been allocated, but the set is not usable.

static VALUE
set_alloc_with_size(VALUE klass, st_index_t size)
{
    VALUE set;
    struct set_object *sobj;

    set = TypedData_Make_Struct(klass, struct set_object,
                                &set_data_type, sobj);
    set_init_table_with_size(&sobj->table, &objhash, size);

    return set;
}

In order for the set to be usable, it must be initialized using the set_init_table_with_size function.

static VALUE
set_alloc_with_size(VALUE klass, st_index_t size)
{
    VALUE set;
    struct set_object *sobj;

    set = TypedData_Make_Struct(klass, struct set_object,
                                &set_data_type, sobj);
    set_init_table_with_size(&sobj->table, &objhash, size);

    return set;
}

This function is passed the memory location at which the table should be initialized.

static VALUE
set_alloc_with_size(VALUE klass, st_index_t size)
{
    VALUE set;
    struct set_object *sobj;

    set = TypedData_Make_Struct(klass, struct set_object,
                                &set_data_type, sobj);
    set_init_table_with_size(&sobj->table, &objhash, size);

    return set;
}

As well as the comparison and hash functions that should be used for the set elements. Set elements use the same comparison and hash functions that are used for hash keys.

static VALUE
set_alloc_with_size(VALUE klass, st_index_t size)
{
    VALUE set;
    struct set_object *sobj;

    set = TypedData_Make_Struct(klass, struct set_object,
                                &set_data_type, sobj);
    set_init_table_with_size(&sobj->table, &objhash, size);

    return set;
}

This passes through the size argument, so the table will be initialized with the correct size.

static VALUE
set_alloc_with_size(VALUE klass, st_index_t size)
{
    VALUE set;
    struct set_object *sobj;

    set = TypedData_Make_Struct(klass, struct set_object,
                                &set_data_type, sobj);
    set_init_table_with_size(&sobj->table, &objhash, size);

    return set;
}

After this, the set instance is fully usable, so it is returned.

static VALUE
set_alloc_with_size(VALUE klass, st_index_t size)
{
    VALUE set;
    struct set_object *sobj;

    set = TypedData_Make_Struct(klass, struct set_object,
                                &set_data_type, sobj);
    set_init_table_with_size(&sobj->table, &objhash, size);

    return set;
}

I'd like to take a few steps back to the table initialization. I mentioned that this first argument specifies the memory location at which to initialize the table.|This is a bit unusual, as many methods that initialize new objects in C would not request the memory for the object be initialized at a specific location.|Instead, they would expect the function to allocate new memory, initialize the newly allocated memory, and return a pointer to that memory. So why do we use a different approach here?

static VALUE
set_alloc_with_size(VALUE klass, st_index_t size)
{
    VALUE set;
    struct set_object *sobj;

    set = TypedData_Make_Struct(klass, struct set_object,
                                &set_data_type, sobj);
    set_init_table_with_size(&sobj->table, &objhash, size);

    return set;
}

This comes back to one of the type flags that we are using,

static const rb_data_type_t set_data_type = {
    .wrap_struct_name = "set",
    .function = {
        .dmark = set_mark,
        .dfree = set_free,
        .dsize = set_size,
        .dcompact = set_update_references,
    },
    .flags = RUBY_TYPED_EMBEDDABLE |
             RUBY_TYPED_FREE_IMMEDIATELY |
             RUBY_TYPED_WB_PROTECTED |
             RUBY_TYPED_FROZEN_SHAREABLE
};

specifically, the embeddable type flag. This type flag allows for an optimization.|Instead of the Ruby object and the data related to the Ruby object being stored at two different places in memory, embeddable types allow for storing the data for the Ruby object in the same slot in memory as the Ruby object.

static const rb_data_type_t set_data_type = {
    .wrap_struct_name = "set",
    .function = {
        .dmark = set_mark,
        .dfree = set_free,
        .dsize = set_size,
        .dcompact = set_update_references,
    },
    .flags = RUBY_TYPED_EMBEDDABLE |
             RUBY_TYPED_FREE_IMMEDIATELY |
             RUBY_TYPED_WB_PROTECTED |
             RUBY_TYPED_FROZEN_SHAREABLE
};

This builds on a feature named variable width allocation, which allows for different sized objects.|Historically, there would not be a way to embed sets inside Ruby objects, because the set table metadata would be too large. With variable width allocation, the object can be large enough to embed the set table metadata.|Embedding provides an performance advantage as it improves cache-locality, which speeds up access to the memory.

Variable

Width

Allocation

When I say the metadata is embedded, what am I talking about?

Metadata

Embedded?

Well, if we remember back to the set_table structure, it includes all of this information.


struct set_table {
    unsigned char entry_power, bin_power, size_ind;
    unsigned int rebuilds_num;
    const struct st_hash_type *type;
    st_index_t num_entries;
    st_index_t *bins;
    st_index_t entries_start, entries_bound;
    set_table_entry *entries;
};

Note that these three members are pointers. While the pointers themselves are embedded, the memory they point to is not embedded.


struct set_table {
    unsigned char entry_power, bin_power, size_ind;
    unsigned int rebuilds_num;
    const struct st_hash_type *type;
    st_index_t num_entries;
    st_index_t *bins;
    st_index_t entries_start, entries_bound;
    set_table_entry *entries;
};

The hash type pointer is static, and it points to the static data given when you created the instance.


struct set_table {
    unsigned char entry_power, bin_power, size_ind;
    unsigned int rebuilds_num;
    const struct st_hash_type *type;
    st_index_t num_entries;
    st_index_t *bins;
    st_index_t entries_start, entries_bound;
    set_table_entry *entries;
};

However, these pointers point to dynamically allocated memory on the C heap. If the set table is resized due to elements being added to the set, these pointers can change to point to new memory locations.


struct set_table {
    unsigned char entry_power, bin_power, size_ind;
    unsigned int rebuilds_num;
    const struct st_hash_type *type;
    st_index_t num_entries;
    st_index_t *bins;
    st_index_t entries_start, entries_bound;
    set_table_entry *entries;
};

Another Ruby feature that the core set implementation supports natively is incremental and generational garbage collection.|In order for garbage collection to work optimally, you need to track when objects are modified to reference other objects. In addition to improving garbage collection,

Incremental &

Generational

Garbage

Collection

this tracking is also necessary for the objects to support garbage compaction.|While Ruby objects backed by C structures are not required to support these garbage collection features, doing so can significantly improve garbage collection performance.

Garbage

Compaction

Let us again go back to the type flags that we are using.

static const rb_data_type_t set_data_type = {
    .wrap_struct_name = "set",
    .function = {
        .dmark = set_mark,
        .dfree = set_free,
        .dsize = set_size,
        .dcompact = set_update_references,
    },
    .flags = RUBY_TYPED_EMBEDDABLE |
             RUBY_TYPED_FREE_IMMEDIATELY |
             RUBY_TYPED_WB_PROTECTED |
             RUBY_TYPED_FROZEN_SHAREABLE
};

This time, we will be looking at the WB protected flag. The WB here stands for write barrier.|Using a write barrier, when one Ruby object is modified to reference another object, Ruby can inform the garbage collector about it, so that the garbage collector will not free the object while it is still actively used.|Using this flag results in a significant amount of risk, because it means that all use of this type correctly uses write barriers.|If you include this flag, and miss adding a write barrier where it should be added, Ruby can crash with a hard to debug error.

static const rb_data_type_t set_data_type = {
    .wrap_struct_name = "set",
    .function = {
        .dmark = set_mark,
        .dfree = set_free,
        .dsize = set_size,
        .dcompact = set_update_references,
    },
    .flags = RUBY_TYPED_EMBEDDABLE |
             RUBY_TYPED_FREE_IMMEDIATELY |
             RUBY_TYPED_WB_PROTECTED |
             RUBY_TYPED_FROZEN_SHAREABLE
};

If we go back to the core Set implementation of the add predicate method.

static VALUE
set_i_add_p(VALUE set, VALUE item)
{
    rb_check_frozen(set);
    if (set_iterating_p(set)) {
        if (!set_table_lookup(RSET_TABLE(set), (st_data_t)item)) {
            no_new_item();
        }
        return Qnil;
    }
    else {
        return set_insert_wb(set, item, NULL) ? Qnil : set;
    }
}

Notice that the set_insert_wb function was called. As you can probably guess, this function, in addition to inserting the element into the set, also ensures that a write barrier is used.

static VALUE
set_i_add_p(VALUE set, VALUE item)
{
    rb_check_frozen(set);
    if (set_iterating_p(set)) {
        if (!set_table_lookup(RSET_TABLE(set), (st_data_t)item)) {
            no_new_item();
        }
        return Qnil;
    }
    else {
        return set_insert_wb(set, item, NULL) ? Qnil : set;
    }
}

Here is the definition of the set_insert_wb function. As you can see, it is pretty simple.

static int
set_insert_wb(VALUE set, VALUE key, VALUE *key_addr)
{
    return set_table_insert_wb(RSET_TABLE(set), set,
                               key, key_addr);
}

We call another function named set_table_insert_wb,

static int
set_insert_wb(VALUE set, VALUE key, VALUE *key_addr)
{
    return set_table_insert_wb(RSET_TABLE(set), set,
                               key, key_addr);
}

Passing the set_table for the set object as the first argument.

static int
set_insert_wb(VALUE set, VALUE key, VALUE *key_addr)
{
    return set_table_insert_wb(RSET_TABLE(set), set,
                               key, key_addr);
}

Here is the definition of the set_table_insert_wb function, which is significantly more complex. There are a few things I want to point out here.

static int
set_table_insert_wb(set_table *tab, VALUE set,
                    VALUE key, VALUE *key_addr)
{
    if (tab->type != &identhash &&
            rb_obj_class(key) == rb_cString &&
            !RB_OBJ_FROZEN(key)) {
        key = rb_hash_key_str(key);
        if (key_addr) *key_addr = key;
    }
    int ret = set_insert(tab, (st_data_t)key);
    if (ret == 0) RB_OBJ_WRITTEN(set, Qundef, key);
    return ret;
}

First is this call, which inserts the element into the set table. Again, the element may already exist in the table. If it does, ret will be 1. If it does not already exist, ret will be 0.

static int
set_table_insert_wb(set_table *tab, VALUE set,
                    VALUE key, VALUE *key_addr)
{
    if (tab->type != &identhash &&
            rb_obj_class(key) == rb_cString &&
            !RB_OBJ_FROZEN(key)) {
        key = rb_hash_key_str(key);
        if (key_addr) *key_addr = key;
    }
    int ret = set_insert(tab, (st_data_t)key);
    if (ret == 0) RB_OBJ_WRITTEN(set, Qundef, key);
    return ret;
}

If ret is 0, that means the element was added to the set, and the set now has a reference to the element.|As we are using the WB protected flag, we must tell the Ruby runtime that the set now references the element, which we do by calling RB_OBJ_WRITTEN.|This is actually the only usage of RB_OBJ_WRITTEN in the set implementation, because all set methods that add an element to a set call into this function.|I thought this was a good design, because it means Set is unlikely to miss write barriers.

static int
set_table_insert_wb(set_table *tab, VALUE set,
                    VALUE key, VALUE *key_addr)
{
    if (tab->type != &identhash &&
            rb_obj_class(key) == rb_cString &&
            !RB_OBJ_FROZEN(key)) {
        key = rb_hash_key_str(key);
        if (key_addr) *key_addr = key;
    }
    int ret = set_insert(tab, (st_data_t)key);
    if (ret == 0) RB_OBJ_WRITTEN(set, Qundef, key);
    return ret;
}

Unfortunately, there was another place where a write barrier was needed, which was found and fixed by John Hawthorn.

@jhawthorn

This place was inside set_i_initialize_copy, used to implement the dup, clone, collect bang, and replace instance methods.

static VALUE
set_i_initialize_copy(VALUE set, VALUE other)
{
    if (set == other) return set;

    if (set_iterating_p(set)) {
        rb_raise(rb_eRuntimeError, "cannot replace set during iteration");
    }

    struct set_object *sobj;
    TypedData_Get_Struct(set, struct set_object, &set_data_type, sobj);

    set_free_embedded_table(&sobj->table);
    set_copy(&sobj->table, RSET_TABLE(other));
    

    return set;
}

This function used the set_copy function to populate the current set with all elements in an existing set.|After this function call, the current set potentially references objects that it didn't previously reference.|As we did not inform the garbage collector about this and we are using the WB protected flag, this resulted in nondeterministic crashes.

static VALUE
set_i_initialize_copy(VALUE set, VALUE other)
{
    if (set == other) return set;

    if (set_iterating_p(set)) {
        rb_raise(rb_eRuntimeError, "cannot replace set during iteration");
    }

    struct set_object *sobj;
    TypedData_Get_Struct(set, struct set_object, &set_data_type, sobj);

    set_free_embedded_table(&sobj->table);
    set_copy(&sobj->table, RSET_TABLE(other));


    return set;
}

The fix in this case is to call the rb_gc_writebarrier_remember function. This function tells the garbage collector to rescan the entire object to see what elements it references.|Thankfully, after this fix, there have been no other write barrier issues found since core Set was merged.

static VALUE
set_i_initialize_copy(VALUE set, VALUE other)
{
    if (set == other) return set;

    if (set_iterating_p(set)) {
        rb_raise(rb_eRuntimeError, "cannot replace set during iteration");
    }

    struct set_object *sobj;
    TypedData_Get_Struct(set, struct set_object, &set_data_type, sobj);

    set_free_embedded_table(&sobj->table);
    set_copy(&sobj->table, RSET_TABLE(other));
    rb_gc_writebarrier_remember(set);

    return set;
}

What about this code? This is not related to write barriers, but I think it is still an interesting part of the implementation.|In order to keep backwards compatibility with the standard library set, which used a hash for storage, the core set implementation does the same thing that hash does if you use an unfrozen string as a hash key, it makes a frozen copy of the string.

static int
set_table_insert_wb(set_table *tab, VALUE set,
                    VALUE key, VALUE *key_addr)
{
    if (tab->type != &identhash &&
            rb_obj_class(key) == rb_cString &&
            !RB_OBJ_FROZEN(key)) {
        key = rb_hash_key_str(key);
        if (key_addr) *key_addr = key;
    }
    int ret = set_insert(tab, (st_data_t)key);
    if (ret == 0) RB_OBJ_WRITTEN(set, Qundef, key);
    return ret;
}

This is not done for sets that use compare_by_identity, just as hashes that use compare_by_identity do not make copies of strings.

static int
set_table_insert_wb(set_table *tab, VALUE set,
                    VALUE key, VALUE *key_addr)
{
    if (tab->type != &identhash &&
            rb_obj_class(key) == rb_cString &&
            !RB_OBJ_FROZEN(key)) {
        key = rb_hash_key_str(key);
        if (key_addr) *key_addr = key;
    }
    int ret = set_insert(tab, (st_data_t)key);
    if (ret == 0) RB_OBJ_WRITTEN(set, Qundef, key);
    return ret;
}

It is only done for instances of the String class, not for string subclasses.

static int
set_table_insert_wb(set_table *tab, VALUE set,
                    VALUE key, VALUE *key_addr)
{
    if (tab->type != &identhash &&
            rb_obj_class(key) == rb_cString &&
            !RB_OBJ_FROZEN(key)) {
        key = rb_hash_key_str(key);
        if (key_addr) *key_addr = key;
    }
    int ret = set_insert(tab, (st_data_t)key);
    if (ret == 0) RB_OBJ_WRITTEN(set, Qundef, key);
    return ret;
}

It is only done if the string is not frozen.

static int
set_table_insert_wb(set_table *tab, VALUE set,
                    VALUE key, VALUE *key_addr)
{
    if (tab->type != &identhash &&
            rb_obj_class(key) == rb_cString &&
            !RB_OBJ_FROZEN(key)) {
        key = rb_hash_key_str(key);
        if (key_addr) *key_addr = key;
    }
    int ret = set_insert(tab, (st_data_t)key);
    if (ret == 0) RB_OBJ_WRITTEN(set, Qundef, key);
    return ret;
}

If those three things are true, the core set code calls the same function that hash uses to make a frozen copy of the string.

static int
set_table_insert_wb(set_table *tab, VALUE set,
                    VALUE key, VALUE *key_addr)
{
    if (tab->type != &identhash &&
            rb_obj_class(key) == rb_cString &&
            !RB_OBJ_FROZEN(key)) {
        key = rb_hash_key_str(key);
        if (key_addr) *key_addr = key;
    }
    int ret = set_insert(tab, (st_data_t)key);
    if (ret == 0) RB_OBJ_WRITTEN(set, Qundef, key);
    return ret;
}

This code is used so that if a non-frozen string was passed, the memory location of the passed non-frozen string can be updated to point to the frozen string.|However, when trying to come up with an example of a situation where this was actually needed, I could not find one. All callers that passed a key_addr argument did not seem to actually need to do so.

static int
set_table_insert_wb(set_table *tab, VALUE set,
                    VALUE key, VALUE *key_addr)
{
    if (tab->type != &identhash &&
            rb_obj_class(key) == rb_cString &&
            !RB_OBJ_FROZEN(key)) {
        key = rb_hash_key_str(key);
        if (key_addr) *key_addr = key;
    }
    int ret = set_insert(tab, (st_data_t)key);
    if (ret == 0) RB_OBJ_WRITTEN(set, Qundef, key);
    return ret;
}

So I was able to take this code.

static int
set_table_insert_wb(set_table *tab, VALUE set,
                    VALUE key, VALUE *key_addr)
{
    if (tab->type != &identhash &&
            rb_obj_class(key) == rb_cString &&
            !RB_OBJ_FROZEN(key)) {
        key = rb_hash_key_str(key);
        if (key_addr) *key_addr = key;
    }
    int ret = set_insert(tab, (st_data_t)key);
    if (ret == 0) RB_OBJ_WRITTEN(set, Qundef, key);
    return ret;
}

and delete it. I then fixed all callers not to pass the argument. This change will be included in Ruby 4.1.

static int
set_table_insert_wb(set_table *tab, VALUE set,
                    VALUE key                     )
{
    if (tab->type != &identhash &&
            rb_obj_class(key) == rb_cString &&
            !RB_OBJ_FROZEN(key)) {
        key = rb_hash_key_str(key);
                                          
    }
    int ret = set_insert(tab, (st_data_t)key);
    if (ret == 0) RB_OBJ_WRITTEN(set, Qundef, key);
    return ret;
}

One thing I was happy to see after introducing core Set was the use of set_table as a replacement for st_table to save on memory.

Internal Use of

set_table

Jean Boussier found a couple places where Ruby was previously using an st_table with all true values, which could easily be replaced with a set_table.

@byroot

One of these places was constant caches, used to speed up constant lookup.

Constant

Caches

Another place was storing locations of unused block warnings, which ensure we do not warn the same location twice.

Unused

Block

Warnings

After the core set implementation was merged, there were relatively few reported problems, which were generally fixed quickly.

Set

However, one issue that remained until shortly before release was how to handle Set subclasses.

Set

Subclasses

Obviously, if the set subclasses tried to access the hash instance variable, that was no longer going to work.

@hash

However, one user who tried out the core set implementation found it broke their subclass, even though their subclass did not access the hash instance variable. The user provided this code.

class MySet < Set
  def initialize(enum = nil)
    compare_by_identity
    super
  end
end

MySet.new.compare_by_identity?
# => true
MySet[].compare_by_identity?
# => false

Here, the user creates a subclass of set,

class MySet < Set
  def initialize(enum = nil)
    compare_by_identity
    super
  end
end

MySet.new.compare_by_identity?
# => true
MySet[].compare_by_identity?
# => false

and overrides the initialize method,

class MySet < Set
  def initialize(enum = nil)
    compare_by_identity
    super
  end
end

MySet.new.compare_by_identity?
# => true
MySet[].compare_by_identity?
# => false

to call compare_by_identity. The user's expectation is that all instances of this set subclass will compare by identity.

class MySet < Set
  def initialize(enum = nil)
    compare_by_identity
    super
  end
end

MySet.new.compare_by_identity?
# => true
MySet[].compare_by_identity?
# => false

They find that with core Set, this works if the class new method is called.

class MySet < Set
  def initialize(enum = nil)
    compare_by_identity
    super
  end
end

MySet.new.compare_by_identity?
# => true
MySet[].compare_by_identity?
# => false

But it does not work if the class aref method is called. This is because core Set was deliberately implemented similarly to Array and Hash.|Just as the Array and Hash class aref methods do not call initialize, the core Set class aref method does not call initialize.|Personally, I believe that expecting the class aref method to call initialize was relying on implementation details.|However, there was significant enough reliance on the implementation details of standard library Set in subclasses, by this user and a number of other users, that something had to be done to keep backwards compatibility.

class MySet < Set
  def initialize(enum = nil)
    compare_by_identity
    super
  end
end

MySet.new.compare_by_identity?
# => true
MySet[].compare_by_identity?
# => false

To handle backwards compatibility, I added a module named Set::SubclassCompatible.

Set::SubclassCompatible

Here is an example of how the SubclassCompatible module works.

class Set
  module SubclassCompatible
    module ClassMethods
      def [](*ary)
        new(ary)
      end
    end
  end
end

It redefines the class aref method,

class Set
  module SubclassCompatible
    module ClassMethods
      def [](*ary)
        new(ary)
      end
    end
  end
end

so that the method calls new. This is a copy of the class aref method in standard library Set.|In addition to being used for the class aref method, the same approach was used for majority of Set's instance methods.

class Set
  module SubclassCompatible
    module ClassMethods
      def [](*ary)
        new(ary)
      end
    end
  end
end

To ensure Set subclasses automatically use this backwards compatibility layer, we use C code that is equivalent to this Ruby code.



def Set.inherited(subclass)
  if self == Set
    subclass.include SubclassCompatible
    subclass.extend SubclassCompatible::ClassMethods
  end
end

We override Set.inherited, which is called every time that Set is subclassed with the subclass.



def Set.inherited(subclass)
  if self == Set
    subclass.include SubclassCompatible
    subclass.extend SubclassCompatible::ClassMethods
  end
end

We only make changes if this is a direct subclass of Set. The changes are not needed for subclasses of subclasses of Set, due to how method lookup works.



def Set.inherited(subclass)
  if self == Set
    subclass.include SubclassCompatible
    subclass.extend SubclassCompatible::ClassMethods
  end
end

We include the SubclassCompatible module into the subclass, so the instance methods in that module override the instance methods inherited from Set.



def Set.inherited(subclass)
  if self == Set
    subclass.include SubclassCompatible
    subclass.extend SubclassCompatible::ClassMethods
  end
end

We also extend the subclass with the ClassMethods module, so the class aref method works as expected for subclasses.|This fixed pretty much all backwards compatibility issues with Set subclasses, though it did result in less optimized code as well as the same thread safety issues that standard library set had.|For Set subclasses that do not need the backwards compatibility layer,



def Set.inherited(subclass)
  if self == Set
    subclass.include SubclassCompatible
    subclass.extend SubclassCompatible::ClassMethods
  end
end

before setting the inherited hook, we create a subclass of Set named CoreSet.|Since we do this before defining the inherited method, CoreSet does not have the backwards compatibility layer applied to it.|This allows subclasses that do not need the backwards compatibility layer to inherit from CoreSet.

Set::CoreSet = Class.new(Set)

def Set.inherited(subclass)
  if self == Set
    subclass.include SubclassCompatible
    subclass.extend SubclassCompatible::ClassMethods
  end
end

Earlier, I explained how the core Set implementation results in a 33% memory savings for large sets.

Large

Sets

However, what about memory usage for small sets? Ideally, we want to improve that as well.

Small

Sets

We should first discuss memory usage for the standard library Set implementation.

stdlib

Set

With the standard library, every Set instance allocates 2 objects.

2 Objects

There would be one T_OBJECT object for the set itself, which takes 40 bytes.

T_OBJECT:

40 bytes

There would be a T_HASH object for the internal hash, which takes 160 bytes. So a total of 200 bytes.

T_OBJECT:

40 bytes

T_HASH:

160 bytes

When I first implemented core Set, unfortunately, the results were worse

Core

Set

The set table structure was 56 bytes.

set_table:

56 bytes

Wrapping the set table structure in a Ruby object added 32 bytes. That is a total of 88 bytes for the embedded object. However, that is over the limit for an 80 byte object slot, which means

set_table:

56 bytes

wrapping:

32 bytes

that set objects require a 160 byte object slot. This does not sound so bad, right, as 160 bytes is still less than the 200 for standary library set.

T_DATA:

160 bytes

However, this is only the size of the Ruby object slot. As I mentioned earlier, this only holds the metadata for the set. The actual data is stored elsewhere in memory.

T_DATA:

embedded:

160 bytes

For sets with fewer than 5 elements, including empty sets, the actual data takes 64 bytes. So combined, core sets would use 224 bytes of memory, or 12% more memory than standard library sets.

T_DATA:

embedded:

160 bytes

malloc:

64 bytes

This is, of course, unacceptable. I had to find a way to reduce the memory usage of small sets.

Unacceptable!

I decided to tackle the problem by looking at the 32 bytes of wrapping.

wrapping:

32 bytes

The underlying data structure for this type of Ruby object looks like this.


struct RTypedData {
  struct RBasic basic;
  const rb_data_type_t *const type;
  const VALUE typed_flag;
  void *data;
}

It starts with the basic information that all Ruby objects start with, which is 16 bytes.


struct RTypedData {
  struct RBasic basic;
  const rb_data_type_t *const type;
  const VALUE typed_flag;
  void *data;
}

It has a pointer to the information for the specific type of object, this is 8 bytes.


struct RTypedData {
  struct RBasic basic;
  const rb_data_type_t *const type;
  const VALUE typed_flag;
  void *data;
}

It stored 8 bytes for the typed flag. This flag was used mostly used to differentiate between RTypedData objects and the older RData objects, but it also recorded whether the object was embedded.|The value was always set to either 1 or 3 for RTypedData objects. This looked like a natural candidate for removal, if there was some other way to differentiate between RData and RTypedData objects. I determined it was possible to embed this information


struct RTypedData {
  struct RBasic basic;
  const rb_data_type_t *const type;
  const VALUE typed_flag;
  void *data;
}

using the low bits of the type pointer. Since the low 2 bits of the type pointer are always 0 due to alignment reasons, they are available to use.


struct RTypedData {
  struct RBasic basic;
  const rb_data_type_t *const type;
  const VALUE typed_flag;
  void *data;
}

That allowed removal of the typed_flag argument, saving 8 bytes.


struct RTypedData {
  struct RBasic basic;
  const rb_data_type_t *const type;
                         
  void *data;
}

That reduced the amount of wrapping bytes from 32 to 24.

wrapping:

24 bytes

When combined with the size of set table, it now totaled 80.

set_table:

56 bytes

wrapping:

24 bytes

This meant the size of small sets is only 80 plus 64, or 144 bytes. That is a 28% reduction in the memory usage of small sets.

T_DATA:

embedded:

80 bytes

malloc:

64 bytes

That is definitely acceptable. Unfortunately, we later found a problem.

Acceptable!

The problem was not in RTypedData, that was fine.

struct RTypedData {
  struct RBasic basic;
  const rb_data_type_t *const type;
  void *data;

}

The problem was in RData, which for implementation reasons has to have a compatible structure with RTypedData.

struct RTypedData {
  struct RBasic basic;
  const rb_data_type_t *const type;
  void *data;

}

struct RData {
  struct RBasic basic;
  RUBY_DATA_FUNC dmark;
  void *data;
  RUBY_DATA_FUNC dfree;
}

The problem with using low bits in RTypedData's type member.

struct RTypedData {
  struct RBasic basic;
  const rb_data_type_t *const type;
  void *data;

}

struct RData {
  struct RBasic basic;
  RUBY_DATA_FUNC dmark;
  void *data;
  RUBY_DATA_FUNC dfree;
}

Is you must ensure there are no low bits set in RData's dmark member. Unfortunately, while normal pointers do not have low bits set due to alignment, function pointers can have low bits set, and this is a function pointer.

struct RTypedData {
  struct RBasic basic;
  const rb_data_type_t *const type;
  void *data;

}

struct RData {
  struct RBasic basic;
  RUBY_DATA_FUNC dmark;
  void *data;
  RUBY_DATA_FUNC dfree;
}

We ended up fixing this by storing the RTypedData flag using 1 bit of the general object flags. General object flags are limited in number and we do not have many to spare, but we were able to find and use an available one.

struct RTypedData {
  struct RBasic basic;
  const rb_data_type_t *const type;
  void *data;

}

struct RData {
  struct RBasic basic;
  RUBY_DATA_FUNC dmark;
  void *data;
  RUBY_DATA_FUNC dfree;
}

We are still storing the embedded information using the low bit of the type pointer, so we only have to use 1 general object flag and not 2.

struct RTypedData {
  struct RBasic basic;
  const rb_data_type_t *const type;
  void *data;

}

struct RData {
  struct RBasic basic;
  RUBY_DATA_FUNC dmark;
  void *data;
  RUBY_DATA_FUNC dfree;
}

Later in the development cycle, Jean wanted to speed up instance variable access for RTypedData.

@byroot

He added a new member to RTypedData to allow that.

struct RTypedData {
  struct RBasic basic;
  VALUE fields_obj;
  const rb_data_type_t *const type;
  void *data;
}

Unfortunately, that would have undone my memory saving changes for small sets, by setting the wrapping bytes back to 32.

set_table:

56 bytes

wrapping:

32 bytes

However, Jean figured out a way around that. He took the bins pointer for the set table struct.


struct set_table {
    unsigned char entry_power, bin_power, size_ind;
    unsigned int rebuilds_num;
    const struct st_hash_type *type;
    st_index_t num_entries;
    st_index_t *bins;
    st_index_t entries_start, entries_bound;
    st_table_entry *entries;
};

And instead allocated that data directly after the end of the entries pointer, and changed the related code to use pointer arithmetic to find the location for the bins.


struct set_table {
    unsigned char entry_power, bin_power, size_ind;
    unsigned int rebuilds_num;
    const struct st_hash_type *type;
    st_index_t num_entries;
                         
    st_index_t entries_start, entries_bound;
    st_table_entry *entries;
};

This reduced the size of the set_table struct to 48 bytes, allowing core set objects to continue to fit in an 80 byte object slot.

set_table:

48 bytes

wrapping:

32 bytes

I hope you had fun learning about the implementation of core Set in Ruby 4.0.

Implementing

Core Set

If you enjoyed this presentation, and want to read more of my thoughts on Ruby programming, please consider picking up a copy of Polished Ruby Programming.|However, you may want to wait a bit, because

I am excited to announce that I've been working on a second edition of Polished Ruby Programming, which is scheduled for release in July, and is now available to preorder.|I am hoping this edition will also be translated into Japanese.

Preorders

That concludes my presentation. I would like to thank all of you for listening to me. If you have any questions, please ask me during the break.