Monday, March 1, 2010

The little optimization that couldn't

Let's say you represent two groups of people. If I collect one penny from each member of Group A, then, from the unbounded kindness of my heart, give one dollar to each member of Group B, has the total wealth of the groups combined become greater or less?

If you answered "greater", this article's for you! You see, there's a question you forgot to ask -- and it's a question that we as programmers forget to ask constantly.

A nicely optimized method?

In our internal core Java libraries at Google, we have a method called StringUtil.repeat(). It returns a string consisting of n copies of a base string -- so StringUtil.repeat("hey", 3) produces "heyheyhey". When I first came across it, and cleaned it up a bit, its implementation looked a little bit like this:

public static String repeat(String base, int count) {
if (base.equals("") || count == 0) {
return "";
}
if (count == 1) {
return base;
}
StringBuilder sb = new StringBuilder(base.length() * count);
for (int i = 0; i < count; i++) {
sb.append(base);
}
return sb.toString();
}

What's going on here? Well, there are four basic cases.

Case one: base is the empty string, so the result should always be the empty string. We don't want to loop and all that, so this optimization returns an empty string straight away.

Case two: count is zero. Here again, why do any actual work? We should return the empty string here and now.

Case three: count is one. We can avoid instantiating a new string by returning the original string directly!

Case four: aww nuts. In this case, we really do have to loop and create the new string. Well, at least we optimized out as much ass we could first!

In each case, we're very carefully doing the bare minimum amount of work we can! With me so far? Sounds good?

When I found this, I proceeded to make the method run even faster. Any guesses how I did it?

That's right, I simply removed all of these so-called optimizations.

Remember that to optimize a special case, you must check for that special case... in every case! That small extra cost goes to every single user of the method. And what of the benefits? Hah! Notice that the "optimized" special cases are the cases that are the fastest to compute anyway!

What's more, surprisingly enough, it doesn't really happen that often that users call a repeat() method passing zero or one as the count. Why would they? Commonly, that is. So we're "optimizing" a case that hardly even exists, at the expense of all the cases that do exist. The special-case checks were a net loss, and better off removed.

It's not like my removing them radically improved the performance of anyone's application. However, the experience is useful as a lesson. You'll encounter this same situation many times in many guises, and it will often be tempting to think about the benefits to the few rather than the overall aggregate cost to society as a whole (hmm... remind you of any politicians?)

If the Group A of my opening scenario has thousands of times more members than Group B -- not to mention that dollar really turns out to be a dime -- it's a bad deal. Just say no!

48 comments:

Sean Parsons said...

I've used the phrase "longcuts" to describe those sorts of optimisation in the past. Makes me wonder how many of these little nuggets might be in the core Java code, for example, just waiting for someone to do exactly what you've just done.

Would be interesting if it was possible to mark these sorts of shortcuts in some way and have something like caliper run tests with and without them to see which is better, so that a more informed decision can be made.

Paul said...

"Longcuts"! Love it, thanks. Nice one Sean.

jed said...

I'm finding that string concatenation can be the root of a lot of evil. Does your caller really need a String? Can you return a CharSequence that delegates to the original String and implement charAt(int) to mod the original string length and get it from that? Then you can do the work in toString() if you absolutely must…

Kartik said...

Keving, What about null checks? Do you think it is advisable to annotate local variable(s) as @NotNull or @Nullable

Kevin Bourrillion said...

This post is only about "optimization".

mk said...

Your point seems to be "weigh the likelihood of each case when optimizing."

But if the simple-minded question that readers forgot to ask was "what's the likelihood of each case"...then what's the answer? What *was* the likelihood of each case, and what was the cost of each case to optimize? Were any of them worth optimizing?

Case one (checking base.equals("")) requires another method call and does sound expensive, but cases two and three (checking the count against 0/1) sound so cheap that I might expect your JVM to optimize them away after it warms up:

if (count <=1) {
return (count == 0) ? "" : base;
} else {
// business as usual
}


Did you try to *just* remove the optimization for case 1 and see if cases 2/3 were still worth fiddling with?

If you expand this into a bigger article, I'd love to see a case study where analysis shows you that some optimizations are worthwhile, while others are too expensive.

gimenete said...

There is an optimization in the general case. Don't create the "i" variable. Just use: for(; count > 0; count--)

rahul said...

probably , we can make use of the count. If count is even , then we can utilize it to append to SB less number of times. So now words, ( try, 4), we can create trytry and then append trytry to it. If count is odd, that case needs to be dealt separate.
Anyways, I enjoyed your youtube video of collections.

Bernd Eckenfels said...

@rahul what you propose is called loop unrolling, and its typically done by the JIT, unless really needed never even think about doing it by hand, since its "optimization" can turn into a "deoptimization" on the next JIT update.

@Kartik I agree, early returns or so called guards are not only for optimization reasons, but also for read- and maintainability, which is often much more important than squeezing out the last bit of performance. Besides with EA and guards it can even get faster in the general case (cause JIT knows he does not need to do null checks anymore).

@mk I agree that the equals is badness, whereas the integer compares can be neglected. I think I would only keep the "1" case as the 0 case is handled by the loop smart anyway.

Unknown said...

Good entry. I had a similar experience with a colleague writing a kind of buffer abstraction where array operations were being done internally. He was constantly checking three or four cases--all of which would've failed immediately anyways. Java byte[] will throw arrayOutOfBounds and dereferencing a null reference will already throw a NPE...no need to check twice...

Steve

Unknown said...

in the same spirit, all arraysoutofbounds check should go away. Or at least we should have a switch in jvm to make it go away when we feel it is safe(i.e., after a period of production run).

combattery84 said...

LG Laptop Battery
SAMSUNG Laptop Battery
SONY Laptop Battery
TOSHIBA Laptop Battery
APPLE M8403 battery
APPLE A1078 Battery
APPLE A1079 battery
APPLE A1175 battery
APPLE a1185 battery
APPLE A1189 battery 1
Acer aspire 5920 battery
Acer btp-arj1 battery
Acer LC.BTP01.013 battery
Acer ASPIRE 1300 battery
Acer ASPIRE 1310 battery
Acer Aspire 1410 battery
Acer ASPIRE 1680 battery
ACER BTP-63D1 battery
ACER BTP-43D1 battery
Acer lc.btp05.001 battery
Acer aspire 3000 battery
Acer Travelmate 4000 battery
ACER aspire 5560 battery
ACER BATBL50L6 battery
ACER TravelMate 240 Battery
ACER BT.00803.004 Battery
ACER Travelmate 4002lmi battery
Acer travelmate 800 battery
Acer aspire 3613wlmi battery
Travelmate 2414wlmi battery
Acer batcl50l battery
Acer Travelmate 2300 battery
ACER aspire 3610 battery
ACER travelmate 4600 battery
Dell Latitude D800 battery

Unknown said...
This comment has been removed by the author.
Unknown said...

What about returning something like <? extends CharSequence>

A. said...

why not simply move the optimizations to the end of the code?

i.e.

if (str.length == 3) {

} else {
// optimizations
}

Unknown said...

Thanks for sharing.

Unknown said...

hp compaq 6510b charger
acer aspire 5517 adapter
dell charger inspiron n5110
apple macbook a1278 battery
macbook a1185 apple battery
dell charger vostro 1310
macbook a1181 apple battery
dell charger inspiron n4010
hp compaq nx6330 charger
acer adapter aspire 5920

Unknown said...

I really like your writing style. Nice Post keep it up.

Asus - 15.6" Laptop - 3GB Memory - 320GB Hard Drive - Brown

Asus - 15.6" Refurbished Laptop - 4GB Memory - 500GB Hard Drive - Matte Dark Brown Suit

TechLovrz said...

This is extremely helpful info!! Very good work. Everything is very interesting to learn and easy to understood. Thank you for giving information.
flaunt your style with these captions

erfgthj said...

pokemon go mod apk joystick

apkdynastys is an all-rounder in an Android Tricks field. We work hard to serve you first, and best of all and to satisfy your hunger for How-To, Tips&Tricks, Modded Games. Here you will be updated with the latest Android Tricks, Modded Games & Apps news and lots more.

Call Of Duty Mobile MOD APK

apkdynastys is an all-rounder in an Android Tricks field. We work hard to serve you first, and best of all and to satisfy your hunger for How-To, Tips&Tricks, Modded Games. Here you will be updated with the latest Android Tricks, Modded Games & Apps news and lots more.

Anti-Terrorism Shooter Mod Apk

Merlin Kristianti said...

Anda akan bisa memilih room taruhan yang anda inginkan dalam permainan Ceme ini. Dimana room taruhan yang tersedia tentunya menyediakan room taruhan kecil dan besar untuk anda.
asikqq
http://dewaqqq.club/
http://sumoqq.today/
interqq
pionpoker
bandar ceme terpercaya
freebet tanpa deposit
paito warna
syair sgp

tech zone said...

finance whatsapp groups

zero2infynite said...

Thank you for sharing wonderful article.
Ethical Hacking Training in chennai
Best Training Institute in Chennai

Devender Gupta said...

https://gizmoxo.com/facebook-stylish-names-list/
https://gizmoxo.com/netflix-cookies/
https://gizmoxo.com/free-netflix-account/
https://gizmoxo.com/netflix-mod-apk-premium/
https://gizmoxo.com/download-kingoroot-apk/

Devender Gupta said...

dtc bus app
dtc bus
dtc bus app download
dtc bus pass
dtc bus route
dtc bus route app
dtc bus app download

khushboo said...

The registrations and auditions for the Bigg Boss 13 are going to start soon. The official list of contestants is not yet announced by the officials. That will be announced by the makers on the inaugural day which is 15 the of September. bigg boss 13 contestants name list with photo Though a few rumored names are coming up as the expected celebrity contestants of the year. They are Nia Sharma, Raghav Juyal, Punit Pathak, Divyanka Tripathi, Garima Chaurasia, Ridhima Pandit, Aditya Narayan, Jasmin Bhasin, Zain Imam, Bhuvan Bam, Chetna Pande, Krystle D’Souza, and Devoleena Bhattacharjee. This year too, the show will be back with a new theme and the star host, Salman Khan. Though the theme is not declared yet officially. Stay tuned with us to know more about the show Bigg Boss 13.

Cognex Technology said...
This comment has been removed by the author.
Cloudi5 said...

Thanks for sharing your knowledge. Keep updating. For more updates visit cloudi5 Technology"

Saad Amir said...

It looks awesome stuff for learners to get in touch and seeking good captions.

Jamish said...

Music is the feed of soul for enjoying the over 40 million songs of best quality visit Spotify APK here.

BB Arora said...

40 Lakh mp3 song download pagalworld, tik tok viral song ,Mr jatt. GetSongName.com – Presenting the audio song ” 40 Lakh ” this song by Jerry Burj Ft. Ellde Fazilka , song is been written Ellde Fazilka40 Lakh mp3 song download pagalworld

Joe said...

IGCSE chemistry
CBSE chemistry
MCAT
AP Chemistry
SAT Chemistry

jeewangarg said...


Jeewan Garg is a leading digital marketing company offering the ultimate SEO services and PPC services. Google Partner in India- Hire Google Adwords Certified Partner in India. FREE consultation for How to become best Adwords Certified Partner. Call @ 9350809090 Now!

Promote Abhi - Business Chalega Tabhi/Startup Development Company said...

Thank You for your information.kindly visit us : Top Branding Companies in India

Unknown said...

Get Rapid Solutions For Norton Antivirus Related Problems..

Visit US: www.norton.com/setup

Study Pharma said...

Sasche Mohr Theory
Preservation of pharmaceutical products
Flow of fluid
Rheology full detailed
Thixotropy/ Measurement of Viscosity/ Instruments

Plumbing & HVAC Services San Diego said...

Compre documentos en línea, documentos originales y registrados.
Acerca de Permisodeespana, algunos dicen que somos los solucionadores de problemas, mientras que otros se refieren a nosotros como vendedores de soluciones. Contamos con cientos de clientes satisfechos a nivel mundial. Hacemos documentos falsos autorizados y aprobados como Permiso de Residencia Español, DNI, Pasaporte Español y Licencia de Conducir Española. Somos los fabricantes y proveedores de primer nivel de estos documentos, reconocidos a nivel mundial.

Comprar permiso de residencia,
permiso de residenciareal y falso en línea,
Compre licencia de conducir en línea,
Compre una licencia de conducir española falsa en línea,
Comprar tarjeta de identificación,
Licencia de conducir real y falsa,
Compre pasaporte real en línea,

Visit Here fpr more information. :- https://permisodeespana.com/licencia-de-conducir-espanola/
Address: 56 Guild Street, London, EC4A 3WU (UK)
Email: contact@permisodeespana.com
WhatsApp: +443455280186

John said...

Acerca de Permisodeespana, algunos dicen que somos los solucionadores de problemas, mientras que otros se refieren a nosotros como vendedores de soluciones. Contamos con cientos de clientes satisfechos a nivel mundial. Hacemos documentos falsos autorizados y aprobados como Permiso de Residencia Español, DNI, Pasaporte Español y Licencia de Conducir Española. Somos los fabricantes y proveedores de primer nivel de estos documentos, reconocidos a nivel mundial. هوروش بند

Plumbing & HVAC Services in San Diego. Call now (858) 900-9977 ✓Licensed & Insured ✓Certified Experts ✓Same Day Appointment ✓Original Parts Only ✓Warranty On Every Job. پازل بند

Elesia said...

Here we gives you opportunity to show T20 World Cup 2021 Live Streaming

Aswi said...

AFS has appreciable potential in solving the issue of the IGST refund pending. The IGST refund process for goods is straightforward. However, while this process of IGST refund, many applicants find it is in the pending stage. afs.ind.in

Tamizhakarthic said...

Thanks for the blog, Its good and valuable information.
Best Digital Marketing Training

French language classes in Chennai said...

Great Article.Thanks for the remarkable information
German Class in Chennai | Online German Classes | Online German Course

Unknown said...

nice post
HIV Treatment in India | Treatment of HIV in India | Aids Treatment in India

Chirs Marc said...

for further details Click here

clickonwebsite741♡ said...

It was my excitement discovering your site last night. I came here now hoping to find out interesting things. I was not dissatisfied. Your ideas for new methods on this subject were useful and an excellent help to myself.
토토사이트
온라인경마

Captions said...

We really like your optimizations. And we've learned a lot. Which we did not know before. We are very happy to get all these optimizations. Thank you very much

Anitya said...

Janam TV live

Divya M said...

Incredible points. Sound arguments. Keep up the great work. Read about dot net consultant chennai from Maria Academy.