Welcome!

Wireless Authors: Pat Romanski, Yeshim Deniz, Carmen Gonzalez, Bernard Golden, Peter Silva

Related Topics: Java, XML, SOA & WOA

Java: Article

i-Technology Viewpoint: Laziness Sometimes Pays

The Gains Made by Better Algorithms Almost Always Outstrip the Gains From Better Hardware

Let me begin by a philosophical rant. There is a motto from scientific computing that carries to many areas of computer science:

/The gains made by better algorithms almost always outstrip the gains from better hardware./

I've frequently seen where algorithm improvements pay by factors of tens to tens of thousands in CPU time. One change I made in a numerical algorithm improved CPU requirements by a factor of 50,000: from weeks on a super-computer to minutes on a workstation.

Any business-savvy engineer knows that algorithm improvements come at a price: the engineer's time. Striking that balance makes software systems move forward rather than staggering to a halt in bloat and dysfunction. It also helps to use people who actually know what they are doing: knowing how to compile code doesn't make you a software engineer any more than knowing how to spell makes you a writer. End of rant.

On to (rant related) business. On most Web sites, think of how many times a data source will be used to retrieve the same data and produce the same content over and over again. Most successful services deliver a highly redundant amount of information to their users. For example, the JDJ website will deliver this (same) content to perhaps a hundred thousand users. If the servers are overtaxed, customers will experience significant delays or malfunctions.

There are several useful solutions to this. Well configured caching proxy servers come to mind, although server-side scripting make this difficult. Buying more hardware will eventually fix the problem, which may be the correct business solution.

But what about asking programmers to be a little more lazy?

For this article I've included the source for the LazyFileOutputStream. It acts just like a regular FileOutputStream except that, if created on a file that already exists, it /reads/ the data from the file instead of writes it. The stream compares what is already in the file with what you are currently writing to it. If at any point it sees there is a difference in the data you are writing this time compared to what is already there, the stream automatically switches to a write-mode that writes over the remainder of the file with the changes.

The upshot is, if your program generates the same output twice, the output file is unmodified the second time (leaving the original modification date). First, by simply changing FileOutputStream to LazyFileOutputStream, any downstream processing can use timestamp information on the files to check if they need to do anything at all. If the timestamp hasn't changed, then neither has the contents.

But wait, there's more! In addition to the standard close(), the LazyFileOutputStream also supports abort(). This method effectively states "I'm done now, leave the rest of the file alone." The remainder of the file will be the same, even without reproducing it. This means that, if you determine at an early point in the processing of the file that it's going to turn out the same, you can simply abort() to leave it alone. Its similar to the idea of not changing the modification dates on files which are rewritten with the same data, but allows for saving CPU time for the current process step as well as downstream processing..

Certain engines produce part of the template before you can conveniently intervene to decide if you really need to regenerate it. By opening up the output as a Lazy file, you can just abort() early and have the old version, with the the old modification time, around for downstream processing.

Okay, rant concluded and point made: CPUs around the planet are spinning through the same data tens of thousands of times producing the same content tens of thousands of times. Instead of buying great big servers to manage this, a smart caching policy based on lazy file writers and some modification time testing could save some sites that same wild-sounding factor of 50,000. Without having to buy 50,000 new servers.

Anecdote # 1. There is a certain technical advantage to this style of writing data as well: most storage devices are easier to read from than write to, adhering to the 80/20 rule: 80% of file access will be reads, 20% will be writes.. The LazyFileOutputStream takes advantage of that for the many files which are simply rewritten with the same content.

Anecdote # 2. There must be a few curled toes out there saying to themselves, "Why not LazyFileWriter?" There are good technical reasons for the OutputStream: the logic of the data written must be checked in its raw /byte/ format for the idea to work correctly, and you can always wrap this in an OutputStreamWriter, followed by a BufferedWriter, which is what I recommend.

Now I'm even done with the anecdotes. Have a nice day.

More Stories By Warren MacEvoy

Warren D. MacEvoy is Asst Professor of Comp Science in the department of Computer Science, Mathematics & Statistics at Mesa State College, Grand Junction, Colorado.

Comments (8) View Comments

Share your thoughts on this story.

Add your comment
You must be signed in to add a comment. Sign-in | Register

In accordance with our Comment Policy, we encourage comments that are on topic, relevant and to-the-point. We will remove comments that include profanity, personal attacks, racial slurs, threats of violence, or other inappropriate material that violates our Terms and Conditions, and will block users who make repeated violations. We ask all readers to expect diversity of opinion and to treat one another with dignity and respect.


Most Recent Comments
Bruce VanOrder 10/19/04 09:25:42 AM EDT

I remember the first PC I bought for myself ... A CompuAdd 286 with lots of memory - 2 MB RAM and a whopping 40Mb hard drive ! On this gargantuan drive I was able to put everytrhing I needed.... WordPerfect 5.1, TurboPascal 5.5, Lotus 123, dBaseIII+, etc, etc, and a few games .... AND I STILL HAD ROOM !

Now I have a Pentium with 256Mb RAM & a 20 Gb hard drive...
MS Office Professional, Borland Delphi, JBuilder, Oracle, SQL Server.

dBaseIII+ could fit on a 1.44Mb 3.5" floppy !

Those were the days my friend, we thought would never end ..
:-)

Warren MacEvoy 10/16/04 12:57:28 AM EDT

Response to Mark M.

Back in the bad-old-days designers would kick around which sort would be better to use. Now practically all sort problems are best solved with Collections.sort() or using a TreeSet or TreeMap. This is a total win situation: it's faster to write, easier to maintain, and better optimized than any roll-your-own sort. So there's almost no context: the Collections' sort is almost always better.

I'll claim LazyFileOutputStream sits one step lower than this: it's almost never worse, and sometimes better than a plain FileOutputStream. If you are writing small chunks to an unbuffered stream (or flushing() after every character), then the adapter pattern it uses to implement its magic may cost you a little in time (but negligibly compared to other costs related to this approach). There is also a buffer overhead because of the (IMHO silly) decision to leave fundamental memory operations like POSIX memcmp out of the java system libraries. But you're writing to a file, and well, that's just kinda slow.

But what you gain is information. When you're done .isDifferent() will tell you if there was a change without having to keep the old copy around to see if there was a change, and the timestamps will tell you even if downstream processing occurs in some logically distant place, like another process.

So there's very little to lose in almost any situation, and a great deal to gain if:

1. your template processing is file-based.
2. you generally only rebuild things unless
they are out of date with respect to their dependencies.

Without timestamp information, implementing part 2 may have seemed like a waste of time (which it would have been, since every template rebuild would look like it was different), but switching to LazyFileOutputStreams can make it effective.

Warren MacEvoy 10/15/04 07:07:48 PM EDT

My apologies, but somehow the wrong link was placed for the source file. The correct adddress to the LazyFileOutputStream which the article refers to is:

http://bpp.sourceforge.net/download/bpp-0.8.5b/src/bpp/LazyFileOutputStr...

JavaDoc'ed at:
http://bpp.sourceforge.net/download/bpp-0.8.5b/doc/javadoc/index.html

You might also note that the class uses abandon() instead of abort(), which is a minor change.

This has nothing to do with

http://www.jdocs.com/ant/1.6.2/api/org/apache/tools/ant/util/LazyFileOut...

Again, my apologies for any confusion this may have created...

Mark M 10/15/04 11:47:56 AM EDT

Response to Warren M.

The key question is not how much more complicated it is to write the class. The key question is what is the context of the problem? Too often generic solutions to problems are presented (even if that is not always the author's intention, these things can be easily mis-interpreted as such) and their validity/necessity almost always depends upon the context of the problem. You yourself emphasize the need for context in your response to Jim M. You have created a useful tool for yourself given the context of the problem you were trying to solve. When the next programmer comes along, the context may be completely different. Often times, many are lead to believe incorrectly in one size fits all philosophies, for instance, it is widely viewed within the industry by working folk like myself that the notions of Bertand Meyer and Kent Beck conflict when in fact they both may be valid solutions under differing contexts. Lack of context is the biggest complaint I have with books on process in this industry. Without it, many arguments are neither valid nor invalid, just ambiguous. There is at least one really bright fella who says a lot about context when he writes. His name is Fred Brooks.

Warren MacEvoy 10/14/04 10:42:09 PM EDT

Response to Mark M.

I agree that it usually a waste of time to optimize without profiling to know where your problems are. You must also have a business argument that the problem needs to be solved and that optimizations are the best way to solve it.

It is wrong to think that optimizations must be complicated. There's plenty of code out there that make poor or no use of Collections, which would be faster to write, maintain and execute if better choices were made. Good programmers should know how to use these features to improve turnaround, defects, and efficiency (the rant part of my article).

The purpose of the article is to point another kind of "low hanging fruit" related to file processing. After all, how much more complicated is it to write "LazyFileOutputStream" compared to "FileOutputStream"?

Response to Jim M.

Completely? Substantially. Completely claims they have nothing to learn from each other, yet there are many business problems with a short lifetime and plenty of rustic scientific codes are dutifully solving the problems they were designed to solve twenty and thirty years after they were written.

Again, the optimizations I'm suggesting don't need to be complicated. The LazyFileOutputStream is as simple as the code it replaces. How does that detriment readability or maintainability?

As far as longevity, I like the analogy of building a wall. The last row of the wall (business or scientific) can be very slipshod and the wall will still be a wall. Much software is written with the (sometimes correct) assumption that they will be part of the last row of bricks. But people change their minds, and what was once the last row is not anymore. In the real world, this is why tens of thousands of people die when there is an earthquake in a third-world country.

Should businesses be happy with a software design model analogous to the slums of Mexico City?

Response to Justin S.

Edit one line of an XML configuration file, changing one attribute. Many elements of your design depend on this XML file, but almost none of them depend on this one attribute. Your solution suggests detailed code to see if the attributes each dependency requires has changed, which would be hugely complicated to write and maintain.

Mine asks that you to rebuild the elements that directly depend on the configuration file. If they don't change, then you don't have to propagate updates further. Not a perfect optimization, but a much more practical one.

The LazyFileOutputStream supports your idea if you choose to pursue it. If a template decides it does not need to regenerate a target, it can simply abort() to leave the current contents alone without going to the trouble of regenerating all of it.

Justin Sadowski 10/14/04 08:27:34 PM EDT

While I agree with your thoughts about the value of avoiding writing the same data over and over, I have to disagree with your LazyFileOutputStream solution. If you find that you are writing the same data to the same file repeatedly, I would suggest that you improve this by avoiding the rewriting altogether, instead of just making the rewriting more efficient.

For example, perhaps you are writing the same output repeatedly because you are operating on the same input; i.e. the data in a database hasn't changed, or a source XML file hasn't changed. If you can detect your input hasn't been modified, you can avoid writing the output altogether.

I would like to hear more details about the specific situation(s) that you have used LazyFileOutputStream -- I would be interested to hear an example of a situation where my logic above does not apply.

Jim T. 10/14/04 07:09:02 PM EDT

Scientific computing and business computing are completely different. In the scientific communality you usually have a very small number of highly skilled people working on a program. That just isn't so in the business world. In the business world I care much more about readability and maintainability rather than speed for 99% of our code. In science, nobody will be using my programs 5 years from now, the data will have all been analyzed and the papers published, in business, the exact same code will be used 5 years from now (or at least it will be for the basis of the code). I believe this is true because it is true of my code from 5 years ago. The physics code is gone/useless and the business code is being resold every day.

mark mcconkey 10/14/04 05:51:12 PM EDT

Several years back I began reading Kent Beck's stuff (XP) and it struck a chord for me because many of my experiences were similar. I believe Kent's general notion is something to the effect that one should not optimize up front because its too difficult to predict the future, and the majority of the time you will have made your code unreadable for no reason whatsoever. Of course, any seasoned programmer has experienced enough to have a feel for when big troubles are over the hill and thus that some optimization up front will be needed. I think though, that what is missing in your article is a lack of discussion of context. If I have 3 weeks to finish something that will take 6 and 50 big whigs in a fortune 500 company have goals dependent upon the completion of my software, it doesn't matter how clever I am. It matters how fast I can produce what is needed. On the other hand, the creators of Amazon probably needed to be quite clever in order to deal with the magnitude of hits on their servers. Without context, its sort of useless to talk about optimization.

@ThingsExpo Stories
SYS-CON Events announced today that Matrix.org has been named “Silver Sponsor” of Internet of @ThingsExpo, which will take place on November 4–6, 2014, at the Santa Clara Convention Center in Santa Clara, CA. Matrix is an ambitious new open standard for open, distributed, real-time communication over IP. It defines a new approach for interoperable Instant Messaging and VoIP based on pragmatic HTTP APIs and WebRTC, and provides open source reference implementations to showcase and bootstrap the new standard. Our focus is on simplicity, security, and supporting the fullest feature set.
Predicted by Gartner to add $1.9 trillion to the global economy by 2020, the Internet of Everything (IoE) is based on the idea that devices, systems and services will connect in simple, transparent ways, enabling seamless interactions among devices across brands and sectors. As this vision unfolds, it is clear that no single company can accomplish the level of interoperability required to support the horizontal aspects of the IoE. The AllSeen Alliance, announced in December 2013, was formed with the goal to advance IoE adoption and innovation in the connected home, healthcare, education, aut...
The Internet of Things (IoT) is making everything it touches smarter – smart devices, smart cars and smart cities. And lucky us, we’re just beginning to reap the benefits as we work toward a networked society. However, this technology-driven innovation is impacting more than just individuals. The IoT has an environmental impact as well, which brings us to the theme of this month’s #IoTuesday Twitter chat. The ability to remove inefficiencies through connected objects is driving change throughout every sector, including waste management. BigBelly Solar, located just outside of Boston, is trans...
SYS-CON Events announced today that Red Hat, the world's leading provider of open source solutions, will exhibit at Internet of @ThingsExpo, which will take place on November 4–6, 2014, at the Santa Clara Convention Center in Santa Clara, CA. Red Hat is the world's leading provider of open source software solutions, using a community-powered approach to reliable and high-performing cloud, Linux, middleware, storage and virtualization technologies. Red Hat also offers award-winning support, training, and consulting services. As the connective hub in a global network of enterprises, partners, a...

SUNNYVALE, Calif., Oct. 20, 2014 /PRNewswire/ -- Spansion Inc. (NYSE: CODE), a global leader in embedded systems, today added 96 new products to the Spansion® FM4 Family of flexible microcontrollers (MCUs). Based on the ARM® Cortex®-M4F core, the new MCUs boast a 200 MHz operating frequency and support a diverse set of on-chip peripherals for enhanced human machine interfaces (HMIs) and machine-to-machine (M2M) communications. The rich set of periphera...

The only place to be June 9-11 is Cloud Expo & @ThingsExpo 2015 East at the Javits Center in New York City. Join us there as delegates from all over the world come to listen to and engage with speakers & sponsors from the leading Cloud Computing, IoT & Big Data companies. Cloud Expo & @ThingsExpo are the leading events covering the booming market of Cloud Computing, IoT & Big Data for the enterprise. Speakers from all over the world will be hand-picked for their ability to explore the economic strategies that utility/cloud computing provides. Whether public, private, or in a hybrid form, clo...
Software AG helps organizations transform into Digital Enterprises, so they can differentiate from competitors and better engage customers, partners and employees. Using the Software AG Suite, companies can close the gap between business and IT to create digital systems of differentiation that drive front-line agility. We offer four on-ramps to the Digital Enterprise: alignment through collaborative process analysis; transformation through portfolio management; agility through process automation and integration; and visibility through intelligent business operations and big data.
The Transparent Cloud-computing Consortium (abbreviation: T-Cloud Consortium) will conduct research activities into changes in the computing model as a result of collaboration between "device" and "cloud" and the creation of new value and markets through organic data processing High speed and high quality networks, and dramatic improvements in computer processing capabilities, have greatly changed the nature of applications and made the storing and processing of data on the network commonplace.
Be Among the First 100 to Attend & Receive a Smart Beacon. The Physical Web is an open web project within the Chrome team at Google. Scott Jenson leads a team that is working to leverage the scalability and openness of the web to talk to smart devices. The Physical Web uses bluetooth low energy beacons to broadcast an URL wirelessly using an open protocol. Nearby devices can find all URLs in the room, rank them and let the user pick one from a list. Each device is, in effect, a gateway to a web page. This unlocks entirely new use cases so devices can offer tiny bits of information or simple i...
The Internet of Things (IoT) is going to require a new way of thinking and of developing software for speed, security and innovation. This requires IT leaders to balance business as usual while anticipating for the next market and technology trends. Cloud provides the right IT asset portfolio to help today’s IT leaders manage the old and prepare for the new. Today the cloud conversation is evolving from private and public to hybrid. This session will provide use cases and insights to reinforce the value of the network in helping organizations to maximize their company’s cloud experience.
Things are being built upon cloud foundations to transform organizations. This CEO Power Panel at 15th Cloud Expo, moderated by Roger Strukhoff, Cloud Expo and @ThingsExpo conference chair, will address the big issues involving these technologies and, more important, the results they will achieve. How important are public, private, and hybrid cloud to the enterprise? How does one define Big Data? And how is the IoT tying all this together?
TechCrunch reported that "Berlin-based relayr, maker of the WunderBar, an Internet of Things (IoT) hardware dev kit which resembles a chunky chocolate bar, has closed a $2.3 million seed round, from unnamed U.S. and Switzerland-based investors. The startup had previously raised a €250,000 friend and family round, and had been on track to close a €500,000 seed earlier this year — but received a higher funding offer from a different set of investors, which is the $2.3M round it’s reporting."
The Industrial Internet revolution is now underway, enabled by connected machines and billions of devices that communicate and collaborate. The massive amounts of Big Data requiring real-time analysis is flooding legacy IT systems and giving way to cloud environments that can handle the unpredictable workloads. Yet many barriers remain until we can fully realize the opportunities and benefits from the convergence of machines and devices with Big Data and the cloud, including interoperability, data security and privacy.
All major researchers estimate there will be tens of billions devices - computers, smartphones, tablets, and sensors - connected to the Internet by 2020. This number will continue to grow at a rapid pace for the next several decades. Over the summer Gartner released its much anticipated annual Hype Cycle report and the big news is that Internet of Things has now replaced Big Data as the most hyped technology. Indeed, we're hearing more and more about this fascinating new technological paradigm. Every other IT news item seems to be about IoT and its implications on the future of digital busines...
Cultural, regulatory, environmental, political and economic (CREPE) conditions over the past decade are creating cross-industry solution spaces that require processes and technologies from both the Internet of Things (IoT), and Data Management and Analytics (DMA). These solution spaces are evolving into Sensor Analytics Ecosystems (SAE) that represent significant new opportunities for organizations of all types. Public Utilities throughout the world, providing electricity, natural gas and water, are pursuing SmartGrid initiatives that represent one of the more mature examples of SAE. We have s...
The Internet of Things needs an entirely new security model, or does it? Can we save some old and tested controls for the latest emerging and different technology environments? In his session at Internet of @ThingsExpo, Davi Ottenheimer, EMC Senior Director of Trust, will review hands-on lessons with IoT devices and reveal privacy options and a new risk balance you might not expect.
IoT is still a vague buzzword for many people. In his session at Internet of @ThingsExpo, Mike Kavis, Vice President & Principal Cloud Architect at Cloud Technology Partners, will discuss the business value of IoT that goes far beyond the general public's perception that IoT is all about wearables and home consumer services. The presentation will also discuss how IoT is perceived by investors and how venture capitalist access this space. Other topics to discuss are barriers to success, what is new, what is old, and what the future may hold.
Swiss innovators dizmo Inc. launches its ground-breaking software, which turns any digital surface into an immersive platform. The dizmo platform seamlessly connects digital and physical objects in the home and at the workplace. Dizmo breaks down traditional boundaries between device, operating systems, apps and software, transforming the way users work, play and live. It supports orchestration and collaboration in an unparalleled way enabling any data to instantaneously be accessed on any surface, anywhere and made interactive. Dizmo brings fantasies as seen in Sci-fi movies such as Iro...
There’s Big Data, then there’s really Big Data from the Internet of Things. IoT is evolving to include many data possibilities like new types of event, log and network data. The volumes are enormous, generating tens of billions of logs per day, which raise data challenges. Early IoT deployments are relying heavily on both the cloud and managed service providers to navigate these challenges. In her session at 6th Big Data Expo®, Hannah Smalltree, Director at Treasure Data, to discuss how IoT, Big Data and deployments are processing massive data volumes from wearables, utilities and other mach...
This Internet of Nouns trend is still in the early stages and many of our already connected gadgets do provide human benefits over the typical infotainment. Internet of Things or IoT. You know, where everyday objects have software, chips, and sensors to capture data and report back. Household items like refrigerators, toilets and thermostats along with clothing, cars and soon, the entire home will be connected. Many of these devices provide actionable data - or just fun entertainment - so people can make decisions about whatever is being monitored. It can also help save lives.