FAST compression and CPU utilization

dimitrylondon_x · November 17, 2008, 4:59am

Imported from previous forum

dimitrylondon_x · November 17, 2008, 4:59am

Hi, everyone,

what are the expectations for the FAST encoder and decoder with respect to CPU utilization? My implementation encodes approximately 90K+ messages per second and decodes 120K+ messages per second, with compression ratio of 3x (for Level2 data).

However, the bad news is that Fast decoder uses more CPU than its non-FAST peer, and the gap widens at higher rates. At 50K messages per second, FAST utiliizes over 2x of CPU (20% compared to 10%).

Is this really expected? I was hoping that since less data travels over the network, the CPU utilization would be comparable (as latency is).

Thanks,
Dimitry

andersfuruhed_x · November 17, 2008, 10:00am

Hi, everyone,

what are the expectations for the FAST encoder and decoder with respect
to CPU utilization? My implementation encodes approximately 90K+
messages per second and decodes 120K+ messages per second, with
compression ratio of 3x (for Level2 data).

However, the bad news is that Fast decoder uses more CPU than its non-
FAST peer, and the gap widens at higher rates. At 50K messages per
second, FAST utiliizes over 2x of CPU (20% compared to 10%).

Is this really expected? I was hoping that since less data travels over
the network, the CPU utilization would be comparable (as latency is).

Thanks, Dimitry

Dimitry,
the difference in message layout, e.g., the use of fewer and larger MarketDataIncrementalRefresh with multiple internal entries in contrast with a feed using more but smaller messages, makes it hard to make comparison between feeds on a messages per second level.
One option is to measure cpu use vs fields per second or FAST encoded bits per second, both as a way of comparing implementations. Using bits per second also makes it possible to compare processing complexity for different feeds.
I think that we have measured a factor of about five in messages per second decoded depending on what data set is used. Also, we have seen a factor of five to ten in encoder/decoder performance comparing the original FAST 1.0 sample code to more heavily optimized implementations.

Cheers, Anders

dimitrylondon_x · November 17, 2008, 3:18pm

Thanks, Anders. The issue is that a process parsing an ascii data stream and creating strings is taking a lot less CPU than a FAST decoder parsing a much smaller data stream and using mostly native (non-string types).

Here are some specifics:

The level2 data contains for 4 market data entries with Price, Time, and Size specified for each entry, with the first entry containing 2 strings for tick and market. Thus, the total number of fields is 14, with 2 strings and 12 native types.
non-FAST decoder receives an ascii stream containing the above data in a proprietary string format, parses it, and copies 14 strings using for all the values. The length of the ascii message is about 200 bytes.
The FAST decoder receives a FAST message of a length of 60 bytes, and as it decodes each field, constructs an object for each of these fields. IOW, the same 14 fields are eventually constructed, with 12 native fields, and 2 strings. This process takes almost twice as much CPU as the #2 above.

Here is a deserialized template snippet:

Group name=MDIncRefresh|ID=0(ROOT)

Sequence name=MDEntries|ID=1|

Group name=Level2|ID=2|

End of Group Name=Level2|ID=2

Group name=Instrument|ID=3

End of Template name=MDIncRefresh|ID=30

Hi, everyone,

what are the expectations for the FAST encoder and decoder with
respect to CPU utilization? My implementation encodes approximately
90K+ messages per second and decodes 120K+ messages per second, with
compression ratio of 3x (for Level2 data).

However, the bad news is that Fast decoder uses more CPU than its non-
FAST peer, and the gap widens at higher rates. At 50K messages per
second, FAST utiliizes over 2x of CPU (20% compared to 10%).

Is this really expected? I was hoping that since less data travels
over the network, the CPU utilization would be comparable (as
latency is).

Thanks, Dimitry

Dimitry, the difference in message layout, e.g., the use of fewer and
larger MarketDataIncrementalRefresh with multiple internal entries in
contrast with a feed using more but smaller messages, makes it hard to
make comparison between feeds on a messages per second level. One option
is to measure cpu use vs fields per second or FAST encoded bits per
second, both as a way of comparing implementations. Using bits per
second also makes it possible to compare processing complexity for
different feeds. I think that we have measured a factor of about five in
messages per second decoded depending on what data set is used. Also, we
have seen a factor of five to ten in encoder/decoder performance
comparing the original FAST 1.0 sample code to more heavily optimized
implementations.

Cheers, Anders

dimitrylondon_x · November 19, 2008, 4:48pm

I made some additional performance improvements by elliminating unnecessary memcpys, and while I did see the marginal improvement in latency, but in terms of CPU the FAST decoder is 20% while NON-Fast is never above 13%, and is mostly 10% at the rate of 50 messages/per second. I can probably squeeze a bit more - but I think my implementation is almost optimal.

I don’t know yet what happens at the higher message rates but are the CPU stats expected? In more general terms, what is the FAST expectation in terms of CPU compared to the similar non-FAST implementation? is 7-10% CPU increase expected?

For example, does anyone have similar stats of decoding CME non-FAST feed vs CME FAST feed?

Thanks,
Dimitry

Thanks, Anders. The issue is that a process parsing an ascii data
stream and creating strings is taking a lot less CPU than a FAST
decoder parsing a much smaller data stream and using mostly native (non-
string types).

Here are some specifics:

The level2 data contains for 4 market data entries with Price, Time,
and Size specified for each entry, with the first entry containing 2
strings for tick and market. Thus, the total number of fields is 14,
with 2 strings and 12 native types.

non-FAST decoder receives an ascii stream containing the above data
in a proprietary string format, parses it, and copies 14 strings
using for all the values. The length of the ascii message is about
200 bytes.

The FAST decoder receives a FAST message of a length of 60 bytes, and
as it decodes each field, constructs an object for each of these
fields. IOW, the same 14 fields are eventually constructed, with 12
native fields, and 2 strings. This process takes almost twice as much
CPU as the #2 above.

Here is a deserialized template snippet:

Group name=MDIncRefresh|ID=0(ROOT)

|fld id=35|fldtype=Primitive|type=String|op=Constant|Value:X |fld
id=8|fld type=Primitive|type=String|op=Constant|Value: FIX.5.0.SP1 |fld
id=34|fld type=Primitive|type=U32|op=None| |fld id=52|fld
type=Primitive|type=U32|op=None|

Sequence name=MDEntries|ID=1|

|fld id=268|fld type=Sequence|type=U32|op=None| |fld id=279|fld
type=Primitive|type=String|op=Copy|flags=Optional |fld id=269|fld
type=Primitive|type=String|op=Copy|flags=Optional |fld id=278|fld
type=Primitive|type=String|op=Copy|flags=Optional |fld id=270|fld
type=Primitive|type=Decimal|op=Copy|flags=Optional |fld id=271|fld
type=Primitive|type=U32|op=Copy|flags=Optional

Group name=Level2|ID=2|

|fld id=346|fld type=Primitive|type=U32|op=Copy|flags=Optional |fld
id=290|fld type=Primitive|type=U32|op=Copy|flags=Optional

End of Group Name=Level2|ID=2

Group name=Instrument|ID=3

|fld id=22|fld type=Primitive|type=String|op=Constant|flags=Group|Value:
122 |fld id=48|fld type=Primitive|type=String|op=Copy|flags=Group

End of Template name=MDIncRefresh|ID=30

Hi, everyone,

what are the expectations for the FAST encoder and decoder with
respect to CPU utilization? My implementation encodes approximately
90K+ messages per second and decodes 120K+ messages per second, with
compression ratio of 3x (for Level2 data).

However, the bad news is that Fast decoder uses more CPU than its
non- FAST peer, and the gap widens at higher rates. At 50K messages
per second, FAST utiliizes over 2x of CPU (20% compared to 10%).

Is this really expected? I was hoping that since less data travels
over the network, the CPU utilization would be comparable (as
latency is).

Thanks, Dimitry

Dimitry, the difference in message layout, e.g., the use of fewer and
larger MarketDataIncrementalRefresh with multiple internal entries in
contrast with a feed using more but smaller messages, makes it hard to
make comparison between feeds on a messages per second level. One
option is to measure cpu use vs fields per second or FAST encoded bits
per second, both as a way of comparing implementations. Using bits per
second also makes it possible to compare processing complexity for
different feeds. I think that we have measured a factor of about five
in messages per second decoded depending on what data set is used.
Also, we have seen a factor of five to ten in encoder/decoder
performance comparing the original FAST 1.0 sample code to more
heavily optimized implementations.

Cheers, Anders

rufusme_x · November 22, 2008, 6:53am

I made some additional performance improvements by elliminating
unnecessary memcpys, and while I did see the marginal improvement in
latency, but in terms of CPU the FAST decoder is 20% while NON-Fast is
never above 13%, and is mostly 10% at the rate of 50 messages/per
second. I can probably squeeze a bit more - but I think my
implementation is almost optimal.

I don’t know yet what happens at the higher message rates but are the
CPU stats expected? In more general terms, what is the FAST expectation
in terms of CPU compared to the similar non-FAST implementation? is 7-
10% CPU increase expected?

For example, does anyone have similar stats of decoding CME non-FAST
feed vs CME FAST feed?

Thanks, Dimitry

Dimitry, I can’t speak for others. But from our own experience with the CME RLC (legacy) vs FIX/FAST feed, we are using approximately 30-35% less CPU vs before. However, our ticker plant is only interested in a subset of products (concept inherited from the old RLC over TIBCO subscription channels). Under RLC, the market data handler has to fully ZLIB decompress the packet, have the complete RLC string in memory, and then parse the string. Under FIX/FAST, we are able to skip the conversion of fields for products that the Ticker Plant does not subscribe to, also for any fields does not have stored value (operators such as COPY, DEFAULT only, etc), the parser will even ignore full parse of that field.

From my experience, it is not the string parse that is CPU intensive, it is the ZLIB compression / decompression that is CPU intensive, for the CME MDP feed. If it is just the string parse, then I would venture to say that FIX/FAST would be slower (I guess I can rig up a test to see how much the difference is).

Any others sharing their experiences would be greatly appreciated.

rolfandersson58_x · November 22, 2008, 9:55am

Rufus, Dimitry,

I believe this discussion is very relevant as it shows that it isn’t trivial to understand the potential performance impact of FAST.

I suggest that we assemble a few test cases and data traces that can be used for apples-to-apples performance analysis.

Best,
Rolf

I made some additional performance improvements by elliminating
unnecessary memcpys, and while I did see the marginal improvement in
latency, but in terms of CPU the FAST decoder is 20% while NON-Fast is
never above 13%, and is mostly 10% at the rate of 50 messages/per
second. I can probably squeeze a bit more - but I think my
implementation is almost optimal.

I don’t know yet what happens at the higher message rates but are the
CPU stats expected? In more general terms, what is the FAST
expectation in terms of CPU compared to the similar non-FAST
implementation? is 7- 10% CPU increase expected?

For example, does anyone have similar stats of decoding CME non-FAST
feed vs CME FAST feed?

Thanks, Dimitry

Dimitry, I can’t speak for others. But from our own experience with the
CME RLC (legacy) vs FIX/FAST feed, we are using approximately 30-35%
less CPU vs before. However, our ticker plant is only interested in a
subset of products (concept inherited from the old RLC over TIBCO
subscription channels). Under RLC, the market data handler has to fully
ZLIB decompress the packet, have the complete RLC string in memory, and
then parse the string. Under FIX/FAST, we are able to skip the
conversion of fields for products that the Ticker Plant does not
subscribe to, also for any fields does not have stored value (operators
such as COPY, DEFAULT only, etc), the parser will even ignore full parse
of that field.

From my experience, it is not the string parse that is CPU intensive, it
is the ZLIB compression / decompression that is CPU intensive, for the
CME MDP feed. If it is just the string parse, then I would venture to
say that FIX/FAST would be slower (I guess I can rig up a test to see
how much the difference is).

Any others sharing their experiences would be greatly appreciated.

fplpo_x · November 24, 2008, 6:33pm

[ original email was from Glenn McClements - glenn@wombatfs.com ]
One project I’m working on is to use FAST to replace a self describing message format (similar to TIB/RV’s)and CPU performance was very important for this use case - it was a requirement hat we had to see an overall reduction in CPU.

After a lot of optimizations and tuning I managed to get message encoding on par or less than the current message format, and seeing a overall reduction in CPU because I was also to pack more messages per packet, so there were fewer kernel calls. The saving was more pronounced at higher message rates.

Note that with this implementation it was not possible to compress across messages as the middleware took care of the message packing, though I did use some intra-message delta encoding for timestamps. Compression was still ~60% - 70%. Decoding time is roughly the same, though I haven’t spent as long optimizing that.

Glenn

Rufus, Dimitry,

I believe this discussion is very relevant as it shows that it isn’t
trivial to understand the potential performance impact of FAST.

I suggest that we assemble a few test cases and data traces that can be
used for apples-to-apples performance analysis.

Best, Rolf

I made some additional performance improvements by elliminating
unnecessary memcpys, and while I did see the marginal improvement in
latency, but in terms of CPU the FAST decoder is 20% while NON-Fast
is never above 13%, and is mostly 10% at the rate of 50 messages/per
second. I can probably squeeze a bit more - but I think my
implementation is almost optimal.

I don’t know yet what happens at the higher message rates but are
the CPU stats expected? In more general terms, what is the FAST
expectation in terms of CPU compared to the similar non-FAST
implementation? is 7- 10% CPU increase expected?

For example, does anyone have similar stats of decoding CME non-FAST
feed vs CME FAST feed?

Thanks, Dimitry

Dimitry, I can’t speak for others. But from our own experience with
the CME RLC (legacy) vs FIX/FAST feed, we are using approximately 30-
35% less CPU vs before. However, our ticker plant is only interested
in a subset of products (concept inherited from the old RLC over TIBCO
subscription channels). Under RLC, the market data handler has to
fully ZLIB decompress the packet, have the complete RLC string in
memory, and then parse the string. Under FIX/FAST, we are able to skip
the conversion of fields for products that the Ticker Plant does not
subscribe to, also for any fields does not have stored value
(operators such as COPY, DEFAULT only, etc), the parser will even
ignore full parse of that field.

From my experience, it is not the string parse that is CPU intensive,
it is the ZLIB compression / decompression that is CPU intensive, for
the CME MDP feed. If it is just the string parse, then I would venture
to say that FIX/FAST would be slower (I guess I can rig up a test to
see how much the difference is).

Any others sharing their experiences would be greatly appreciated.

francosabini_x · December 7, 2008, 9:49am

I made some additional performance improvements by elliminating
unnecessary memcpys, and while I did see the marginal improvement in
latency, but in terms of CPU the FAST decoder is 20% while NON-Fast is
never above 13%, and is mostly 10% at the rate of 50 messages/per
second. I can probably squeeze a bit more - but I think my
implementation is almost optimal.

Hello,
we have just passed the CME certification and moved our feed handler in production.
Our software is using more processor than the non-fast older decoder, would you have some hints on how optimize the cme code ?

Thanks
Franco

rolfandersson58_x · December 7, 2008, 10:04am

Franco -

How do you measure the resource utilization?
Are you using the CME sample code, if so Java or C++?

/Rolf

Hello, we have just passed the CME certification and moved our feed
handler in production. Our software is using more processor than the
non-fast older decoder, would you have some hints on how optimize the
cme code ?

Thanks Franco

francosabini_x · December 7, 2008, 1:33pm

Franco -

How do you measure the resource utilization? Are you using the CME
sample code, if so Java or C++?

/Rolf

Our process run on a Solaris box, I’ve used the standard ‘top’ to get the processor % being used.
The feed is written in C++ and is based on CME sample code.
We often have delays and show old information, the program is running on the same machine that hosted the RLC-based feed handler.

Thanks
Franco

rufusme_x · November 24, 2008, 8:33am

have seen a factor of five to ten in encoder/decoder performance
comparing the original FAST 1.0 sample code to more heavily optimized
implementations.

Cheers, Anders

Anders, this is our experience as well. We started with the FAST 1.0 reference code, and was about 95% done with the CME testing / certification (in fact, I even posted a message here about potentially open sourcing our changes!). But then a little “side experiment” showed soo much perf gains, that we ended up replacing the ref code with our own implementation and rewriting good chunk of it. Sure it took us another 6 weeks or so, but the perf gain was 2-3x.

Dimitry, back to some performance numbers (since I am curious myself). For coding, at 100k msg / sec (playback of a CME recorded stream, Interest Rate in this case), the CPU barely registers (maybe 1%?), at 500k msg / sec, the CPU usage is around 4-5% sustained. This is on a standard 2x quad core E5430 at 2.66 ghz, single threaded.

Naturally, as Rolf pointed out, we need to have a set of base line test cases (and test configurations) before we can really do an apples to apples comparison. We will contribute as much as we can, but this darn market thing keep on getting in the way of our “system related side projects”. Not being a vendor has its pluses and minuses.

dimitrylondon_x · November 26, 2008, 7:58pm

In our case, the original non-FAST decoder is very optimized - it simply parses incoming strings and does nothing else. The Fast decoder, on the other hand, parses and does cache lookups/updates (for dictionary fields). So, unlike ZLIB, this processing takes very little CPU.

There are 400% savings in terms of bandwidth for FAST, but the number of instructions is greater (valgrind shows instruction fetch cost at 2x). So the real comparison is between scanning 4x less data and more processing. As I decrease the number of instructions in FAST, the CPU usage goes down. Currently, at 50K msg/sec, FAST takes about 4% more CPU than non-FAST.

I have been adding all sorts of benchmark testing within FAST itself, and I noticed that decoding of a single message takes on avg 6 microseconds but there are occasional spikes causing millisecond responses - this may be the real reason why using FAST appears to take more CPU.

thanks,
Dimitry

have seen a factor of five to ten in encoder/decoder performance
comparing the original FAST 1.0 sample code to more heavily optimized
implementations.

Cheers, Anders

Anders, this is our experience as well. We started with the FAST 1.0
reference code, and was about 95% done with the CME testing /
certification (in fact, I even posted a message here about potentially
open sourcing our changes!). But then a little “side experiment” showed
soo much perf gains, that we ended up replacing the ref code with our
own implementation and rewriting good chunk of it. Sure it took us
another 6 weeks or so, but the perf gain was 2-3x.

Dimitry, back to some performance numbers (since I am curious myself).
For coding, at 100k msg / sec (playback of a CME recorded stream,
Interest Rate in this case), the CPU barely registers (maybe 1%?), at
500k msg / sec, the CPU usage is around 4-5% sustained. This is on a
standard 2x quad core E5430 at 2.66 ghz, single threaded.

Naturally, as Rolf pointed out, we need to have a set of base line test
cases (and test configurations) before we can really do an apples to
apples comparison. We will contribute as much as we can, but this darn
market thing keep on getting in the way of our “system related side
projects”. Not being a vendor has its pluses and minuses.

dimitrylondon_x · January 3, 2009, 1:22am

Hi everyone,

we have been running extensive performance tests for the past couple of months, and after a few more optimizations (such as representing a pmap as an array of 64-bit integers and using bit operations instead byte loop), the FAST CPU utilization is no worse than non-FAST while yielding 200-400% compression. This proves, I think, that FAST performs very well even compared to the most lean applications.

Dimitry

In our case, the original non-FAST decoder is very optimized - it simply
parses incoming strings and does nothing else. The Fast decoder, on the
other hand, parses and does cache lookups/updates (for dictionary
fields). So, unlike ZLIB, this processing takes very little CPU.

There are 400% savings in terms of bandwidth for FAST, but the number of
instructions is greater (valgrind shows instruction fetch cost at 2x).
So the real comparison is between scanning 4x less data and more
processing. As I decrease the number of instructions in FAST, the CPU
usage goes down. Currently, at 50K msg/sec, FAST takes about 4% more CPU
than non-FAST.

I have been adding all sorts of benchmark testing within FAST itself,
and I noticed that decoding of a single message takes on avg 6
microseconds but there are occasional spikes causing millisecond
responses - this may be the real reason why using FAST appears to
take more CPU.

thanks, Dimitry

have seen a factor of five to ten in encoder/decoder performance
comparing the original FAST 1.0 sample code to more heavily
optimized implementations.

Cheers, Anders

Anders, this is our experience as well. We started with the FAST 1.0
reference code, and was about 95% done with the CME testing /
certification (in fact, I even posted a message here about potentially
open sourcing our changes!). But then a little “side experiment”
showed soo much perf gains, that we ended up replacing the ref code
with our own implementation and rewriting good chunk of it. Sure it
took us another 6 weeks or so, but the perf gain was 2-3x.

Dimitry, back to some performance numbers (since I am curious myself).
For coding, at 100k msg / sec (playback of a CME recorded stream,
Interest Rate in this case), the CPU barely registers (maybe 1%?), at
500k msg / sec, the CPU usage is around 4-5% sustained. This is on a
standard 2x quad core E5430 at 2.66 ghz, single threaded.

Naturally, as Rolf pointed out, we need to have a set of base line
test cases (and test configurations) before we can really do an apples
to apples comparison. We will contribute as much as we can, but this
darn market thing keep on getting in the way of our “system related
side projects”. Not being a vendor has its pluses and minuses.

Topic		Replies	Views
CME FastFix Decoder imported , fast-protocol , xid_169643	21	51	September 18, 2008
CME FIX/FAST decoder imported , fast-protocol , xid_169483	16	213	September 16, 2011
FAST Complaints imported , fast-protocol , xid_169600	26	71	February 4, 2010
FAST too complex? imported , fast-protocol , xid_169710	35	56	January 17, 2009
Reinventing Text and NICs imported , fast-protocol , xid_169642	18	222	November 9, 2012

FAST compression and CPU utilization

Related topics