All you need to know about QuickSort

It would be true to say that Quicksort is one of the most popular sorting algorithms. You can find it implemented on the most of the languages and it is present in almost any core library. In Java and Go Quicksort is default sorting algorithm for some data types and it is used in in C++ STL (Introsoft which is used there begins with Quicksort). Such popularity can be explained by the fact that on average, Quicksort is one of the fastest known sorting algorithms. Interestingly that complexity of Quicksort is not less than it is for other algorithms like MergeSort or HeapSort. The best case performance is O(nlogn) and on the worst case it gives O(n^2). Latter, luckily, is exceptional case for the proper implementation. Quicksort performance is gained by the main loop which tends to make excellent usage of CPU caches. Another reason of popularity is that it doesn't need allocation of additional memory.

Personally for me Quicksort appeared as one of the most complex sorting algorithms. The basic idea is pretty simple and usually takes just a few minutes to implement. But that version, of course, if not practically usable. When it comes to details and to efficiency, it is getting more and more complicated.

Quicksort was first discovered by C.A.R. Hoare in 1962 (see "Quicksort," Computer Journal 5, 1, 1962) and in following years algorithm slightly mutated. The most known version is Three-way Quicksort. The most comprehensive of widely known ones is Dual-Pivot Quicksort. Both algorithms will be covered in that post.

JCaptcha, SecureRandom & performance

Personally, I'm not big fan of JCaptcha library and recently was lucky enough to find another problem there. The problem is related mostly to linux and it's implementation of java.security. SecureRandom, which is known to be slow and is locking on every call to it.

For some reason (I suspect that this was the reason) JCaptacha overuse java.security.SecureRandom when it generates background image using FunkyBackgroundGenerator. Number of calls to get next random float can easily reach something around 100 000 per one captcha image. It is basically called at least once for each pixel.

Lets run some quick tests to have a look how bad is that. I have wrote write simple captch engine:

public static class MyImageCaptchaEngine extends ListImageCaptchaEngine {
  protected void buildInitialFactories() {
      WordGenerator wgen = new RandomWordGenerator("ABCDEFGHIJKLMNOPQRSTUVWXYZ123456789");
      RandomRangeColorGenerator cgen = new RandomRangeColorGenerator(
         new int[] {0, 100},
         new int[] {0, 100},
         new int[] {0, 100});
      TextPaster textPaster = new RandomTextPaster(new Integer(7), new Integer(7), cgen, true);

      BackgroundGenerator backgroundGenerator = new FunkyBackgroundGenerator(new Integer(200), new Integer(100));

      Font[] fontsList = new Font[] {
         new Font("Arial", 0, 10),
         new Font("Tahoma", 0, 10),
         new Font("Verdana", 0, 10),
      };

      FontGenerator fontGenerator = new RandomFontGenerator(new Integer(20), new Integer(35), fontsList);

      WordToImage wordToImage = new ComposedWordToImage(fontGenerator, backgroundGenerator, textPaster);
         this.addFactory(new GimpyFactory(wgen, wordToImage));
  }
}

And the test itself:

long begin = System.currentTimeMillis();
for(int i = 0; i != 100; ++i) {
  engine.getNextCaptcha();
}
long end = System.currentTimeMillis();
System.out.println("Total time is [" + (end - begin) + "]");

now lets run it:

Total time is [10967]

Ok, so what we have now it 10967ms, which, I believe, is bad. It can be significantly improved. I'm not very big fan of high-quality random backgrounds, so I will replace SecureRandom class, used by parent of FunkyBackgroundGenerator with "pseudo" random Random class. Funs of high-quality random backgrounds can still use SecureRandom for seeding, through:

public static class MyFunkyBackgroundGenerator extends FunkyBackgroundGenerator {
  public MyFunkyBackgroundGenerator(Integer width, Integer height) {
     super(width, height);
     try {
         Field rndField = AbstractBackgroundGenerator.class.getDeclaredField("myRandom");
         rndField.setAccessible(true);
         rndField.set(this, new Random());
     }
     catch (Exception e) {
         e.printStackTrace();
     }
  }
}

I know, that is dirty hack, but as far "myRandom" is declared with default visibility, that's the shortest way to replace it for now . And what we have now is:

Total time is [1308]

Approximately 7 time quicker. Not that bad, specially for a sample case. In real world application improvement will be even more significant because some other processes may use '/dev/(u)random' or application itself can utilize SecureRandom for other purposes.

That's not it. There is another bottleneck, which is usage of Java2D for rendering captcha images. Java2D is well known for it's problems with multi-threading and the summary of these problems is that Java2D doesn't scale well. Some details can be found here. Possibly the way to fix that problem may be removing Java2D and using direct access to image via WritableRaster instead. However, it doesn't solve all problems, as far as Java2D is still used for drawing text.

ConcurrentHashMap revealed

Java 1.5 introduced some new cool concurrency stuff which is located in java.util.concurrent package. There are lots of good things there including new ConcurrentHashMap class which I'm going to talk about. That class is targeted to be used in concurrent environment and provides significant performance benefits over synchronized version of HashMap. Javadoc doesn't really provide lots of details on how that class works and why can be better than synchronized version of HashMap. I think that understanding of these details is crucial for using that class in a right way, so I've made some research to undercover implementation details and mechanisms used to implement that class.

Some hints for writing secure code

Security and data protection are becoming now more and more popular topics. We are coming into the world where too much information is transfered/used/processed by computer systems and any leak of that information can cause a big trouble. Thus, it is very important for application to protect customer information as much as it can and do not allow it to spread out.

There are many aspects of application security and these cover processes, architecture, infrastructure, code, etc. The whole topic is extremely big and versatile and there are some books written to cover all its possible verges. I will touch just a small piece which is related to something which is in area of developer's responsibility - code and application architecture. Also, I assume that that reader mostly works on web applications implemented on Java or similar platform.

Killing the private (and protected)

Recently on one forum I've found topic which released from memory my C++ days. That was topic about using "private" modifier on methods. The question there was about cases where to use it and why. Everybody knows when you are programming on C++ (as the most glaring example) one of "good practices" is "less client can do - better". Of course that's not in sense of functionality provided to client, but in mind of something which is not explicitly provided. In C++, I believe, the main reason for that is fragility of runtime, which can be easily killed if someone accidentally will do something wrong, which can also cause physical damage to person who is responsible for doing that (worth mentioning, in Java situation is slightly different, it's hard (but still possible, of course) to kill the application by "accidental coding"). And a consequence of such “good practice” is the basic rule – “make private as much as you can”.

Public key infrastructure

Some time ago I was asked to create presentation for my colleagues which describes Public Key Infrastructure, its components, functions, how it generally works, etc. To create that presentation, I've collected some material on that topic and it would be just dissipation to throw it out. That presentation wasn’t technical at all, and that post is not going to be technical as well. It will give just a concept, high-level picture, which, I believe, can be a good base knowledge before start looking at details.

Mac in 1984

Was looking for some presentations on Web and found one made by Steve Jobs in 1984. The reaction of people there is just amazing, I have never seen anything similar on IT event. I wish I would visit one which will be the same impressive :)

Redirecting or error output to variable in shell

Spent couple of painful hours trying to do that. And eventually, here is the code which will output standard output into the file and error into the variable:

var=`(ls -l > ./file.txt) 2>&1`

bloody shell...

Java bridge methods explained

Bridge methods in Java are synthetic methods, which are necessary to implement some of Java language features. The best known samples are covariant return type and a case in generics when erasure of base method's arguments differs from the actual method being invoked.

Kill all child processes from shell script

Small and simple script. Creates Ctrl-C trap and kills all it's child processes in it. Nice to have when your script has many child processes which execution have to be stopped when main script is interrupted by Ctrl-C or other signal.

kill_child_processes() {
    isTopmost=$1
    curPid=$2
    childPids=`ps -o pid --no-headers --ppid ${curPid}`
    for childPid in $childPids
    do
        kill_child_processes 0 $childPid
    done
    if [ $isTopmost -eq 0 ]; then
        kill -9 $curPid 2> /dev/null
    fi
}

# Ctrl-C trap. Catches INT signal
trap "kill_child_processes 1 $$; exit 0" INT

for ((  i = 0 ;  i <= 5;  i++  ))
do
  # do something...
  sleep 10 &
done

wait

Exporting keys from keystore

Recently I had a similar feeling to one I had writing one of previous posts. It appeared that standard java tools do not have some basic functionality, which obviously (well, probably just for me :) ) should be there. Now I had to export key stored in keystore to share it with other department. It appeared, that keytool can't do that and you have to write tiny program by yourself. Not a big problem, really, it's even nice.

There are lots of posts in web describing how to solve that problem, and here is the best code example I found so far to solve that it.
And here is copy/paste of code snipped, just in case if original post will pass away.

File keystoreFile = new File("The filename of the keystore");
KeyStore ks = KeyStore.getInstance("JKS"); // or whatever type of keystore you have
char[] pw = "the keystore password".toCharArray();
InputStream in = new FileInputStream(keystoreFile);
ks.load(in, pw);
in.close();
for (Enumeration en = ks.aliases(); en.hasMoreElements();)
{
    String alias = en.nextElement();
    System.out.println("  Alias\t:" + alias);
    // If the key entry password is not the same a the keystore password then change this
    KeyStore.Entry entry = ks.getEntry(alias, new KeyStore.PasswordProtection(pw)); 
    if (entry instanceof KeyStore.SecretKeyEntry) {
        System.out.println("    SecretKey");
        KeyStore.SecretKeyEntry skEntry = (KeyStore.SecretKeyEntry) entry;
        SecretKey key = skEntry.getSecretKey();
        System.out.println("      alg\t: " + key.getAlgorithm());
    } else if (entry instanceof KeyStore.PrivateKeyEntry) {
        System.out.println("    PrivateKey");
        KeyStore.PrivateKeyEntry pkEntry = (KeyStore.PrivateKeyEntry) entry;
        PrivateKey key = pkEntry.getPrivateKey();
        System.out.println("      alg\t: " + key.getAlgorithm());
        java.security.cert.Certificate certificate = pkEntry.getCertificate();
        System.out.println("      Certificate type\t: " + certificate.getType());
        System.out.println("      Public key\t: " + certificate.getPublicKey().getAlgorithm());
    } else if (entry instanceof KeyStore.TrustedCertificateEntry) {
        System.out.println("    Certificate");
        KeyStore.TrustedCertificateEntry certEntry = (KeyStore.TrustedCertificateEntry) entry;
        java.security.cert.Certificate certificate = certEntry.getTrustedCertificate();
        System.out.println("      type\t: " + certificate.getType());
    }
}

If you need to send key to someone, it handy to make it base64 encoded:

byte[] keyData = key.getEncoded();
BASE64Encoder b64Encoder = new BASE64Encoder();
String b64 = b64Encoder.encode(keyData);
System.out.println("-----BEGIN KEY-----");
System.out.println(b64);
System.out.println("-----END KEY-----");

Compile recursively with javac

To my shame I have never used javac directly for compiling source files, always it was something like "ant". And today it was the first time on my memory when I had to do that :) It was a simple application, just an example for presentation and I didn't want to add anything additional there.
Thing which looks like a trivial task appeared to be not so trivial, because javac doesn't recursively compile files in directories, you have to specify each directory separately or create file with list of files for compilation, something like that:

find ./src -name "*.java" > sources_list.txt
javac -classpath "${CLASSPATH}" @sources_list.txt


On Windows first line should be replaced with: dir .\src\*.java /s /B > sources_list.txt