Stop an Iterating Loop


While I was writing a piece of code to solve a problem, I wrote an innocent looking for loop which I had to break when a particular condition was met. Hence wrote the most obvious looking code ever - it used break once condition was met and this way the flow broke out of the loop. Once my solution was accepted by an online judge I thought could I have done anything else here?

This triggered me to benchmark different ways to get out of an iterating loop. The two of the most common ways to stop iterating a loop are

  • use break statement
  • write the condition of the loop in a way that is becomes false when you want to stop the iteration

The Example

Everything is better with an example. Let's say we need to find if character a is present in the array and we need to set the value of bool variable a_found accordingly.

Using break statement

bool a_found = false;

for (int i = 0 ; i < n ; i++) {
    if (str[i] == 'a') {
        a_found = true;
        break;
    }
}

Using loop condition

bool a_found = false;

for (int i = 0 ; a_found == false && i < n ; i++) {
    if (str[i] == 'a') {
        a_found = true;
    }
}

Should there be considerable difference in performance? My efforts to write an article about this gives you the obvious answer. YES! there is a significant difference.

Benchmark

The code to benchmark iterates over a string to see if a is present or not. The length of the string is variable and goes from 500 to 1000000000. We measure the time taken for each approach - standard benchmark practice. You can find the code here - code to benchmark stopping the loop iteration

Following graph shows the time taken by the two approaches varying with respect to the number of iterations of the loop (X Axis v/s Left Y-Axis) and the performance difference between the two approach (X Axis v/s Right Y-Axis).

benchmark-time-taken-for-break-loop

We see that a diverging graph that suggests one approach is significantly and always better than the other. The blue line shows the approach where we break the loop and it is always below the red one which represents the approach of stopping the iteration using condition.

We observe that using break to stop the iteration is on an average 45% better and it does not change with the number of iterations (post 1000 iterations). The raw data used for plotting this graph can be found here.

Conclusion

Using break statement to break the loop is 45% better than using condition to stop the iteration and get out of the loop.


Arpit Bhayani

Arpit's Newsletter

CS newsletter for the curious engineers

❤️ by 21000+ readers

If you like what you read subscribe you can always subscribe to my newsletter and get the post delivered straight to your inbox. I write essays on various engineering topics and share it through my weekly newsletter.




Other essays that you might like


Pseudorandom Number Generation using Cellular Automata - Rule 30

1011 reads 2020-02-14

Generating pseudorandom numbers is an interesting problem in Computer Science. In this article, we dive deep into an alg...

Fast and Efficient Pagination in MongoDB

3898 reads 2017-06-06

MongoDB is a document based data store and hence pagination is one of the most common use case of it. Find out how you c...

Setting up Graphite and Grafana on an Ubuntu server

278 reads 2015-12-14

Part 2: Monitor your production systems and application analytics using Graphite. This article will help you setup these...

Publish python package on PyPI

321 reads 2015-11-10

If you have written something cool in Python and want to make it installable via pip and easy_install, this post will he...


Be a better engineer

A set of courses designed to make you a better engineer and excel at your career; no-fluff, pure engineering.


Paid Courses

System Design Masterclass

A masterclass that helps you become great at designing scalable, fault-tolerant, and highly available systems.

1000+ learners

Details →

Redis Internals

Learn internals of Redis by re-implementing some of the core features in Golang.

28+ learners

Details →

Free Courses

Designing Microservices

A free playlist to help you understand Microservices and their high-level patterns in depth.

17+ learners

Details →

GitHub Outage Dissections

A free playlist to help you learn core engineering from outages that happened at GitHub.

67+ learners

Details →

Hash Table Internals

A free playlist to help you understand the internal workings and construction of Hash Tables.

25+ learners

Details →

BitTorrent Internals

A free playlist to help you understand the algorithms and strategies that power P2P networks and BitTorrent.

42+ learners

Details →

Topics I talk about

Being a passionate engineer, I love to talk about a wide range of topics, but these are my personal favourites.





  • v13.8.8
  • © Arpit Bhayani, 2022

Powered by this tech stack.