Tuesday, August 11, 2009

Performance of Amino Queue

Now we got the performance result of Amino Queue in an 8-core X86 machine which is running Linux and IBM JDK v6. We compared the performance of Amino's LockFreeQueue and java.util.concurrent.ConcurrentLinkedQueue. Both of the two queues used lock-free algorithm. Amino queue's algorithm comes from the brilliant paper "An Optimistic Approach to Lock-Free FIFO Queues" of Edya Ladan-Mozes and Nir Shavit. Result of the micro-benchmark shows Amino queue has some advantage:


The key idea behind the new algorithm is a novel way of replacing the singly-linked list of Michael and Scott, whose pointers are inserted using a costly compare-and-swap (CAS) operation, by an optimistic doubly-linked list, whose pointers are updated using a simple store, yet can be fixed if a bad ordering of events causes them to be inconsistent.

2 comments:

Mackenzie said...

Hey guys, I would really like to know the performance of the priority queue running in a Terracota cluster. Do you think it can perform better than the standard priority queue? I'm working in a big system and maybe this could solve a big scalability problem.

Thanks!

James Gan said...

Mackenzie,

Amino Queue is not suitable for the purpose of a priority queue. The function is pretty different. Priority queue needs to maintain priority and much complexer than a normal queue.