The Joys of String Allocation

Note: This post will only be of interest to other software developers.  Feel free to skip it if you’re not a programmer :)

After a large corporate customer of ours upgraded to the latest version of FeedDemon, they complained that the "Subscription Home" report took a much longer time to display than it did in the previous version.

At first I was stumped by this, since nobody else had mentioned similar problems.  But then I discovered that they were subscribed to several thousand feeds – far more than most FeedDemon customers.  Most of these feeds had unread items, which meant that the subscription report was displaying pretty much every feed they were subscribed to.

After I got a copy of their feeds, I saw the problem right away: it turned out to be caused by the favicons that were added to this report in the latest version.  The way I had coded it, the string which held the contents of the report was being reallocated every single time a favicon was inserted into it.  So with this customer’s subscriptions, the report string was being reallocated several thousand times.  Ouch.

High-level programming languages usually handle memory allocation behind-the-scenes, so you’re often unaware that it’s happening, but I should’ve known better.  Many years ago I programmed in assembler, so I know what’s really going on when dealing with string operations.  Memory allocation is a big reason why many string operations are slow, and when you insert one string into another, the memory for the destination string has to be reallocated to allow enough room for the inserted characters.

Anyway, after chiding myself for my newbie mistake, I rewrote the code so that all memory was pre-allocated up front, and the favicons were simply copied directly into this pre-allocated memory (in other words, inserting favicons into the report string now requires a single memory allocation).  The code is significantly more complex than it was, but my profiler shows that it’s now 1137.81% faster than before.

That strikes me as a pretty good illustration of the performance cost of memory allocation :)

2 thoughts on “The Joys of String Allocation

  1. Ouch! Good job on catching it Nick!
    It’s funny how the simplest things that slip by you can cause such unintended havoc down the line, at least you noticed very shortly after adding the offending code. You could have not known about this till 6 months time.. would you have found it so easily then?

    Like

  2. I had a similar issue with NewsMonster….
    If users had a LOT of feeds the template to build the page would take forever to build and then render.
    Worked on a few hundred but not a few thousand.
    I ended up reworking it to include an inline HTTP server and then dovetailing that into the Mozilla XPCOM layer so that newsmonster: URLs would then serve from Tomcat into the browser so I could use a real template language.
    That’s where Rojo came from ;)

    Like

Comments are closed.