Subject: Some timing information for parsing

From: Henning Schulzrinne <[email-masked]>
Date: Sat, 05 Jun 1999 09:00:42 -0400

I wrote a small parser for SIP messages with abbreviations (but
"traditional" CSeq). It only splits the message into lines and then
assigns the header values to the right variables, but does not parse the
header (such as Via or From) itself. (It does parse CSeq and
Content-Length, due to their simplicity.) Continuation lines are
handled, as are CR, CRLF and LF line separations.

Results on a SPARC Ultra 1/170, gcc version egcs-2.91.60, after 100,000
executions, no compiler optimizations:
66.4 microseconds per message. I won't present -O4 results here, since I
suspect that it optimizes out the code itself - the result of the
computation not being used anywhere... [-O4 reduces the execution time
to 17.4 microseconds/message, but as I said, don't trust this result.]

This measurement approach is only realistic if one assumes that the code
is in the cache; it does not account for things like reading data from a
socket or context-switch overhead, but actual computation time is likely
to be about 20-30% smaller due to compiler optimizations. Somebody
should do profiling within a whole system.

The gprof profiler indicates that
72.45% of the time is spent splitting the message (probably since the
routine needs to look at each character);
10.91% of the time is spent actually extracting header values;
 0.7%  of the time is spent in strcasecmp, the routine that checks for
CSeq.

This result was confirmed by changing CSeq to q and comparing the
measured execution time. It changed from 66.4 to 65 us.

Thus, even if one looks only at a small subset of the parser, e.g.,
without URL or Via parsing, making the change suggested saves less than
1% of the computation. Clearly, with any real system, this will be at
least an order of magnitude less, even within the parser. This estimate
is based on the expense of touching each character in parsing the more
complicated headers.

Also, optimizing the line splitting is going to be far more effective
than mucking with header names.

Henning

---

From: Scott Petrack <[email-masked]>
Date: Sat, 5 Jun 1999 23:44:05 -0400 (EDT)

I'm afraid that I'm starting to find this all a bit silly.

SIP proxies look at headers and route the messages based on those headers.
In my optimized proxy, it would improvement throughput by several percent
to have every header the proxy needs to understand on a "fast path." I am
surprised that this is even controversial. No, I am afraid that I can't
share with you the tricks I use to get me to the point where header
parsing is noticeable. My current estimate is somewhere around 2-4%. One
reason I "dared" suggest compact forms to get such an increase is the
absolutely *trivial* amount of work it would entail on the part of older
implementations. Every SIP implementation in the galaxy could have been
made to recognize "q:" for CSeq in much less time than it would have taken
to complain about it.

My application is a highly
optimized proxy server, as stateless as possible as often as possible, 
coded to get the very largest throughput possible. All it does is 
route SIP packets to the next destination (perhaps rewriting the
Request-URI). Of course if there are errors or special problems then
things are much slower. There is no media going through these SIP proxies.
They are doing nothing else. They almost never look at the session 
description.

In toy code made up from my own application, I can get about 2-5%
improvement by using 2-byte fixed length headers. Before you scoff and
shush, please read:

Henning's results really don't reflect my reality, because I have already
optimized a great deal of processing. After optimizing absolutely
everything I can, I got a small but real improvement in my application by
having all headers be a fixed two-byte length. I also noticed that indeed
I might save 20-30 bytes in SIP messages with 5-10 optional headers
(and it is these messages which get me dangerously close to the MTU).  It
was at this point that I posted my note to confctrl. I never suggested
that this will somehow make a server go from 10 SIP messages/second to 
10,000. Henning's toy results showed a 2% improvement with just one field
(66.4 us to 65 us). As Henning so rightly remarked, such results are not
very realistic -- what is realistic is that in this very large proxy
server, comparing strings of many header fields slows things by several
percent. 

To answer other points made in this discussion:

1. Surely in the case of 400 Bad Request at least, a server should copy
all fields from the request into the response. Copying only the fields it
understands may well destroy the "badness" of the request. (Note that this
is STILL not a problem for the CSeq field -- getting back a message with
no CSeq in it is as good an indication as any that that the server could
not understand any CSeq line in the request. There is no need to match the
response to the original request in this case, it is enough for the client
to know that the server did not see any CSeq line)

2. About Anup's comments -- my application is fundamentally different from
the RTSP case, because I am not talking about a User Agent client or
server that is doing a lot of processing of the packets. It is rather like
a large RTSP proxy. My basic bound is the speed of raw IO processing, and
then memory, and after that comes parsing -- I have been able to find
tricks for other things).

3. I accept the argument that we really must remain RFC 822 -like, so I
accept that things other than a colon may be a bad idea. But this still
gives us 26 short headers, which is enough for all common fields.

4. I seem to touched a raw nerve on the "binary vs.
text" debate, and I did not mean to be so controversial. I actually
believe that the two byte short form ("q:", "x:", "w:") seemed to me to be
an elegant compromise -- it can be treated as binary for speed processing,
but really is not harder to understand than "CSeq". For goodness sake, 
you have to be a rather specialized human to think that "CSeq" is human
readable.

Scott

> The gprof profiler indicates that
The SIP parser I have in mind is highly optimized to be a very
The SIP parser I have in mind is highly optimized to be a very