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:
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.
[ Parent
| on HN ]
> 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.
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.
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.)
A jump address table could be even faster since it's not branching...
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/5twfXfEtUnless it bloats your data to the point where other stuff falls out of L1 cache.
Let's not go too far with that. L1 cache started with 8K on i486. I'm talking about 256 bytes.