CInk version 0.1 preview


For past few weeks I have been on working on this. This has come out to be quite good. The above video shows rendering being done on latest Google Chrome browser. I have tested my code in Chrome and FireFox 5, and it works with reasonable performance.

About CInk

Sometime back I stumbled upon Aza Raskin’s very inspiring and beautiful Algorithm Ink[sup] 1[/sup]. It’s easy to use and you can create some truly amazing art. From there I learnt that it is a Javascript implementation of Context Free Design Grammar (CFDG), invented by Chris Coyne[sup]2[/sup]. Also, that CFDG contains more language constructs which Algorithm Ink didn’t support, like loops, z-index, etc. Instead it provided a link to C implementation of CFDG – Context Free Art[sup]3[/sup]. When I saw what still more amazing stuffs people have done there, particularly a B/W artwork, “Bleak” [sup]4[/sup], then I decided of re-implementing CFDG in Javascript.

Why Javascript

CInk is not a replacement for its C counterpart – Context Free, but it adds to it. First this allows a way for random nettizens to stumble on it and create something amazing, even if by chance. Second, CInk clearly separates parsing and rendering logics, making it possible to be used to draw your site’s background. Yeah I find that cool. 😉 Third, as a side-effect of the trick Aza used to keep the browser from locking up as the script draws the art, makes for a visual treat. Which the C counterpart cannot, as it is too efficient and fast to render. 😛

Algorithm Ink

CInk can be considered an enhancement of Algorithm Ink, as the rendering logic’s fundamental concepts are from it.  Except for that it is purely a new product. The parser has been created using JSCC[sup]5[/sup] with slightly modified grammar than given in Context Free’s source code.  Output rendered by CInk is now very much like its Context Free. CInk retains support for MOUSEMOVE and MOUSECLICK predefined rules, introduced by Aza. One major difference between CInk and Algorithm Ink is that, unlike Context Free, Algorithm Ink used HSL to RGB color conversion, but CInk uses HSV to RGB conversion. Also CInk code has been made modular and it doesn’t litter the global namespace.

Overall CInk is compatible to Algorithm Ink and Context Free. So, codes for Algorithm Ink will run in CInk and codes for Context Free may need to be scaled down. You can use size {} command for that.


This is just a preview. I haven’t released CInk yet. It will be online when I have created its site. It will be GPL licensed. Currently path commands like LINETO, etc. are not supported, but will be in little future. Though tile{} command is supported but the output will be less than appealing. I am not sure if it is possible to fix this now. For now tile{} will remain broken. Since <canvas> doesn’t support z-indexes, so CInk creates stack of them when rendering a code that refers to z indices. At the end of the rendering all these stacks are merged into the one. This is of course a hack, but can’t help it unless HTML5 specification and browser developers do something about it.

  1. (Algorithm Ink)
  2. (CFDG inventor)
  3. (Context Free Art)
  4. (Bleak Artwork)
  5. (JS Compiler Compiler)

Java subList() gotcha.

Recently I stumbled upon an issue of stuck thread. The thread seemed to be stuck with stack trace something like the one below:-

java.util.SubList$1.nextIndex( ...Repeated 100s of times...
java.util.SubList$ ...Again repeated 100s of times...
org.apache.myfaces.trinidad.util.CollectionUtils$DelegatingCollection.hashCode( ...

My initial reaction was – huh?! Well googling revealed a blog post related to this issue – Java subList Gotcha. Ya I too have used the same title, as it seems to be the most appropriate one.

The gotcha

The author of that blog post explained, that contrary to what you may expect but subList() does not return a new instance of the list but it returns a ‘view’ of it. What this means is that subList() will return an instance of class SubList or RandomAccessSubList, based on if the original list doesn’t or does implement RandomAccess interface, and they contain a reference to the original list. Note that both these classes are actually inner classes of AbstractList. For most part you can simply disregard this piece of information but in some cases it has some serious consequences. Check out the code below.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Sublist {
    public static void main(String[] args) {
        weirdList(new LinkedList<Integer>()); // Will result in generation of
                                              // SubList
        weirdList(new ArrayList<Integer>()); // Will result in generation of
                                             // RandomAccessSubList

    static void weirdList(List<Integer> list) {
        List<Integer> alist = list, blist = list;
        for (int i = 1; i <= 5000; i++) {
        for (int i = 1; i <= 500; i++) {
            alist = alist.subList(1, alist.size()); // Wrong
        for (int i = 1; i <= 500; i++) {
            blist = new ArrayList<Integer>(blist.subList(1, blist.size())); // Correct
        long startTime = System.nanoTime();
        long endTime = System.nanoTime();
        System.out.println("Total time taken for hasCode() = " + (endTime - startTime) / 1000000.0 + "ms");
        startTime = System.nanoTime();
        endTime = System.nanoTime();
        System.out.println("It should take = " + (endTime - startTime) / 1000000.0 + "ms\n");

If you run the above code then you will notice that alist.hasCode() will typically take 4s more than blist.hasCode(). Even though they both pointed to the very same list!

How the hell hashCode() end up triggering this mess?

Before I continue, I would urge that you take a look at how AbstractList.hashCode() is implemented. This will help you to understand as to as how did the code end up calling next() in SubList. See below.

public int hashCode() {
    int hashCode = 1;
    for (E e : this)
        hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
    return hashCode;

From above it seems that a list’s has-code is calculated based on the hash-codes of all its elements. The for-each loop actually gets a reference of the iterator of the list by calling the list’s iterator() method. Then it calls the next() method over the iterator to get the next element if hasNext() returned true. Now lets get back to the first Java code listing. The whole reason for bad performance of alist is due to the following line:-

alist = alist.subList(1, alist.size());

Yes this simple benign looking line. Let’s understand its reason.

Here comes the innocent devil

I already mentioned that subList() returns instance of SubList or RandomAcessSubbList. Now let’s see that code snippet from AbstractList.

public List<E> subList(int fromIndex, int toIndex) {
    return (this instanceof RandomAccess ?
        new RandomAccessSubList<E>(this, fromIndex, toIndex)
        : new SubList<E>(this, fromIndex, toIndex));

Well let’s take the case where alist refers to an instance of LinkedList, and since LinkedList is does not implement RandomAccess so alist.subList() will return a new instance of SubList. This instance of SubList will point to the original list which actually has the elements. So, lets represent that visually as below:-

SubList-1->OriginalList After executing the code alist = alist.subList() for the first time, the situation will be like below:-

(alist = SubList-1)->OriginalList After executing that code the second time, it becomes:-

(alist = SubList-2)->SubList-1->OriginalList So after n-iterations it will be:-

(alist = SubList-n)->SubList-(n-1)->…->SubList-1->OriginalList

Ok, now you must be wondering, what exactly does the above represent? Well then let’s see the code of Sublist.iterator(int).

public ListIterator<E> listIterator(final int index) {
    return new ListIterator<E>() {
        private final ListIterator<E> i = l.listIterator(index+offset);
        public boolean hasNext() { return nextIndex() < size; }
        public E next() {
            if (hasNext())
                throw new NoSuchElementException();
        public boolean hasPrevious() { return previousIndex() >= 0; }
        public E previous() {
            if (hasPrevious())
                return i.previous();
                throw new NoSuchElementException();
        public int nextIndex() { return i.nextIndex() - offset; }
        public int previousIndex() { return i.previousIndex() - offset; }
        public void remove() {
            SubList.this.modCount = l.modCount; size--;
        public void set(E e) { i.set(e); }
        public void add(E e) {
            SubList.this.modCount = l.modCount; size++;

When hashCode() is called on alist, it actually calls hashCode() on the instance of SubList-n. So to get the iterator hasCode() actually invokes SubList.iterator() which in-turn invokes SubList.listIterator() and which finally invokes SubList.listIterator(int) (whose code is shown above). Note that this method returns an anonymous instance of ListIterator. Now take a close look at the stack trace (right at the top of this post). Did you notice the $1 in the stack trace? This means the method is stuck in next() of the anonymous ListIterator. So, the hashCode() code first calls SubList$1.hasNext() which in-turn invokes its own nextIndex() which further invokes the nextIndex() of the iterator of the list it points. So, in case of SubList-n this will be SubList-(n-1). This call will go on and on till the code reaches the original list. If hasNext returned true then next the hashCode() code will invoke SubList$ Which will invoke its own hasNext() and that will again go through all the steps mentioned above, and when it returns true then it will invoke next() on the iterator of the list it references. So for each iterations in hasCode() of SubList-n the code has to recursively go down the full the depth almost 3-times^1!

Finding the maxima. Err… involves some simple maths

Try to run the Java code listed at the top of the post and try changing 5000 to 1000. Then try running that program multiple times, each time increasing the values of the rest two for loops in multiples of 100. You will notice the peak performance penalty comes at iteration of 700 for 1000 elements. You might be surprised at first but think about this. When you increase the iterations so much that SubList-n has zero elements then there will be no performance penalty. This is a limiting case. So there must be some peak point between the two extremes, i.e. when the SubList-n directly refers to the original list (when n=1) but it contains n-1 elements, and the other extreme being when SubList-n has only zero elements. So, we begin. After 1st iteration the number of elements in alist is n-1 and has 1 SubList to reach the original list. After 2nd iteration the number of elements in alist is n-2 and has 2 SubLists to reach the original list. … After xth iteration the number of elements in alist is n-x and has x SubLists to reach the original list.

$$ \begin{align} O(n) &= x (n-x)\\ &= xn – x^2 \end{align} $$

Now to find the maxima,

$$ \begin{align} \frac{dO(n)}{dx} = 0\\ &\Rightarrow \frac{d(xn – x^2)}{dx} = 0\\ &\Rightarrow \frac{ndx}{dx} – \frac{d(x^2)}{dx} = 0\\ &\Rightarrow n – 2x = 0\\ &\Rightarrow n = 2x\\ &\Rightarrow x = \frac{n}{2} \end{align} $$

So from above it is clear that the maxima is reached when number of partitioning (iterations with alist=alist.subList()) is half the total amount of data. Practical experiments show that the actual maxima is slightly shifted further away from the half point.

Summary. Phew! Finally!

If you use subList wrongly then a time will come when dealing with large data your thread will appear to be stuck. In reality the code is not really hung but is doing a hell lot of iterations. In fact if you take the snapshot of your stuck thread then you will see the stack is growing, if not then at least note the position of the line java.util.SubList$1.hasNext( The position of this line would be changing rapidly in the stack.

^1 More accurately n+n+(n-1)+(n-2)+...+1=\frac{n}{2}(3+n)

Computer Science is Great – The Proof

In our college there is a general feeling that computer science is a useless, fancy engineering branch, but I beg to disagree. Without us (programmers) the computer is a useless junk. I made this animation video as a proof for that.This video has been made in Blender and edited in Windows Movie Maker. Everything, even the ‘It is a Junk without us’ portion too has been done in Blender, but, the credits portion has been done in Windows Movie Maker.