Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Validating UTF-8 bytes using only 0.45 cycles per byte (AVX edition)

lemire.me

Post reply on HN
Print view View original

41–50 of 54 posts

Re: Validating UTF-8 bytes using only 0.45 cycles per byte (AVX edition)

#41

Post by wmu »

the_clarence wrote: post #24

I see a lot of applications trying to take advantage of SIMD, but what when you try to run them on systems that don't support these instructions? My guess is that you need to write multiple files taking advantage of different sets of instructions and then dynamically figure out which to use at runtime with cpuid, but isn't that cumbersome and a way to inflate a codebase dramatically?

Speaking of the Intel world it's not that bad. There are three major version right now: SSE4.1, AVX and AVX2 (AVX512 is not popular yet).

In the past (roughly 10 years ego) it was a problem, as there were: MMX, SSE, SSE2, SSE3, SSSE3, SSE4.1, SSE4.2, XOP, 3DNow and perhaps a few more extensions.

it's not a typo, there are three 'S' :)

Re: Validating UTF-8 bytes using only 0.45 cycles per byte (AVX edition)

#42

Post by paavoova »

Dylan16807 wrote: post #30
knome wrote: post #26

Earlier quoted context omitted.

> A 0 byte is perfectly acceptable in a utf8 string (or any unicode string, really) What? My understanding was that utf8 was crafted specifically so that the only null byte in it was literally NUL. That all normal human language described by a utf8 string will never contain a NUL. They're comparable to C strings in that way, where it can be used safely as an end of string marker. If you have embedded NULs, it's not r…

> My understanding was that utf8 was crafted specifically so that the only null byte in it was literally NUL. Correct. > That all normal human language described by a utf8 string will never contain a NUL. Correct. > If you have embedded NULs, it's not really utf8, is it? Incorrect. NUL is a valid character. If you accept arbitrary utf-8, or arbitrary ascii, or arbitrary 8859-1, then there might be embedded NUL. You c…

It's invalid for unix filenames to have a null character. Therefore, if your application is printing filenames in their unicode representation, it doesn't ever need to consider there to be a null byte. This of course isn't an arbitrary case, but it shows one can make assumptions regardless of the "validity" of a character. I believe for most cases of arbitrary input, the correct and safe thing to do is to assume a byte stream of unknown encoding.

Re: Validating UTF-8 bytes using only 0.45 cycles per byte (AVX edition)

#43

Post by Thiez »

paavoova wrote: post #42
Dylan16807 wrote: post #30

Earlier quoted context omitted.

> My understanding was that utf8 was crafted specifically so that the only null byte in it was literally NUL. Correct. > That all normal human language described by a utf8 string will never contain a NUL. Correct. > If you have embedded NULs, it's not really utf8, is it? Incorrect. NUL is a valid character. If you accept arbitrary utf-8, or arbitrary ascii, or arbitrary 8859-1, then there might be embedded NUL. You c…

It's invalid for unix filenames to have a null character. Therefore, if your application is printing filenames in their unicode representation, it doesn't ever need to consider there to be a null byte. This of course isn't an arbitrary case, but it shows one can make assumptions regardless of the "validity" of a character. I believe for most cases of arbitrary input, the correct and safe thing to do is to assume a by…

Since we arrived on this null-character discussion by considering text manipulation in C, I suspect most comments in this thread are made in the assumption that the text must be manipulated in some way (mine are!), so treating it as a byte stream of unknown encoding doesn't really solve the problem.

While null in filenames may be forbidden on Unix (and also on Windows), there are more exotic systems where it is allowed [1]. When writing portable software it's probably best not to make assumptions about what characters will never be in a filename.

Naturally if you have a problem where you can get away with just moving bytes around and never making assumptions about its contents then that is a great solution.

[1]: https://en.wikipedia.org/wiki/Filename#Comparison_of_filenam...

Re: Validating UTF-8 bytes using only 0.45 cycles per byte (AVX edition)

#44

Post by saagarjha »

the_clarence wrote: post #24

I see a lot of applications trying to take advantage of SIMD, but what when you try to run them on systems that don't support these instructions? My guess is that you need to write multiple files taking advantage of different sets of instructions and then dynamically figure out which to use at runtime with cpuid, but isn't that cumbersome and a way to inflate a codebase dramatically?

Darwin platforms ship binaries with different slices for different versions of Intel processors. You have the generic x86_64 and the newer x86_64h which supports more features.

Re: Validating UTF-8 bytes using only 0.45 cycles per byte (AVX edition)

#45

Post by londons_explore »

oconnor663 wrote: post #40
the_clarence wrote: post #24

I see a lot of applications trying to take advantage of SIMD, but what when you try to run them on systems that don't support these instructions? My guess is that you need to write multiple files taking advantage of different sets of instructions and then dynamically figure out which to use at runtime with cpuid, but isn't that cumbersome and a way to inflate a codebase dramatically?

> inflate a codebase dramatically This is usually only done for very specific algorithms. Unicode validation, hash functions, things like that. Unless you have an absolutely tiny application (which you might, if you're some kind of microcontroller), it's going to be a small percentage of your overall code size.

In a microcontroller, I don't think you'll be needing AVX2...

Re: Validating UTF-8 bytes using only 0.45 cycles per byte (AVX edition)

#46

Post by Rebelgecko »

londons_explore wrote: post #45
oconnor663 wrote: post #40

Earlier quoted context omitted.

> inflate a codebase dramatically This is usually only done for very specific algorithms. Unicode validation, hash functions, things like that. Unless you have an absolutely tiny application (which you might, if you're some kind of microcontroller), it's going to be a small percentage of your overall code size.

In a microcontroller, I don't think you'll be needing AVX2...

I'm not sure where exactly the line is drawn between a microcontroller and a CPU, but even some of the lower end ARMs support SIMD instructions.

Re: Validating UTF-8 bytes using only 0.45 cycles per byte (AVX edition)

#47

Post by [deleted] »

en4bz wrote: post #25
the_clarence wrote: post #24

I see a lot of applications trying to take advantage of SIMD, but what when you try to run them on systems that don't support these instructions? My guess is that you need to write multiple files taking advantage of different sets of instructions and then dynamically figure out which to use at runtime with cpuid, but isn't that cumbersome and a way to inflate a codebase dramatically?

https://gcc.gnu.org/wiki/FunctionMultiVersioning

[deleted]

Re: Validating UTF-8 bytes using only 0.45 cycles per byte (AVX edition)

#48

Post by kwillets »

lorenzhs wrote: post #12
kissiel wrote: post #11

Earlier quoted context omitted.

Nice. So I understand that AVX2 is not bringing the CPU's clock down. Got any sources for power consumption figures/comparisons of those AVX units?

Heavy use of complex AVX2 operations causes downclocking, too, but typically less so than AVX-512. More details are documented in https://en.wikichip.org/wiki/intel/frequency_behavior -- also see e.g. https://en.wikichip.org/wiki/intel/xeon_gold/6138#Frequencie... for an example how the frequencies differ depending on the number of active cores. I think the reason for reducing clock speed when vector units are in hea…

This doesn't do anything harder than a saturating subtract.

Re: Validating UTF-8 bytes using only 0.45 cycles per byte (AVX edition)

#49

Post by rurban »

mcbain wrote: post #39
why_only_15 wrote: post #36

Earlier quoted context omitted.

In my understanding when you use intrinsics and build for a processor without support for the intrinsics then GCC for example will replace it with equivalent code.

Unfortunately, no. That is the case with GCCs __builtin functions. With a few exceptions, intrinsics are basically macros for inline asm that the compiler can reason about. If on x86-64 you use a _mm256* intrinsic and compile without AVX support you just get a compile error, not a pair of equivalent SSE instructions.

Even worse. You mostly get run-time errors when the built machine supported that feature, your machine doesn't, and the features aren't separated into multiversioning or loading different shared libs.

Re: Validating UTF-8 bytes using only 0.45 cycles per byte (AVX edition)

#50

Post by rurban »

akarambir wrote: post #2

What does linux utilities like sed, awk use for text manipulation because they were very slow when I was changing a few table names in a sql file.

They are still mostly not multi-byte string (i.e. unicode) aware after decades of work. I.e. you cannot really search for strings, with case-folding or normalized variants.

See http://crashcourse.housegordon.org/coreutils-multibyte-suppo... and http://perl11.org/blog/foldcase.html for an overview of the performance problems.

This tool only does the minor task of validation of the UTF-8 encoding, nothing else. There are still the major tasks of decoding, folding and normalization to do.

Post reply on HN