Archive for August, 2009
MapReduce
Aug 4th
The computer was originally designed as a sequential processor. This notion has become ingrained in our minds. We are often bogged down by this constraint while developing algorithms.
Advancements in computers have brought in more and more parallelism but our algorithms have not started to embrace it. Map Reduce is a design paradigm which forces us to think parallel. The algorithms developed using this method as well suited for running on parallel computers.
Map Reduce Algorithms, as the name suggests, work in 2 steps. The first step called “Map” consists of tasks that can be done in parallel. This step generates the intermediate results which are then passed to the Reduce step. In the Reduce step these result is collated to generate the final results. The second step is the sequential part.
The current algorithms we have usually do the Map steps sequentially inside a loop and keep collating the results. These results are presented at the end of the loop.
As simple example, take the case of counting the no of words in a file.
// Normal algorithm public int noOfWordsInFile(String fileName) { filecount = 0; while(not eof) { line = read line from file; linecount = noOfWordsInLine(line); filecount = linecount + filecount; } return filecount; }
|
// Map Reduce algorithm public void map(String line) { lineCount = noOfWordsInLine(line); save lineCount } public void reduce(int linecount) { load fileCount; fileCount = fileCount + lineCount. save fileCount; } |
Update : Some folks though that this is my idea.. I have just rephrased what has been talked about already.
Find more details about at .. Mapreduce
GWT vs Java vs C
Aug 3rd
They say history repeats itself. Here is an instance where it happened twice.
The “C” Days
In the days of 8086 and MIPS there were different types of instruction sets for different processors. Due to this programs written in assembly language for one processor could not run on another.
The “C” approach came in as a gospel, where in the programmer can write code in one language and compile it to any instruction set. This revolutionized the computer industry in the 1970s-80s, and we saw millions of lines of code written during this time.
The “Java” Days
Then during the 1990s the same problem manifested in a different form. This time there was a different verity of Operating systems. The “c” code could not keep up with the different flavors of underlying OS operations and quickly writing ubiquitous code became a herculean task.
This is when smart folks at Sun rewrote history and invented Java. The concept was same, write code in one language then compile it such that it can be run on different platforms (OS). Though there is a slight variation, this time the compiled code runs over a Virtual machine which wraps the underlying platform. This virtual machine in turn takes care of platform variation.
The “GWT” Days
As we said earlier, History has knack of repeating itself. Now in 2000, our industry is moving towards the client server architecture. JavaScript is the leading technology for writing the rich clients these days. Many frameworks have sprung up which tries to make JavaScript development fast and easy. But again all these frameworks face the same issue as did java and c. JavaScript can run on different browser IE, FireFox, Google Chrome and many more. All these browsers have different implementations of JavaScript which cause a nightmare for developers.
Enter GWT (Google Web Toolkit). The concept is same again. The code is written in Java and its is compiled to Java Script. All the nitty-gritty’s related to browser is taken care of by the GWT compiler. This technology was released by Google around mid 2006 and it has come a long way since then. Its much stable and production ready. GWT is on its way to become a force similar to C and Java.
Conclusion
These are few designs which are so powerful that can alter the course of history. The compiler is one such thing. We have seen it revolutionize the IT industry time and again. This time it’s taken the form of GWT. As developers, it’s high time that we look upon this technology closely and prepare ourselves for the new future.