14

(This post is regarding High Frequency type programming)

I recently saw on a forum (I think they were discussing Java) that if you have to parse a lot of string data its better to use a byte array than a string with a split(). The exact post was:

One performance trick to working with any language, C++, Java, C# is to avoid object creation. It's not the cost of allocation or GC, its the cost to access large memory arrays that dont fit in the CPU cache.

Modern CPU's are much faster than their memory. They stall for many, many cycles for each cache miss. Most of the CPU transister budget is allocated to reduce this with large caches and lots of ticks.

GPU's solve the problem differently by having lots of threads ready to execute to hide memory access latency and have little or no cache and spend the transistors on more cores.

So, for example, rather than using String's and split to parse a message, use byte arrays that can be updated in place. You really want to avoid random memory access over large data structures, at least in the inner loops.

Is he just saying "dont use strings because they're an object and creating objects is costly" ? Or is he saying something else?

Does using a byte array ensure the data remains in the cache for as long as possible? When you use a string is it too large to be held in the CPU cache? Generally, is using the primitive data types the best methods for writing faster code?

2 Answers 2

16

He's saying that if you break a chunk text up into separate string objects, those string objects have worse locality than the large array of text. Each string, and the array of characters it contains, is going to be somewhere else in memory; they can be spread all over the place. It is likely that the memory cache will have to thrash in and out to access the various strings as you process the data. In contrast, the one large array has the best possible locality, as all the data is on one area of memory, and cache-thrashing will be kept to a minimum.

There are limits to this, of course: if the text is very, very large, and you only need to parse out part of it, then those few small strings might fit better in the cache than the large chunk of text.

3
  • You said "they can be spread all over the place". Are the characters of a String stored in continuous memory, or like a linked list?
    – user997112
    Oct 24, 2011 at 14:24
  • The characters are in continuous memory. But generally a string object consists of two independent chunks: the string object itself, and an array to hold the characters. Then if you create many strings, each of those strings, and each of their arrays, is someplace, and there's no guarantee than any of that multitude of objects is going to be on the same region of memory; each one, being separately allocated, could be anywhere. In C++, the string objects themselves could all be in the same place if they were allocated in a value array; in Java you wouldn't even have that. Oct 24, 2011 at 14:36
  • The characters within a String are continous, however if you have multiple strings they can be all over the place. If you use String.substring in Java, it is a view to the underlying string, so this won't happen, however C++ and C# take copies of the source data when taking a substring of another String. Oct 24, 2011 at 14:52
3

There are lots of other reasons to use byte[] or char* instead of Strings for HFT. Strings consists of 16-bit char in Java and are immutable. byte[] or ByteBuffer are easily recycled, have good cache locatity, can be off the heap (direct) saving a copy, avoiding character encoders. This all assumes you are using ASCII data.

char* or ByteBuffers can also be mapped to network adapters to save another copy. (With some fiddling for ByteBuffers)

In HFT you are rarely dealing with large amounts of data at once. Ideally you want to be processing data as soon as it comes down the Socket. i.e. one packet at a time. (about 1.5 KB)

4
  • How would you keep a byte array off the heap, wouldn't you have to use 'new' in the declaration?
    – user997112
    Oct 24, 2011 at 14:26
  • In C++, you need to use new or malloc In Java, you can use a ByteBuffer.allocateDirect() (which is a wrapper for a malloced block of memory) Using reflection or JNI you can change where the address points to so it can access a network adapter directly (if you are using kernel by-pass) You can do away with the ByteBuffer completely if you use the Unsafe class (though it rarely makes enough of a difference) Oct 24, 2011 at 14:39
  • Dear Peter, could you possibly elaborate on "Using reflection or JNI you can change where the address points to so it can access a network adapter directly (if you are using kernel by-pass)". Do you know any websites with some small example code? I presume this is much easier to do in C++ than in Java?
    – user997112
    Oct 24, 2011 at 16:48
  • This is trivial to do in C or C++. All you need is a pointer which is second nature. In Java you have to jump through a few hoops but you can achieve the same thing. I am not sure what examples I can show you other than it just setting a field using reflection. i.e. Field.setLong(); Oct 24, 2011 at 21:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.