[OPEN-ILS-DEV] C nits: object.c (Part 5)

[Scott McKellar]

The attachment includes a new version of the jsonFormatString 
function from object.c.  With the test data I used, this version is 
about twelve times as fast as the original.

In the attachment, this new version is named new_jsonFormatString.
The original is also included for comparison purposes.  Various
supporting functions are also included verbatim from the code 
currently on the website, except that in a few places I replaced the
OSRF_MALLOC macro with the safe_malloc function.

In the first phase of the rewrite, my main goal was to minimize calls
to malloc() and free(), since those are relatively expensive
operations.  Here is a summary of the first phase of the rewrite:

---------------

1. Instead of initializing the growing_buffer with a fixed size,
I initialize it with a size equal to four times the length of the
input string. In most cases (including my test string) this initial
allocation should eliminate the need to expand the internal buffer 
within the growing_buffer.

2. I call strlen() on the input string just once, and save the
result, rather than calling it for every iteration.

3. I capture string[i] in a new variable c, rather than subscripting
into the character array repeatedly within the loop.  In theory
this approach may be more efficient, especially if c can be stored
in a register.  In practice the compiler may apply this optimization
anyway.

4. Instead of calling buffer_fadd(), I make separate calls to 
buffer_add_char().  By this means I avoid many calls to memset()
and vsnprintf().  (Later I created a more efficient replacement for
buffer_add_char(), as described below.)

5. Instead of calling __tabs(), I created a new utility function
buffer_pad().  It appends a specified number of occurrences of a
specific character, in this case blank spaces, to a growing_buffer.
Every time I avoid a call to __tabs(), I eliminate three calls to 
malloc(), memset(), and free().

6. At the end of the function, instead of strduping the internal
buffer of the growing_buffer and then throwing that internal
buffer away, I capture the internal buffer and reuse it.  To do so
I wrote a trivial new utility function buffer_release().

----------------------

For test data, I used a sample JSON string that I got from the web
somewhere.  With this test string, the old jsonFormatString() makes
84 calls to malloc() and free() (including calls to strdup(), which
calls malloc() internally).  The new version calls them only twice,
and calls vsnprintf() not at all.

The test driver calls each version of this function 10,000 times
and captures the timing with clock().  On my system, one clock tick
equals one microsecond.  10,000 calls to the old version take about
980 milliseconds.  10,000 calls to the newer version, as described
above, took about 410 milliseconds.

I was surprised that the improvement was no greater than that, so
I looked around for something else to optimize, and found one in
buffer_add_char().

The original version of this function packages the input character
in a string and passes it to buffer_add().  I rewrote 
buffer_add_char() as a new function new_buffer_add_char(), which
is modeled on buffer_add() but specialized for a single character.

When I changed new_jsonFormatString to use this new utility function,
most of the remaining overhead disappeared.  10,000 calls to the new
function now take 80 milliseconds -- about one twelfth of the 
original elapsed time.

Tastes may of course vary, but in my opinion the new version of
jsonFormatString() is just as readable and maintainable as the
original.

----------------

I suspect that jsonFormatString() is not used so much that the
speedup will be noticeable.  However a couple of the optimizations 
used here are applicable elsewhere.

I have seen several places where we use a growing_buffer as a
temporary workspace, make a copy of the internal buffer, and 
immediately throw the growing_buffer away.  There are probably other
such places that I haven't seen yet.  They can benefit from the new
buffer_release function.

The rewrite of buffer_add_char() will probably have more of an 
impact, and without changing any of the code that calls it.  It's 
the sort of function that tends to be called repeatedly, so any 
speedup is welcome.

Scott McKellar
http://home.swbell.net/mck9/aargh/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: jsonfmt.c
Type: text/x-csrc
Size: 7577 bytes
Desc: 1021146075-jsonfmt.c
Url : http://list.georgialibraries.org/pipermail/open-ils-dev/attachments/20070409/8a8f596c/jsonfmt.bin