How to increase performances on custom UICollectionsViewLayout using Binary search

November 2, 2018 by Giorgia Marenda

GIPHY’s iOS app grid design includes a particular layout called the “Waterfall Layout.”It allows differentsized GIFs and Stickers to fit together in a continuous steam.An issue with this kind of layout is that we need to dynamically calculate the frame-size of every cell because we don’t know what the height of the GIF will be in advance. This could be very inefficient without applying any optimizations, so in this article we’ll describe how to build a waterfall layout  efficientl

Collection view layouts are subclasses of the abstract UICollectionViewLayout class, and they serve the purpose of telling the UICollectionView where the content is displayed. They define the visual attributes of every item in your collection view. The individual attributes are instances of UICollectionViewLayoutAttribute
and contain the properties of each item in your collection view, such as the item’s frame or transform.The implementation of a custom layout is made of three core steps:


1. Prepare method. This is called every time the layout is invalidated. This is the time when we calculate our attributes.

2. Cache. While computing the attributes we want to cache them so we don’t need to do it again until the layout is invalidated. As a first optimization, we will maintain an array of UICollectionViewLayoutAttributes. After that, we’ll see how much better we can do with a binary tree.

3. LayoutAttributesForElements(in rect: CGRect). This method is called periodically by the UICollectionView, asking for a set of attributes that match a certain region. So we need to filter the cached array of attributes and return an array that contains all the attributes that correspond to all the items that are going to appear within that rect in our UICollectionView.


The green rectangle is the rect representing the screen, so the attributes we need to return are just the ones which need to be displayed (purple rectangles). In other words we want to find all the items that intersect the rect.

A simple implementation could be something like:

override func layoutAttributesForElements(in rect: 
CGRect) -> [UICollectionViewLayoutAttributes]? {
  return cache.filter {

Now this solution works fairly well when the number of items are limited, since the filter method has a linear complexity with the number of elements in the array. The worst case complexity of linear search is O(n). In the GIPHY’s case we potentially have a huge number of GIFs, and the performance degrades as the user scrolls deeper and deeper.


At the WWDC18, Apple presented a Tour of UICollectionView, explaining optimization to save a considerable amount of CPU work, simply by using a different algorithm to filter the attributes.
We can observe that our cache array of attributes is sorted by nature, since our layout demands every cell next to or below its preceding cell.
A much more performant algorithm to search for an item in a sorted array is Binary Search. The worst case complexity of binary search is O(log n).

Here a generic Swift implementation takes an array a and returns the index of the first element that matches the criteria described by the compare function:

func binarySearch(_ a: [T], where compare: ((T)-> ComparisonResult)) -> Int? {
    var lowerBound = 0
    var upperBound = a.count
    while lowerBound < upperBound { 
        let midIndex = lowerBound + (upperBound - lowerBound) / 2
        if compare(a[midIndex]) == .orderedSame { 
            return midIndex 
        } else if compare(a[midIndex]) == .orderedAscending { 
            lowerBound = midIndex + 1 
        } else { 
            upperBound = midIndex 
    return nil 


Now we can use the binary search to find an index that match our criteria: (attribute.frame.intersects(rect)).

let index: Int? = binarySearch(cache) { (attribute) -> ComparisonResult in
    if attribute.frame.intersects(rect) {
        return .orderedSame
    if attribute.frame.minY > rect.maxY {
        return .orderedDescending
    return .orderedAscending


Starting from this index we can start looping forward and backward to find all the other items that match our criteria.

for attributes in cache[..<index].reversed() { 
    guard attributes.frame.maxY >= rect.minY else { break }

for attributes in cache[index...] {
    guard attribute.frame.minY <= rect.maxY else { break }


Now, let’s see how much that helps. We can use some tests to compare the performance using an array of 10,000 sorted elements versus a binary tree. In this case, we’ll search for the last item:

func testPerformanceWithoutBinarySearch() {
    self.measure {
        _ = sortedArray.filter { $0 == 99999 }

measured [Time, seconds] average: 0.0215

func testPerformanceWithBinarySearch() {
    self.measure {
        _ = binarySearch(sortedArray, key: 99999)

measured [Time, seconds] average: 0.00000645




On the Apple Performance Tips, the number one tip is reduce your app power consumption. This optimization may not result in a noticeable change in the final product. The scroll experience will be smooth using a linear search as well, especially on newer phones, but reducing the amount of CPU usage will improve the device’s battery life.


-Giorgia Marenda, Lead iOS Engineer