Optimizing atof and strtod in MSVC 2008

I recently wrote a text parser for Wavefront OBJ files and once I got it all up and running, I was surprised by the performance. I tend to be somewhat performance conscious when writing code so after realizing I had somehow created the slowest OBJ parser known to man, I was perplexed. It was taking 20 seconds to load the Stanford Bunny (4.83MB as an OBJ file with exported normals).

When parsing a 3d mesh from an OBJ file, it is optimal to collapse equal vertices into an indexed list. This is one of the more complicated steps so my suspicion was that something went wrong there. I was using a hash table to do the comparisons so it should have been fast. I disabled that section of code, and timed the load again. It barely affected the result.

Another common pitfall when parsing files is getting stalls from seeking through the file itself. I had already taken that into consideration and just loaded the whole thing into memory for processing. I was out of ideas and decided to profile the load and see what I had done wrong. I learned that almost all of my time was spent in strlen which was a big red flag considering I never even called strlen during my entire load.

Because I was loading such a large text file, the obvious conclusion is that something was running strlen on the entire buffer it and it was doing it a lot. The culprit was strtod. If you are unfamiliar with strtod, it is basically a version of atof that tells you where it stopped parsing the number. This makes it and it pretty useful for text parsing along with the similar functions strtol and strtoul. For some reason the coder behind the strtod implementation shipped with Visual Studio 2008 decided that he needed to run strlen on the input string. There is somewhere around zero reasons that you should come even close to calling strlen from inside a strtod implementation. It should also be noted that strtol and strtoul do not have the problem. On the other hand, atof does have the problem and is in turn prohibitively slow when called on a large text buffer.

I found some posts online about similar issues and read that it has been fixed in Visual Studio 2010, but I am yet to confirm it. Regardless, I am more interested in a solution that isn't compiler dependent. As I see it, there are a few options here: a) write my own strtod implementation, b) find another string parsing function that can output the same information as strtod (maybe something with streams), or c) write a wrapper on strtod that accounts for its poor implementation. Writing a proper string to floating point number conversion is non-trivial. I also wanted to keep it pretty low level and not get into any more standard library implementation problems that might arise from seeing what magic I could to with stream based parsing. This left me with bandaging up strtod.

The general idea is to quickly figure out where the floating point number ends in the string and copy that over to a local NUL-terminated buffer that strtod can be run on. If for some reason it doesn't fit in the local buffer, just run strtod normally and take the performance hit. I should also point out that there is the option of placing the NUL termination into the input buffer and then restoring the overwritten character at the end of the function. I decided against this method to keep the procedure thread safe. The input is a pointer to const data and the user should be able to assume it will not be modified and allow multiple threads to interact with it at once.

After implementing the new function, my load time for the file went from 20 seconds to 1.5 seconds. You can see the resulting code below.


/******************************************************************************
  Copyright (c) 2008-2010 Ryan Juckett
  http://www.ryanjuckett.com/
 
  This software is provided 'as-is', without any express or implied
  warranty. In no event will the authors be held liable for any damages
  arising from the use of this software.
 
  Permission is granted to anyone to use this software for any purpose,
  including commercial applications, and to alter it and redistribute it
  freely, subject to the following restrictions:
 
  1. The origin of this software must not be misrepresented; you must not
     claim that you wrote the original software. If you use this software
     in a product, an acknowledgment in the product documentation would be
     appreciated but is not required.
 
  2. Altered source versions must be plainly marked as such, and must not be
     misrepresented as being the original software.
 
  3. This notice may not be removed or altered from any source
     distribution.
******************************************************************************/

//******************************************************************************
// StringToF64
// This is a wrapper on 'strtod' because the VS2008 implementation calls
// 'strlen' on the input string which can be very slow if the parsed number is
// part of a large buffer. In order to speed up the potential 'strlen' we load
// the number portion of the string into an internal buffer first.
// 
//    strtod expects the input to point to a string of the following form:
//    [whitespace] [sign] [digits] [.digits] [{d | D | e | E}[sign]digits]
//******************************************************************************
double StringToF64(const char * pString, char ** ppEnd)
{
    //---
    // Find the start of the string
    const char * pNumberStart = pString;
 
    // skip whitespace
    while( isspace(*pNumberStart) )
        ++pNumberStart;
 
    //---
    // Find the end of the string
    const char * pNumberEnd = pNumberStart;
 
    // skip optional sign
    if( *pNumberEnd == '-' || *pNumberEnd == '+' )
        ++pNumberEnd;
 
    // skip optional digits
    while( isdigit(*pNumberEnd) )
        ++pNumberEnd;
 
    // skip optional decimal and digits
    if( *pNumberEnd == '.' )
    {
        ++pNumberEnd;
 
        while( isdigit(*pNumberEnd) )
            ++pNumberEnd;
    }
 
    // skip optional exponent
    if(    *pNumberEnd == 'd'
        || *pNumberEnd == 'D'
        || *pNumberEnd == 'e'
        || *pNumberEnd == 'E' )
    {
        ++pNumberEnd;
 
        if( *pNumberEnd == '-' || *pNumberEnd == '+' )
            ++pNumberEnd;
 
        while( isdigit(*pNumberEnd) )
            ++pNumberEnd;
    }
 
    //---
    // Process the string
    const unsigned numberLen = (pNumberEnd-pNumberStart);
    char buffer[32];
    if( numberLen+1 < sizeof(buffer)/sizeof(buffer[0]) )
    {
        // copy into buffer and terminate with NUL before calling the
        // standard function
        memcpy( buffer, pNumberStart, numberLen*sizeof(buffer[0]) );
        buffer[numberLen] = '\0';
        const double result = strtod( buffer, ppEnd );
 
        // translate end of string back from the buffer to the input string
        if( ppEnd )
        {
            *ppEnd = const_cast<char*>( pNumberStart + (*ppEnd-buffer) );
        }
 
        return result;
    }
    else
    {
        // buffer was too small so just call the standard function on the
        // source input to get a proper result
        return strtod( pString, ppEnd );
    }
}

Here's a wrapper for 32-bit floats. It's technically less correct than the 64-bit version above because MSVC doesn't support strtof. That said, Microsoft's current implementation of strtod has some rounding issues with the last digit of anyway so you might not care.


//******************************************************************************
// StringToF32
// This is a helper function to wrap up StringToF64 for 32 bit values.
//******************************************************************************
float StringToF32(const char * pString, char ** ppEnd)
{
    return (float)StringToF64(pString,ppEnd);            
}

 

Comments