Visible lag while scrolling two way scrolling UICollectionView with large number of cells (250,000 or more)

Question

I am subclassing UICollectionViewFlowLayout in order to get two way scrolling in a UICollectionView. The scrolling works fine for smaller number of row and section count (100-200 rows and sections) but there is visible lag while scrolling when I increase row and section count over 500 i.e 250,000 or more cells in the UICollectionView. I have traced the source of the lag to be for in loop in the layoutAttributesForElementsInRect. I am using a Dictionary to hold UICollectionViewLayoutAttributes of each cell to avoid recalculating it and looping through it to return attributes of cells from layoutAttributesForElementsInRect

import UIKit

class LuckGameCollectionViewLayout: UICollectionViewFlowLayout {

    // Used for calculating each cells CGRect on screen.
    // CGRect will define the Origin and Size of the cell.
    let CELL_HEIGHT = 70.0
    let CELL_WIDTH = 70.0

    // Dictionary to hold the UICollectionViewLayoutAttributes for
    // each cell. The layout attribtues will define the cell's size
    // and position (x, y, and z index). I have found this process
    // to be one of the heavier parts of the layout. I recommend
    // holding onto this data after it has been calculated in either
    // a dictionary or data store of some kind for a smooth performance.
    var cellAttrsDictionary = Dictionary<NSIndexPath, UICollectionViewLayoutAttributes>()
    // Defines the size of the area the user can move around in
    // within the collection view.
    var contentSize = CGSize.zero

    override func collectionViewContentSize() -> CGSize {
        return self.contentSize
    }

    override func prepareLayout() {

        // Cycle through each section of the data source.
        if collectionView?.numberOfSections() > 0 {
            for section in 0...collectionView!.numberOfSections()-1 {

                // Cycle through each item in the section.
                if collectionView?.numberOfItemsInSection(section) > 0 {
                    for item in 0...collectionView!.numberOfItemsInSection(section)-1 {

                        // Build the UICollectionVieLayoutAttributes for the cell.
                        let cellIndex = NSIndexPath(forItem: item, inSection: section)
                        let xPos = Double(item) * CELL_WIDTH
                        let yPos = Double(section) * CELL_HEIGHT

                        let cellAttributes = UICollectionViewLayoutAttributes(forCellWithIndexPath: cellIndex)
                        cellAttributes.frame = CGRect(x: xPos, y: yPos, width: CELL_WIDTH, height: CELL_HEIGHT)

                        // Save the attributes.
                        cellAttrsDictionary[cellIndex] = cellAttributes
                    }
                }

            }
        }

        // Update content size.
        let contentWidth = Double(collectionView!.numberOfItemsInSection(0)) * CELL_WIDTH
        let contentHeight = Double(collectionView!.numberOfSections()) * CELL_HEIGHT
        self.contentSize = CGSize(width: contentWidth, height: contentHeight)

    }

    override func layoutAttributesForElementsInRect(rect: CGRect) -> [UICollectionViewLayoutAttributes]? {
        // Create an array to hold all elements found in our current view.
        var attributesInRect = [UICollectionViewLayoutAttributes]()

        // Check each element to see if it should be returned.
        for (_,cellAttributes) in cellAttrsDictionary {
            if CGRectIntersectsRect(rect, cellAttributes.frame) {
                attributesInRect.append(cellAttributes)
            }
        }

        // Return list of elements.
        return attributesInRect
    }

    override func layoutAttributesForItemAtIndexPath(indexPath: NSIndexPath) -> UICollectionViewLayoutAttributes? {
        return cellAttrsDictionary[indexPath]!
    }

    override func shouldInvalidateLayoutForBoundsChange(newBounds: CGRect) -> Bool {
        return false
    }
}

Edit: Following are the changes that I have come up with in the layoutAttributesForElementsInRect method.

override func layoutAttributesForElementsInRect(rect: CGRect) -> [UICollectionViewLayoutAttributes]? {        
    // Create an array to hold all elements found in our current view.
    var attributesInRect = [UICollectionViewLayoutAttributes]()

    let xOffSet = self.collectionView?.contentOffset.x
    let yOffSet = self.collectionView?.contentOffset.y
    let totalColumnCount = self.collectionView?.numberOfSections()
    let totalRowCount = self.collectionView?.numberOfItemsInSection(0)

    let startRow = Int(Double(xOffSet!)/CELL_WIDTH) - 10    //include 10 rows towards left
    let endRow = Int(Double(xOffSet!)/CELL_WIDTH + Double(Utils.getScreenWidth())/CELL_WIDTH) + 10 //include 10 rows towards right
    let startCol = Int(Double(yOffSet!)/CELL_HEIGHT) - 10 //include 10 rows towards top
    let endCol = Int(Double(yOffSet!)/CELL_HEIGHT + Double(Utils.getScreenHeight())/CELL_HEIGHT) + 10 //include 10 rows towards bottom

    for(var i = startRow ; i <= endRow; i = i + 1){
        for (var j = startCol ; j <= endCol; j = j + 1){
            if (i < 0 || i > (totalRowCount! - 1) || j < 0 || j > (totalColumnCount! - 1)){
                continue
            }

            let indexPath: NSIndexPath = NSIndexPath(forRow: i, inSection: j)
            attributesInRect.append(cellAttrsDictionary[indexPath]!)
        }
    }

    // Return list of elements.
    return attributesInRect
}

I have calculated the offset of the collectionView and used it to calculate the cells that will be visible on screen(using height/width of each cell). I had to add extra cells on each side so that when user scrolls there are no missing cells. I have tested this and the performance is fine.

Answer 1

By taking advantage of the layoutAttributesForElementsInRect(rect: CGRect) with your known cell size you don't need to cache your attributes and could just calculate them for a given rect as the collectionView requests them. You would still need to check for the boundary cases of 0 and the maximum section/row counts to avoid calculating unneeded or invalid attributes but that can be easily done in where clauses around the loops. Here's a working example that I've tested with 1000 sections x 1000 rows and it works just fine without lagging on the device:

Edit: I've added the biggerRect so that attributes can be pre-calculated for before the scrolling gets there. From your edit it looks like you're still caching the attributes which I don't think is needed for performance. Also it's going to lead to a much larger memory footprint with the more scrolling you do. Also is there a reason your don't want to use the supplied CGRect from the callback rather than manually calculate one from the contentOffset?

class LuckGameCollectionViewLayout: UICollectionViewFlowLayout {

let CELL_HEIGHT = 50.0
let CELL_WIDTH = 50.0

override func collectionViewContentSize() -> CGSize {
    let contentWidth = Double(collectionView!.numberOfItemsInSection(0)) * CELL_WIDTH
    let contentHeight = Double(collectionView!.numberOfSections()) * CELL_HEIGHT
    return CGSize(width: contentWidth, height: contentHeight)
}

override func layoutAttributesForElementsInRect(rect: CGRect) -> [UICollectionViewLayoutAttributes]? {
    let biggerRect = rect.insetBy(dx: -2048, dy: -2048)
    let startIndexY = Int(Double(biggerRect.origin.y) / CELL_HEIGHT)
    let startIndexX = Int(Double(biggerRect.origin.x) / CELL_WIDTH)
    let numberOfVisibleCellsInRectY = Int(Double(biggerRect.height) / CELL_HEIGHT) + startIndexY
    let numberOfVisibleCellsInRectX = Int(Double(biggerRect.width) / CELL_WIDTH) + startIndexX
    var attributes: [UICollectionViewLayoutAttributes] = []

    for section in startIndexY..<numberOfVisibleCellsInRectY
        where section >= 0 && section < self.collectionView!.numberOfSections() {
            for item in startIndexX..<numberOfVisibleCellsInRectX
                where item >= 0 && item < self.collectionView!.numberOfItemsInSection(section) {
                    let cellIndex = NSIndexPath(forItem: item, inSection: section)
                    if let attrs = self.layoutAttributesForItemAtIndexPath(cellIndex) {
                        attributes.append(attrs)
                    }
            }
    }
    return attributes
}

override func layoutAttributesForItemAtIndexPath(indexPath: NSIndexPath) -> UICollectionViewLayoutAttributes? {
    let xPos = Double(indexPath.row) * CELL_WIDTH
    let yPos = Double(indexPath.section) * CELL_HEIGHT
    let cellAttributes = UICollectionViewLayoutAttributes(forCellWithIndexPath: indexPath)
    cellAttributes.frame = CGRect(x: xPos, y: yPos, width: CELL_WIDTH, height: CELL_HEIGHT)
    return cellAttributes
}
}

Answer 2

You need to come up with a data structure for your cells which is ordered by dimension(s), in order to come up with some algorithm using those dimension(s) to narrow down the search range.

Let's take the case of a table with cells 100 pixels tall by the full width of the view, and 250_000 elements, asked for the cells intersecting { 0, top, 320, bottom }. Then your data structure would be an array ordered by top coordinate, and the accompanying algorithm would be like

let start: Int = top / 100
let end: Int = bottom / 100 + 1
return (start...end).map { cellAttributes[$0] }

Add as much complexity as your actual layout requires.