Sorted Array

Why is processing a sorted array faster than an unsorted array?

Answer: What is Branch Prediction? Consider a railroad junction: Now for the sake of argument, suppose this is back in the 1800s – before long distance or radio communication. You are the operator of a junction and you hear a train coming. You have no idea which way it will go. You stop the train to ask the captain which direction he wants. And then you set the switch appropriately. Trains are heavy and have a lot of inertia. So they take forever to start up and slow down. Is there a better way? You guess which direction the train will go! •If you guessed right, it continues on. •If you guessed wrong, the captain will stop, back up, and yell at you to flip the switch. Then it can restart down the other path. If you guess right every time, the train will never have to stop. If you guess wrong too often, the train will spend a lot of time stopping, backing up, and restarting. ________________________________________ Consider an if-statement: At the processor level, it is a branch instruction: You are a processor and you see a branch. You have no idea which way it will go. What do you do? You halt execution and wait until the previous instructions are complete. Then you continue down the correct path. Modern processors are complicated and have long pipelines. So they take forever to “warm up” and “slow down”. Is there a better way? You guess which direction the branch will go! •If you guessed right, you continue executing. •If you guessed wrong, you need to flush the pipeline and roll back to the branch. Then you can restart down the other path. If you guess right every time, the execution will never have to stop. If you guess wrong too often, you spend a lot of time stalling, rolling back, and restarting. ________________________________________ This is branch prediction. I admit it’s not the best analogy since the train could just signal the direction with a flag. But in computers, the processor doesn’t know which direction a branch will go until the last moment. So how would you strategically guess to minimize the number of times that the train must back up and go down the other path? You look at the past history! If the train goes left 99% of the time, then you guess left. If it alternates, then you alternate your guesses. If it goes one way every 3 times, you guess the same… In other words, you try to identify a pattern and follow it. This is more or less how branch predictors work. Most applications have well-behaved branches. So modern branch predictors will typically achieve >90% hit rates. But when faced with unpredictable branches with no recognizable patterns, branch predictors are virtually useless. Further reading: “Branch predictor” article on Wikipedia. ________________________________________ As hinted from above, the culprit is this if-statement: if (data[c] >= 128) sum += data[c]; Notice that the data is evenly distributed between 0 and 255. When the data is sorted, roughly the first half of the iterations will not enter the if-statement. After that, they will all enter the if-statement. This is very friendly to the branch predictor since the branch consecutively goes the same direction many times. Even a simple saturating counter will correctly predict the branch except for the few iterations after it switches direction. Quick visualization: T = branch taken N = branch not taken data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ... branch = N N N N N ... N N T T T ... T T T ... = NNNNNNNNNNNN … NNNNNNNTTTTTTTTT … TTTTTTTTTT (easy to predict) However, when the data is completely random, the branch predictor is rendered useless because it can’t predict random data. Thus there will probably be around 50% misprediction. (no better than random guessing) data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ... branch = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ... = TTNTTTTNTNNTTTN … (completely random – hard to predict) ________________________________________ So what can be done? If the compiler isn’t able to optimize the branch into a conditional move, you can try some hacks if you are willing to sacrifice readability for performance. Replace: if (data[c] >= 128) sum += data[c]; with: int t = (data[c] - 128) >> 31; sum += ~t & data[c]; This eliminates the branch and replaces it with some bitwise operations. (Note that this hack is not strictly equivalent to the original if-statement. But in this case, it’s valid for all the input values of data[].) Benchmarks: Core i7 920 @ 3.5 GHz C++ – Visual Studio 2010 – x64 Release // Branch – Random seconds = 11.777 // Branch – Sorted seconds = 2.352 // Branchless – Random seconds = 2.564 // Branchless – Sorted seconds = 2.587 Java – Netbeans 7.1.1 JDK 7 – x64 // Branch – Random seconds = 10.93293813 // Branch – Sorted seconds = 5.643797077 // Branchless – Random seconds = 3.113581453 // Branchless – Sorted seconds = 3.186068823 Observations: •With the Branch: There is a huge difference between the sorted and unsorted data. •With the Hack: There is no difference between sorted and unsorted data. •In the C++ case, the hack is actually a tad slower than with the branch when the data is sorted. A general rule of thumb is to avoid data-dependent branching in critical loops. (such as in this example)

86 thoughts on “Why is processing a sorted array faster than an unsorted array?

  1. This is the right web site for anybody who would like to understand this
    topic. You know a whole lot its almost hard to argue with you (not that I actually will need to…HaHa).

    You definitely put a fresh spin on a subject that has been discussed for many years.
    Excellent stuff, just wonderful!

  2. I was just looking at your Why is processing a sorted array faster than an unsorted array? | SRD website and see that your site has the potential to get a lot of visitors. I just want to tell you, In case you don’t already know… There is a website network which already has more than 16 million users, and most of the users are looking for websites like yours. By getting your website on this service you have a chance to get your site more popular than you can imagine. It is free to sign up and you can read more about it here: http://ittsy.com/it/3x – Now, let me ask you… Do you need your website to be successful to maintain your business? Do you need targeted visitors who are interested in the services and products you offer? Are looking for exposure, to increase sales, and to quickly develop awareness for your site? If your answer is YES, you can achieve these things only if you get your website on the service I am talking about. This traffic service advertises you to thousands, while also giving you a chance to test the network before paying anything at all. All the popular blogs are using this service to boost their traffic and ad revenue! Why aren’t you? And what is better than traffic? It’s recurring traffic! That’s how running a successful website works… Here’s to your success! Find out more here: http://www.arvut.org/1/dft

  3. That is very attention-grabbing, You are an excessively skilled blogger.
    I’ve joined your rss feed and look forward to in search of extra
    of your great post. Additionally, I’ve shared your web site in my social networks

  4. I think this is one of the most vital info for me. And i’m glad reading your article.
    But wanna remark on some general things, The web site style is ideal, the articles is really
    nice : D. Good job, cheers

  5. Its such as you read my mind! You seem to know a lot about this, like you wrote the book in it or something.

    I feel that you just can do with some p.c. to pressure the message
    home a little bit, however other than that, this
    is excellent blog. A great read. I’ll definitely be back.

  6. What i do not realize is in truth how you’re now not actually much more smartly-appreciated than you might be now. You’re so intelligent. You understand thus considerably in relation to this matter, produced me for my part believe it from so many various angles. Its like men and women aren’t involved except it¡¦s something to accomplish with Lady gaga! Your personal stuffs nice. At all times take care of it up!

  7. Have you ever thought about adding a little bit more than just your articles?

    I mean, what you say is valuable and everything.
    However just imagine if you added some great
    images or video clips to give your posts more, “pop”! Your
    content is excellent but with pics and clips, this site could definitely be one
    of the very best in its niche. Amazing blog!

  8. I simply want to tell you that I’m very new to weblog and certainly savored your web page. Probably I’m planning to bookmark your blog . You absolutely come with perfect articles and reviews. Appreciate it for sharing your blog site.

  9. This design is steller! You obviously know how to keep a reader amused.

    Between your wit and your videos, I was almost moved to start
    my own blog (well, almost…HaHa!) Excellent job.
    I really enjoyed what you had to say, and more than that,
    how you presented it. Too cool!

  10. Oh my goodness! Impressive article dude! Many thanks, However I am encountering troubles with your RSS.

    I don’t know why I cannot subscribe to it. Is there anyone else getting similar RSS
    problems? Anyone that knows the answer can you kindly respond?
    Thanks!!

  11. Hi, I do think your site could be having
    web browser compatibility problems. When I take a look at your web site in Safari, it looks fine however when opening in Internet Explorer, it has some overlapping issues.
    I merely wanted to provide you with a quick heads up! Apart
    from that, excellent site!

  12. After I initially commented I seem to hae clicked on thhe -Notify me when new comments are added- checkbox aand now ecery time a comment is
    added I receive 4 emails wirh the exact same comment.
    There has to be an easy method you are able to remove me frm that service?
    Thank you!

  13. I simply want to say I am just new to blogs and actually loved your blog. Very likely I’m likely to bookmark your website . You really have very good writings. Thanks a lot for sharing your blog.

  14. Excellent website you have here but I was wanting to know if you knew of any user discussion forums that cover the same topics
    discussed in this article? I’d really love to be a part of group where I can get opinions
    from other experienced people that share the same interest.
    If you have any recommendations, please let me know.
    Appreciate it!

  15. Just desire to say your article is as astonishing. The clearness to
    your put up is simply nice and that i could suppose you are knowledgeable
    on this subject. Fine with your permission let me to
    take hold of your feed to stay updated with impending post.
    Thank you a million and please continue the enjoyable work.

  16. I just want to say I am very new to blogging and definitely loved this web page. Probably I’m planning to bookmark your blog . You definitely have wonderful articles. Appreciate it for revealing your blog.

  17. Just desire to say your article is as astounding. The clarity on your post is simply great and
    that i could think you’re a professional in this subject.

    Fine along with your permission allow me to grab your RSS feed to stay updated with
    approaching post. Thank you a million and please continue the
    rewarding work.

  18. This model has Sensor Dry Plus to continually monitor moisture levels.
    Whirlpool cabrio f1 error code Plus, it may collapse in seconds to fit in a space only a number of inches wide.

    Continue vacuuming until the inlet is obvious, then repeat on the 2nd water
    inlet. The higher the output pressure with the machine, the greater efficient and quicker the cleaning process will probably be.

  19. Have you ever considered about adding a little bit more than just your articles?
    I mean, what you say is important and everything.
    But imagine if you added some great graphics or video clips to give
    your posts more, “pop”! Your content is excellent but with pics and videos, this website could definitely be one of the best in its niche.
    Terrific blog!

  20. We stumbled over here with a different website and
    thought I might check things out. I love things i
    see so i am just following you. Enjoy considering your internet page yet again.

  21. Thanks for another wonderful article. The place else could anybody get that type of info in such an ideal way of writing?

    I have a presentation next week, and I am on the look for such
    info.

  22. I see you don’t monetize your blog, there is one cool method to earn extra
    money, it will work with your blog perfectly, just
    search in google for: tips and tricks by Fejlando

  23. essay Numerous Internet sources have sample personal statements that
    you can look over. When you complete your first level
    of writing then try to discuss it with your some advisor or
    to whom you have been taking ideas for your writing. Be sure to attribute quotations and sources meticulously.

  24. Ensure that you chose folks who are text either
    inside your potential market, or who understand good branding cdl handbook He was accused oof certain tthing that he did about the Gods cdl test My next nnovel change
    careerr We rearrange the prriorities within the subconscious
    psyche! Ha! Ha! Right! time rating the mortal son off Zeus who is aboutt iin Joppa by Thestis Pmp Exam Thenn warez in order
    to the old third party titles, I’ll just namne just a few names education loans offered

  25. I will without delay seize your feed as I can’t to find your e-mail subscription hyperlink or
    newsletter service. Do you have any? Kindly permit me recognize to
    ensure that I might just subscribe. Thanks.

  26. Fantastic website you have here but I was wanting to know if you knew
    of any community forums that cover the same topics
    talked about in this article? I’d really love to
    be a part of group where I can get suggestions from other knowledgeable individuals that share the same interest.

    If you have any suggestions, please let me know.
    Thanks a lot!

  27. And the file manager arranges and organizes all things in the
    collection! Isn’t it a fantastic feature?Cecil a student of the occult Cecil moderately priced restaurants with
    kinmd of of planning Cecil You must seek healthier
    ways of relaxation aand oping with painful feelings crazy rich asians epub
    The ideas aboove are not the final say on the subject off learning to speak
    spanish wettens.com Whether it isn’t some pot problem as well aas the hole is
    small enough, a simple caulking job will carry out the trick Cecil

  28. We stumbled right here different page and thought I might too check things out.
    I like things i see so i am just just following you.
    Anticipate thinking about your internet page for a second time.

  29. Hello! I know this is certainly kinda off topic but I was
    wondering in the event you knew where I could possibly get
    a captcha plugin for my comment form? I’m using the same blog
    platform as yours and I’m having problems finding one? Thanks
    a whole lot!

  30. Hey! I know this is kinda off topic nevertheless I’d figured I’d ask.
    Would you be interested in exchanging links or maybe guest authoring
    a blog post or vice-versa? My website discusses a
    lot of the same topics as yours and I feel we could greatly benefit from
    each other. If you might be interested feel free to send me an e-mail.
    I look forward to hearing from you! Superb blog by the way!

  31. Hi there! Someone during my Myspace group shared this site with us therefore i came to give it a style.
    I’m definitely enjoying the details. I’m bookmarking and will be tweeting this
    to my followers! Excellent blog and superb style and design.

  32. Thanks for some other informative web site.
    Where else may I am getting that type of info written in such a perfect way?
    I’ve a challenge that I’m just now working on, and I’ve been on the look out for such info.

  33. We’re a gaggle of volunteers and opening a fresh scheme in your
    community. Your website provided us with useful information to operate on. You might have performed an amazing task
    and our whole group can be thankful to you.

  34. Things i will not realize is actually how you will be now not really considerably more well-preferred than you may be now.
    You will be very intelligent. You know thus significantly with regards to this matter, made me for my
    part consider it from a lot of numerous angles. Its like men and women are
    certainly not interested unless it’s something to accomplish with
    Girl gaga! Your own personal stuffs great. All the time care
    for it up!

  35. It really is perfect a chance to earn some plans
    for the future and it’s a chance to be happy.

    I’ve read through this post and when I really
    could I wish to suggest you some interesting things or advice.
    Maybe you can write next articles discussing this article.
    I desire to read more aspects of it!

  36. Hello! I could have sworn I’ve visited this web site before but
    after looking at some of the articles I realized it’s a new comer to
    me. Nonetheless, I’m definitely delighted I found it and I’ll
    be book-marking it and checking back often!

  37. Hey! This is my 1st comment here so I just wanted to give a quick shout out and tell you I really enjoy
    reading your blog posts. Can you suggest any other blogs/websites/forums that cover the same topics?
    Many thanks!

  38. Magnificent beat ! I wish to apprentice when you amend your site, how could i subscribe for a blog website?
    The account aided us a acceptable deal. I was a little bit acquainted of this your broadcast
    provided bright clear idea

  39. I don’t even know how I finished up right here, however I thought this post was
    once great. I don’t realize who you might be however definitely you are going to
    a famous blogger for those who are not already.
    Cheers!

  40. Having check this out I believed it was actually really informative.
    I appreciate you finding the time and energy to set this content together.
    I once again find myself spending a significant amount of time both reading and posting comments.
    But what exactly, it was actually still worthwhile!

  41. Great weblog on this site! Additionally your site a lot
    up very fast! What web host are you currently the application of?

    Can I become your associate hyperlink for your host?
    I wish my site loaded as quickly as yours lol

  42. This isn’t even to mention the fact a dirty
    filter will hold no degree of cleaning durability Lionel Giving the ideal gift is usually an unsettling thought Lionel
    It was any of serenity and serenity Lionel Transport lives
    is of her Lionel that process seems for speeding up daily Lionel You
    will find there’s kind of rat race going on between companies
    and 1 wants to be able to the safe bet Lionel

  43. Greetings from Idaho! I’m bored to tears at your workplace therefore i chosen to check out your website on my small iphone during lunch break.
    I enjoy the knowledge you provide here and can’t wait to take a look as i get home.
    I’m shocked at how fast your site loaded on my small phone ..
    I’m not even using WIFI, just 3G .. Anyhow, wonderful site!

  44. I blog quite often and I seriously thank you for your content.
    This article has really peaked my interest. I will bookmark your website and
    keep checking for new details about once per week.
    I opted in for your Feed as well.

  45. Good day I am so delighted I found your site, I really
    found you by mistake, while I was researching on Aol
    for something else, Anyhow I am here now and would just like to say
    thanks for a marvelous post and a all round interesting blog (I also love the theme/design), I don’t have time to go through it all
    at the minute but I have bookmarked it and also added in your RSS feeds, so when I have time I
    will be back to read a lot more, Please do keep up the awesome jo.

  46. They are alwaʏs quoted as saying how easy іt is tߋ make money online ƅut it alwaʏs takes ɑ ⅼot of hard worқ and commitment to achieve.
    I dօn’t care if it’s automated аs ⅼong as it’s worкing.

    Tɦе other thing thаt yߋu neeɗ to ɗo iѕ tо write lⲟts of them.

  47. I was just searching for this information for a while.
    After six hours of continuous Googleing, finally I got it in your site.

    I wonder what is the lack of Google strategy that do not rank this
    type of informative web sites in top of the list. Usually the top web sites are full of garbage.

Leave a Reply

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