7 ms·

These tricks won't have a great time with Unicode encodings.

by justinjlynn 9y ago

loeg 9y ago
These tricks work just fine with UTF-8.
- user5994461 9y ago
  Unicode is more than just UTF-8.
  - pjscott 9y ago
    Unicode can be encoded as UTF-8, and as long as you're okay with defining "whitespace" as code points less than 32, the algorithm here will handle it correctly.
    - adrianratnapala 9y ago
      The beautiful thing about UTF-8 is that a lot of simple seemingly-ascii algorithms will will work correctly with unicode: as long as you define "correctly" in a way that ignores complicated unicode semantics. And we can often do that: for example a programming language could just ban non-ASCII characters everywhere but in string literals. But sadly, we do often need to care about all those complicated unicode character classes etc. And if we are talking explicitly about Unicode, then by default we should be considering the whole standard, not just the bits we like.
ams6110 9y ago
Unless the hot spot in your code is removing spaces from strings, these tricks are just academic and not something you would ever do yourself. You'd use a well tested, safe string handling library in real code.
- hedora 9y ago
  Someone has to implement those libraries. Also, this space remover looks a lot like a CSV parser, and CSV is a fine high level format if your data is a table (and you care at all about performance).
- wongarsu 9y ago
  It's mostly interesting because it's a subproblem of many interesting problems. "get a bunch of data, discard uninteresting/invalid data, do stuff with the rest" is something that easily becomes a hotspot. "Removing spaces" is the "discard uninteresting/invalid data" part, in the easy case that the data is a bunch of bytes and there is some arbitrary threshold that decides what to keep (not unusual with sensor data of all kinds). So I'm not sure "academic" is quite the right word, but I agree that worrying about Unicode is not the point here.
- glangdale 9y ago
  I am not an academic. I have done this myself. Of course, we wrote a regex library... These tricks are in general something that it's well worth learning how to do if you do any performance critical code, as often the boundary of the way that they are implemented in someone's library is not useful for the actual task (i.e. you may have a fast 'find a space' function, but it might not be fast by the time you painfully iterate through each of its results removing spaces one by one). Sadly, a lot of this sort of processing doesn't compose very well unless you have access to an omniscient optimzer. But yes, if this isn't your hot spot, don't do this thing in particular. It's still possible you might learn something useful by reading about it.
kazinator 9y ago
But, boy, it could speed up Fortran 66 compilation!
- tjalfi 9y ago
  The CDC STAR-100 included an instruction[0] for parsing Fortran. [0] https://groups.google.com/d/msg/comp.arch/QhQDFCcny7w/wVOpIh2-y6sJ https://groups.google.com/d/msg/comp.arch/QhQDFCcny7w/wVOpIh...
thechao 9y ago
I do a lot of low-level systems programming; think rasterizers, drivers, etc. There's numerous occasions where I've needed to hand-code some sort of work-around, or to paper over a gap in the functionality provided by the hardware. In C/++, this isn't really a thing: the language only has so much flexibility in what in can say. When I really have to get into things, though, I end up writing assembly for the truly hot-loops. In that case, as fugly as x86/64 is, it is one of the best ISAs for exactly expressing the algorithm I have in mind. Personally, I find the most advanced NEON specs are about a decade behind the x86 vector specs. Generally, while the ARM implementations can keep up cycle-for-cycle on commodity parts for scalar, algorithmically, x86/64 blows it out of the water. I think the article cites about 5x? In the worst case, I've seen places where ARM falls entirely out of the I$ and thrashes its D$ & I$ on scalar work-arounds for gaps in its NEON set, where x86/64 manages to just squeak by completely vectorized. In those cases I see 50x (or more) delta, even though the spec sheet would imply that ARM is "just as good" as x86/64. I like Mike Abrash's quote on this (to paraphrase): "assembly isn't faster than C++; assembly is more expressive than C++".
- pjmlp 9y ago
  Back in the MS-DOS days, when I had lots of fun using TASM, the common way to write high performance C and other higher level languages on 8 and 16 bit computers was using inline Assembly everywhere. The typical for 80% of the application void func(args) { asm { } } Literally poor man's macro assembler. Now 40 years of optimizing compiler improvements, we have younger generations thinking that C is like writing Assembly and C compilers were always blazing fast. So when I see statements about other compilers generating slower code than C ones, I remember those days and smile.

These tricks won't have a great time with Unicode encodings.

loeg 9y ago

These tricks work just fine with UTF-8.

user5994461 9y ago
Unicode is more than just UTF-8.
- pjscott 9y ago
  Unicode can be encoded as UTF-8, and as long as you're okay with defining "whitespace" as code points less than 32, the algorithm here will handle it correctly.
  - adrianratnapala 9y ago
    The beautiful thing about UTF-8 is that a lot of simple seemingly-ascii algorithms will will work correctly with unicode: as long as you define "correctly" in a way that ignores complicated unicode semantics. And we can often do that: for example a programming language could just ban non-ASCII characters everywhere but in string literals. But sadly, we do often need to care about all those complicated unicode character classes etc. And if we are talking explicitly about Unicode, then by default we should be considering the whole standard, not just the bits we like.

ams6110 9y ago

Unless the hot spot in your code is removing spaces from strings, these tricks are just academic and not something you would ever do yourself. You'd use a well tested, safe string handling library in real code.

hedora 9y ago
Someone has to implement those libraries. Also, this space remover looks a lot like a CSV parser, and CSV is a fine high level format if your data is a table (and you care at all about performance).
wongarsu 9y ago
It's mostly interesting because it's a subproblem of many interesting problems. "get a bunch of data, discard uninteresting/invalid data, do stuff with the rest" is something that easily becomes a hotspot. "Removing spaces" is the "discard uninteresting/invalid data" part, in the easy case that the data is a bunch of bytes and there is some arbitrary threshold that decides what to keep (not unusual with sensor data of all kinds). So I'm not sure "academic" is quite the right word, but I agree that worrying about Unicode is not the point here.
glangdale 9y ago
I am not an academic. I have done this myself. Of course, we wrote a regex library... These tricks are in general something that it's well worth learning how to do if you do any performance critical code, as often the boundary of the way that they are implemented in someone's library is not useful for the actual task (i.e. you may have a fast 'find a space' function, but it might not be fast by the time you painfully iterate through each of its results removing spaces one by one). Sadly, a lot of this sort of processing doesn't compose very well unless you have access to an omniscient optimzer. But yes, if this isn't your hot spot, don't do this thing in particular. It's still possible you might learn something useful by reading about it.

kazinator 9y ago

But, boy, it could speed up Fortran 66 compilation!

tjalfi 9y ago
The CDC STAR-100 included an instruction[0] for parsing Fortran. [0] https://groups.google.com/d/msg/comp.arch/QhQDFCcny7w/wVOpIh2-y6sJ https://groups.google.com/d/msg/comp.arch/QhQDFCcny7w/wVOpIh...

thechao 9y ago

I do a lot of low-level systems programming; think rasterizers, drivers, etc. There's numerous occasions where I've needed to hand-code some sort of work-around, or to paper over a gap in the functionality provided by the hardware. In C/++, this isn't really a thing: the language only has so much flexibility in what in can say. When I really have to get into things, though, I end up writing assembly for the truly hot-loops. In that case, as fugly as x86/64 is, it is one of the best ISAs for exactly expressing the algorithm I have in mind. Personally, I find the most advanced NEON specs are about a decade behind the x86 vector specs. Generally, while the ARM implementations can keep up cycle-for-cycle on commodity parts for scalar, algorithmically, x86/64 blows it out of the water. I think the article cites about 5x? In the worst case, I've seen places where ARM falls entirely out of the I$ and thrashes its D$ & I$ on scalar work-arounds for gaps in its NEON set, where x86/64 manages to just squeak by completely vectorized. In those cases I see 50x (or more) delta, even though the spec sheet would imply that ARM is "just as good" as x86/64. I like Mike Abrash's quote on this (to paraphrase): "assembly isn't faster than C++; assembly is more expressive than C++".

pjmlp 9y ago
Back in the MS-DOS days, when I had lots of fun using TASM, the common way to write high performance C and other higher level languages on 8 and 16 bit computers was using inline Assembly everywhere. The typical for 80% of the application void func(args) { asm { } } Literally poor man's macro assembler. Now 40 years of optimizing compiler improvements, we have younger generations thinking that C is like writing Assembly and C compilers were always blazing fast. So when I see statements about other compilers generating slower code than C ones, I remember those days and smile.