In a recent discussion about the quality of software I was confronted with the following question:
"Picture a developer writing mediocre software. His product is published on the App-store and is an instant hit. Another guy develops an application and the internal quality is second to none. After publishing his application, he sells one license per week. Which of these two guys is the smart one?"
Obviously the first developer was more able to identify the needs of his potential customers. At least better than his competitor. But the discussion was not about marketing, it was about quality of software.
Making money developing software is the worst argument for delivering mediocre code.
November 10, 2012
October 02, 2012
Notification pattern vs. Observer
In a previous article I wrote about the Notification pattern and it's implementation in Javascript, the language I've been using the last couple of months to implement an application allowing users to design greeting cards online using a web browser.
From a technical point of view the application would best have been based on SVG or the HTML5 CANVAS element, but that's a different story altogether. The application uses HTML and CSS and every trick -even those not in the books- to perform it's job. These tricks mostly relate to CSS-magic and a lot of Javascript to make IE perform tasks that do not require programming for other browsers. Sigh!
But enough on that, let's get back to the main subject of this blogpost, comparing the Notification-pattern to the Observer pattern.
Observer pattern
Observer is a design pattern where observers can register with a subject that implements the observable interface. The interface defines methods for registering and unregistering as observer. The subject is responsible for keeping track of observers.
The goal of this pattern to allow observers to be notified of a state-change in the subject, allowing the observers to take appropriate action and keep in sync with the state of the subject. This sounds like an ideal solution applicable in many situations. And in some situations it indeed is. But there are major drawbacks to the pattern.
Object life-cycle
During application execution, objects come and go. In interactive applications mostly because of user interaction. Let's consider a simple drawing application with a canvas like area. The application allows the user to create objects (Images, text etc.) and manipulate these. The application has a tools palette whose contents depends on the currently selected object. The contents of the tools palette is determined by the type of object currently selected and the state of the object.
Such a situation implies the tools palette (or more likely: it's controller) needs to be informed when new objects are instantiated. It needs to have access to each and every object capable of instantiating objects relevant to the tools palette. Next to that it needs to be registered as observer with all these objects.
This is the major drawback of the observer pattern. A shortcoming that can be remedied by introducing a third party: the Notifier.
Notification pattern
The notification pattern introduces a third party that decouples observer and observable. This decoupling has several implications. Observers need not register with each and every observable. They register with the notifier for the receipt of given notifications. Observers also aren't bothered anymore with the complications caused by instantiation of new objects. A final benefit is that observables are relieved of implementing the interface keeping track of all observers and distributing messages to these observers. In the notification pattern, these tasks are performed by the notifier.
Considering all these benefits, situations where use of the observer pattern is favorable over the notification pattern will be rare.
In the near future I will post a live example showing a use-case of the notification pattern.
Update- The example and extensive documentation is available: Notifier design pattern.
From a technical point of view the application would best have been based on SVG or the HTML5 CANVAS element, but that's a different story altogether. The application uses HTML and CSS and every trick -even those not in the books- to perform it's job. These tricks mostly relate to CSS-magic and a lot of Javascript to make IE perform tasks that do not require programming for other browsers. Sigh!
But enough on that, let's get back to the main subject of this blogpost, comparing the Notification-pattern to the Observer pattern.
Observer pattern
Observer is a design pattern where observers can register with a subject that implements the observable interface. The interface defines methods for registering and unregistering as observer. The subject is responsible for keeping track of observers.
The goal of this pattern to allow observers to be notified of a state-change in the subject, allowing the observers to take appropriate action and keep in sync with the state of the subject. This sounds like an ideal solution applicable in many situations. And in some situations it indeed is. But there are major drawbacks to the pattern.
Object life-cycle
During application execution, objects come and go. In interactive applications mostly because of user interaction. Let's consider a simple drawing application with a canvas like area. The application allows the user to create objects (Images, text etc.) and manipulate these. The application has a tools palette whose contents depends on the currently selected object. The contents of the tools palette is determined by the type of object currently selected and the state of the object.
Such a situation implies the tools palette (or more likely: it's controller) needs to be informed when new objects are instantiated. It needs to have access to each and every object capable of instantiating objects relevant to the tools palette. Next to that it needs to be registered as observer with all these objects.
This is the major drawback of the observer pattern. A shortcoming that can be remedied by introducing a third party: the Notifier.
Notification pattern
The notification pattern introduces a third party that decouples observer and observable. This decoupling has several implications. Observers need not register with each and every observable. They register with the notifier for the receipt of given notifications. Observers also aren't bothered anymore with the complications caused by instantiation of new objects. A final benefit is that observables are relieved of implementing the interface keeping track of all observers and distributing messages to these observers. In the notification pattern, these tasks are performed by the notifier.
Considering all these benefits, situations where use of the observer pattern is favorable over the notification pattern will be rare.
In the near future I will post a live example showing a use-case of the notification pattern.
Update- The example and extensive documentation is available: Notifier design pattern.
September 06, 2012
Erlang r15b02 released.
Today, Erlang R15B02 was released. I picked up the 64-bit Mac OS X release release from Erlang Solutions. Installation took only a few minutes. I'm now running tests on my code against the new Erlang version. So far everything looks good.
June 13, 2012
The Times They Are A Changing
I am currently working on a web-project that unavoidably makes use of transformations on HTML-elements. The first version allows the user to select an object on a webpage and rotate it. In future versions users will probably will be able to perform other transformations on the object (e.g. skew, scale or perspective). My current implementation uses a jQuery slider to allow the user to rotate the selected object.
I was happily programming along and the design and implementation took me about half a day. That was until I checked what my implementation looked like in Internet Explorer versions 8 and 7. That's where the horror kicked in.
Rotation in all browsers (including IE 9 to be fair) was around the center of the selected object. But with IE 7 and IE 8, the point of rotation seemed to change in an inimitable way.
The trouble with DXImageTransform.Microsoft.Matrix
Studying the documentation of this filter one is lead to expect that the top-left of the object is the point of the rotation. But this simply is not the case. Microsoft took the liberty to augment the transformation you perform with a free-of-charge transformation from the boys in Redmond themselves.
As far as I was able to check, the free-of-charge transformation makes sure that the top-left of the boundingbox after rotating an element gets the same position as the top-left of the original element. While this might sound plausible, it actually is nonsens. One executes a transformation on an object and does not expect a free-of-charge extra transformation to be part of the deal. MS's documentation does not mention the extra transformation, let alone that it explains how it can be undone.
Check this example to see the ugly effect of this transformation. Click "huwelijkskaartjes" and next click on the card showing the text "Wij gaan trouwen". Now click on an element on the card and play around with the slider labeled "Rotatie".
The example is the version of the application I am currently re-implementing. Whatever browser you're using, rotation of an object mimics the way IE rotates an element. After days of struggle my predecessors capitulated. Unable to fix the wrongdoings of DXImageTransform.Microsoft.Matrix they decided the simplest way to tackle this was to make other browsers behave like IE. And indeed it was!
Another Redmond-Monkey pulling my leg.
I refused to capitulate but it took me several days and a sleepless night to tackle this problem. The sad part is that my solution works with IE 7, not with IE 8. Some intellectual in Redmond decided that an inner HTML-element should not take the transformations of the parent-element into account if the position of the inner-element is "absolute". This is where I capitulated. I managed to trick IE into rotating around the center of the object and my solution did not work in IE-8. So I finally capitulated and decided to block IE-8 using the following construct:
<!--[if lt IE 9]>
<meta http-equiv="X-UA-Compatible" content="IE=7,9" >
<![endif]-->
History haunts Microsoft
The dominant position of Microsoft with a 90% marketshare is long gone. Thanks to open-source initiatives -Mozilla Firefox, KHTML (Webkit)- IE's marketshare is rapidly dwindling. A couple of years ago Microsoft's filters provided capabilities beyond any other browser. The filters also introduce idiosyncrasies that are very difficult to overcome.
In my current project it took me half a day to implement the rotation functionality for all modern browsers -Mozilla, Safari, Chrome, IE-9 and Opera. To get it working on IE-7 took me several days.
Until now my client is concerned about IE-7 and IE-8. My client wants me to deliver software that works on IE-7 and IE-8. He's a lot less concerned about older versions of Mozilla, Chrome, Safari and Opera. For those browsers my implementation only needs to support the latest stable release.
Turn of the tables
With MS's dwindling browser-share it becomes more and more difficult to justify the extra effort to make web-sites and web-applications work well with MS's legacy browsers. Most versions of Mozilla, Safari, Chrome and Opera all work perfectly on most versions of Windows.
In times long gone one would encounter websites that stated "This site is best viewed on Internet Explorer version xx.xx". It's about time we turned the tables and used our browser-sniffing to tell users they're using a sub-standard browser and should switch to a non-MS alternative.
Let's be fair to Microsoft
We must be fair to Microsoft and give them credit for what they've accomplished. So what did they accomplish? Let's compare MS to Opera. A couple of years ago about 1.000 people within Microsoft where involved with Internet Explorer and Microsoft spend around $100 million per annum on Internet Explorer.
Today, Opera as a company has a total of 700 employees, part of whom work on the Opera browser. Their budget doesn't even come close to the $100 million per annum MS invested in Internet Explorer. With their limited resources Opera produced a browser that with almost every release was far ahead of Microsoft's Internet Explorer.
So let's be fair indeed and conclude that a small company like Opera in each and every way surpassed Microsoft. Opera had -compared to Microsoft- hardly any resources. Only a few people and a very limited budget. But the browser they delivered beat IE in each and every version in each and every aspect.
What about the future, IE-9 and IE-10?
Frankly, I couldn't care less about IE-9 or IE-10. Microsoft's market share is dwindling and rightly so. I'll use any trick in the book to convince my clients to completely neglect Microsoft and IE. MS produces a browser that adheres to the W3C standards? Fine with me. But I actually couldn't care less and will do my utmost to convince my clients of the same. For the times they are a changing and MS no longer dictates the WWW.
I was happily programming along and the design and implementation took me about half a day. That was until I checked what my implementation looked like in Internet Explorer versions 8 and 7. That's where the horror kicked in.
Rotation in all browsers (including IE 9 to be fair) was around the center of the selected object. But with IE 7 and IE 8, the point of rotation seemed to change in an inimitable way.
The trouble with DXImageTransform.Microsoft.Matrix
Studying the documentation of this filter one is lead to expect that the top-left of the object is the point of the rotation. But this simply is not the case. Microsoft took the liberty to augment the transformation you perform with a free-of-charge transformation from the boys in Redmond themselves.
As far as I was able to check, the free-of-charge transformation makes sure that the top-left of the boundingbox after rotating an element gets the same position as the top-left of the original element. While this might sound plausible, it actually is nonsens. One executes a transformation on an object and does not expect a free-of-charge extra transformation to be part of the deal. MS's documentation does not mention the extra transformation, let alone that it explains how it can be undone.
Check this example to see the ugly effect of this transformation. Click "huwelijkskaartjes" and next click on the card showing the text "Wij gaan trouwen". Now click on an element on the card and play around with the slider labeled "Rotatie".
The example is the version of the application I am currently re-implementing. Whatever browser you're using, rotation of an object mimics the way IE rotates an element. After days of struggle my predecessors capitulated. Unable to fix the wrongdoings of DXImageTransform.Microsoft.Matrix they decided the simplest way to tackle this was to make other browsers behave like IE. And indeed it was!
Another Redmond-Monkey pulling my leg.
I refused to capitulate but it took me several days and a sleepless night to tackle this problem. The sad part is that my solution works with IE 7, not with IE 8. Some intellectual in Redmond decided that an inner HTML-element should not take the transformations of the parent-element into account if the position of the inner-element is "absolute". This is where I capitulated. I managed to trick IE into rotating around the center of the object and my solution did not work in IE-8. So I finally capitulated and decided to block IE-8 using the following construct:
<!--[if lt IE 9]>
<meta http-equiv="X-UA-Compatible" content="IE=7,9" >
<![endif]-->
This construct is ignored by non-MS browsers. But for Internet Explorer, this causes IE-8 to behave like IE-7.
History haunts Microsoft
The dominant position of Microsoft with a 90% marketshare is long gone. Thanks to open-source initiatives -Mozilla Firefox, KHTML (Webkit)- IE's marketshare is rapidly dwindling. A couple of years ago Microsoft's filters provided capabilities beyond any other browser. The filters also introduce idiosyncrasies that are very difficult to overcome.
In my current project it took me half a day to implement the rotation functionality for all modern browsers -Mozilla, Safari, Chrome, IE-9 and Opera. To get it working on IE-7 took me several days.
Until now my client is concerned about IE-7 and IE-8. My client wants me to deliver software that works on IE-7 and IE-8. He's a lot less concerned about older versions of Mozilla, Chrome, Safari and Opera. For those browsers my implementation only needs to support the latest stable release.
Turn of the tables
With MS's dwindling browser-share it becomes more and more difficult to justify the extra effort to make web-sites and web-applications work well with MS's legacy browsers. Most versions of Mozilla, Safari, Chrome and Opera all work perfectly on most versions of Windows.
In times long gone one would encounter websites that stated "This site is best viewed on Internet Explorer version xx.xx". It's about time we turned the tables and used our browser-sniffing to tell users they're using a sub-standard browser and should switch to a non-MS alternative.
Let's be fair to Microsoft
We must be fair to Microsoft and give them credit for what they've accomplished. So what did they accomplish? Let's compare MS to Opera. A couple of years ago about 1.000 people within Microsoft where involved with Internet Explorer and Microsoft spend around $100 million per annum on Internet Explorer.
Today, Opera as a company has a total of 700 employees, part of whom work on the Opera browser. Their budget doesn't even come close to the $100 million per annum MS invested in Internet Explorer. With their limited resources Opera produced a browser that with almost every release was far ahead of Microsoft's Internet Explorer.
So let's be fair indeed and conclude that a small company like Opera in each and every way surpassed Microsoft. Opera had -compared to Microsoft- hardly any resources. Only a few people and a very limited budget. But the browser they delivered beat IE in each and every version in each and every aspect.
What about the future, IE-9 and IE-10?
Frankly, I couldn't care less about IE-9 or IE-10. Microsoft's market share is dwindling and rightly so. I'll use any trick in the book to convince my clients to completely neglect Microsoft and IE. MS produces a browser that adheres to the W3C standards? Fine with me. But I actually couldn't care less and will do my utmost to convince my clients of the same. For the times they are a changing and MS no longer dictates the WWW.
May 12, 2012
Event notification pattern in Javascript
The event notification pattern is widely used in Model-View-Controller based applications but is also applicable in other situations. The pattern allows unrelated objects to communicate information without having any knowledge about each others functionality. The pattern obeys the law of Demeter, also known as the principle of least knowledge. Sensible use of the pattern helps developers avoid a lot of messy code.
The impementation I wrote has the following functions:
Notifier.instance()
Returns the singleton notifier instance. The notifier instance provides methods allowing objects to post notifications and register or unregister for the receipt of notifications.
The instance has the following methods:
registerObserver(anObserver, msg, aMethod)
msg: the messages the observer wants to receive.
anObserver: the object that wants to observe.
aMethod: the function to invoke on the observer upon
receiving the given message. The function is
invoked with two arguments, the message (usually
a string) and a notification object:
{sender: aSender, userInfo: theUserInfo}. aSender
and theUserInfo being the arguments given in the
call to postNotification.
unregisterObserver(anObserver[, msg])
anObserver: the observing object.
msg: the message the observer previously registered
for. If msg is undefined the observer will be
unregistered for any message it was registered.
postNotification(msg[, userParams])
msg: the message
userParams: additional information possibly accompanying
the message.
Now imagine having a user-interface element on a webpage. Let's say a delete button the user clicks when he wants to delete the currently selected record on display. Ideally the button should not be bothered with details on how to remove the record from the database, nor how to remove the visual representation of the record. It's sole responsibility is to inform others it was clicked. Here's an example of a delete button using the event notification pattern:
<INPUT TYPE=BUTTON
onclick="Notifier.instance().postNotification('Delete');"
VALUE="delete">
If the button is clicked it performs its sole duty: notifying others it was clicked.
Let's have a peek at the ViewController responsible for removing the visual representation of the record:
This code clearly shows the beauty of the event notification pattern. The tablerows have no knowledge of the controllers and the controllers have no knowledge of the user-interface elements.
I implemented this pattern on a project for one of my customers. So unfortunately I feel not at liberty to disclose the source-code. Thus I'll do the next best thing and publish the boilerplate for the Notifier:
I hope the boilerplate gives a good hint at how to implement this pattern. Remember, programming should be fun and in no way should lead to an uncoordinated mess of statements. This pattern is useful in many situations and will help you avoid messy code where objects unwillingly have knowledge of the functionality of a myriad of other objects.
Having problems implementing this pattern in whatever language? Give me a call at janwillem.luiten at gmail . com!
The impementation I wrote has the following functions:
Notifier.instance()
Returns the singleton notifier instance. The notifier instance provides methods allowing objects to post notifications and register or unregister for the receipt of notifications.
The instance has the following methods:
registerObserver(anObserver, msg, aMethod)
msg: the messages the observer wants to receive.
anObserver: the object that wants to observe.
aMethod: the function to invoke on the observer upon
receiving the given message. The function is
invoked with two arguments, the message (usually
a string) and a notification object:
{sender: aSender, userInfo: theUserInfo}. aSender
and theUserInfo being the arguments given in the
call to postNotification.
unregisterObserver(anObserver[, msg])
anObserver: the observing object.
msg: the message the observer previously registered
for. If msg is undefined the observer will be
unregistered for any message it was registered.
postNotification(msg[, userParams])
msg: the message
userParams: additional information possibly accompanying
the message.
Now imagine having a user-interface element on a webpage. Let's say a delete button the user clicks when he wants to delete the currently selected record on display. Ideally the button should not be bothered with details on how to remove the record from the database, nor how to remove the visual representation of the record. It's sole responsibility is to inform others it was clicked. Here's an example of a delete button using the event notification pattern:
<INPUT TYPE=BUTTON
onclick="Notifier.instance().postNotification('Delete');"
VALUE="delete">
If the button is clicked it performs its sole duty: notifying others it was clicked.
We'll write a controller class and make an instance of that class responsible for keeping track of the selected record and removing the visual representation when it receives a notification to do so. Keeping track of selection is simple. We display a selection of records in a table and supply a onclick attribute for each row in the table:
<tr id="4" onclick="Notifier.instance().postNotification('Select', this.id);">
We could have yet another class (a model class) being responsible for performing the magic of having the server-side application remove the record from the database.
Let's have a peek at the ViewController responsible for removing the visual representation of the record:
This code clearly shows the beauty of the event notification pattern. The tablerows have no knowledge of the controllers and the controllers have no knowledge of the user-interface elements.
I implemented this pattern on a project for one of my customers. So unfortunately I feel not at liberty to disclose the source-code. Thus I'll do the next best thing and publish the boilerplate for the Notifier:
I hope the boilerplate gives a good hint at how to implement this pattern. Remember, programming should be fun and in no way should lead to an uncoordinated mess of statements. This pattern is useful in many situations and will help you avoid messy code where objects unwillingly have knowledge of the functionality of a myriad of other objects.
Having problems implementing this pattern in whatever language? Give me a call at janwillem.luiten at gmail . com!
April 28, 2012
Study, choices and focus
Choices, choices, choices.
In the past few weeks I've been looking into a number of things I would like to study in the coming months. On the database side I had a look at NoSQL solutions. Notably CouchDB, CouchBase and MongoDB. I installed all of these on my Mac and experimented a couple of hours with each of them.
Programming languages.
I had a look at Scala and Erlang. Languages I never used before and that both present me with a few new concepts. I implemented one chore in Scala and multiple chores in Erlang. I published my Scala chore and the Erlang equivalent on this blog (Erlang chore here, Scala chore here).
On Rosetta Code I completed three simple tasks in Erlang. Count occurrences of a substring, HQ9+ and Ceasar cipher. These are, from a computer science point of view, simple chores. The idea behind implementing them was not they would present me with an intellectual challenge. The goal was to get familiar with the syntax. To get a feel for the beauty or ugliness and the possibilities and limitations of these languages.
Limitations.
Now it's about time to make up my mind what to study the coming months. I can't study all these things in parallel. Next to the intellectual challenge this would present, I've got a day-time job to attend. Besides that the missus and our children, while very patient, also deserve attention. Luckily my Mac is in the living room. That gives me, the missus and the kids a sense of togetherness while each doing our own thing. Here's a difference with my previous live where a subject would totally "suck me in". Completely unable to react or respond to events in my environment. Now I happily chat with the missus or the kids while figuring out map/reduce in CouchDB or hammering out some code in Erlang or Scala.
Choice of language.
Back to the choice of language to study. The fact I implemented more chores using Erlang already gives a hint. Perhaps I didn't do justice to Scala. Perhaps I should have implemented more chores to get more proficient in Scala. But the truth is that Erlangs syntax is really, really simple. Scala's syntax is more elaborate but the advantages of this more complex syntax over Erlang remain unclear.
Martin Oderski was quite upset when someone stated Scala was about to become the next C++. In my view Martin and his team already set the first steps in making Scala the next C++. It's difficult to top the ugliness of C++'s syntax. And let's be fair, Scala currently doesn't come close, But for me, Scala comes close enough to keep away from it for the time being. That does not mean Scala isn't worth studying. It is. It's capabilities and the fact it produces code for the world's most popular runtime will make it a popular language. No doubts about that.
Erlang's syntax is very simple and elegant. Some minor points ignored (e.g. the ugly "if" construct, the use of which is by the way not mandatory), Erlang's syntax is the ultimate application of "Occam's razor" and stands in stark contrast with Scala's elaborate and sometimes incromprehensible language constructs.
So the coming months I'll be studying Erlang and especially OTP. I'm excited about Erlang as a language and OTP as a framework for designing massively parallel and fault tolerant systems. The elegance simply grabbed me and implementing simple chores like the Ceasar Cipher gave me a feel of true elegance. It convinced me that Erlang is a language that allows me to express my ideas in a very elegant manner. Not because of my programming-abilities or my proficiency in Erlang but because of the elegance of the language.
Perhaps I didn't do right to Scala by implementing only a single chore. But the beauty and elegance of Erlang simply grabbed my attention while Scala's syntax repelled me. While Erlang's language constructs feel natural, elegant and simple, Scala's constructs sometimes feel artificial.
My point of view is that Martin Oderski is desperately in need of Occam's razor and is well advised to take the remark that Scala will be the next C++ as a kind and very relevant advise.
Nagging aspects in language choice.
I see two nagging aspects in my choice for Erlang vs Scala. One is Scala's Akka framework which is relevant without any doubt and really looks like a thing of beauty. The other aspect is the Play framework which looks very promising.
Akka.
The fact that a small team is able to implement capabilities that rival Erlang's OTP framework is an accomplishment in itself. The relevant metrics in comparing Akka and OTP would be simplicity of use, performance and lines of code spent using Akka or OTP.
The concurrency provided by Akka and Erlang is based on Communicating Sequential Processes. In Erlang this is implemented as a language feature, while Akka is a framework written in Scala.
Erlang/OTP has a proven track record with respect to reliability and uptime. Many Erlang/OTP based systems showed uptimes of 5*9 or even better. In this respect Erlang is in a class of its own. It remains to be seen wether Scala/Akka will be able to deliver the same with equal or comparable cost in hardware or development effort .
Play framework.
Another compelling aspect of Scala is the "Play" framework. The value of such a framework is beyond imagination. Frameworks like Play and Akka will propell Scala, that's for sure. Just like Ruby on Rails and ActiveRecord propelled Ruby.
Truth is that the guys that implemented Play borrowed about 99% of their ideas from David Heinemeier Hanssons work on Ruby on Rails without adding significant new ideas. Play to me looks and feels like Rails. Been there, done that. In fact still doing it. So no real benefit in studying Play. That's not to say Play isn't worth studying. It is. Play's performance gain over frameworks like Ruby on Rails is tremendous.
Choice of database.
To be fair I must admit I have no experience with NoSQL databases like CouchDB, CouchBase, MongoDb or BigTable. A colleague of mine successfully used CouchDB in one of his projects saving him a ton of work.
My choice of NoSQL database has no foundation and is completely random. I picked MongoDB combined with Ruby to study for the coming months. Simply because the combination of MongoDB and Ruby could become relevant in my day-time job.
In the past few weeks I've been looking into a number of things I would like to study in the coming months. On the database side I had a look at NoSQL solutions. Notably CouchDB, CouchBase and MongoDB. I installed all of these on my Mac and experimented a couple of hours with each of them.
Programming languages.
I had a look at Scala and Erlang. Languages I never used before and that both present me with a few new concepts. I implemented one chore in Scala and multiple chores in Erlang. I published my Scala chore and the Erlang equivalent on this blog (Erlang chore here, Scala chore here).
On Rosetta Code I completed three simple tasks in Erlang. Count occurrences of a substring, HQ9+ and Ceasar cipher. These are, from a computer science point of view, simple chores. The idea behind implementing them was not they would present me with an intellectual challenge. The goal was to get familiar with the syntax. To get a feel for the beauty or ugliness and the possibilities and limitations of these languages.
Limitations.
Now it's about time to make up my mind what to study the coming months. I can't study all these things in parallel. Next to the intellectual challenge this would present, I've got a day-time job to attend. Besides that the missus and our children, while very patient, also deserve attention. Luckily my Mac is in the living room. That gives me, the missus and the kids a sense of togetherness while each doing our own thing. Here's a difference with my previous live where a subject would totally "suck me in". Completely unable to react or respond to events in my environment. Now I happily chat with the missus or the kids while figuring out map/reduce in CouchDB or hammering out some code in Erlang or Scala.
Choice of language.
Back to the choice of language to study. The fact I implemented more chores using Erlang already gives a hint. Perhaps I didn't do justice to Scala. Perhaps I should have implemented more chores to get more proficient in Scala. But the truth is that Erlangs syntax is really, really simple. Scala's syntax is more elaborate but the advantages of this more complex syntax over Erlang remain unclear.
Martin Oderski was quite upset when someone stated Scala was about to become the next C++. In my view Martin and his team already set the first steps in making Scala the next C++. It's difficult to top the ugliness of C++'s syntax. And let's be fair, Scala currently doesn't come close, But for me, Scala comes close enough to keep away from it for the time being. That does not mean Scala isn't worth studying. It is. It's capabilities and the fact it produces code for the world's most popular runtime will make it a popular language. No doubts about that.
Erlang's syntax is very simple and elegant. Some minor points ignored (e.g. the ugly "if" construct, the use of which is by the way not mandatory), Erlang's syntax is the ultimate application of "Occam's razor" and stands in stark contrast with Scala's elaborate and sometimes incromprehensible language constructs.
So the coming months I'll be studying Erlang and especially OTP. I'm excited about Erlang as a language and OTP as a framework for designing massively parallel and fault tolerant systems. The elegance simply grabbed me and implementing simple chores like the Ceasar Cipher gave me a feel of true elegance. It convinced me that Erlang is a language that allows me to express my ideas in a very elegant manner. Not because of my programming-abilities or my proficiency in Erlang but because of the elegance of the language.
Perhaps I didn't do right to Scala by implementing only a single chore. But the beauty and elegance of Erlang simply grabbed my attention while Scala's syntax repelled me. While Erlang's language constructs feel natural, elegant and simple, Scala's constructs sometimes feel artificial.
My point of view is that Martin Oderski is desperately in need of Occam's razor and is well advised to take the remark that Scala will be the next C++ as a kind and very relevant advise.
Nagging aspects in language choice.
I see two nagging aspects in my choice for Erlang vs Scala. One is Scala's Akka framework which is relevant without any doubt and really looks like a thing of beauty. The other aspect is the Play framework which looks very promising.
Akka.
The fact that a small team is able to implement capabilities that rival Erlang's OTP framework is an accomplishment in itself. The relevant metrics in comparing Akka and OTP would be simplicity of use, performance and lines of code spent using Akka or OTP.
The concurrency provided by Akka and Erlang is based on Communicating Sequential Processes. In Erlang this is implemented as a language feature, while Akka is a framework written in Scala.
Erlang/OTP has a proven track record with respect to reliability and uptime. Many Erlang/OTP based systems showed uptimes of 5*9 or even better. In this respect Erlang is in a class of its own. It remains to be seen wether Scala/Akka will be able to deliver the same with equal or comparable cost in hardware or development effort .
Play framework.
Another compelling aspect of Scala is the "Play" framework. The value of such a framework is beyond imagination. Frameworks like Play and Akka will propell Scala, that's for sure. Just like Ruby on Rails and ActiveRecord propelled Ruby.
Truth is that the guys that implemented Play borrowed about 99% of their ideas from David Heinemeier Hanssons work on Ruby on Rails without adding significant new ideas. Play to me looks and feels like Rails. Been there, done that. In fact still doing it. So no real benefit in studying Play. That's not to say Play isn't worth studying. It is. Play's performance gain over frameworks like Ruby on Rails is tremendous.
Choice of database.
To be fair I must admit I have no experience with NoSQL databases like CouchDB, CouchBase, MongoDb or BigTable. A colleague of mine successfully used CouchDB in one of his projects saving him a ton of work.
My choice of NoSQL database has no foundation and is completely random. I picked MongoDB combined with Ruby to study for the coming months. Simply because the combination of MongoDB and Ruby could become relevant in my day-time job.
April 26, 2012
Making things more Erlangy
In a previous blogpost I wrote a little Erlang to find sequences n, n+1, ..., n+m that have a given sum:
I now dislike the code I wrote because of the ugly if-construct. Now that I've read some more and experimented a little I come to the conclusion that this construct, while efficient, is not Erlangy. "If" looks like a language design after-thought. Guards simply have a better feel to them. So here we go:
That's more the way things are supposed to be in Erlang. At least that's my point of view. To me, this looks more elegant than the code using the if-construct.
Be aware that the guards are evaluated in the order in which they occur in the source. Moving the code guarded by Tail + Head > Goal further down will cause an infinite loop.
seqwithsum(Goal) ->
seqwithsum(1, 2, 3, Goal, []).
seqwithsum(Tail, Head, Sum, Goal, L) ->
if
Tail + Head > Goal ->
L;
Sum < Goal ->
% advance head
seqwithsum(Tail, Head+1, Sum+Head+1, Goal, L);
Sum > Goal ->
% advance tail
seqwithsum(Tail+1, Head, Sum-Tail, Goal, L);
true ->
% Prepend matching sequence to list and advance tail
seqwithsum(Tail+1,Head,Sum-Tail,Goal,[{Tail, Head}] ++ L)
end.
I now dislike the code I wrote because of the ugly if-construct. Now that I've read some more and experimented a little I come to the conclusion that this construct, while efficient, is not Erlangy. "If" looks like a language design after-thought. Guards simply have a better feel to them. So here we go:
seqwithsum(Goal) ->
seqwithsum(1, 2, 3, Goal, []).
seqwithsum(Tail, Head, Sum, Goal, Results) when Sum < Goal ->
% advance Head
seqwithsum(Tail, Head+1, Sum+Head+1, Goal, Results);
seqwithsum(Tail, Head, _Sum, Goal, Results) when Tail + Head > Goal ->
Results;
seqwithsum(Tail, Head, Sum, Goal, Results) when Sum > Goal ->
%advance Tail
seqwithsum(Tail+1, Head, Sum-Tail, Goal, Results);
seqwithsum(Tail, Head, Sum, Goal, Results)
seqwithsum(Tail+1, Head, Sum- Tail, Goal, [{Tail, Head} | Results]).
That's more the way things are supposed to be in Erlang. At least that's my point of view. To me, this looks more elegant than the code using the if-construct.
Be aware that the guards are evaluated in the order in which they occur in the source. Moving the code guarded by Tail + Head > Goal further down will cause an infinite loop.
April 04, 2012
Erlang performance revisited; HiPE to the rescue
In my two previous articles I solved a trivial problem in Scala and Erlang: Write a program that -given G- produces sequences of numbers x, x+1, x+2..., x+n such that G = sum(x, x+1...x+n). The challenge was not to solve this trivial problem. My quest was to compare the performance of an Erlang solution to a Scala implementation.
I stated beforehand these were my first lines of code in both Erlang and Scala. For smaller values for G, the Erlang implementation outperformed 'single-shot' execution of the Scala equivalent by a wide margin. I then modified the Scala implementation in a direction where I knew JIT would shine. And, lo and behold, in this setup Scala outperformed Erlang. For larger values for G even by a wide margin.
And then I picked up the book "Erlang and OTP in Action" by Martin Logan et al. The introduction mentions the HiPE project (High Performance Erlang), a native code compiler for Erlang. This wetted my apetite for further experiments.
So I checked my Erlang installation and was happy to find it contained HiPE support. I recompiled my little Erlang program using HiPE with maximum optimization. This dramatically improved performance.
In my article on Scala I assumed that the larger the load on a system, the more JIT would shine and the more Scala would outperform an equivalent Erlang implementation. But this was no more than an assumption. One I'm not too sure about anymore. In the Scala setup I explicitly picked a situation that would clearly benefit JIT; a small piece of code repeatedly executed to warm up JIT in order to let it shine.
Both Scala and Erlang are directed towards large scale projects containing million+ lines of code. Erlang already proved to be able to hold its ground in such situations. For Scala this remains to be seen. In a large scale system a lot of the code is executed and a lot of it is executed in parallel. But when it's different code that gets executed all the time, JIT would suffer from its warm up delay. Causing effects that resemble my first attempts with Scala where I used "one shot" execution. A situation where Erlang outperformed Scala by a margin of 1.000
My experiments so far show Erlang clearly does not suffer from any startup delay, on the contrary. So I now doubt wether my conclusion that the larger the load on a large scale system, the more JIT will shine is correct. Especially since it is probable that in such a large scale system major parts of the code will only execute incidentally. Most of the time the system will be busy executing incidental code. In such a system a small part of the code will be executed almost continually, giving JIT an opportunity to show its strength. But most of the time the system will be busy executing incidental code and will, in the Scala case, suffer from the warm up delay which severely degrades performance.
Erlang shows not to suffer from such a warm up delay and performance is quite consistent. So in the Erlang case, performance becomes predictable. Predicting performance of Scala/JIT is much more difficult because the warm up delay plays a major role. My guess is that in a large scale system most code executed, is executed some of the time, some code is executed most of the time. That spells bad for JIT because in such a situation most of the code will suffer from warm up delay.
Best case, Scala will outperform Erlang with a factor 3. But worst case, Erlang will outperform Scala with a factor of better than 1000. In my Scala post I stated my money would be on Scala. I'm glad no one took the bet.
I stated beforehand these were my first lines of code in both Erlang and Scala. For smaller values for G, the Erlang implementation outperformed 'single-shot' execution of the Scala equivalent by a wide margin. I then modified the Scala implementation in a direction where I knew JIT would shine. And, lo and behold, in this setup Scala outperformed Erlang. For larger values for G even by a wide margin.
And then I picked up the book "Erlang and OTP in Action" by Martin Logan et al. The introduction mentions the HiPE project (High Performance Erlang), a native code compiler for Erlang. This wetted my apetite for further experiments.
So I checked my Erlang installation and was happy to find it contained HiPE support. I recompiled my little Erlang program using HiPE with maximum optimization. This dramatically improved performance.
In my article on Scala I assumed that the larger the load on a system, the more JIT would shine and the more Scala would outperform an equivalent Erlang implementation. But this was no more than an assumption. One I'm not too sure about anymore. In the Scala setup I explicitly picked a situation that would clearly benefit JIT; a small piece of code repeatedly executed to warm up JIT in order to let it shine.
Both Scala and Erlang are directed towards large scale projects containing million+ lines of code. Erlang already proved to be able to hold its ground in such situations. For Scala this remains to be seen. In a large scale system a lot of the code is executed and a lot of it is executed in parallel. But when it's different code that gets executed all the time, JIT would suffer from its warm up delay. Causing effects that resemble my first attempts with Scala where I used "one shot" execution. A situation where Erlang outperformed Scala by a margin of 1.000
My experiments so far show Erlang clearly does not suffer from any startup delay, on the contrary. So I now doubt wether my conclusion that the larger the load on a large scale system, the more JIT will shine is correct. Especially since it is probable that in such a large scale system major parts of the code will only execute incidentally. Most of the time the system will be busy executing incidental code. In such a system a small part of the code will be executed almost continually, giving JIT an opportunity to show its strength. But most of the time the system will be busy executing incidental code and will, in the Scala case, suffer from the warm up delay which severely degrades performance.
Erlang shows not to suffer from such a warm up delay and performance is quite consistent. So in the Erlang case, performance becomes predictable. Predicting performance of Scala/JIT is much more difficult because the warm up delay plays a major role. My guess is that in a large scale system most code executed, is executed some of the time, some code is executed most of the time. That spells bad for JIT because in such a situation most of the code will suffer from warm up delay.
Best case, Scala will outperform Erlang with a factor 3. But worst case, Erlang will outperform Scala with a factor of better than 1000. In my Scala post I stated my money would be on Scala. I'm glad no one took the bet.
March 27, 2012
Second attempt to shoot myself in the foot; Scala
In this blogpost I will use Scala to solve the exact same problem I described in my previous blogpost:
write a program that given G produces sequences of numbers x, x+1, x+2..., x+n such that G = sum(x, x+1...x+n).
Scala currently is at the center of attention and rightly so. Scala allows for massively parallel and fault-tolerant computing. It supports both object-orientation and functional programming and produces code for Java's Virtual Machine, a highly optimized and robust runtime. No surprise more and more companies adopt Scala.
Looking at Scala one thing becomes obvious. Martin Odersky and his team are clearly heading in the right direction. Previous attempts at tools for massively parallel computing —Occam and Erlang among others— never became generally adopted. Chances are that Scala will become a mainstream language, as it is already adopted for production by companies like Twitter, LinkedIn, UBS, CSC and others.
So here's my attempt using Scala:
import scala.annotation.tailrec
object FindRangeWithSum {
def find(goal:Int):List[(Int,Int)] = {
@tailrec def scan(tail:Int, head:Int, sum:Int, goal:Int,
accu: List[(Int, Int)]):List[(Int, Int)] = {
if (tail + head > goal)
accu
else if (sum < goal)
scan(tail, head+1, sum+head+1, goal, accu)
else if (sum > goal)
scan(tail+1, head, sum-tail, goal, accu)
else /*(sum == goal)*/
scan(tail+1, head, sum-tail, goal, (tail, head):: accu)
}
scan(1, 2, 3, goal, List())
}
}
import Profiling._
object RangeFinder extends App {
val data = timed(printTime("Execution took: ")) {
val list = FindRangeWithSum.find(10000)
println(list)
}
accu: List[(Int, Int)]):List[(Int, Int)] = {
if (tail + head > goal)
accu
else if (sum < goal)
scan(tail, head+1, sum+head+1, goal, accu)
else if (sum > goal)
scan(tail+1, head, sum-tail, goal, accu)
else /*(sum == goal)*/
scan(tail+1, head, sum-tail, goal, (tail, head):: accu)
}
scan(1, 2, 3, goal, List())
}
}
import Profiling._
object RangeFinder extends App {
val data = timed(printTime("Execution took: ")) {
val list = FindRangeWithSum.find(10000)
println(list)
}
}
scala.annotation.tailrec provides an annotation that checks wether a method allows for tailrec elimination. A method annotated with @tailrec is checked to be tail recursive. If not, the compiler issues a warning. Compared to Erlang that's a better. While this problem is simple there are a lot of situations where tail-recursion is a lot less obvious.
By the way, if you're interested in experimenting with this code you need to pickup the profiling code written by Matthias Mann.
Now to the performance of this code. This will run within the JVM which uses JIT (Just In Time compilation). JIT is known to have a startup delay. I've been tinkering around firing the code with different values for goal. For most values for goal the Erlang example outperformed the Scala implementation by a wide margin where the Scala code never came in the range of micro seconds. Only for goal = 1.000.000.000 the Scala code outperformed the Erlang implementation.
To do justice to the JVM and the effort a lot of bright minds put into JIT, I modified the code:
10^1 Execution took: 12ms 858us 0ns
10^2 Execution took: 33us 0ns
10^3 Execution took: 59us 0ns
10^4 Execution took: 356us 0ns
10^5 Execution took: 4ms 261us 0ns
10^6 Execution took: 3ms 79us 0ns
10^7 Execution took: 32ms 903us 0ns
10^8 Execution took: 307ms 669us 0ns
10^9 Execution took: 2s 969ms 420us 0ns
10^1 Execution took: 35us 0ns
10^2 Execution took: 21us 0ns
10^3 Execution took: 23us 0ns
10^4 Execution took: 49us 0ns
10^5 Execution took: 316us 0ns
10^6 Execution took: 2ms 977us 0ns
10^7 Execution took: 29ms 556us 0ns
10^8 Execution took: 298ms 727us 0ns
10^9 Execution took: 2s 977ms 928us 0ns
By the way, if you're interested in experimenting with this code you need to pickup the profiling code written by Matthias Mann.
Now to the performance of this code. This will run within the JVM which uses JIT (Just In Time compilation). JIT is known to have a startup delay. I've been tinkering around firing the code with different values for goal. For most values for goal the Erlang example outperformed the Scala implementation by a wide margin where the Scala code never came in the range of micro seconds. Only for goal = 1.000.000.000 the Scala code outperformed the Erlang implementation.
To do justice to the JVM and the effort a lot of bright minds put into JIT, I modified the code:
object RangeFinder extends App {
for (runs <- 0 to 1) {
for (x <- 1 to 9) {
val data = timed(printTime(" Execution took: ")) {
val list = FindRangeWithSum.find(math.pow(10, x).toInt)
print("10^" + x)
}
}
}
}
for (runs <- 0 to 1) {
for (x <- 1 to 9) {
val data = timed(printTime(" Execution took: ")) {
val list = FindRangeWithSum.find(math.pow(10, x).toInt)
print("10^" + x)
}
}
}
}
This lead to remarkable results that definitely confirm the startup delay of JIT. When warming up JIT by repeating the code, Scala outperforms Erlang for almost every value for goal.
10^1 Execution took: 12ms 858us 0ns
10^2 Execution took: 33us 0ns
10^3 Execution took: 59us 0ns
10^4 Execution took: 356us 0ns
10^5 Execution took: 4ms 261us 0ns
10^6 Execution took: 3ms 79us 0ns
10^7 Execution took: 32ms 903us 0ns
10^8 Execution took: 307ms 669us 0ns
10^9 Execution took: 2s 969ms 420us 0ns
10^1 Execution took: 35us 0ns
10^2 Execution took: 21us 0ns
10^3 Execution took: 23us 0ns
10^4 Execution took: 49us 0ns
10^5 Execution took: 316us 0ns
10^6 Execution took: 2ms 977us 0ns
10^7 Execution took: 29ms 556us 0ns
10^8 Execution took: 298ms 727us 0ns
10^9 Execution took: 2s 977ms 928us 0ns
This shows Scala clearly outperforms the Erlang implementation. And by a wide margin. Note the 3 seconds for goal = 1,000,000,000. It took the Erlang version 2 minutes to complete.
Let me try to put these results into perspective. With 'one-shot' execution, Erlang outperforms Scala by a wide margin. But when code executes repeatedly, Scala really shines and Erlang is -let's be fair- no match. Now try to imagine what will happen in a situation where an application is comprised of hundreds or possibly thousands of SCP's (Sequential Communicating Processes). Each of these processes complete a distinct and hopefully well defined and simple task.
The larger the load on such a system, the more Scala and JIT will shine and the more it will outperform an equivalent implementation in Erlang. Until now Erlang used to be in a class of it's own when it came to applications under heavy load. In a shoot out between Apache and YAWS (a web server implemented in Erlang), YAWS was still functioning at over 80,000 parallel connections. Apache died when subject to a load of 4,000 parallel connections. Check the Apache vs Yaws report for further details.
In a similar setup for Erlang vs. Scala my money definitely would be on Scala. I didn't dive into Akka yet, but the information I've seen until now gives me confidence that Scala, accompanied by frameworks like Akka and Play will be a winning combination for those who have the guts to dare. Especially Play is worth noting since it combines the strengths of Node.js (asynchronous I/O) with those of Erlang (massively parallel processing).
March 21, 2012
First attempt to shoot myself in the foot; Erlang
Acquiring knowledge is one of the joys in my every day life. Greater joys do exist and while important, are beyond the scope of this blog.
I recently installed Erlang and Scala and started experimenting with both of them. To get acquainted with a new programming language, I first read a little. After a couple of chapters I write some code and play around with it. If there's an interactive shell available, I play with it to get a feel for the syntax and semantics. I play around until I'm satisfied I've got a firm grip on the subjects presented in the first chapters. I then repeat this until I'm satisfied with the knowledge gathered.
So here's my first experiment with Erlang. Please take into account that these are my first lines of Erlang code. Comments are explicitly encouraged, especially from seasoned Erlang programmers.
Let's write a program that given G produces sequences of numbers x, x+1, x+2..., x+n such that G = sum(x, x+1...x+n).
Here's my first attempt using Erlang
seqwithsum(Goal) ->
Max = Goal + 1 div 2,
[ {Tail, Head} ||
Tail <- lists:seq(1, Max-1),
Head <- lists:seq(Tail+1, Max),
lists:sum(lists:seq(Tail,Head)) =:= Goal
].
I recently installed Erlang and Scala and started experimenting with both of them. To get acquainted with a new programming language, I first read a little. After a couple of chapters I write some code and play around with it. If there's an interactive shell available, I play with it to get a feel for the syntax and semantics. I play around until I'm satisfied I've got a firm grip on the subjects presented in the first chapters. I then repeat this until I'm satisfied with the knowledge gathered.
So here's my first experiment with Erlang. Please take into account that these are my first lines of Erlang code. Comments are explicitly encouraged, especially from seasoned Erlang programmers.
Let's write a program that given G produces sequences of numbers x, x+1, x+2..., x+n such that G = sum(x, x+1...x+n).
Here's my first attempt using Erlang
seqwithsum(Goal) ->
Max = Goal + 1 div 2,
[ {Tail, Head} ||
Tail <- lists:seq(1, Max-1),
Head <- lists:seq(Tail+1, Max),
lists:sum(lists:seq(Tail,Head)) =:= Goal
].
Nice. Compact, elegant and inefficient. Execution time will be some third degree function of G. Nonetheless these 7 lines of code perform fairly well for smaller values for G:
1> timer:tc(mycalc, seqwithsum, [100]).
{2207,[{9,16},{18,22}]}
2>
2.2 milliseconds to compute the answer. However, for larger values of G performance quickly degrades. G = 1000 takes 1.6 seconds. Let's have a look at the numbers:
| G | time(µs) | |
|---|---|---|
| 10 | 12 |  |
| 20 | 46 | |
| 30 | 109 | |
| 40 | 230 | |
| 50 | 382 | |
| 60 | 727 | |
| … | … | |
| 100 | 2396 | |
| 200 | 16600 | |
| 300 | 50000 | |
| 400 | 112000 | |
| 500 | 212000 | |
| … | … | |
| 1000 | 1619000 | |
This clearly does not scale well with regards to G. There's two generators and one filter computing the sum of a sequence (and thus iterating over the sequence at hand). Execution time is some third degree function of G. Using polyfit from GNU Octave here's an approximation for t as a function of g:
t = 0.01*g^3 + 6.4*g^2 - 3854*g + 161950
Let's try to get rid of these three nested loops. To do so I'll use recursion, which is said to be a natural fit for Erlang. So let's have a go:
t = 0.01*g^3 + 6.4*g^2 - 3854*g + 161950
Let's try to get rid of these three nested loops. To do so I'll use recursion, which is said to be a natural fit for Erlang. So let's have a go:
seqwithsum(Goal) ->
seqwithsum(1, 2, 3, Goal, []).
seqwithsum(Tail, Head, Sum, Goal, L) ->
seqwithsum(Tail, Head, Sum, Goal, L) ->
if
Tail + Head > Goal ->
L;
Sum < Goal ->
% advance head
seqwithsum(Tail, Head+1, Sum+Head+1, Goal, L);
Sum > Goal ->
% advance tail
seqwithsum(Tail+1, Head, Sum-Tail, Goal, L);
true ->
% Prepend matching sequence to list and advance tail
seqwithsum(Tail+1,Head,Sum-Tail,Goal,[{Tail, Head}] ++ L)
end.
Tail + Head > Goal ->
L;
Sum < Goal ->
% advance head
seqwithsum(Tail, Head+1, Sum+Head+1, Goal, L);
Sum > Goal ->
% advance tail
seqwithsum(Tail+1, Head, Sum-Tail, Goal, L);
true ->
% Prepend matching sequence to list and advance tail
seqwithsum(Tail+1,Head,Sum-Tail,Goal,[{Tail, Head}] ++ L)
end.
Execution time now will be a linear function of G. Let's have a look at how this performs:
1> timer:tc(mycalc, seqwithsum, [100]).
{17,[{18,22},{9,16}]}
17 µs? That's better than I expected. A 140 fold improvement over the previous approach. That looks promising indeed. The few extra lines of code were definitely worth their while. Let's experiment some more with this version to see where that takes us:
2> timer:tc(mycalc, seqwithsum, [10000]).
{1450,[{1998,2002},{388,412},{297,328},{18,142}]}
Looking even better compared to the previous algorithm where G=1000 took 1.6 seconds to compute the result. Literally a thousand times better than the first approach. Let's try to comprehend the consequences of this experiment. Some extra tinkering led to a thousand fold performance gain!
Back to the code. This is a recursive solution to the problem. Experience tells me I must be able to break this. It's a recursive approach so it must be easy to force a stack overflow. A recursive implementation of fac in Pascal caused a stacktrace with fac(5000), so my recursive seqwithsum(1000000)will break for sure. No greater joy for a programmer than break his own programs. Let's give this another try:
Back to the code. This is a recursive solution to the problem. Experience tells me I must be able to break this. It's a recursive approach so it must be easy to force a stack overflow. A recursive implementation of fac in Pascal caused a stacktrace with fac(5000), so my recursive seqwithsum(1000000)will break for sure. No greater joy for a programmer than break his own programs. Let's give this another try:
3> timer:tc(mycalc, seqwithsum, [1000000]).
{131456,
[{199998,200002},
{39988,40012},
{7938,8062},
{7749,7876},
{1288,1912},
{1243,1882}]}
This time the answer consists of 6 sequences and it took BEAM 131 ms to compute. These figures support the conclusion that execution time is a linear function of G. Determined to bring the beast to it's knees I type:
> timer:tc(mycalc, seqwithsum2, [1000000000]).
Hah, that seems to have knocked out BEAM. I stare at the screen convinced that victory is mine. Find sequences of integers where the sum of the sequence is 1 billion. That wil break things for sure. Since the algorithm is recursive this will result in a stack overflow. No doubt about that.
The cursor blinks and two of the four cores of my Mac OS X system consume somewhere around 50% cpu. I threw a brick at Erlang and it will shatter its windows to pieces, that's for sure.
But after 132 seconds disappointment kicks in as BEAM responds with the following:
The cursor blinks and two of the four cores of my Mac OS X system consume somewhere around 50% cpu. I threw a brick at Erlang and it will shatter its windows to pieces, that's for sure.
But after 132 seconds disappointment kicks in as BEAM responds with the following:
{131827022,
[{199999998,200000002},
{39999988,40000012},
{7999938,8000062},
{1599688,1600312},
{976051,977074},
{318438,321562},
{192753,197872},
{56188,71812},
{26263,51862}]}
Puzzling this didn't result in a stack-overflow? Head and Tail will advance until the end condition Head + Tail > GOAL is reached. Each advancement of Head and each advancement of Tail will add one to the recursion-depth, resulting in GOAL-1 recursive calls to seqwithsum/5. For GOAL = 1 billion, this ought to create 1 billion -1 stack frames. But no paging occurred. Memory allocated to BEAM is steady at 10MB during this calculation.
Clearly there's something else going on here: tail-recursion. Tail recursion allows the compiler to replace the recursive function calls with a simple jump to the entry point of the function.
My next blogpost will be about solving this problem in Scala and comparing the results of the Scala solutions with the results of the solutions In Erlang.
Erlang specialists are explicitly invited to comment on this article.
Clearly there's something else going on here: tail-recursion. Tail recursion allows the compiler to replace the recursive function calls with a simple jump to the entry point of the function.
My next blogpost will be about solving this problem in Scala and comparing the results of the Scala solutions with the results of the solutions In Erlang.
Erlang specialists are explicitly invited to comment on this article.
Subscribe to:
Posts (Atom)