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

31–40 of 54 posts

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

#31

Post by masklinn »

Dylan16807 wrote: post #27
masklinn wrote: post #19

Earlier quoted context omitted.

> Which you probably want to do anyway because pascal-strings are simply better. They're not though. While having an explicit length is great, p-strings means the length is the first item of the data buffer, which is just awful, and why Pascal was originally limited to 255 byte strings. Rust or C++ use record-strings, where the string type is a "rich" stack-allocated structure of (*buffer, length[, capacity], …) rath…

> p-strings means the length is the first item of the data buffer, which is just awful You can represent it as a struct of (length, char[]) which isn't awful.

> You can represent it as a struct of (length, char[]) which isn't awful.

It kinda is still: if you're storing it on the stack you're dealing with an unsized on-stack structure which is painful, and if you're not you're paying a deref for accessing the length which you don't need to. If by `char[]` you mean `char*` then it's a record string, not a p-string.

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

#32

Post by Dylan16807 »

masklinn wrote: post #31
Dylan16807 wrote: post #27

Earlier quoted context omitted.

> p-strings means the length is the first item of the data buffer, which is just awful You can represent it as a struct of (length, char[]) which isn't awful.

> You can represent it as a struct of (length, char[]) which isn't awful. It kinda is still: if you're storing it on the stack you're dealing with an unsized on-stack structure which is painful, and if you're not you're paying a deref for accessing the length which you don't need to. If by `char[]` you mean `char*` then it's a record string, not a p-string.

I mean a variable-length array, all stored together.

Presumably you'd allocate it on the heap in general. But a record string also requires a heap allocation.

Most of the time you're touching the length you're probably touching the string data too, so that dereference isn't going to cost very much. And it comes with a tradeoff of more compact local data. So I stand by it being not awful! It may not be perfect, but it's a solid option.

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

#33

Post by jmgrosen »

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?

Generally speaking, I think if you care enough about performance to write manual SIMD code, being a little more cumbersome is a tradeoff you’re willing to make.

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

#34

Post by Thiez »

Dylan16807 wrote: post #32
masklinn wrote: post #31

Earlier quoted context omitted.

> You can represent it as a struct of (length, char[]) which isn't awful. It kinda is still: if you're storing it on the stack you're dealing with an unsized on-stack structure which is painful, and if you're not you're paying a deref for accessing the length which you don't need to. If by `char[]` you mean `char*` then it's a record string, not a p-string.

I mean a variable-length array, all stored together. Presumably you'd allocate it on the heap in general. But a record string also requires a heap allocation. Most of the time you're touching the length you're probably touching the string data too, so that dereference isn't going to cost very much. And it comes with a tradeoff of more compact local data. So I stand by it being not awful! It may not be perfect, but it…

When you have record strings you get slicing for free though. Without the indirection of a pointer you have to copy data when you slice (or you must have a separate 'sliced string' type).

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

#35

Post by Dylan16807 »

Thiez wrote: post #34
Dylan16807 wrote: post #32

Earlier quoted context omitted.

I mean a variable-length array, all stored together. Presumably you'd allocate it on the heap in general. But a record string also requires a heap allocation. Most of the time you're touching the length you're probably touching the string data too, so that dereference isn't going to cost very much. And it comes with a tradeoff of more compact local data. So I stand by it being not awful! It may not be perfect, but it…

When you have record strings you get slicing for free though. Without the indirection of a pointer you have to copy data when you slice (or you must have a separate 'sliced string' type).

"free" if you ignore the cost of doing lifetime management. So beneficial in some use cases but not others.

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

#36

Post by why_only_15 »

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?

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.

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

#37

Post by masklinn »

knome wrote: post #26
Thiez wrote: post #18

Earlier quoted context omitted.

While it sure is possible to do text manipulation in C, I don't think it should ever be the first choice, even if 'fastest' is a goal. A 0 byte is perfectly acceptable in a utf8 string (or any unicode string, really). But C has those annoying zero-terminated strings, so if you want to manipulate arbitrary unicode strings the first thing you can do is kiss the string functions in the C standard library goodbye. Which…

> 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…

> 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 really utf8, is it?

It is. NUL is a C-string convention, as far as unicode is concerned NULL (U+0000) is a perfectly normal codepoint (very much unlike e.g. the U+D800–U+DFFF range).

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

#38

Post by eesmith »

why_only_15 wrote: post #36
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?

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.

That is true. Here's a couple of negatives. First, you still need to build once for each architecture, either as different executables, or as different object files, and provide some dispatch mechanism to use the right one based on what hardware is available.

Second, if the intrinsics aren't built-in then there may be faster alternatives than using the GCC emulated version.

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

#39

Post by mcbain »

why_only_15 wrote: post #36
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?

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.

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

#40

Post by oconnor663 »

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.

Post reply on HN