A string processing rant | Hacker News Reader

A string processing rant

fgiesen.wordpress.com

60 pointswaffle_ss35 comments

Nice article! Lots of deja vu there :) (I'm a tools programmer working at Treyarch)

Here is another little thing you can optimize out (probably not saving much, but still bugs me):

  SoftwareOcclusionCulling/CPUT/CPUT/CPUT.h:#define SAFE_DELETE(p)      {if((p)){HEAPCHECK; delete (p);     (p)=NULL;HEAPCHECK; }}
  SoftwareOcclusionCulling/CPUT/CPUT/CPUT.h:#define SAFE_DELETE_ARRAY(p){if((p)){HEAPCHECK; delete[](p);    (p)=NULL;HEAPCHECK; }}

There is no need to check for NULL array or pointer before calling delete[] or delete, the standard allows for it.

Lots of stuff coming from Intel is just badly written for some reason. Few years ago there was the SMOKE demo using Thread Building Blocks, and there were O(N^2) and even O(N^3) things for the particles.

Intel, you are supposed to show us how to code to the metal... Or maybe their ICC compiler is specifically better if you write this way (lol, what a conspiracy).

This guy's biggest problem is that he doesn't know the standard library very well.

I admit it's ugly, but the code below removes whitespace using only standard C++ calls. There's also an isspace() function from the <locale> header that takes a specific locale, but I'm not sure it's important for whitespace.

    std::wstring removeSpaces(std::wstring theStr) {
        return std::wstring(theStr.begin(),
                            std::remove_if(theStr.begin(), 
                                           theStr.end(),
                                           std::iswspace));
    }

There's also codec conversion in the <locale> header [1]. It's also pretty ugly, but it's easier to understand than his home grown solution, and if nothing else, is already debugged. And to be honest, if you're using C++ you should be used to the code being verbose and ugly.

[1] http://en.cppreference.com/w/cpp/locale/codecvt

The code in the blog post removes only leading or trailing white space, not all of it.

    std::wstring remove_side_spaces(const std::wstring& str) {
        auto begin = std::find_if_not(str.begin(), str.end(), std::iswspace);
        if (begin == str.end()) {
            return std::wstring();
        } else {
            auto end = std::find_if_not(str.rbegin(), str.rend(), std::iswspace);
            return std::wstring(begin, end.base());
        }
    }

Believe it or not, that doesn't compile because begin and end have different types due to begin/end returning different iterator types than rbegin/rend. It could be a bug in both clang and g++.

This works, but I don't like the &strt and &endp:

    std::wstring trim(std::wstring theStr) {
        auto strt = std::find_if_not(theStr.begin(), theStr.end(), std::iswspace);
    
        if (strt == theStr.end()) return L"";
    
        auto endp = std::find_if_not(theStr.rbegin(), theStr.rend(), std::iswspace);
    
        return std::wstring(&*strt,&*endp+1);
    }

The easiest way is to use Boost's string algorithms library, though:

    std::wstring trimb(std::wstring theStr) {
        boost::trim(theStr);
        return theStr;
    }

I also corrected my example. Thanks!

It's really a C++ rant, not a string processing rant, though.

Is it also sort of a Windows rant? It seems like he would not have these problems with iconv() or its various wrappers on POSIX.

The C/C++ level API used is essentially identical and mostly part of C/C++ standard (including iconv()). But the main difference is that on Unix most people don't bother to use any of this and either don't care about encoding at all, or convert everything into utf-8 and process utf-8 strings byte by byte, or use some high level library for string handling.

OK, that makes sense. So the reason people on Windows do bother with this is that the Windows system libraries use UTf-16 for everything, right? (IANAWindowsDeveloper)

Also, C++11 adds std::u16string and std::u32string to make life a bit easier and write cross-platform code without worrying about whether wchar_t is 2 bytes (e.g. Windows) or 4 bytes (e.g. Linux).

Then again I would avoid anything non-8 bit for asset parsing. We have tons of text files for our level maps (Quake map format), used to have (transitioninig) all models/animation in text format again. Not only this takes significant time to sync these off P4, but they take more space on the disk, later more I/O, memory, and you are the mercy of strod, atof, etc. to work fast and properly (which usually is not the case).

For assets that don't make much sense merging (polygon data) - we are moving to binary data. For the rest (level data), we might keep text files - some merging is possible there.

The only time we'll ever need UTF8, UTF16, etc. is for the localized data - game text, etc. There is absolutely no need for such encoding to be in your assets.

> Then again I would avoid anything non-8 bit for asset parsing.

Nitpick: you probably meant non-7 bit (there's a reason why ruby and python2 default to non-ext ascii source code, and barf at you otherwise)

Yup. 7-bit, but the point is even if character above 127 were used it would've been okay.

7-bit (8-bit) ASCII has a long life to live :) It's just machine optimal, and the same time not flexible for modern days needs... just like "C", and I love it.

I'm using Qt5 these days, and there is QString and QByteArray (and also QLatin1String) - and I need to keep in memory lots of properties for our editor, going to QString (wide-chars) just uses more memory for no reason. Sticking to QByteArray/QLatin1String makes more sense for them.

The default changed to utf8 in Ruby for 2.0 though, so I suppose that reason is less obvious than you think.

Wide chars/strings are horribly broken and should be avoided at all cost. While UTF-16 itself is not technically broken, many implementations of it are and UTF-16 has no benefits compared to alternatives. So I'd steer clear of it too. Once you avoid these two pitfalls then string processing becomes at least somewhat sensible, although Unicode is pita in any case.

Well, the C and C++ libraries are what we call "organically grown". I sure as hell am glad to be using a language based on Unicode and length-encoded strings right from the start.

Well I guess it makes me feel better to know that there is stupidity to be found even amongst the mighty C programmers!

So where is "The Definitive Guide to C++ String Processing"?

Next to the bourbon and pistol.

Can someone explain me why something dealing with graphics needs to read: "several megabytes worth of text files"? Why aren't these binary data?

(I'm not familiar with graphical / texture code)

But I am familiar with fast text processing. From Java the problem is even worse: it's not so much that the methods are inefficiently written in themsevles. The issue is that string processing tends to create lots of garbage which then needs to be garbage collected.

The optimization when all these strings processing methods are the bottleneck? Do not create hundreds of thousands or millions of object. Instead of doing, say, "s2 = removeLeadingAndTrailingStuff();" and then "parse(s2);" you do write your own method directly: "parseButDoNotTakeIntoAccountLeadingAndTrailingStuff()".

It's oversimplified and crazy camel case is used above to make a point ; )

It's always the same : when objects creation become the bottleneck, make it so you're not creating that many objects.

It's exactly what the LMAX Disruptor "pattern" is about: using gigantic arrays of primitives and hardly any object creation at all (to process 12 million events per second in Java on a single core!).

That said in TFA I still don't understand why several megabytes of Unicode text files have to be processed...

> Why aren't these binary data?

Just guessing, but it's very coder-friendly to have particular kinds of data available as text. For example the (old, old) Wavefront .obj format is a text based 3d model format that's ridiculously easy to parse. I could imagine someone would choose to do the same with, say, entire game levels.

That said, there's another class of programs that often need to read several megabytes worth of text files: compilers. Who's to say they're not parsing something programming-languagey?

I don't know much about DirectX, so this is from an OpenGL specific standpoint.

3d graphics applications include shaders, which are programs that get compiled by the graphics drivers and loaded directly into the graphics pipeline on the video card. The source code is standardized, but the binaries vary from card to card and driver to driver, so applications have to include the source and let the driver build it into working shaders. The text being processes is possibly shader source code.

It would be interesting to see a comparison of Java (and Python) string processing with Go. In Go you use slices refer to underlying string data, which are basically (pointer, length) pairs. So you may still create garbage in terms of these small slice objects, but that should cause less of a problem than creating tons of temporary immutable strings.

Actually, Java strings work exactly like that. And if you use them correctly, string processing is no problem at all on a modern VM using a generational GC.

Ah OK I didn't know that (not a Java programmer). What happens if you create a huge 10MB string, then a 10 byte substring of it, and then remove all references to the 10MB string. Does that memory ever get reclaimed?

I guess the difference in Go is that the string abstraction and the slice abstraction is exposed to the programmer, so it will be apparent if that happens.

There is some info here but I was unable to find a good explanation: http://stackoverflow.com/questions/2909848/how-does-java-imp...

Nope, that's one way to have a memory leak. But you can avoid the problem by using the new String(oldString) constructor - it copies only the part of the underlying char array that the String uses. You're absolutely right that it would be much better if all that were part of the API rather than an implementation detail.

The SO question and answers are confusing because they talk about two competely separate issues: the above and the interning mechanism.

I believe in Go, slices get passed by value so you shouldn't get garbage from passing them around. Also, it's a triple rather than a pair due to the capacity.

In Go, a slice is a reference to a segment of an underlying array.

Yes, but the reference (along with size information) is passed by value, so no garbage.

The trick with doing this in a language without reference counting (like C) is keeping track of who owns the buffer all your slices point to. Windows uses UNICODE_STRING[1] internally for a great many things, paths being one of them. There are some functions[2][3] in the FilterManager's API for parsing paths that take advantage of this so as to avoid allocating extra memory for path components that already exist in the original path.

Note also the proscription against modifying the parsed path components[3] because they're shared. Since there's no support for immutable strings, you're counting on everybody to read the documentation and follow it. Admittedly, this specific restriction comes about from getting the file name information from the FilterManager in the first place, which has the explicit purpose of reducing the number of copies of paths floating around in kernel memory, but it still demonstrates the original point of needing to know who owns the memory at the end of the day.

[1]http://msdn.microsoft.com/en-us/library/windows/desktop/aa38... [2]http://msdn.microsoft.com/en-us/library/windows/hardware/ff5... [3]http://msdn.microsoft.com/en-us/library/windows/hardware/ff5...

That's a topic that comes once in a while in our studio. Artists, generally non-technical people like to look what's inside the file. This way they can spot an extra bone in an animation, or material that should've not been used in an model. Sometimes changing the model allows for merging, or doing diff in the source control system.

A more elaborate 3D diffing is what's needed, like the one shown here: http://3drepo.org/ - but it's not an easy thing, and not very easy to integrate either.

Sometimes binary files might be bigger than text, not often but possible - for example if double is used for number it always takes 8 bytes, while as text it might be just two (0 and space).

Also certain source control systems (like perforce I think) can store differences only if the files are text, otherwise they have to store full copies (that's really not a big game changer, but one more little detail to be aware).

Artists, coders often would look for a material/bone by just using Find in Files/grep/etc, and although this might work for binary files, it's harder to show the data.

That is probably similar to source code vs compiled object code. The textual graphic code is the human readable source code for describing the graphic. Reading and parsing them are similar to interpret them.

To make things faster, you can read them (compile) ahead of time and write the binary objects to binary files. In runtime loading them will be fast.

In this case, he's working with external code (Intel's example code) that happened to use data in that way. Why - good question. I guess someone at Intel thought "hey this is just example code how to do software rasterizer for occlusion, who cares what is the data format" and went with that. Badly ;)

I would think that string immutability has much to do with the object creation. That might be why regular expressions was such a focus of the Java 1.4 release.

Reply on news.ycombinator.com