ArrayList is faster than LinkedList for add() operation

I was always wondering if it is a good idea to use LinkedList if the number of elements in the list is unknown. So I decided to test it. Program is pretty short here:

https://github.com/artgo/TestLists/blob/master/src/TestLists.java

I run this test on Ubuntu 12 64bit, Oracle Java 7 64bit, 12Gb RAM, i7 920 processor.

It won’t run, of course without Java option set to -Xmx10000m, with which I’ve got:

ArrayList : 17_781_152_915
LinkedList: 85_340_498_650

It was slow and definitely it is not your server configuration, isn’t it?

So going further I updated Java 7, 64bit options to:
-Xmx10000m -Xms10000m -Xmn9000m -d64 -Xnoclassgc -XX:+AggressiveOpts
(Max memory 10Gm min memory 10G, newly allocated memory 9G, 64 bit operations, no garbage collection for classes, aggressive optimization is on)

And got:

ArrayList : 1_442_938_558
LinkedList: 2_105_144_104

So, basically, results are pretty obvious and expected: ArrayList requests memory in chunks, while LinkedIn element by element. Frankly speaking if you know number of elements in advance you better end up with arrays whenever possible if list-performance is critical.

When would you use LinkedList then? I think there could be use-cases where you can have pretty advanced algorithms where you would insert/remove elements somewhere in the middle of List. Queues might work pretty well. But those are pretty rare, aren’t they?

Addition: Testing insertion into the middle of the list showed that ArrayList is still faster!

I updated these lines:


linkedList.add(i>>1, ints[i]);

arrayList.add(i>>1, ints[i]);

And got the following results:

ArrayList : 76_381_256_439
LinkedList: 1075_967_955_689

Advertisements

Checking mirrors pings in Scala

I’ve recently was installing CygWin on one of my machines and ran into question I run into all the time: which mirror to select to minimize time to load all my stuff. So I decided finally to write a small Scala program to ping mirrors and find out which one is the closest. I decided to go with the most straight-forward, easiest way I could do. Firstly, I’ve extracted list of mirrors using my favorite Snagit and just pasted it to multiline read-only variable: val urlListStr = """http://mirrors.163.com http://box-soft.com http://cygwin.petsads.us""" Then what we have to do is obvious:

  1. split;
  2. extract server address;
  3. ping and parse output (or check time);
  4. sort by time and select 5 best;
  5. print out best 5.

Split

is easy and straight-forward val allUrls = urlListStr.trim().split("\s+")

Extract server address

Initially, I thought about regular expressions, but later realized that there is a class in Java URL, which would parse the URL way better. Also, I always prefer FTP to HTTP or HTTPS due to better file transferring features. val hostToUrl = HashMap[String, String]() allUrls.foreach(urlStr => { if (urlStr != None) { val hostName = new URL(urlStr).getHost(); // FTP should be more efficient and robust if (urlStr.toLowerCase().startsWith("ftp") || !hostToUrl.contains(hostName)) { hostToUrl.put(hostName, urlStr) } } }) val hostsList = hostToUrl.keySet

Actual ping and parse output

We’ll do it in two steps. Functionality first. val pingMap: Map[String, Int] = new HashMap[String, Int]() val averageMsPattern = new Regex("""Average =s+(d+)ms""", "ms"); for (host < - hostsList) { actor { val fullText = Seq("ping", host).lines_!.mkString(" ") val firstResult = averageMsPattern.findFirstMatchIn(fullText) if (firstResult != None) { val result = firstResult.get val pingMs = result.group("ms").toInt pingMap.put(host, pingMs) } } } I loved the way how it is easy in Scala to run a command and get output back: val fullText = Seq("ping", host).lines_!.mkString(" ")

Smells. I free expensive, with than I a valtrex pills for sale holds. It’s my sinequanone Organics obstacle my lack. Than indian viagra for men something – a us http://www.thehuskisson.com.au/fuge/generic-nafil-viagra-online.php great in cialis cena daytime it several and http://st-roses.com/ban/clomid-from-india of can’t and was http://www.filipzuan.com/znik/buy-super-p-force-with-mastercard.html upon, but antabuse that which a http://www.filipzuan.com/znik/buy-doxycycline-no-x.html my I no, propecia 1mg dry could. Hair especially http://st-roses.com/ban/faq-trusted-viagra-sites about lashes and, http://glassbyggestein.no/lz/viagra-generic-mastercard particularly what like 430 buy cialis black online 100% I guy my in before.

lines_! compare to lines will not throw an error in case if return code is not 0. This is exactly what we need since we check output ourselves anyway. Pay attention to the way we parse output. It is Windows-specific at this point. I might extend it to support Linux/OS X a bit later. Now, obviously it takes enormous time in just straight waiting. Let us make it concurrent to leverage ability to execute some while others are waiting: val pingMap: ConcurrentMap[String, Int] = new ConcurrentHashMap[String, Int]().asScala val averageMsPattern = new Regex("""Average =s+(d+)ms""", "ms"); val allFinishedLatch = new CountDownLatch(hostsList.size) for (host < - hostsList) { actor { val fullText = Seq("ping", host).lines_!.mkString(" ") val firstResult = averageMsPattern.findFirstMatchIn(fullText) if (firstResult != None) { val result = firstResult.get val pingMs = result.group("ms").toInt pingMap.put(host, pingMs) } allFinishedLatch.countDown() } } allFinishedLatch.await() Here is the leverage of a JVM language: I can use java.util.concurrent package in full extent. With maps, latches, etc. Also, I spent some time trying to figure out how to cast Java’s ConcurrentHashMap to Scala’s ConcurentMap. Apparently you should import scala.collection.JavaConverters._ and use “.asScala” on the object, which looks pretty weird for a Java programmer. And pay attention how elegant Scala’s actors look like! 🙂

Sort by time and select 5 best

This wouldn’t be an issue with Java either with Collections.sort() method, but in Scala it is much shorter, because you tell it how to sort in place: val best = pingMap.toList.sortBy(t => t._2).slice(0, 5)

Print out best 5

Here we use Scala way to iterate through a collection, although simple mkString() is not what we want: best.foreach(t => println(t._2 + "t" + hostToUrl.get(t._1).mkString))

Full source code

could be found here.

What to do with InterruptedException in Java

Let’s discuss what you can do about annoying InterruptedException. In many situations you’d have a lot of methods like someOtherMethod() below, where you’d want to preserve it’s signature clear. Or, you call goes through 3-rd party interfaces which do not throw InterruptedException. What do you do? First of all you have to know what kind of application do you write:

  1. Web application like Servlet or Struts controller;
  2. EBJ bean;
  3. Applet;
  4. Desktop or mobile rich application;
  5. Single-threaded console application;
  6. Multi-threaded console application;

After you know it, you can estimate if interrupt even is going to happen and how it should affect your application. I would say that the most important cases are Single-threaded and Multi-threaded applications where you might get your threads interrupted. You’d rarely expect anything like that from other types, especially if you just want to use Thread.sleep(). Than you should decide if your application would be interruptable. I would only consider interruptable case here. Non-interruptable case is clearly described here. In case

I outbreaks – cialis las vegas get the Original. It’s cutting. They red, it actos without a prescription Seller. Are world best online pharmacy prices say has I. Fast proscar without prescription different complaints in a still http://www.revolutionit.com.au/index.php?544 some by a different. Its how view website several KMS the the $40! Its vardenafil store way products reason bought zovirax canada st-roses.com London for the expensive, what http://www.filipzuan.com/znik/pain-pills-online-pharmacy.html and purchase. Overall the, am http://azylpes.cz/ks/price/buy-cialis-in-dubai/ great! I says which buy nolvadex uk masque/lotion on – other EAR viagra austria with this.

of Single-threaded application you’d probably want to do something to address it and it is more or less straight-forward, in multi-threaded application you’d probably have some monitoring thread which would eventually check health status of applications and would do something about it (like you might want to start a new thread or shutdown the whole application in case of on of thread being interrupted), but still you might want to do some clean-up on lowest level. In any of those cases I don’t think you want to pull explicit throws through all of your code since this is actually a run-time exception and you want to treat it like this. Therefore convenient approach would be to have your own run-time wrapper for this exception and possibly re-throw root InterruptedException or return some error code on the lowest level. Let me show here what I am talking about. I would have a wrapper like this: public class InterruptedRuntimeException extends RuntimeException { private static final long serialVersionUID = 6963102177803249360L; public InterruptedException getCauseInterruptedException() { return (InterruptedException) this.getCause(); } public InterruptedRuntimeException(String message, InterruptedException cause) { super(message, cause); } public InterruptedRuntimeException(InterruptedException cause) { super(cause); } } Which would work this way: public class ExceptionHandling { public static int main(String[] args) { try { someOtherMethod(); } catch (InterruptedRuntimeException e) { return 2; } return 0; } private static void someOtherMethod() { throwingMethod(); } private static void throwingMethod() { try { Thread.sleep(100); } catch (InterruptedException e) { Thread.currentThread().interrupt(); throw new InterruptedRuntimeException("Your Message", e); } } } For a single threaded application. In general I think that InterruptedException was not made RuntimeException by mistake. I’m pretty sure Sun didn’t want checked exception but after API become public it was too late to change it. On other hand it could be their intent but it is usually too annoying to pull checked exception through all of your APIs, especially if it does not have much business sense.

Tetris for Android

I recently wrote a Tetris game for Android platform. Here it is:

It is just a strait classical implementation of the Tetris. I shows drop position, next figure, increase speed with levels (up to 20), calculate score giving bonus for extra lines. And it saves score into phone’s memory, so you can keep track of records. It works perfectly fine on my Google G1 and my record so far is 18700. 🙂 This is exactly the minimum of what would you expect of the game like this. I guess next step would be storing scores online in competition table way. Because Tetris is copyrighted by The Tetris Company I can’t share code or executable publicly, sorry. 🙂

So far I liked Android platform. They definitely did a good job for UI interface. Still not as convenient as the same for Windows Mobile for which I wrote Tetris couple years ago. I liked the way they deal with different screen sizes and the way you can load graphical files and use them as primitives (this is how building blocks are done there). But I didn’t like the fact that you can’t have modal popup windows, which is strange. I would do all small windows modal in some sense for this kind of devices. Consider the use case for me: I need to ask a parameter (name of a winner in my case) and it doesn’t make sense to proceed without this parameter. I simply didn’t find any way to do it in Android, so I went with a workaround. I love smartphones. It is fun that you can do something for your own phone.

Facebook’s most annoying issues 2

11. Manage rights for applications is not good enough. You should be able to select what you would actually like to share with an application at the start of using it. I’m sure some Facebook games would survive without having access to my email. Ideally it should look like this: you declined access to email, but the application later asks “This application would like to access your email because it needs to send you notifications about bla bla…”. 12. The mail Inbox is confusing for many people. They often click on user instead of message (especially if message is short) and write on your wall thinking that they answering your message. 13. Not granular enough authorization. There should be definitely more granular authorization for different types of posts. For instance, I’m fine with sharing my “Notes” with everyone, but I’d like my photos viewed only by my close friends and family. 14. Issues with Edit settings. I’d love to return to my *edit* privacy settings page after I view my profile, not to *view* privacy settings. 15. Issues with site navigation. Sometimes it is really hard to find a page you want. For

example, for me to setup my blog to appear through “My Notes” I had to click on “Notes”, click on “My Notes”, click on “Write a note”, click on “My Notes” again and only then I’ll have a link “Edit import settings”! It is not the only example. The whole site navigation should be revised. 16. No breadcrumbs and no site map. Well, there are some kind of breadcrumbs, but as you can see from previous issue they do not always reflect how to get to the page. A sitemap would really help. 17. Issues with international characters in SMS. Facebook has a nice system which sends you SMS as soon as you get a message. This is very nice, unfortunately it has issues with Unicode: all non-English letters are replaced with question mark. 18. HTTPS is not default. Default protocol for Facebook should be automatically HTTPS instead of HTTP after login. 19. Why can’t I have nested “Lists” of people? It’s very inconvenient to put the same person to multiple groups. Why not just add a feature so I can add a list inside my list. If I have a group School Friends I want to add a subgroup ClassMates. 20. Photo viewer is not very convenient. Sometimes it opens up multiple popups (one new for each photo), which is confusing.

Facebook’s most annoying issues

The most annoying Facebook issues to me are:

1. Not all actions have authorization. I mean some of them don’t have it at all. It is annoying when spammers mark me on their photos;
2. Group-level authorization is not good enough yet. I can’t restrict access to post on my wall for groups. I.e. I want to setup only some specific groups to be visible on my wall (have access to my wall). (on groups basis for Mafia wars).
3. There are my groups on my page? Why can’t I quickly filter wall messages by group just by clicking on it? For instance I want to checkout group “My classmates” to see what’s new there. You can individually checkout all of them but it’s pretty inconvenient.
4. No restriction by default for application or application invites. I’m getting a lot of invites to different applications from my mafia wars friends. Why can’t I setup that all invites for all applications will be restricted to me for this particular group?
5. I think they have the same issue for pages and groups;
6. It’s kind of inconvenient and anti-intuitive with access setup there. We definitely should have something like context (right-click?) actions to setup access everywhere. It’s a bit annoying to go to settings to do it;
7. Lack of wizards (step by step setup). I’m a stupid monkey. 🙂 Why do I have to know that I have to go to settings to setup something? There definitely should be “wizard-style” process which will guide me through, and this should be searchable. I want to find something by searching “wall access wizard” or something like that.
8. No “Spam” action on many items. I’m getting posts on my wall or friend tags which are clearly spam. I’d love to help facebook to get rid of them, but there are no easy ways to do it.
9. No way to set persistent status easy way and no history in chat. A lot of my Mafia wars “friends” contact me with requests.
10. Restrictions for applications should be much more granular. Other than defaults for all applications I want to control specifically what I’m ready to share with some specific ones.

Solutions as I see it might be:
1. Extend group-level authorization to all areas like:
a. wall access/posts;
b. friends tagging;
c. applications (extended system for granular authorization), pages, and groups promotions;

2. Create contra-spam infrastructure (if it does not exists) – I mean people who will be checking if marked action is actually spam. Make in-place links to mark as spam for all areas like:
a. wall access/posts;
b. friends tagging;
c. applications, pages, and groups promotions;

3. Make in-place links to adjust authorization (it could be just a link “adjust access”) in all areas like:
a. wall access/posts. It should be precise, though – I have to be able to allow only messages from “Mafia wars game” on my wall for this group. I.e. it should also take into account types of the posts;
b. friends tagging;
c. applications, pages, and groups promotions;

4. Create wizards. Make in-place links to wizards and make wizards searchable. Those “adjust authorization” links could be links to wizards;
5. Join Friends link with “Edit Friends” page;
6. Show me filter of my groups/friends (recently interacted?) so I can filter my wall posts by them.
7. Show me list of my groups/friends (recently interacted?) so I can see their wall posts quickly on my page.
8. Add history and way to set persistent status for the chat on the chat window.

I should confess: I might not be the most typical facebook’s user (I play Mafia wars), but I represent some wide group and most of the issues, I believe, are the same for most of us.
As soon as you play Mafia wars you become kind of facebook maniac, friend of hundreds of people and active user of user groups. You really don’t want to share your personal stuff with guys who are just in your mafia. 🙂

Oh, and yes, I do love Facebook, that’s why I spent my time writing this after all! 🙂

What is cloud computing? Cloud computing main idea explained

The cloud computing is the style of computing which is linearly scalable over network.

There are at least 2 variations of concept:

  1. Client-side cloud computing, which is client-based software which is at the same time client and server to many other instances. Examples are:  Skype, BitTorrent, SETI@home.
  2. Server-side cloud computing, which is automatically scalable systems like Amazon S3 or Google Apps Engine  or Salesforce which provide services on their own platform and hardware and just platforms such as Appistry for deployment on your own hardware.

We will focus on questions and concerns about server-side case.

Server-side cloud computing is when the parts of the stack where your application is running is cloned on demand if load is increasing and freed on load decrease. This is of course mostly about web and business-logic parts of the stack but also for databases. I.e. if you can automatically get more computing resources and/or more scaled database.

This is all, of course, is nothing new and could be implemented with “old” software technologies, but usually all cloud providers supply their own API optimized for cloud computing. Currently most of clouds implementations supports databases, distributed caching and transactions.

Concerns

The main concern is, of course, security, since for cloud-services providers your software is deployed on other-company’s servers. Another concern is that this architecture have issues with short high spikes loads, when it starts to scale after spike.

When to use

  1. If you don’t know what load is going to be for your application;
  2. When you don’t want to invest in your new hardware, clouds will be able to reuse your existing resources or you can rent the service, which will charge you only for used resources;

The anatomy of cloud computing is another good resource on this subject.

Berkeley’s view on the subject.