# Why Is PayPal Screwing Indians? Short version.

Today I received the following mail from PayPal

As part of our commitment to provide a high level of customer service, we would like to give you a 30-day advance notice on changes to our user agreement for India.

With effect from 1 March 2011, you are required to comply with the requirements set out in the notification of the Reserve Bank of India governing the processing and settlement of export-related receipts facilitated by online payment gateways (“RBI Guidelines”).

In order to comply with the RBI Guidelines, our user agreement in India will be amended for the following services as follows:

1. Any balance in and all future payments into your PayPal account may not be used to buy goods or services and must be transferred to your bank account in India within 7 days from the receipt of confirmation from the buyer in respect of the goods or services; and
2. Export-related payments for goods and services into your PayPal account may not exceed US$500 per transaction. PayPal always conviniently quote RBI for all wrong doings but from a post – Why Is PayPal Screwing Indians? An ex-RBI Employee Tells Me The Facts, I came to know of the reason. Which can be summarized as, any organization which stores others’ money for more than 7 days need to be treated as banks. Also all inflow of cash of more than 500 USD needs to be reported to RBI. Paypal neither wants to follow the bank regulations nor it wants to go into hassle of informing RBI. So, finally all Indian startups end up loosing. I wonder what is keeping banks like ICICI, Citi or HDFC to start such a service in India? This is a great new open market with practically no competition in India. # Amar’s blog: Making sense of standard deviation Very good blog post which tries to explain the intuitive meaning of Standard Deviation. # 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(AbstractList.java:713)
java.util.SubList$1.nextIndex(AbstractList.java:713) ...Repeated 100s of times... java.util.SubList$1.nextIndex(AbstractList.java:713)
java.util.SubList$1.hasNext(AbstractList.java:691) java.util.SubList$1.next(AbstractList.java:695)
java.util.SubList$1.next(AbstractList.java:696) ...Again repeated 100s of times... java.util.SubList$1.next(AbstractList.java:696)
java.util.AbstractList.hashCode(AbstractList.java:526)
java.util.Collections$UnmodifiableList.hashCode(Collections.java:1152) org.apache.myfaces.trinidad.util.CollectionUtils$DelegatingCollection.hashCode(CollectionUtils.java:603) ...

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.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;
list.clear();
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();
System.out.println(alist.hashCode());
long endTime = System.nanoTime();
System.out.println("Total time taken for hasCode() = " + (endTime - startTime) / 1000000.0 + "ms");
startTime = System.nanoTime();
System.out.println(blist.hashCode());
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) {
checkForComodification();
return new ListIterator<E>() {
private final ListIterator<E> i = l.listIterator(index+offset);
public boolean hasNext() { return nextIndex() < size; }
public E next() {
if (hasNext())
return i.next();
else
throw new NoSuchElementException();
}
public boolean hasPrevious() { return previousIndex() >= 0; }
public E previous() {
if (hasPrevious())
return i.previous();
else
throw new NoSuchElementException();
}
public int nextIndex() { return i.nextIndex() - offset; }
public int previousIndex() { return i.previousIndex() - offset; }
public void remove() {
i.remove();
SubList.this.modCount = l.modCount; size--;
}
public void set(E e) { i.set(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 SubList1.next(). 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.SubList1.hasNext(AbstractList.java:691). 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)$

# Bloggers’ Rights | Electronic Frontier Foundation

Rights of a blogger.

# Java Performance in 64bit land

Verdict: If your application runs on 32bit Java then don’t upgrade to 64bit Java!

You surprised? Click on the link above.

# Windows Phone 7 is, as we speak, losing fantastic applications because of its approval process.

I would like to quote one para from the linked post.

I can’t overestimate how frustrated my clients are with the Microsoft approval process. It ranges from sadness to fury. Clients who are on virtually all other platforms are expressing frustration that they have never had so much trouble getting through an approval process. The rejection reports are inconsistent, spotty, and fragmented. We will submit an app 5 times and get different “errors” back each time. Nine times out of ten, those errors are not errors, but complaints about UX functionality. Of those, at least half of them are complaints about functionality that, if fixed, would worsen the user experience.

I love Microsoft and I love Windows Phone 7, but rejecting apps based on the UX guidelines (while not giving us the tools to abide by the guidelines effectively) is a recipe for suicide.