C# to Java latency sensitive class conversion, would TreeMap replace SortedList in my case?

Question

Im replicating a C# class in Java. (Im a Java newbie.)

My class needs to track int values associated with doubles. It then needs to create an Alerter(int) whenever a value crosses below or a above the doubles.

Alerter.LatencySensitiveAction() , needs to be called immediatly, it is latency sensitive and time critical code. The purpose of the DoubleMap Class is to call LatencySensitiveAction() as fast as possible.

DoubleMap.OnData() is the latency sensitive method of the class (below).

Does TreeMap make sense? I use SortedList in C#. Im looking for an associative collection that stores key/value pairs in sorted order with fast traversal.

I was told that this Java code

for (Map.Entry<Double,Alerter> entry : mAscend.entrySet() )

is not efficient because it creates a new object. What should I use instead?

So basically, i'm asking what collection to use that can associate a double with and int, is stored in sorted order, and what is the fastest way to traverse the collection in order.

I believe my C# code (below) does the job, need help with converting it to Java. If you think my C# code can be improved too.. please do tell.. ty.

Java Code:

public class DoubleMap {

    TreeMap<Double,Alerter> mAscend, mDecend, mHoldAscend, mHoldDecend;

    public DoubleMap()
    {
        mAscend = new TreeMap<Double, Alerter>();
        mDecend = new TreeMap<Double, Alerter>(new ReverseComparator());
    }

    public void Add(boolean rAscend, double value, int size)
    {
        TreeMap<Double,TradeOrder> list = rAscend ? mAscend : mDecend;

        Alerter to = list.get(value);
        if ( to != null )
        {
            Alerter.size += size;
        }
        else 
        {
            to = new Alerter (size);           
            list.put(value, to);
        }
    }

    public void Remove(boolean rAscend, double value, int size)
    {
        TreeMap<Double,TradeOrder> list = rAscend ? mAscend : mDecend;

        Alerter to = list.get(value);
        if ( to != null )
        {
            long nsize = to.size - size;
            if ( nsize <= 0 )
                list.remove(value);
            else
                to.size = nsize;
        }
    }

    public void Ondata(double rValue)
    {
        for (Map.Entry<Double,Alerter> entry : mAscend.entrySet() )
        {
            if ( entry.getKey() > rValue )
                break;

            entry.getValue().LatencySensitiveAction();

            if ( mHoldAscend == null )
                mHoldAscend = new TreeMap<Double,Alerter>(mHoldAscend);
            mAscend.remove(entry.getKey());
        }

        for (Map.Entry<Double,TradeOrder> entry : mDecend.entrySet() )
        {
            if ( entry.getKey() < rValue )
                break;

            entry.getValue().LatencySensitiveAction();

            if ( mHoldDecend == null )
                mHoldDecend = new TreeMap<Double,TradeOrder>(mHoldDecend);
            mHoldDecend.remove(entry.getKey());
        }

        if ( mHoldAscend != null )
        {
            mAscend = mHoldAscend;
            mHoldAscend = null;
        }

        if ( mHoldDecend != null )
        {
            mDecend = mHoldDecend;
            mHoldDecend = null;
        }

    }
}

C# Code:

public class DoubleMap
{
    private SortedList<double, Alerter> mAscend, mDecend, mHoldAscend, mHoldDecend;

    public DoubleMap()
    {
        mAscend = new SortedList<double, Alerter>();
        mDecend = new SortedList<double, Alerter>(new DescendingComparer<double>());
    }

    public void Add(bool rAscend, double rValue, long rSize)
    {
        var list = rAscend ? mAscend : mDecend;
        Alerter to;
        if (list.TryGetValue(rValue, out to))
        {
            to.Size += rSize;
        }
        else
        {
            to = new Alerter(rSize);
            list.Add(rValue, to);
        }
    }

    public void Remove(bool rAscend, double rValue, long rSize)
    {
        var list = rAscend ? mAscend : mDecend;
        Alerter to;
        if (list.TryGetValue(rValue, out to))
        {
            long nqty = to.Size - rSize;
            if (nqty <= 0)
            {
                list.Remove(rValue);
            }
            else
                to.Size = nqty;
        }
    }

    public void OnData(double rValue)
    {
        foreach (var pair in mAscend)
        {
            if (pair.Key > rValue)
                break;

            pair.Value.LatencySensitiveAction();

            if (mHoldAscend == null)
                mHoldAscend = new SortedList<double, Alerter>(mAscend);
            mHoldAscend.Remove(pair.Key);
        }

        foreach (var pair in mDecend)
        {
            if (pair.Key < rValue)
                break;

            pair.Value.LatencySensitiveAction();

            if (mHoldDecend == null)
                mHoldDecend = new SortedList<double, Alerter>(mDecend, new DescendingComparer<double>());
            mHoldDecend.Remove(pair.Key);
        }

        if (mHoldAscend != null)
        {
            mAscend = mHoldAscend;
            mHoldAscend = null;
        }

        if (mHoldDecend != null)
        {
            mDecend = mHoldDecend;
            mHoldDecend = null;
        }
    }
}

class DescendingComparer<T> : IComparer<T> where T : IComparable<T>
{
    public int Compare(T x, T y)
    {
        return y.CompareTo(x);
    }
}

Answer 1

If latency is so important for you, I'd recommend implementing a custom class to handle your order book (this is an order book, right? :-) )

I'd suggest something like the following:

• An array of doubles representing the prices (p.s. why are you using doubles? shouldn't this be either BigDecimal or a fixed point integer to avoid floating point inaccuracy?)
• A corresponding array of longs for the order sizes
• A corresponding array of alerters
• Sort all arrays according to price
• You can then use a binary search directly on the price array to seek out prices in any given range

This approach will give you very low latency.

Downside is that it's O(n) to add/remove orders. But it's such a cheap O(n) with just three arraycopys, that unless your order book is very large the overhead will be so low that you won't notice.

You may also be interested in Javolution which contained a set of very low latency libraries for Java, I think some of which are specifically designed for trading applications.

Answer 2

If you're only doing traversal, why would you use a map at all? You can't perform traversal in less than O(n).

I'd recommend you make an object to encapsulate the order, and take a look at PriorityQueue for your collection.

If you need to do range search, you might also look into TreeSet (if your values are unique) or TreeMap. (But note that you have to do iteration a certain way to get sorted output from these classes.)

EDIT

Are you sure that your reviewer meant that the for (Map.Entry<Double,Alerter> entry : mAscend.entrySet()) was inefficient, and not the code inside the for loop? You're performing new collection creation each time you match a pair (not an inexpensive job on its own, and certainly not a good thing to do inside time-sensitive code). You're doing the same thing inside your C# code.

Try this:

Code Deleted; See history

EDIT 2

I realized that your implementation is actually much slower than necessary because it's relying solely on a TreeMap to do both sorting and lookup. Here is a much faster implementation:

public class DoubleMap {
    HashMap<Double, Alerter> mAscend, mDescend;
    PriorityQueue<Double> pricesAscending, pricesDescending;

    public DoubleMap()
    {
        pricesAscending = new PriorityQueue<Double>(100);
        pricesDescending = new PriorityQueue<Double>(100, new ReverseComparator());
    }

    public void Add(boolean rAscend, double value, int size)
    {
        Map<Double, Alerter> map = rAscend ? mAscend : mDescend;

        Alerter to = map.get(value);
        if ( to != null )
        {
            Alerter.size += size;
        }
        else 
        {
            to = new Alerter (size);           
            map.put(value, to);
            pricesAscending.offer(value);
            pricesDescending.offer(value);
        }
    }

    public void Remove(boolean rAscend, double value, int size)
    {
        Map<Double, Alerter> map = rAscend ? mAscend : mDecend;

        Alerter to = map.get(value);
        if ( to != null )
        {
            long nsize = to.size - size;
            if ( nsize <= 0 )
                map.remove(value);
                pricesAscending.remove(value);
                pricesDescending.remove(value);
            else
                to.size = nsize;
        }
    }

    public void Ondata(double rValue)
    {
        while (pricesAscending.peek() < rValue) {
            mAscend.getValue(pricesAscending.peek()).LatencySensitiveAction();

            mAscend.remove(pricesAscending.poll());
        }

        while (pricesDescending.peek() > rValue) {
            mDescend.getValue(pricesDescending.peek()).LatencySensitiveAction();

            mDescend.remove(pricesDescending.poll());
        }
    }
}

Differences: HashMap has constant-time get() and remove() operations, where TreeMap has O(log(n)) performance for those operations.

PriorityQueue has constant-time peek() and poll() performance.

Answer 3

One thing to keep in mind whenever dealing with "low latency" applications on a modern OS is that it is preemptive. It's not a realtime operating system so any thread can be suspended at any time, and no guarantees are made as to response time. If you're trying to achieve honest low latency/consistent latency, then at least you'll need to push your applications to realtime in the task scheduler. Although even this isn't true realtime, but it will help your threads get more processor time. Also consider that the GC can stop the threads to clean up.

If you are truly interested in achieving the lowest latency, or at least a more guaranteed latency, then I would at least switch to C++ or C. At least then you can control your memory allocations and don't have to worry about a GC going underneath you and causing unexpected latency.