00:00:01.920
Here we go, here we go. Hello, hello, hello, everybody!
00:00:13.799
Welcome! I'm really excited to be here. I haven't been to Brazil in many years, so thank you for having me. My name is Aaron Patterson, and you can find me online as Tender Love.
00:00:27.080
Lately, I've been doing a lot of live streaming, so please join me on my live stream. Make sure to click the bell and subscribe. Don't forget to comment below.
00:00:39.800
In my live stream, I do a lot of pair programming, focusing on Ruby internals and Rails internals. If there's anything that any of you want me to cover, please let me know. I'd be happy to do that.
00:00:50.920
I work for a company called Shopify on the Ruby and Rails infrastructure team, which involves Ruby and Rails development. Before giving this presentation, I wanted to reflect on my last visit to Brazil, so I searched through my photos.
00:01:08.400
I could only find one photo from my 2011 trip, and I looked a lot younger back then, 13 years younger! Unfortunately, I lost all my other photos from my previous visits to Brazil, so after this talk, please come say hello to me and let’s take some photos together to create new memories.
00:01:38.680
Today, I’m going to talk about some Ruby implementation details, and I’m extremely nervous about this because I know it's 6 PM, and we’re going to discuss some very deep topics. I apologize in advance; I'll try to make it as entertaining as possible. We're going to cover performance improvements in Ruby 3.3, focusing specifically on data structures like binary trees and red-black trees.
00:02:12.120
We'll also discuss instance variables and object shapes, analyze what makes instance variables slow, and how we can speed them up. I apologize for the math involved, but I promise it's not too complicated. I was watching some earlier presentations about front-end development, which I find much harder, and I assure you that the math we'll discuss will be much easier than that.
00:02:58.200
The first topic is data structures, particularly binary trees. A binary tree is a type of tree where each parent node has up to two children. The left child has a value smaller than its parent node, while the right child has a value larger than its parent.
00:03:22.519
For example, in a tree with the values 5, 3, and 7, 3 is on the left of 5 and 7 is on the right of 5. When building a binary tree, we start with an empty structure, inserting the root node, which could be the number 5. Next, we would insert 3, moving to the left since 3 is smaller than 5.
00:04:09.879
Then we insert 2, which goes on the left of 3, since 2 is less than 3, and 4, which goes to the right of 3 because it's greater than 3 but smaller than 5. This process continues for all the values we're working with.
00:05:03.120
Inserting the number 9 will require checking and comparing it starting from 5, then going right to 7, then to 8, before finally inserting it as a new node. This process is relatively straightforward to implement in Ruby.
00:05:59.360
Searching for a value works similarly—we compare the number we want with the values in the tree, returning true if we find the value, or false if we hit a dead end. For example, searching for 8 requires us to traverse down the tree checking each node.
00:06:47.720
However, if we look for a number that doesn't exist, like 10, we end up traversing the right side until we reach a leaf with no further nodes, ultimately returning false. The worst-case performance scenarios in searching heap structure look bad when we think about inserting data in order, which leads to a skewed tree that mimics a linked list. In that case, the time complexity of searching becomes O(n), which is quite inefficient.
00:07:49.200
Speaking of binary trees, while many assume it's not common to deal with ordered lists, I believe they are quite prevalent in Rails applications. It’s relatively easy to generate ordered lists, and that's where one of my favorite methods in Ruby comes in: the bsearch method.
00:08:29.880
The bsearch method allows us to treat a sorted list as a binary tree, improving our search efficiency within it. For instance, when looking for a specific post within a list of Active Record objects, using bsearch can significantly enhance performance over searching manually or using include.
00:09:21.400
I ran a benchmark comparing the time taken between include and bsearch. The results showed that using include is about 30 times slower than bsearch. It's essential to understand the difference between O operations; optimizing the search with a binary search drastically reduces search time.
00:10:17.800
Returning to the binary tree structure, it’s important to understand that the performance is not practical and thus, I’ve rarely written code utilizing a binary tree. Instead, to optimize performance, the solution lies in maintaining a balanced tree.
00:11:07.080
This brings us to red-black trees: a balanced variant of binary trees. Red-black trees ensure efficiency by balancing themselves as we insert nodes, in contrast to regular binary trees that could become unbalanced.
00:11:43.920
Each node in a red-black tree is colored either red or black, with specific rules that enforce balance: All leaf nodes are black, red nodes cannot have red children, and every path from a given node to leaf nodes passes through the same number of black nodes. Additionally, it is important to note that the root node is always black.
00:12:36.320
Let's implement a functional approach to creating a red-black tree. The leaf nodes will be black, and we’ll use Ruby’s pattern matching feature for the generalization in our data structure. This functional method allows us to avoid mutating existing trees, ensuring only new red nodes are created.
00:13:49.999
Our red-black tree must be constructed by inserting various keys while ensuring we maintain the tree's balance. This involves careful checks to align each insertion with the tree's rules. An auxiliary method will handle inserting elements through recursive algorithm assurance that the tree remains balanced.
00:14:50.000
As we continue inserting various keys into the structure, we manage the layering of nodes which contributes to the necessity of rotations to sustain the balance of the tree, as nodes shift red-black colors based on insertion rules.
00:15:47.600
After building our tree structure, we need to implement a search functionality to check the existence of keys, which follows similar principles as insertion but with a focus on whether the desired key is found in our red-black structure.
00:16:31.920
Each insertion will yield a new version of the tree, allowing you to track various iterations effectively without duplicating the entire tree structure.
00:17:25.280
One critical feature of the red-black tree is that it shares memory to enhance speed and performance. While we cannot delete from the structure, it’s important to note that shapes observed during usage will never need to be deleted.
00:18:05.760
Discussing the implications of object shapes and how they influence instance variables gives us an opportunity to explore how properly utilizing trees can support performance. By mapping instance variables to indexes, we can efficiently manage memory allocations.
00:20:56.799
It's crucial to maintain consistency with instance variable definitions to avoid inefficient lookups. Each object's instance variable access entails examining the structure to verify its existence before making changes, which can introduce additional latency.
00:21:37.000
Keeping track of performance implications across multiple instances reveals the slowdowns that can occur when managing shape trees inefficiently. Introducing inline caching mechanisms allows for rapid retrieval of instance variable checks, preventing unnecessary overhead in method calls.
00:23:00.000
As we explore the impacts of cache hits and misses, we learn how strategically using red-black trees can enhance performance by lowering the expected time complexity, even in edge cases where instance variables are absent.
00:24:48.000
Through precise benchmarks and exploratory testing in Ruby 3.2 and 3.3, we identify the performance gains achieved in newer versions by utilizing data structures effectively.
00:25:46.000
In conclusion, while I have used binary trees zero times, I have relied on red-black trees once to illustrate their effectiveness in optimizing instance variables. I encourage developers to utilize these data structures effectively, never compromising on their coding style.
00:27:04.000
If you take away anything from this talk, remember that optimizations are beneficial, but your primary concern should always be writing code you feel comfortable with.
00:27:48.359
Thank you all for your attention, and I'm grateful for the opportunity to discuss Ruby 3.4 with such an enthusiastic audience. Obrigado!
