Slashdot Mirror

Did you maybe mean to say 'And then they code those regular expressions in Perl. Now I have a problem'? I have no problems with Perl, especially when it concerns regular expressions. There is a reason why libpcre is as popular as it is after all...

Agreed. I see this sort of complaining about perl and/or regexes all the time, and I just don't get it.

For the regex stuff, I get that regexes are difficult and people aren't generally very good at them. So I can see how when someone solves a problem with a regex, it can make it difficult when someone else (who sucks at regexes) has to take over that code later. But the solution there is for everyone else to actually educate themselves on how to use regexes better. To complain and make jokes about it is just ignorant. It reminds me of other ignorant behaviors, like christians mocking scientists over the "absurdity" of evolution.

As for perl, that I just don't get. I mean, I understand that perl has a lot of REALLY flexible syntax, and that you can do some REALLY outrageously funky stuff with it. But for the most part, and in the way most people use it, it's not really any different that any other programming language. 99% of the perl code that I write, and 99% of the perl code that I've seen other people write, should be fairly easily understandable by anyone familiar with C++, java, or any other modern programming language. It just takes a little time to familiarize yourself with the language. And I know perl and regexes usually sort of go hand-in-hand, so it sort of ties back to my previous point about those, too.

Did you maybe mean to say 'And then they code those regular expressions in Perl. Now I have a problem'? I have no problems with Perl, especially when it concerns regular expressions. There is a reason why libpcre is as popular as it is after all...

He doesn't mention his age. For all we know, he could be 13 years old, but just be smart enough to know the truth of the matter. What he says is right, regardless of age. Furthermore, regular expressions are not at all difficult to do in C. The GNU C library has good support for regexes, and there's always PCRE if you're not using the GNU C library. Both make using regexes from C very trivial.

Your regexp example isn't awfully good - any language that has regexp support will have lines like that. These days, PHP has regexp support (possibly always has), C has regexp support, C++ has it, Java has it, and I expect that even C# has regexp libraries.

That's quite true. And in many cases, regexp support comes from this regexp library.

A basic unit of currency in the Linux world is the distribution, as you have discovered. A distribution is essentially just a collection of packages which are, in turn, just compiled versions of (mostly) upstream sources. The thing that makes a distro what it is are the customizations made to the package sources and occasionally packages unique to the distro. All the big distros (ie the ones that matter) are fully open source though so technology which shows up in one pretty quickly migrates upstream somewhere, and then back down again to the other distributions.

That leaves the customizations made, and what exact packages are included by default. This is where problems start to appear.

The traditional solution taken to things that don't really fit into any obvious upstream project is for each distribution to roll their own code. In the past this has happened with menus, hardware detection/pluggability, GUI configuration tools, bootup scripts, and installers. There are others I probably forgot.

In the case of menus, KDE and GNOME used different systems so distributions, not wanting to do a million different files in each package for each individual desktop and window manager each came up with their own solution. Debian has some custom system that Mandrake then adopted as well, SuSE only really supported KDE anyway, Red Hat 8 introduced this thing called "vFolders" which was an aborted attempt at a desktop-neutral standard and was one of the first things specced out at freedesktop.org. Later vFolders was shown to have serious problems and was abandoned but not before being integrated upstream into GNOME (but not KDE!). Red Hat abandoned vFolders in Fedora Core 2 but upstream GNOME did not do the same. So now we're still at this point where while everybody has agreed on a standard, it's not actually implemented uniformly at all.

D'oh. What a mess. This sort of thing has been repeated over and over, whenever something didn't really fit into any upstream project. As time goes by more and more is being sucked upstream into projects like freedesktop.org ... hardware detection is now being handled by HAL (though there is some internal resistance from SuSE who have a .... surprise .... custom solution called suseplugger), network config scripts are destined for replacement by NetworkManager if Red Hat have their way, etc etc.

So ... the random hacks different distros use to tie these disparate pieces of code together are gradually disappearing. This is good. It does, however, leave the second problem:

What packages are included? This is a bigger issue than you may think. There really is no such thing as the "Linux platform". There are small, mostly stable subsets like GNOME and KDE but this is the exception rather than the norm. Specialised libraries like pcre, OpenSSL, libpng and so on which aren't affiliated with any central project policies tend to break backwards compatibility all the time - often it could have been avoided. Each time this happens, you need a new parallel installable package that other packages can depend upon.

Typically, distributions are recompiled entirely on each new revision. So let's say that libfoo breaks backwards compatibility. The new version is included in the new distribution version, all the packages are recompiled or patched to use it, and now the old version isn't included any more.

This has the unfortunate side effect that you cannot make any assumptions about what features are available on any given Linux system beyond some really basic base libraries like libc, Xlibs etc.

Worse, even projects like GNOME and GTK+ often refuse to avoid breaking applications if they deem them "buggy" or "broken", which tends to have a very wide definition. So, the net result

I'm fairly sure that (a|b|c) will produce exactly the same DFA as [abc].

Well, in a perfect world, it certainly should. I'm just saying that it might conceivably matter, in our imperfect world.

In other words, although the regexp might be a bit smaller, and perhaps compile marginally quicker, it would make no difference to the running time.

What if the problem was the compilation process, not the runtime part? Even if it would generate an identical DFA, if the route to that DFA is sufficiently more convoluted to get there, perhaps it would be more likely to exceed some internal limits on the regexp complexity? Again, it's conceivable that making this change could help.

Not to say that I'd be holding my breath, mind you, but it might be worth some experimentation.

What I was interested in, however, was getting around the limit of the GNU regexp DFA. It seemed to use a 64K buffer, and 64K branch offsets, which means the maximum size of a regexp you can compile is comparatively small. (Much larger than anything you might write by hand, of course, but quite limiting when you start to write code which writes regexps). There was no easy way to get around these limitations, so I ended up using various hacks to limit the size of the regexp (splitting into multiple regexps), and also tried using a flex-generated lexer instead.

64K does sound quite limiting, but why couldn't you just increase the size of those buffers? (and change the branch offset size to 32 bits?)

A flex-generated lexer is an interesting idea -- how well did that work out?

If the GNU regexp library is just too limited, why not use a different one? PCRE jumps to mind...

PCRE stands for Perl Compatable Regular Expressions, its an implementation of Perl's regular expressions that is separate from Perl proper. Also, I doubt that python's .beginswith .endswidth string methods are any more efficient than Perl's $string =~ /^text/; or $string =~ /text$/; regular expressions. Anchored searches are the quickest.

I don't do lisp, so

First of all -- what's the deal with this whole "WARMUPS" thing? This is just the most explicit way possible of training the JIT mechanisms without measuring its overhead. That might be fine if you believe that the overhead asymptotically costs nothing, however, I don't know what evidence there is of this. The test should use other mechanisms other than this explicit mechanism to allow the language itself to demonstrate that the overhead is of low cost.

The way this test is set up, the JIT people could spend hours or days optimizing the code without it showing up in the tests. This is the wrong approach and will do nothing other than to encourage the JIT developers to cheat in a way such as this just to try to win these benchmarks.

Ok as to the specific tests:

1. FloatInteger conversion on x86 are notoriously slow and CPU micro-architecturally dependent. It also depends on your rounding standard -- the C standard dictates a rounding mode that forces the x86s into their slowest mode. However using the new "Prescott New Instructions", Intel has found a way around this issue that should eventually show up in the Intel C/C++ compiler.

This does not demonstrate anything about a language other than to ask the question of whether or not the overhead outside of the fi rises to the level of not overshadowing the slowness of the conversion itself.

(That said, obviously Intel's compiler knows something here that the other guys don't -- notice how it *RAPES* the competition.)

2. Integer to string conversion is just a question of the quality of the library implementation. A naive implement will just use divides in the inner loop, instead of one of the numerous "constant divide" tricks. Also, string to integer will use multiplies and still just be a limited to the quality of implementation as its most major factor determining performance.

3. The Pi calculation via iteration has two integer->floating point conversions and a divide in the inner loop. Again, this will make it limited to CPU speed, not language speed.

4. The Calculation of Pi via recursion is still dominated by the integer divide calculation. It will be CPU limited not language limited.

5. The Sieve of Erastothenes (sp?) is a fair test. However, if SLOTS is initialized to millions, and the comparable C implementation uses true bits, instead of integers, then I think the C implementation should beat the pants off of C#, Java, or anything else.

6. The string concatenation test, of course, is going to severely ding C for its pathetic string library implemenation (strcat, has an implicit strlen calculation in it, thus making it dramatically slower than it needs to be.) Using something like bstrlib would negate the advantage of C#, Java, or any other language.

7. The string comparison with switch is a fair test, and gives each language the opportunity to use whatever high level "insight" that the compiler is capable of delivering on. It should be noted that a sufficiently powerful C compiler should be capable of killing its competition on this test, however, I don't believe any C compiler currently in existence is capable of demonstrating this for this case. I.e., this *could* be a legitimate case to demonstrate that C# or Java's high level abstractions give it an advantage over where the state of the art is in C compilers today.

8. Of course the tokenization is another serious ding on the rather pathetic implementation of the C library. None of strtok, strspn, etc are up to the task of doing serious high performance string tokenization. If you use an alternative library (such as bstrlib or even just PCRE) you would find that C would be impossible to beat.

-----

Ok, while the results here are interesting, I don't think there were enough tests here to truly test the language, especially in more real world (and less laboratory-like) conditions. Please refer to The Great Win32 Computer Language Shootout for a more serious set of tests.

Yes, the library is definitely Perl Compatible Regular Expressions.

You can get the the C source, great documentation, and C++ wrappers from http://www.pcre.org

This is the library that PHP and Apache 2.0 (and several other programs) use for regular expressions.

Also, my book Regular Expression Pocket Reference is a companion to MRE and includes a chapter on PCRE. I own both editions of MRE and highly recommend the second edition. I think it's fair to say that Friedl taught me everything I know on this subject.

This makes sense when you think about it from their risk-averse perspective: releasing even small pieces of otherwise-useless specialized code is all downside and no upside.

But that's not entirely true... there is a distinct downside, although whether or not you want to bring it up is up to you.

If you don't release the changes back then you must make sure that any GPL or LGPL code you use (or similarly licensed code) is never, ever distributed to an outside party. That places a potentially immense risk on your codebase, since violation could mean forfeiture of all of your copyrights to the code (at least in the case of GPL). At the very least it would mean replacing all of those bits with code written entirely by your company, or purchased from another company and then integrated -- both of which are huge time sucks.

Of course, the risk of pleading this case is that they'll simply say not to use any GPL/LGPL code at all. To which you can only argue time and cost... and I know that without libraries like Boost, OTL, libxml, PCRE, and libcurl we'd be writing a shitload more code, taking far more time, and have a far less stable product.

And that's not even counting things like gcc, automake, gmake, vim, cvs, and other tools we use to actually create and maintain code! (No... no gdb... it seriously dislikes AIX 4.3 and C++)

Why would you want to embed perl into a C application? Probably to access perl's powerful regular expressions. If that's the case, the Perl Compatible Regular Expressions library is a more ideal solution. PHP, Python, and Ruby all use it to support perl regexes.

The biggest downside of the STL is when it doesn't work.

Sure, the standard is >3 years old now, but a lot of compiler vendors are still working out bugs with either the STL, their compiler, or their linker still.

Under AIX, we've run into relatively few problems with the STL itself, but the linker is pretty bad. Between it and the compiler compiles take forever (which is why I've been surfing /. more recently), and the executables are freaking huge.

This is, obviously, an AIX-specific problem. And it's pretty much an old story - every vendor has their own quirks with the compiler and/or linker.

Beyond that -- I've found a few things missing in the STL that would be really nice to have.

First, the only smart pointer is std::auto_ptr. It's pretty useless, since you can't use it in a collection, and you can't have more than one thing pointing at an object/memory block at once. This can be worked around though, since there are libraries that have better smart pointers. Check out Loki or Boost for two.

Second, there's no way to automagically ignore case on a std::string, or to upper/lower case it easily. Yes, I know, you can muck around with traits, but that's a PITA and renders your string uncopyable to other strings easily. Yes, I also know that you can use a transform() to do it. But this still isn't as nice as myString.lower().

Third, there's no date or datetime classes. You have to fall back on C time functions for them. I haven't looked for a good C++ library to handle date/time, but I'm sure there's one out there.

Fourth, there's no regular expression matching on strings. We use PCRE with a C++ wrapper and it works fine for what we need though.

Both 2 and 3 are due largely to internationalization issues... in the case of 2 there's a lot of languages in which upper and lower case are non-sensical. And after having thought about the i18n issues regarding dates, I don't blame the standardization committee a bit for running away screaming from them (what date range? which calendar? how do you change between calendars? what about date weirdness with some calendars (like the missing days in the Gregorian calendar)? etc).

I used RogueWave prior to this job, so I tried to think of some of the things I was used to in RW and weren't in the STL. By and large I prefer the STL though. The container classes in particular are a lot more sane than RW's.