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

11–20 of 54 posts

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

#11

Post by kissiel »

masklinn wrote: post #10
kissiel wrote: post #9

I wonder about the Joules per byte. AFAIK AVX units are quite expensive energy-wise.

Don't they also tend to work at a lower clock due to their higher energy requirements? edit: though this is AVX2 ("AVX-256") rather than AVX-512, and Lemire has covered AVX and the possibility of throttling (with or without AVX) in the past so they're probably aware of the potential issue and consider that they either won't get triggered or the gain is good enough to compensate the lower frequency.

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?

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

#12

Post by lorenzhs »

kissiel wrote: post #11
masklinn wrote: post #10

Earlier quoted context omitted.

Don't they also tend to work at a lower clock due to their higher energy requirements? edit: though this is AVX2 ("AVX-256") rather than AVX-512, and Lemire has covered AVX and the possibility of throttling (with or without AVX) in the past so they're probably aware of the potential issue and consider that they either won't get triggered or the gain is good enough to compensate the lower frequency.

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 heavy use is to keep power usage in check.

You might also find https://blog.cloudflare.com/on-the-dangers-of-intels-frequen... helpful, which goes into detail about a specific case where dynamic frequency scaling resulted in AVX-512 code running slower than AVX2 code.

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

#13

Post by bradleyjg »

Under the new string model in java > 8 a fairly frequent workflow is:

1) get external string

2) figure out if it is UTF-8, UTF-16, or some other recognizable encoding

3) validate the byte stream

4) figure out if the code points in the incoming string can be represented in Latin-1

5) instantiate a java string using either the Latin-1 encoder or the UTF-16 encoder

I know some or all of these steps are done using hotspot intrinsics, and then the JIT/VM does inlining, folding and so on, but I wonder how fast a custom assembly function to do all these steps at once could be.

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

#14

Post by masklinn »

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…

And here are some of Lemire's own posts on the subject:

* https://lemire.me/blog/2018/04/19/by-how-much-does-avx-512-s...

* https://lemire.me/blog/2018/08/13/the-dangers-of-avx-512-thr...

* https://lemire.me/blog/2018/08/15/the-dangers-of-avx-512-thr...

* https://lemire.me/blog/2018/08/24/trying-harder-to-make-avx-...

* https://lemire.me/blog/2018/08/25/avx-512-throttling-heavy-i...

* https://lemire.me/blog/2018/09/04/per-core-frequency-scaling...

* https://lemire.me/blog/2018/09/07/avx-512-when-and-how-to-us...

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

#15

Post by the8472 »

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…

The downclocking does not apply at all to simple 256bit bit juggling operations. The code in question should run at full speed.

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

#16

Post by etatoby »

akarambir wrote: post #6
akx wrote: post #5

Earlier quoted context omitted.

How slow? On my 2013 MBP, `gsed` (sed from coreutils) can do a replacement like that at about 350 MiB/s (of which most seems to be spent writing to disk, since writing to /dev/null hikes it up to 800 MiB/s).

It was sed substitute command on a ~800Mb file on Thinkpad T470 with SSD. It was taking around 40-50 sec for each substitution. Though as others have pointed, it may not be directly related to article in discussion.

Did you use any quadratic or worse regex algorithm? Such as having more than one .* in a single regex.

Did you set LANG=C before running sed, to bypass the UTF-8 logic?

Also, if you had a list of substitutions to perform, did you try writing them as a single sed script?

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

#17

Post by twtw »

kissiel wrote: post #9

I wonder about the Joules per byte. AFAIK AVX units are quite expensive energy-wise.

It could well be lower than a scalar approach. SIMD units like AVX are power hungry, but a greater fraction of that power is relevant computation rather than power for control, schedule, etc. Ideally, the constant instruction overhead to get it executing on a functional unit is amortized over the width of the vector.

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

#18

Post by Thiez »

coldtea wrote: post #7
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.

What was the size of the SQL file? A "few table names" doesn't mean much if the SQL file is 20GB. In any case, sed and awk are plenty fast, but not the fastest methods of text manipulation. You could write a custom C program for that.

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 you probably want to do anyway because pascal-strings are simply better.

I would use Rust or C++ for this task.

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

#19

Post by masklinn »

Thiez wrote: post #18
coldtea wrote: post #7

Earlier quoted context omitted.

What was the size of the SQL file? A "few table names" doesn't mean much if the SQL file is 20GB. In any case, sed and awk are plenty fast, but not the fastest methods of text manipulation. You could write a custom C program for that.

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…

> 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], …) rather than just a buffer/pointer.

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

#20

Post by Thiez »

masklinn wrote: post #19
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…

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

That is a fair point, I misunderstood the term to refer to any type of string where the length is stored explicitly. I'll try and refer to them by their correct name ('record strings') from now on :-)
Post reply on HN