News for hackers. Stuff that matters.
Re:A Python Optimization Anecdote by Jabbles on Tuesday October 25, 2011 @06:17AM (#3153523)
In C you could replace

    if x in WHITELIST
with

    if ((x >= '0' && x <= '9') ||
        (x >= 'A' && x <= 'Z') ||
        (x >= 'a' && x <= 'z'))
which I suspect would be much faster than any hash-table implementation. Also I believe that should work for UTF-8 as well as ascii. I realise that this makes it harder to expand the whitelist. I'm not very familiar with python, is there something similar that could be done?
Re:A Python Optimization Anecdote by bbrizzi on Tuesday October 25, 2011 @07:41AM (#3153695)
If you want to be picky, I'ld go with:

    if ((x >= 'a' && x <= 'z') ||
        (x >= 'A' && x <= 'Z') ||
        (x >= '0' && x <= '9'))
As in a regular text file you're more likely to hit an alphanumerical character than a number. If the first OR statement is true, any good compiler will skip the next two clauses.
Re:A Python Optimization Anecdote by schrototo on Tuesday October 25, 2011 @10:33AM (#3154187)
> If the first OR statement is true, any good compiler will skip the next two clauses.

This has nothing to do with the compiler, it's part of the language specification. If your compiler doesn't comply with this, it's broken.

Re:A Python Optimization Anecdote by viraptor on Tuesday October 25, 2011 @08:13AM (#3153760)
If you want to be super-picky, then char[256] with 1/0 values for each character will be faster than 6 comparisons in the worst case.
Re:A Python Optimization Anecdote by DrJokepu on Tuesday October 25, 2011 @08:41AM (#3153838)
And if you want to be super-super picky, int[256] on 32-bit or long[256] on 64-bit would be even faster.

(Although I'm not sure if lookup would be faster at all than a few comparisons, considering caches and everything, but this is not my domain.)

Re:A Python Optimization Anecdote by viraptor on Tuesday October 25, 2011 @09:05AM (#3153903)
A jump address table could be even faster since it's not branching...
Re:A Python Optimization Anecdote by mikeash on Tuesday October 25, 2011 @10:06AM (#3154072)
Would it? Loading a single byte should still be fast (in the absolute worst case, it's a single shift and a mask on top of the cost of loading 4 or 8 bytes) and using less memory means it's much more likely for the table to remain in cache (and evict less other stuff). In fact, I'd go so far as to wager that a uint8_t[16] (or uint64_t[4] or whatever) with one bit per character, manually extracted, would be the fastest way to do it. Not that I've tested this or anything, and I could certainly be wrong.
Re:A Python Optimization Anecdote by maximilianburke on Tuesday October 25, 2011 @02:19PM (#3155177)
I hate to break up perfectly good hand-waving with numbers but I put together a test. On my Core i7 with an 18mb input, which is a large novel duplicated many times, the performance factors, normalized to the if-based version are:

    if: 1x
    byte-based lookup: 0.83x
    int-based lookup: 0.84x
    bit-vector based lookup: 0.93x
http://pastebin.com/5twfXfEt
Re:A Python Optimization Anecdote by ori_b on Tuesday October 25, 2011 @11:36AM (#3154402)
Unless it bloats your data to the point where other stuff falls out of L1 cache.
Re:A Python Optimization Anecdote by viraptor on Tuesday October 25, 2011 @12:28PM (#3154649)
Let's not go too far with that. L1 cache started with 8K on i486. I'm talking about 256 bytes.
Re:A Python Optimization Anecdote by ori_b on Tuesday October 25, 2011 @05:11PM (#3155899)
Current L1 caches are 32k. There's an awful lot of data that would like to be in there -- If you're going to talk about micro-optimization, it's something to keep an eye on.
Re:A Python Optimization Anecdote by sausagefeet on Tuesday October 25, 2011 @07:47AM (#3153710)
You couldn't in C actually without making assumptions the language doesn't guarantee. The language specifies that you can't guarantee the alphabet is in order like that. Ctypes.h provides functions for checking letters though </pedantic>
Re:A Python Optimization Anecdote by icebraining on Tuesday October 25, 2011 @09:34AM (#3153980)
Language? The alphabet order is related to the encoding, and UTF-8 (which is what they're probably using) certainly does ensure that, since it's backwards compatible with ASCII.
Re:A Python Optimization Anecdote by CountHackulus on Tuesday October 25, 2011 @11:22AM (#3154354)
Sure, that works for ASCII and UTF-8, but what if I'm on an IBM System Z machine? Then everything's in EBCDIC, and that's just a nightmare.
Re:A Python Optimization Anecdote by ori_b on Tuesday October 25, 2011 @11:34AM (#3154396)
Then you read in ASCII or UTF-8, and don't do your I/O in EBCDIC. Also, you run Z/Linux.
Re:A Python Optimization Anecdote by maximilianburke on Tuesday October 25, 2011 @12:27PM (#3154645)
Then you write your own optimization for that case -- for most people assuming that 0-9, A-Z, and a-z will work just fine. Chances are slim that you're running on a system using EBCDIC without knowing it.
Re:A Python Optimization Anecdote by beej71 on Tuesday October 25, 2011 @02:31PM (#3155231)
Or, as was said, use ctypes.h, which is the Right Thing.
Re:A Python Optimization Anecdote by JesseAldridge on Tuesday October 25, 2011 @12:39PM (#3154707)
You could do that in Python using the ord function.

    white_ranges = [('0', '9'), ('A', 'Z'), ('a', 'z')]
    any([ord(low) <= ord(x) <= ord(high) for low, high in white_ranges])
Re:A Python Optimization Anecdote by vilya on Tuesday October 25, 2011 @09:07AM (#3153910)
In python there's no such thing as a char, there's only single-character strings. The above would actually be doing 6 string comparisons. That may still be faster... or may not. Measuring is the only way to be sure.
Re:A Python Optimization Anecdote by bjoernbu on Tuesday October 25, 2011 @12:25PM (#3154638)
since there are only ascii chars in the whitelist you could just declare an array of size 256 (doesn't really matter if it's a bitvector or char array, int array or whatever) and replace in WHITELIST by

    return (CHAR_MAP_ARRAY[c] = 'y')
Any UTF-8 start or follow byte shoudl be > 128 where there should always be values indicating false