• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
AvCol

[C++] Holy cow are string streams slow

15 posts in this topic

I decided to change my parser ( not really a parser more of a line getter and string manipulator ) to using string streams for more elegant and readable code. Elegant and readable code was what I got but the performance hit is massive. Currently it uses getline to get a string and then uses that string to construct a string stream. The string stream is used for various operations like getting the line header / tokens / body / ignoring comments etc. etc..

But just that one operation string -> stringstream takes 6 seconds(!!) looping through a 40MB standford lucy wavefront obj file. 6 seconds!!!!! and that's on a Q6600 (not the best desktop chip nowadays but its not like its some ancient pos either). By comparison just getline without the string stream construction takes 2.3 seconds.

Why on earth does this one constructor triple the time of the code.

The >> operator seems slow as well. The body of the obj loader (consists of getting a header and tokens and then doing some atois and atofs) went from taking 13 seconds to taking 28.

My old parser used manual searching and tokenizing with for loops, but the input stream was still a C++ stl style one, and for comparison it was able to load lucy in ~18 seconds total, which isn't fast but its a lot better than the current 48 (12 of which is just sstream construction ).

So three questions:

1) Is using old school C style file input recommended over the C++ way?
2) alternatively are there some C++ stream speed secrets I am not yet privy to?
3) Is there some way to bypass that slow slow slow slow string stream constructor and getline directly into the string stream? Seriously.
0

Share this post


Link to post
Share on other sites
Unless you're comparing against a build with full optimizations enabled, your claims are unfounded. Do you have full optimizations enabled?
0

Share this post


Link to post
Share on other sites
[quote name='fastcall22' timestamp='1304063621' post='4804342']
Unless you're comparing against a build with full optimizations enabled, your claims are unfounded. Do you have full optimizations enabled?
[/quote]


Of course. /Ox in VC++ 10. I also turned off checked iterators and secure scl ( I think I read somewhere that one of these has implications for even release builds ).
0

Share this post


Link to post
Share on other sites
[quote name='fastcall22' timestamp='1304065702' post='4804349']
You could also try compiling the text file into a binary format for faster parsing.
[/quote]

I could, and I do this with my own internal format (which I export as a raw chunk of indices, vertices, skeletal weights, material strings etc.). But I am not concerned with that at the moment, I am concerned with why I can't write a fast text file parser using the classes of the C++ standard library.
0

Share this post


Link to post
Share on other sites
Tried running the program through the profiler in VS2010? I would try reusing the same stringstream object if possible to avoid having to reallocate the internal buffer all the time.
0

Share this post


Link to post
Share on other sites
[quote name='_swx_' timestamp='1304067364' post='4804353']
Tried running the program through the profiler in VS2010? I would try reusing the same stringstream object if possible to avoid having to reallocate the internal buffer all the time.
[/quote]

You are onto something. Please explain further. My current code is

[code]

string line;
getline( input, line );
stream = stringstream( line ); // member of the class doing this code.

[/code]

This is code that takes 6 seconds going through the entire file.

By contrast

[code]

string line;
getline( input, line );

[/code]


takes only 2. There must be a better way to get a line into a stream. I feel like such a noob with this
0

Share this post


Link to post
Share on other sites
[quote name='rip-off' timestamp='1304067719' post='4804356']
Can you show us the code?
[/quote]

Why not.

[code]

class Parser
{
public:
Parser( std::wstring file );

virtual void Ignore( const std::string& start, const std::string& end );
virtual void Rewind( void );
virtual void Next( void );
virtual void GetLine( std::string& line );
virtual void GetTokens( std::vector<std::string>& tokens );
virtual void GetHeader( std::string& header );
virtual void GetBody( std::string& body );
virtual void GetBodyTokens( std::vector<std::string>& bodyTokens );
virtual bool Good( void );

std::stringstream stream;

protected:
void TrimLine( std::string& line );

int ignoring;
std::vector<std::string> excludeDelims;
std::vector<std::string> includeDelims;
std::ifstream input;
};[/code]


[code]
void Parser::Ignore( const std::string& start, const std::string& end )
{
excludeDelims.push_back( start );
includeDelims.push_back( end );
}

void Parser::Rewind( void )
{
input.seekg( 0, ios::beg );
input.clear();

ignoring = -1;
stream = stringstream( "" );
}

void Parser::Next( void )
{
string line;
getline( input, line );

if( !input.good() )
return;

if( line.empty() )
{
Next();
return;
}

TrimLine( line );
if( line.empty() )
{
Next();
return;
}

stream = stringstream( line );
}

void Parser::GetLine( std::string& line )
{
line.assign( stream.str() );
}

void Parser::GetTokens( std::vector<std::string>& tokens )
{
tokens.clear();
stream.clear();
stream.seekg( 0, ios::beg );

string token;

while( stream >> token )
tokens.push_back( token );
}

void Parser::GetHeader( std::string& header )
{
header.clear();
stream.clear();
stream.seekg( 0, ios::beg );

stream >> header;
}

void Parser::GetBody( std::string& body )
{
body.clear();
stream.clear();
stream.seekg( 0, ios::beg );

body.assign( stream.str() );

size_t i = 0;

// Ignore any white spaces at the beginning of the line.
while( body[i] == ' ' && body[i] == '\r' && body[i] == '\t' && i < body.length() )
i++;

// Ignore the first word
while( body[i] != ' ' && body[i] != '\r' && body[i] != '\t' && i < body.length() )
i++;

body = body.substr( i, body.length() );
}

void Parser::GetBodyTokens( std::vector<std::string>& bodyTokens )
{
bodyTokens.clear();
stream.clear();
stream.seekg( 0, ios::beg );

string token;

stream >> token;
while( stream >> token )
bodyTokens.push_back( token );
}

bool Parser::Good( void )
{
return input.good();
}

void Parser::TrimLine( string& line )
{
if( ignoring != -1 )
{
size_t incPos = line.find( includeDelims[ignoring] );
if( incPos != string::npos )
{
line = line.substr( incPos, line.length() );
ignoring = -1;
TrimLine( line );
}
else
line.clear();
}
else
{
for( size_t i = 0; i < excludeDelims.size(); i++ )
{
size_t excPos = line.find( excludeDelims[i] );
if( excPos != string::npos )
{
string tail = line.substr( excPos, line.length() );
line = line.substr( 0, excPos );

// If the includeDelim is the end of the line just return the head.
if( includeDelims[i] == "\n" )
return;

ignoring = i;
TrimLine( tail );
line += tail;
return;
}
}
}
}
[/code]

Here is the obj loader code, although this hasn't changed since my 18 second lucy bench mark, just the above posted backend has.

[code]
shared_ptr<Mesh> ImportImpl::LoadObjMesh( wstring file )
{
shared_ptr<Mesh> mesh = LookupMesh( file );
if( mesh )
return mesh;

mesh = shared_ptr<Mesh>( new Mesh );

wstring path = FindFullPath( file );
ObjParser parser( path );

int numPositions = 0;
int numTexcoords = 0;
int numNormals = 0;
int numGroups = 0;
int numFaces = 0;

parser.Ignore( "#", "\n" );

// Preliminary run through to gather information.
while( parser.Good() )
{
parser.Next();
string line;

parser.GetLine( line );

switch( line[0] )
{
case 'v':
switch( line[1] )
{
case ' ':
numPositions++;
break;
case 't':
numTexcoords++;
break;
case 'n':
numNormals++;
break;
}
break;
case 'f':
numFaces++;
break;
case 'g':
numGroups++;
break;
}
}

if( !numPositions )
throw ExcFailed( L"[ImportImpl::LoadObjMesh] " + file + L" does not contain vertex positions.\n" );
if( numPositions < 0 || numFaces < 0 || numGroups < 0 )
throw ExcFailed( L"[ImportImpl::LoadObjMesh] " + file + L" holds way too much attribute data.\n" );
parser.Rewind();

vector<Position> positions;
vector<Normal> normals;
vector<Texcoord> texcoords;

positions.reserve( numPositions );
normals.reserve( numNormals );
texcoords.reserve( numTexcoords );
mesh->subMeshes.reserve( numGroups );
mesh->triangles.reserve( numFaces );

wstring_convert<std::codecvt_utf8<wchar_t>> converter;
Hash hasher;
forward_list<int> hashGrid[65536];

while( parser.Good() )
{
parser.Next();

string header;
vector<string> tokens;

parser.GetHeader( header );
parser.GetBodyTokens( tokens );

if( header == "v" )
{
Position p;

p.x = float( ( atof( tokens[0].c_str() ) ) );
p.y = float( ( atof( tokens[1].c_str() ) ) );
p.z = float( ( atof( tokens[2].c_str() ) ) );

if( tokens.size() == 4 )
p.w = float( ( atof( tokens[3].c_str() ) ) );
else
p.w = 1.0f;

positions.push_back( p );
}
else if( header == "vt" )
{
Texcoord o;

o.s = float( atof( tokens[0].c_str() ) );
o.t = float( atof( tokens[1].c_str() ) );

texcoords.push_back( o );
}
else if( header == "vn" )
{
Normal n;

n.x = float( atof( tokens[0].c_str() ) );
n.y = float( atof( tokens[1].c_str() ) );
n.z = float( atof( tokens[2].c_str() ) );

normals.push_back( n );
}
else if( header == "f" )
{
vector<Vertex> faceVertices = parser.GetFaceVertices( positions, normals, texcoords );

for( unsigned int i = 0; i < tokens.size() - 2; i++ )
{
Vertex v[3];

v[0] = faceVertices[0];
v[1] = faceVertices[i + 1];
v[2] = faceVertices[i + 2];

// Fill out the vertex indices of the triangle by either pushing vertices into
// the mesh vector, or finding the index of an already existant equivalent.
Triangle tri;
for( int j = 0; j < 3; j++ )
{
unsigned int hash = hasher.GenerateHash16( v[j] );
bool found = false;
int index;

forward_list<int>::iterator it = hashGrid[hash].begin();
while( it != hashGrid[hash].end() )
{
if( mesh->vertices[*it] == v[j] )
{
index = *it;
found = true;
break;
}
it++;
}

if( !found )
{
index = mesh->vertices.size();
mesh->vertices.push_back( v[j] );
hashGrid[hash].push_front( index );
}

// Vertices are even indices in the t array.
tri.t[j * 2] = index;
}

mesh->triangles.push_back( tri );

if( !mesh->subMeshes.empty() )
mesh->subMeshes.back().triangleIndices.push_back( mesh->triangles.size() );
}
}
else if( header == "g" )
{
mesh->subMeshes.push_back( SubMesh() );
}
else if( header == "usemtl" )
{
wstring mtl = converter.from_bytes( tokens[0] );

mesh->subMeshes.back().materialIndex = mesh->materials.size();
mesh->materials.push_back( LoadMtlMaterial( mtl ) );
}
}

mesh->FindTriangleNeighbors();

if( normals.empty() )
mesh->FindVertexNormals();

mesh->Trim();

meshCache.push_back( Record<Mesh>( file, mesh ) );
return mesh;
}
[/code]

Before you mention it, TrimLine has an overhead of an extra 0.3 seconds on lucy, and that is an overhead I am willing to pay for something that can get rid of /* */ and // style commented text on the fly.The GetBody function has an assignment that I can probably cut out but I don't use it in the obj loader ( I do in the md5 loader but I am just looking at the obj loader for profiling the backend for now ). The part of the obj loader that hashes vertices is welding them on the fly as my internal format requires them that way: that algorithm is not super fast (incurs at least a 6 second overhead) but fast enough considering what it does.
0

Share this post


Link to post
Share on other sites
In your next function:
[code]stream = stringstream( line );[/code]

should you not use..

[code] stream << line ;[/code]

I haven't read every line of the code but I'm not sure you need to be creating a new stringstream on each read.
1

Share this post


Link to post
Share on other sites
[quote name='Gorbstein' timestamp='1304069522' post='4804366']
In your next function:
[code]stream = stringstream( line );[/code]

should you not use..

[code] stream << line ;[/code]

I haven't read every line of the code but I'm not sure you need to be creating a new stringstream on each read.
[/quote]

That one change actually makes things at least one order magnitude slower, that was the only change I made and my timing went over 800 seconds so I decided to stop. But thanks for trying to give me some practical advice anyway, its appreciated.
0

Share this post


Link to post
Share on other sites
I've found that if you just want to write a straight forward implementation and don't want to spend a lot of time optimising it then the C-style stream functions are the way to go. There's nothing inherently slow with the C++ streams by design it's just that the VC++ implementation of them does a lot of extra work (even with the full array of optimisation flags).
0

Share this post


Link to post
Share on other sites
Is using the trim line function actually faster than just letting the switch statements ignore the unnecessary characters?

While going through the file twice (to find number of verts etc.) may be faster, perhaps keeping the file in memory and using that the second time would be quicker than reading everything off disk twice?
0

Share this post


Link to post
Share on other sites
[quote name='__sprite' timestamp='1304079841' post='4804397']
Is using the trim line function actually faster than just letting the switch statements ignore the unnecessary characters?

While going through the file twice (to find number of verts etc.) may be faster, perhaps keeping the file in memory and using that the second time would be quicker than reading everything off disk twice?
[/quote]
The going through the file twice isn't slowed down because of the disk, as I am sure this gets cached by the OS / HDD anyway: its slowed down most by that string stream constructor. And yeah it is way faster finding the right amount of verts because for a large data set ( like lucy ) if you don't reserve vector space, the whole thing runs almost five times as long (184 seconds )

No, it is a little slower. A switch statement works well in ignoring lines that start with # as the comment character ( like in obj files ) but if you have a comment like /* this is a comment */ that can span over multiple lines or be in the middle of a line or even have a line /* blah blah blah */ full off /* blah blah blah */ such comments like that, then you need something better, and the parser class is used to parse a few types of text files.


So everyone can see here is an implementation of my parser class I just created which loads lucy in 10 seconds, compared to the 48 it takes with the before posted one using string streams.

[code]

Parser::Parser( wstring file )
{
input.open( file );
ignoring = -1;

if( !input.is_open() )
throw ExcFailed( L"[Parser::Parser] Could not open file " + file + L"\n" );
}

void Parser::Ignore( const std::string& start, const std::string& end )
{
excludeDelims.push_back( start );
includeDelims.push_back( end );
}

void Parser::Rewind( void )
{
input.seekg( 0, ios::beg );
input.clear();

ignoring = -1;
line.clear();
}

void Parser::Next( void )
{
getline( input, line );

if( !input.good() )
return;

if( line.empty() )
{
Next();
return;
}

TrimLine( line );
if( line.empty() )
{
Next();
return;
}
}

void Parser::GetLine( std::string& _line )
{
_line = line;
}

void Parser::GetTokens( std::vector<std::string>& tokens )
{
tokens.clear();
string buff;

size_t from = 0;
while( from < line.length() )
{
GetNextToken( buff, from );
tokens.push_back( buff );
}
}

void Parser::GetHeader( std::string& header )
{
header.clear();

size_t from = 0;
GetNextToken( header, from );
}

void Parser::GetBody( std::string& body )
{
body.clear();

size_t i = 0;
// Ignore any white spaces at the beginning of the line.
while( line[i] == ' ' && line[i] == '\r' && line[i] == '\t' && i < line.length() )
i++;

// Ignore the first word
while( line[i] != ' ' && line[i] != '\r' && line[i] != '\t' && i < line.length() )
i++;

body = line.substr( i, line.length() );
}

void Parser::GetBodyTokens( std::vector<std::string>& bodyTokens )
{
bodyTokens.clear();

string buff;

size_t from = 0;
GetNextToken( buff, from );
while( from < line.length() )
{
GetNextToken( buff, from );
bodyTokens.push_back( buff );
}
}

bool Parser::Good( void )
{
return input.good();
}

void Parser::TrimLine( string& line )
{
if( ignoring != -1 )
{
size_t incPos = line.find( includeDelims[ignoring] );
if( incPos != string::npos )
{
line = line.substr( incPos, line.length() );
ignoring = -1;
TrimLine( line );
}
else
line.clear();
}
else
{
for( size_t i = 0; i < excludeDelims.size(); i++ )
{
size_t excPos = line.find( excludeDelims[i] );
if( excPos != string::npos )
{
string tail = line.substr( excPos, line.length() );
line = line.substr( 0, excPos );

// If the includeDelim is the end of the line just return the head.
if( includeDelims[i] == "\n" )
return;

ignoring = i;
TrimLine( tail );
line += tail;
return;
}
}
}
}

void Parser::GetNextToken( string& container, size_t& from )
{
size_t to = from;

while( from != line.length() && ( line[from] == ' ' || line[from] == '\t' || line[from] == '\r' ) )
from++;

to = from + 1;
while( to != line.length() && line[to] != ' ' && line[to] != '\t' && line[to] != '\r' )
to++;

container = line.substr( from, to - from );

from = to;
}
[/code]


Which is a shame because I think string streams are a really elegant way of parsing and formatting data, but I don't know how to use them in a way that isn't mega mega slow.
0

Share this post


Link to post
Share on other sites
[quote name='AvCol' timestamp='1304080953' post='4804403']
A switch statement works well in ignoring lines that start with # as the comment character ( like in obj files ) but if you have a comment like /* this is a comment */ that can span over multiple lines or be in the middle of a line or even have a line /* blah blah blah */ full off /* blah blah blah */ such comments like that, then you need something better.
[/quote]

But that's not a valid comment in a .obj file.

If the stringstream is really that slow, you could try processing the line string using boost string algorithms or something instead (I'm not sure it would be faster, but it's an option to try).
0

Share this post


Link to post
Share on other sites
This is text book example of how costly memory allocations are.

There is no decent way around it using standard stream implementations.

One could use custom allocator which would go a long way, but very third-party libraries support such strings, so if you depend on any of them, it'll be a problem.


Parsing .obj files is also best done using standard FSM-based parser which can work with no overhead or extra allocations beyond the extracted data.
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0