calling all geniuses - major issues :(

[Daniil Sosonkin]

Hello everyone!

Well, I'm stumped and I have no idea what to do I have an issue and I'm not up to the task. So here is my question

I'm writing a financial application which processes, well, stock information coming from exchange. Maybe Java shouldn't be the language of the choice for this (as I'm inclined to think at the moment) but I wouldn't be able to write this in anything else. I'm getting a feed of data with 1MB/s which has to be parsed and some of it redistributed to the subscribers. This is a stock information, so all the data is stored in the Quote object which stored in a HashMap. There are total of 190604 of those objects - that eats memory the same way I eat cheese danish for breakfast.

I'm reusing objects left and right - there's almost no object creation after its all loaded. But I just can't avoid it. And it takes forever to collect it:

0.000: [GC 419456K->418160K(837696K), 1.3565100 secs]
1.357: [Full GC 418160K->418160K(837696K), 0.9539170 secs]
11.774: [Full GC 785202K->757836K(996160K), 23.6389870 secs]
49.772: [Full GC 996159K->834700K(996160K), 34.0950670 secs]
93.869: [Full GC 996159K->830803K(996160K), 82.5172410 secs]
191.697: [Full GC 996159K->830811K(996160K), 62.8875100 secs]

Its impossible! Its killing me! I'm desparate and out of ideas - suddenly the world is a dark and lonely place. And at work, I have no one else to ask a question.

Can anyone offer a hand? This is btw using jdk1.5 on 2Xeon EM64T CPU's w/ 1GB RAM.

[Ernest Friedman-Hill]

Well, I suspect one reason the collection is taking so long is that your Java heap is as big as all of RAM, leaving no space for the OS. Therefore the OS will be swapping memory pages out to disk, and back in, and back out... which takes loads of time. It seems counterintuitive, I know, but your app may well run faster if you cut the heap size by 25-50%.

Otherwise, it's clearly not true that there's "almost no" object creation -- lots of garbage is being created. It just might not be obvious where. There are plenty of heap analysis tools you can use: some IDEs have them, and there are standalone tools like JProbe. JDK 1.5 has its own monitoring tools, although I've not actually used them myself yet (Stan?) But in any case, you want to run a memory profile which shows you what objects are being collected, so you know where to concentrate your efforts. We can guess all we want, but a million guesses are still inferior to one piece of hard data.

[Daniil Sosonkin]

The problem with all those tools - they can't be launched remotely and my computer isn't powerful enough. And another issue is that the application is in almost none-working condition 10 seconds after start. So much data - its hellish!

I did try doing this one the other instance. Still trying to sift through the hard data, but so far it looks that my object reuse is working fine and doesn't seem to be a cause of garbage.

[Ernest Friedman-Hill]

Actually, a lot of those tools can be launched remotely. The JVMDP uses TCP communications!

But in any case, 10 seconds of runtime is more than enough, Make the heap much smaller, run the code for 5 seconds, then look at the data.

[Daniil Sosonkin]

What is JVMDP? I can't seem to find it.

[Ilja Preuss]

As an aside, you would probably attract more geniuses by using a meaningful subject line.

[Ernest Friedman-Hill]

The current, correct acronym is JVMTI. The instrumentation interface for communicating between the JVM and debuggers and other tools. The details are not important -- just the idea that the mechanism is intrinsically distributed.

[Daniil Sosonkin]

Thank you for help. This has been one horrible day I've tried to play around with garbage collector, reducing memory sizes, all the jazz. Then took a look at JVMTI - scary or I'm just good for nothing. Then stumbled upon this library - Javolution. Played around and in half an hour my application loaded just fine But unfortunately market is now closed and I will have to wait to test until tomorrow. But the good news is that it did load with much reduced heap size.

Yes, I should create butter subject lines. But then again if I could write better english, I doubt I'd be coding at all.

[Ilja Preuss]

Originally posted by Daniil Sosonkin:

Yes, I should create butter subject lines. But then again if I could write better english, I doubt I'd be coding at all.

In my opinion, your english is good. It's just that the subject line was a little bit unspecific. I know that it can be hard, especially when you are already stressed out, but investing some effort in a good subject line *really* can make a big difference!

Anyway, nice to see that you seem to have found a solution! Keep us up to date on what happens next...

[Daniil Sosonkin]

Well, here is the update. I give up; its impossible to do. The whole options exchange consists of around 196000 symbols each having trade depth and Level2. The class for that comes out to about 5786 bytes. Multiply that and you have 1.1GB of memory from the start just for the symbols. This will grow and grow and grow and Level2 will keep on changing madly. As soon as ceiling for heap is reached, GC kicks in and thats it - takes about 7mins! Thats it; its over; its done.

Thanks for you help guys!

[Ernest Friedman-Hill]

It's not impossible -- it's just different from what you've done so far. Remember that the creators of UNIX had a 24K machine to work with: that's right, 24 kilobytes of RAM. You might have heard, also, about Doug McIlroy's encoding of a 75K-word English dictionary in 64K of memory. Sometimes the solution isn't obvious, but that doesn't mean it's impossible.

OK, so: you've shown that the symbols can't be stored as 5786-byte objects in-core. There are two ways to approach that, which can be used together or separately: first, use less storage per symbol; second, don't store them in memory. You could, for example, store them on disk, or in a database.

Out of those 190604 objects, I'll bet there are some (actively traded issues) that are used constantly, and some that are used very rarely. Therefore a most-recently-used cache, backed by a database, would likely let you keep only, say, 10% of the symbols in-core at any time. What do you think?

[Ilja Preuss]

You might also want to take a look at the Flyweight design pattern.

[Daniil Sosonkin]

Thanks. I'll be doing a complete rewrite of my quote storage then.

How about this. I'll be storing X amount of quotes in memory and the rest will be writted on disk. Only the most recently quotes will be in memory or those that are being `watched` by clients. Would something like this make sense?

Also thanks for Flyweight design pattern. I think I'm using it in a sense right now. Just have to make it more visible. MMID and Symbol object are being reused. In fact, Symbol is not a String but an object that wraps around byte[] and calculates the hashcode on the fly and resizes the internal array only when needed (by default its 7).

So, a lot of work ahead. Lets see if it works.

[Ernest Friedman-Hill]

Originally posted by Daniil Sosonkin:

How about this. I'll be storing X amount of quotes in memory and the rest will be writted on disk. Only the most recently quotes will be in memory or those that are being `watched` by clients. Would something like this make sense?

Absolutely. That's exactly what I was saying.

[Cormac Blackwell]

Resusing objects can be one of the worst things you can do for garbage collection times. Have a look at http://javaspecialists.co.za/archive/Issue115.html
You also could have a look at high performance collection libraries like trove or javolution.

[Bugra Cakir]

Maybe you can tune GC algorithms. Give it a try.

java "Program" -Xincgc -XX:+NewRatio=4 -Xmx700m

[ October 26, 2005: Message edited by: Bugra Cakir ]
[ October 26, 2005: Message edited by: Bugra Cakir ]

[Mr. C Lamont Gilbert]

There will be nothing slower than writing to disk. Forget that, memory is cheap. First impression I get is that you are not running in a server class VM.

Let us see what your Object class looks like for each symbol.

You should tune your symbol object. The rest of the work you should do by tweaking your GC parameters. Do not reduce the memory available to your JVM (except that you need to leave some for the OS for sure!). Instead tweak the GC of the JVM. The GC is your problem so that is where you should start looking for your answers. Boosting the memory you give to the JVM without tweaking the GC will get you just where you are. The JVM will load up the memory until its full and then dump it. Search for documentation on tuning the GC. I think the 1.5 GC is very tuneable.

As for flyweight, it seems like a natural fit here.

Also, can you create a 2nd program to feed data into your program so you can test this not just during market hours!?

[JuanP barbancho]

Hi,

I think that the problem is the Size of individual objects.

Try to use the pattern Value.

A Question : Are you use Calendar ?

Thanks you

[Daniil Sosonkin]

Thanks for suggestions guys. Let me go though each issue raised to see how I can answer. First of all, let say that I've decided to switch to C++ as I see no viable solution in the near future. And also because the database will go immencely in the upcoming months. Anyone dealing with the market would understand. But I'm not going to abandon Java attempts just out of sheer challenge

First of, I do need to reuse object since constant creation of such makes on sense. There's a stream of data coming in which contain certain info for already existing information - its all about updates. There's a symbol coming from a stream - MSFT - and all I have to do is calculate the new hashcode and lookup a quote object. After that, the object is useless. But I'm reusing its instance because building 100 hashcodes a second is faster than creating 100 useless ojects. Obviously it looks like a variation of a Flyweight design pattern.

Also, all those objects have to be kept in memory of a long time - its an in-memory database. I've tried w/ disk - and yes, its just too slow. I've tried all the possible GC parameter configurations - no luck. So, more memory is the solution.

Below is the code for the Quote object:

 public final class Quote
    {
        public static final int TRADE_HISTORY = 50;
 
        public Symbol symbol;
        public String description;
        public String market;
        public String exparation;
        public boolean option;
        volatile public int decimal_position;
        volatile public int strike_position;
        volatile public float yesterdayClose;
        volatile public float openingPrice;
        volatile public float dayHigh;
        volatile public float dayLow;
        volatile public float ask;
        volatile public float bid;
        volatile public float lastPrice;
        volatile public float strikePrice;
        volatile public float change;
        volatile public int askSize;
        volatile public int bidSize;
        volatile public int volume;
        volatile public int yesterdayVolume;
        volatile public int openInterest;
        public Regional[] regionals;
        public Trade[] trades;
        public byte[] regions;
        public Level2 level2;
        public int tradePosition;
} 

And symbol:

 public final class Symbol
    {
        private byte[] symbol;
        private byte[] actual;
        private int hash;
        private int size;
 
        public Symbol(final String sym)
            {
                this(sym.getBytes());
            }
 
        public Symbol(final byte[] buf)
            {
                this(buf, buf.length);
            }
 
        public Symbol(final byte[] buf, final int len)
            {
                hash = 17;
                symbol = new byte[len];
                size = len;
 
                for (int i = 0; i < len; i++)
                    {
                        symbol[i] = buf[i];
                        hash = 37 * hash + (int)symbol[i];
                    }
            }
 
        public void buildFrom(final byte[] buf, final int len)
            {
                hash = 17;
                size = len;
 
                if (symbol.length < size)
                    symbol = new byte[size];
                
                for (int i = 0; i < len; i++)
                    {
                        symbol[i] = buf[i];
                        hash = 37 * hash + (int)symbol[i];
                    }
 
                actual = null;
            }
 
        public final int getLength()
            {
                return size;
            }
 
        public final byte[] getBytes()
            {
                if (symbol.length == size)
                    return symbol;
 
                if (actual != null && actual.length == size)
                    return actual;
 
                actual = new byte[size];
                for (int i = 0; i < size; i++)
                    actual[i] = symbol[i];
 
                return actual;
            }
 
        public final boolean equals(Object obj)
            {
                if (!(obj instanceof Symbol))
                    {
                        if (obj instanceof String)
                            return new String(symbol).equals(obj);
 
                        return false;
                    }
 
                if (obj == this)
                    return true;
 
                Symbol sym = (Symbol)obj;
                if (sym.size != size)
                    return false;
 
                for (int i = 0; i < size; i++)
                    if (symbol[i] != sym.symbol[i])
                        return false;
 
                return true;
            }
 
        public final int hashCode()
            {
                return hash;
            }
 
        public final String toString()
            {
                return new String(symbol, 0, size);
            }
    }
 

[Cormac Blackwell]

Ok what the heck is the point of actual? What is the stream coming in as? Strings or byte arrays? Calling getBytes on a String is very slow and of course is creating new bytes arrays which will cause garbage collection.

Actually if equals against a string or toString is getting called you are allocating lots of objects for no apparent reason.

I would say you could be better of using Strings instead of Symbols and possibly interning the Strings

Object creation is almost free if the object is not held on too.

If the symbol is coming in as a byte array and it won't change while you are doing the lookup then you could use a much simpler wrapper

If you can't figure out your Java performance problems and go to C++ you are going to be well and truly boned.

[Mr. C Lamont Gilbert]

Ouch. Thats some pretty bad string work. You realize that Strings are interned? And just because you are not referencing it does not mean the string is gone? Sure it may eventually be collected. In order to successfully do what you are doing here you would need the String to never exist in the first place. Once you create it, you might as well hold onto it.

So either take the bytes right off the stream and store them as a series of bytes and compare they as a series of bytes, or just use the string as is and dont try to dump it. Besides, I doubt if string is all that heavy of an instance.

Also, what you are doing in equals is bad. That method will be called each time the object is checked in the map. You are creating and dumping Strings like nobodies business there. insane. [Edit: removed complaint about all hashes == 17]

Also, what you describe is not like the flyweight pattern. Flyweight pattern is when you change the guts of an object to repsent a new object rather than creating a new object from scratch. Its not when you just hold onto old references for reuse.

Did you try a simple String first? Which map are you using? How did you tune your map parameters? What GC parameters exactly did you try? I doubt seriously if you tried the incremental GC -Xincgc. Are you using the String/Symbol as a key into a map?

[ October 27, 2005: Message edited by: Mr. C Lamont Gilbert ]
[ October 27, 2005: Message edited by: Mr. C Lamont Gilbert ]

[Daniil Sosonkin]

You see what it means to work in a place where no one can offer a critical input. Ok, let me answer some questions. First of all, I have a FastMap from javolution which much faster compared to HashMap. Then, Quote objects are mapped by Symbol:

Symbol symbol = new Symbol("MSFT");
Quote quote = new Quote();
quote.symbol = symbol;
 
quotes.put(quote.symbol, quote);

Something like that. Then I have a separate Symbol which uses buildFrom() method to built its internals and lookup Quote by it. I'm getting all the data from a stream of bytes. The Quote is never looked up by String - thats only for debugging. And yes, my first version was using regular String object. No matter what you guys say - this is version works actually much faster and no garbage collection (I did test it for about a week).

The reason for byte[] actual - I'm distributing this info to clients in a binary stream. And when symbol is sent, it uses getBytes(). Instead of creating whole new string or returning size as well - bug prone. New byte[] is created once thats its. So I can call getBytes() a million times at zero cost as long as internal Symbol data doesn't change as it doesn't in 99% of the cases.

[Mr. C Lamont Gilbert]

OK, so did you try the incremental garbage collector?

There should also be a way for the GC to tell you what types of objects are being collected the most. Your problem lies in the JVM not the code for the most part. The JVM is a significant part of a well functioning Java program. It can not be ignored or treated as insignificant.
[ October 27, 2005: Message edited by: Mr. C Lamont Gilbert ]

[Jim Yingst]

Hey, are these symbols all standard 4-letter uppercase stock market abbreviations like MSFT? If so, you could actually encode each symbol as an int instead. There are only 26*26*26*26 = 456976 possible combinations of 4-letter symbols, so an int would certainly be big enough. (Big enough for up to 6 letters in fact if you needed.) You could write one static method which takes 4 characters read from a stream and converts it to an int, and another which takes an int and converts it to 4 characters which it writes to a stream. If you do it right you wouldn't need to create any objects at all for your symbols - they can all be represented with ints.

Now that doesn't really do anything for all the other data you've got in memory. I don't know what's in the Trade, Regional, and Level2 objects, or how many of each there are. If there are a lot of those in memory, and they can't be converted to some simpler form like the Symbol class can, then you may well still have a very big problem on your hands.

Probably the previous suggestions are more valuable in the long run - an MRU cache, heap analysis to find where the biggest problems are, etc. But since you showed the Symbol class specifically I thought it was worthwhile to consider how it might be eliminated entirely.

[Ilja Preuss]

Originally posted by Mr. C Lamont Gilbert:
You realize that Strings are interned?

That's only true for compile time constants and those Strings on which you call the intern() method explicitely. Other Strings that are constructed at runtime aren't interned at all.

[Mr. C Lamont Gilbert]

Originally posted by Ilja Preuss:


That's only true for compile time constants and those Strings on which you call the intern() method explicitely. Other Strings that are constructed at runtime aren't interned at all.

Hey, I didn't know that Perhaps he can buy some time by interning his strings? Then he can compare with == which should be much faster than equals(). (but his map may not agree) Seems like a natural Idea for a server class program. Gobble memory as tradeoff for speed.

I think the conversion to int of the tickers is a good idea for a hashcode. That will make the map really fast.

Nevertheless, his problem is poor GC tweakage. A full GC should not be happening. and it certainly will NEVER happen on the incremental GC. He for sure a a minimum should be using the incremental GC because he can't afford random sized pauses. We should push him away from discussion of his code and into discussion of his tweakage of the GC.
[ October 31, 2005: Message edited by: Mr. C Lamont Gilbert ]

[Tim Cao]

Daniil,

In my opinion, there is no real advantage switching to C++. You still have as much data as with Java to deal with. You can allocate as much memory in Java as you can do in C++. Also, you wont have as good a colection library in C++ as in Java. STL is flawed from its design to implementation, Boost is too complex and underdocumented, etc. There are some other Windows based library but that would tie you to Microsoft platform.

I think your problem is with the design. Do you have the exact requirements for the software? I have tried to get the big picture from your posts but not really fully understand what the problem is. Lets say, you have a collection of quotes, which is readed from a stream. You then need to search, access, update delete them in real time? Or is it something else.

Why dont you post your full problem description and/or requirements here so we can all look at it? If the information is confidential (you seem to be working for a financial company ), then rephrase it . You can pm me too.

Best regards,

Tim.

Originally posted by Daniil Sosonkin:
[QB]Thanks for suggestions guys. Let me go though each issue raised to see how I can answer. First of all, let say that I've decided to switch to C++ as I see no viable solution in the near future. And also because the database will go immencely in the upcoming months. Anyone dealing with the market would understand. But I'm not going to abandon Java attempts just out of sheer challenge

[Daniil Sosonkin]

Sorry for not replying everyone. Thank you very much for the comments. Let me address issues raised.

Mr. Gilbert, I did test a lot of different GC parameters. There's a page somewhere on Sun's site that has an in-depth look at GC and the possible configurations. The incremental GC was the most promising in the beginning. But, as the name seems to imply, it incrementally got slower and slower until sockets timed out. I've actually spoken to few other people who are developing similar applications and it seems that avoiding any and all GC is the prime objective. While it seems that GC is really great feature to have, I begin to suspect that in this particular case it seems to be more of a trouble. Mr. Blackwell, I did read that article - in fact, I'm getting those newsletters and find them an excellent source of useful information - but in this particular case, the objects have to be in memory for the lifetime of the application. Wouldn't it be nice to be able to inform JVM that some objects need not be checked for collection at all

After thinking about the task at hand I've come to the conclusion that (a) my design if faulty (b) I do not have enough experience (c) there's something so obvious and is in front of me that I just don't see it or (d) maybe Java just isn't the tool of choice. Yes, I work for a financial company and as a result its hard to reveal some information. But the basic idea behind the application is this - connect to the ticker plant, get the updates, and distribute them to any clients that subscribe. There's quite a lot of processing of data before it can be distributed to the clients because I do have to extract all the trades and L2 information. The data is coming in at the rate of 1.5MB/s at the market open/close and on average of 700KB/s throughout a day. Thats a lot; but luckily Java can handle the flow What it can't handle is the amount of objects in memory. No matter how you put it, all the quotes have to be in memory forever. So at the moment I have one thread that processes the information from tickerplant and generates client messages (if such are necessary). Then another thread is the one that distributes the messages for all clients. Only 2 threads in all. Everything goes over TCP/IP. The data is being updated in real-time; clients complain if there's just half a second delay - I'm actually amazed that Java can handle this so fast

I love that idea of creating my own hashmap and hashing those symbols. Too bad my math skills are that of an infant The idea crossed my mind several times.

As for C++, well, so far the app is going along. Its been running for couple of days now. For threads I'm using CommonGNU C++ library - very nice too. Its so wierd to program in C++; I keep forgetting its not Java. Hopefully it works out since the data feed will grow much bigger over time.

Maybe I missed few points in my reply.

[Ilja Preuss]

If I'm reading correctly, you are running the system on a two-processor system? Have you tried using the Parallel GC? If I understand correctly, that one should be able to run on one of the processors without stopping your application code running on the other one...

[Daniil Sosonkin]

Originally posted by Ilja Preuss:
If I'm reading correctly, you are running the system on a two-processor system? Have you tried using the Parallel GC? If I understand correctly, that one should be able to run on one of the processors without stopping your application code running on the other one...

Yes, this is a dual CPU. And yes, I've tried parallel GC. But I got the same result. It seems that I didn't configure it correctly because no matter how I tried it seemed to work the same as regular GC although CPU usage indicated otherwise.

[Wagner Danda Da Silva Filho]

Originally posted by Daniil Sosonkin:
... The data is coming in at the rate of 1.5MB/s at the market open/close and on average of 700KB/s throughout a day. Thats a lot; but luckily Java can handle the flow What it can't handle is the amount of objects in memory. No matter how you put it, all the quotes have to be in memory forever. ...

... As for C++, well, so far the app is going along. Its been running for couple of days now. ...

What I still can't understand is why your C++ code can handle all the objects in memory and why java don't... Is your design approach for both languages the same?

[Daniil Sosonkin]

Thats rather simple. The overhead of describing data is a little bigger in Java. Take my Quote class. It contains classes Symbol, Level2, String, Regional and Trade. Then Level2 contains in itself L2Bid and L2Ask which in turn contain Symbol classes. From what I've read the overhead for each class instance can reach up to 12 bytes (for the life of me I can't remember where I've read except that it was somewhere on theserverside.com). Lets not forget that arrays in Java are just special Objects. But in C++, I'm using structs to contain the same data. Also, I'm not using any special Symbol class but just char[]. All in all it came out to less memory allocation. Unless, of course, (c) applies here. Also, I still didn't implement Level2 in C++ so I'm not sure how it will hold up. It seems there's a need to change the implementation - which will prompt me to rewrite Java code as well.

[Wagner Danda Da Silva Filho]

So, if you're sure that your problem in java code is memory capacity (and it doesn't have any memory leaks), it's obviously in my point of view that you'll need to re-factor your java classes to a smaller version (like you did in C++) if you want that code working.
[ November 07, 2005: Message edited by: Wagner Danda ]

[Paul Clapham]

Don't forget that Strings in Java contain 16-bit Unicode characters whereas (as far as I know, correct me if I'm wrong), in C++ you are probably using 8-bit bytes to represent the same data. If your text data is all ASCII and you need to save memory, you could store it as byte arrays in Java.

[Daniil Sosonkin]

Well, at this moment I feel absolutely stupid I've done as Wagner has suggested and basically wrote the same Quote structure as used in C++ into Java. Guess what, stupid stupid me, the result is now that everything seems to be fitting into memory:

Quote about: 112
Trade about: 32
Symbol about: 44
Array: 22,309,832 (array of 192326 Quote)

Now I'm writing a quick program to see how it handles w/ the data. But so far - stupid stupid stupid!

[Wagner Danda Da Silva Filho]

Great news!

[William Brogden]

Hey! Knock off the - plenty of programmers don't recognize the magnitude of additional overhead Strings cause. instead
Thats why there are Performance forums, books and websites.
Please keep us up to date on the status of your project - with a big job like that you are sure to run into interesting problems.
Bill