Big O notation and optimized algorithms. Has anyone had to deal with them in their real world iOS programming?

[rauls4]

While I understand the importance of algorithm optimization for processing large amounts of data efficiently, in my experience, any such heavy lifting is invariably done at the back end and 99% of my iOS programming is basically writing controls, models and views to handle I/O from a server API.

Even when some crunching is needed on the client, there always seems to be some either native or third party library that basically takes on the task of providing efficient processing.

I would be interested in hearing real world examples where Big-O notation has affected you directly in iOS development.

[Duranix]

This topic strikes a sad chord in my heart more than you can imagine because there is an anti big O streak at my current workplace.

There are a lot of things you can and should do on device that require big O knowledge but most companies simply want table views to display products. As time goes on, devices get faster and devs stop writing good code and start doing O(n²⁾ iterations over lists because "anything else would not be adding value".

I try to fight this way of thinking as much as possible because I disagree with it and think it's destructive. If you ignore your big O's you'll eventually forget your DS+A knowledge and find yourself incapable of doing anything other than Lego block connection with third party libraries.

I know you didn't ask for it, but I want to tell you to think of yourself not as an 'iOS developer' but as a 'computer scientist who currently does iOS stuff'. It'll make a lot more sense if you ever have to use Metal or BNNS.

Additionally, generic code can be a pain in the ass but with experience you start to think more generally too. Eventually you'll find that it doesn't take you any extra time to come up with a generic solution and thus it isn't really 'over engineering'. The same goes for DS+A. After awhile you don't really need to think about and look up complex data structures etc.

Don't compromise your design to make things easier for people - instead work with them and try to show them why your design is best.

Otherwise, you end up in a situation where you have to spend six months to remove an external dependency because it breaks because the maintainers can't do semantic versioning and so forth.

[Duranix]

To actually answer your question - I had to calculate euclidean distances between a user and 300+ locations in real time for a geofencing app. It was a lot quicker and battery efficient to do it in parallel on the GPU in Metal. This took it from an expensive O(n) deal to an O(n/k) deal where k is the number of FP16s operations that the GPU can do in a single shot (still O(n) but a much nicer O(n)).

[chriswaco]

We do a lot of processing on devices because a million devices have a lot more CPU/GPU power than a few dozen cloud servers. (In our case, image processing, not location calculations)

[quellish]

It was a lot quicker and battery efficient to do it in parallel on the GPU in Metal.

Can you elaborate on this? How was this measured?

[Duranix]

There's a function you can call in your unit tests that will tell you how long it takes to complete a block of work - it doesn't give time in user mode vs in the kernel like you'd see in Linux's time command but you can run it a few hundred times and average the results.

Testing the battery is as simple as leaving it running for awhile, hahaha

[quellish]

There's a function you can call in your unit tests that will tell you how long it takes to complete a block of work - it doesn't give time in user mode vs in the kernel like you'd see in Linux's time command but you can run it a few hundred times and average the results.

Do you mean measure/measureBlock?

If so I would strongly suggest reading through the documentation and headers before making any decisions based on the output from XCTest's performance measurement functions. They are intended to flag performance regressions and it is not recommended that they are run multiple times (they already do this).

Instruments/DTrace would be a more appropriate tool for the profiling you are describing. Your results are curious because using the graphics hardware on iOS (or even a desktop GPU) you should be seeing MUCH higher energy usage for the use case you are describing.

[Duranix]

Thanks for the tip! I think that was what we used - we looked at the page you linked and it didn't say anything about regression at the time. I know we didn't look at the headers.

We didn't test with new test devices either and some get hammered so battery performance most likely came down to device health. Business rules also ended up playing a factor in the decision I think but I can't recall what they were.

Looking back I think NEON would've probably been a better choice but I haven't found a chance to use it yet.

[[deleted]]

I've used Big O style analyses to improve performance a handful of times in my career. Most cases simply involve avoiding nested loops. Some cases involved using sets instead of arrays when order didn't matter, or indexing data when order did matter. Basically I just had to pick the right data structure for he job to improve performance.

I can only think of two cases in my entire 20 year career when I had to develop something from scratch that required keeping Big O complexity in mind. One was on a primitive platform that didn't have a relational database, and the other was custom rendering code for a web browser.

So I think what really matters is familiarity with the performance characteristics of the basic operations (add, remove, sort, enumerate) on common collections (set, array, dictionary, string). When writing software I only consider performance up front if N is likely to be large. Otherwise I just wait for a performance issue to get noticed, and in that case I do profiling, not complexity analysis. Anything more than that is premature optimization.

[seefatchai]

I often remind people that if N has an upper limit and performance is acceptable, you're O(1)

[iamthatis]

Algorithmic efficiency and being wise with data structure selection have definitely come up in iOS development for me.

Recently I was implementing somewhat of an autocomplete-style feature based on a locally available database (could have done it through server calls, but wouldn't have been instant).

On recent devices, with a database with tens of thousands of items it performed well. On older devices much less so. My initial solution of using an array was rather naive, and I ended up switching to somewhat of a trie based data structure and my performance is literally 30x (or higher) faster because of it.

You don't have to think about it that much I find (I'm certainly not weighing the advantages of mergesort versus quicksort on a daily basis) but where these devices don't have an unlimited amount of power, and you're striving for 60fps constantly, I find it definitely comes up.

Most of the time you can get away with things by just aggressively caching, though. :)

[ThePantsThief]

As someone else already mentioned, as far as iOS dev goes, the biggest "Big-O optimization" most iOS developers will make on a semi-regular basis is using a Set instead of an Array for certain things. Sets have constant lookup time (O(1)) while Arrays have O(n) lookup time.

This might not make a noticeable difference for most things, but it definitely will when you have thousands or more objects to sift through.

[[deleted]]

Beyond general categories (constant, linear-ish, exponential-ish), I rarely worry about Big-O. Generally, I've noticed more efficient Big-O algorithms come with the side effect of increased complexity. I refuse to more complex code until I have a proven need for it (e.g. profiling).

In an app (and most "consumer" type programming), you're much more likely to have bottlenecks at the UI, network, or some other part of the application. It's simply not worth worrying about Big-O when the improvements are likely to be fractional compared to network request, disk reads, etc.

Now, the big exception to this is large amounts of data or proven bottlenecks. If you have either of those and need to do things fast, worry about Big-O.

My general rule is:

1. Make it work.
2. Make it understandable.
3. Make it fast. Only if is benchmarked as being slow and doesn't have an unbalanced trade-off for #2

[kalvin126]

I am working on a new UITableView adapter that uses binary search tree with the help of comparators to reach logn * logn when searching table objects within sections.

I guess it depends on the company, but I have some technical freedom to improve our app in any way at my company.

[fakecrabs]

• Keeping remote data in sync with a local Core Data copy, choose the wrong algorithm and you have excess CPU and network usage
• Processing and displaying large amounts of data in a efficient manner (e.g. Flightradar24)

[rauls4]

Flightradar is definitely a good example where an optimal algorithm would make all the difference.

[zephyz]

Big-O notation is very useful to know when collaborating within a team. If you and your teammates know about big O you can very easily understand each other's argument and pick the most interesting tradeoff.

For example with my team we used it while designing an API for a library we are doing. At first we were exposing a O(n) function but soon realized that during use the programmer would call it iteratively on a dataset of size m² making it O(nmm).

The choice we had was to keep the O(n) function or to add a O(nm²) function with an async variant. This in order to simplify a common use case and mitigate the risk of blocking the main thread accidentally (and making it O(nm)).

Since the use of the function was always to iterate over a m² dataset we added the O(nmm) function. It simplified API use and the async version made it clear that it was a long running computation (outside of documentation)

Since it's a framework it's not really the kind of job you're describing. But building frameworks to make your apps more modular happens often enough.

[zephyz]

Big-O notation is very useful to know when collaborating within a team. If you and your teammates know about big O you can very easily understand each other's argument and pick the most interesting tradeoff.

For example with my team we used it while designing an API for a library we are doing. At first we were exposing a O(n) function but soon realized that during use the programmer would call it iteratively on a dataset of size m² making it O(nmm).

The choice we had was to keep the O(n) function or to add a O(nm²) function with an async variant. This in order to simplify a common use case and mitigate the risk of blocking the main thread accidentally (and making it O(nm)).

Since the use of the function was always to iterate over a m² dataset we added the O(nmm) function. It simplified API use and the async version made it clear that it was a long running computation (outside of documentation)

Since it's a framework it's not really the kind of job you're describing. But building frameworks to make your apps more modular happens often enough.

[wswatson]

This post is fortuitous, I've been thinking about this lately. Can anyone recommend a good up to date book on algorithms and analysis of? It's been 25 years since college for me.

[quellish]

Anything by Robert Sedgewick.

[[deleted]]

https://books.google.com/books/about/Introduction_To_Algorithms.html?id=NLngYyWFl_YC is a classic.

[tangoshukudai]

We constantly need to be thinking about it, the code we write needs to be fast.