Android: Proof that findViewById() is slower than using a ViewHolder

I was recently asked to provide proof of why using a ViewHolder would be faster than just using findViewById() when populating the item views of each item in a ListView. A fair question since empirically stating “it seems faster” is hardly proof and my results may have been from other factors I had not thought of at the time. So, I delved into the Android source code and pulled a bit of research together to present proof of why using a ViewHolder mechanism instead of findViewById() inside a ListView.getView() is more efficient and faster. I will be using Big O notation here, so if you need a refresher on it’s definition and meaning, I highly recommend skimming the definition over at Wiki as well as reading a fairly clear explanation of the meaning of using Big O notation from William Shields.

First, some assumptions need to be made. The list contains m number of items. Each item contains a ViewGroup, such as a LinearLayout or RelativeLayout, consisting of n number of views needing to be found and populated. Small numbers of either list items or views will not show a significant difference, but once you start using more than a handful of either, the difference become noticeable.

findViewById() is O(n!)

The findViewById() Android API method requires an algorithm to search your view hierarchy every time you call it by traversing the entire structure looking for the ID of your view. Traversing the hierarchy to find all n Views will result in the algorithm having O(n!) efficiency at best. A very simple example would be a LinearLayout with 5 views and no subchild views to search through. The first findViewById() would find the first view on the first child; the second find will read the first view and then the second; the third find would read the first, second, and then return the third view; and so on. You can verify my take on this algorithm by researching the Android source code yourself. To help get you started, I will point you to the ViewGroup’s method that actually performs the find (in Android 2.3.4 r1).

ViewHolder is O(1)

The ViewHolder mechanism stores the results returned by findViewById() in a HashMap and subsequent calls search the HashMap for the view instead of using findViewById(). In general, a hash algorithm is fast because it “hashes” the key and turns it directly into the location of the bin where the value is stored, making it an O(1) operation. Since we are using an int for our key and we are using Java’s HashMap, we have an O(1) efficiency (some discussion about this can be found here).

O(m) is better than O(m n!)

Comparing the two methods, ViewHolder is the best case scenario with O(1) and findViewById() comes in second with O(n!), but the distinction becomes even more apparent when you factor in the fact that these methods are done for each item in your list. O(m) is noticeably more efficient than O(m n!) — depending on the values of m and n, this can sometimes be better or worse than O(m2), but it will always be worse than O(m) for lists with more than 1 item.

3 thoughts on “Android: Proof that findViewById() is slower than using a ViewHolder

  1. Hey ya… So, you are not going to call atleast once findbyviewId() in your getView() method. I don’t think, your explanation is right in terms of Big_O notation.

    Your are half right. If we have M-rows and N-Views in the ViewGroup. If we scroll up-down some P-times.
    Without ViewHolder pattern :
    O(P * M * N!)
    With ViewHolder pattern :
    O(M * N! + overhead)

    ViewHolder is obviously good, because we are going to store what we have already loaded.
    But here we have to compramise on space to store all the view objects.

    I think I make little sense here.

  2. I think you mean O(n^2), not O(n!), because n! is N-factorial, which is N*(N-1)*(N-2)…*1. So for 10 views it would take 3,628,800 steps, but it’ll actually take time proportional to 100 (and closer to 50).

Leave a Reply to Lawrence Kesteloot Cancel reply

Your email address will not be published. Required fields are marked *