6 ms·

Vectorized execution brings a 10x performance increase for expression evaluation

95 points by Lilian_Lee 7y ago

qeternity 7y ago
I’ve seen a fair bit about TiDB but not much from actual users. Can someone who uses this in production explain why and what alternatives they evaluated (we use Citus so would be curious to hear).
- jinqueeny 7y ago
  You can check out the case studies from our users here: https://pingcap.com/success-stories/ https://pingcap.com/success-stories/
userbinator 7y ago
You can also get a 10x accessibility increase for viewing your site, by not doing shit like this: <div class="center-element" id="page-loader"> <svg id="hexagon" viewbox="0 0 129.78 150.37" ... </div> <div id="page-content" style="display:none"> (actual page content here) This is another one of these pages that shouldn't require JS, but deliberately hides the content and then uses JS to un-hide it. WTF!? I know this is a little off-topic but I found it ironic that a post about optimising performance would be presented so outrageously inefficiently and inaccessibly. (I just turned off the CSS to read it.)
- lawn 7y ago
  How does something like this get created in the first place?
  - steve_taylor 7y ago
    Multivariate (i.e. A/B) testing tools. They change the page client-side, which introduces a problem they call “flicker”. It just means that for a moment you see the server-side rendered page as-is, then the tool hacks it into something else, depending on which group you’re in. This can obviously be jarring. The “flicker” is overcome by a page-hiding snippet that shows the page after the tool has done its dirty business or after a timeout (typically 3s). Often, these tools aren’t used for multivariate testing at all. They’re used because the marketing team doesn’t want to go through the web team, so they get an exec to force the web team to install the tool (along with 50 other pieces of marketing crapware) so marketing can hack its changes into the website after it’s loaded. It’s not uncommon for these tools to completely break the website, because the web team makes a change that breaks assumptions relied upon by the marketing team’s hacks. Often, the marketing team will have these changes made by a developer who they hire directly. They are unqualified to interview developers and this is one of many ways incompetent developers find employment.
    - Normal_gaussian 7y ago
      on the flip side many websites run completely without an in house dev team, using a corporate hosting provider and retainer based web companies. The ability to use an injection tool and hire devs for small changes on quick turnarounds can be massive in enabling the marketing department to move forwards. And yet another side shows sites deliberately engineered this way to allow agile behaviour by non-devs. I've seen a few where they track an internal metric so that a dev somes and consolidates it all before it gets too bad.
      - steve_taylor 7y ago
        The problem is it doesn’t work reliably because a lot of people use blockers. Instead of seeing the intended content, they see a blank page for a few seconds, followed by the original content that had already loaded a few seconds ago. Some websites don’t have a timeout, causing many users to see just a blank page unless they disable their blockers. Also, it’s terrible for SEO.
    - Causality1 7y ago
      I'm not sure I've ever seen A/B testing in web articles that wasn't a case of A being an accurate headline and B being the most outrageous thing you could possibly title it without outright lying, and B always wins.
      - colejohnson66 7y ago
        AreTechnica is guilty of this. They do A/B testing of headlines for 10 minutes, but their headlines aren’t the worst. I have seen some outrageous headlines regarding Republicans doing something they don’t like (Ars is a left leaning site) that are clearly designed to get clicks. It’s quite annoying.
        Causality1 7y ago
        That's precisely the site I was thinking of, actually. Some of their writers like Jim Salter and Megan Guess are absolutely fantastic and others you pre-cringe before clicking the story.
- _Nat_ 7y ago
  This worked for me on Chrome with JavaScript disabled: 1. F12 for developer tools. 2. Found <div id="page-content" style="display:none"> and changed it to <div id="page-content"> 3. Clicked off to another element for the change to take effect.
- DougBTX 7y ago
  The page isn’t loading at all for me
- estebarb 7y ago
  It's there any way to read it from a phone? It's 5:04am and I don't want to open a laptop just for reading it...
- manigandham 7y ago
  I usually save articles to Pocket and read it there. If it can't render the article then I don't bother.
- iamxy 7y ago
  An SRE at PingCAP here. Got it. Thanks! We found that using JS to toggle page visibility has some usability issues. We just removed the JS loading animation and will deliver content with good compatibility and progressive enhancement. Sorry for the issues with the display!
  - withdavidli 7y ago
    Nice to see quick response. Page loading on mobile for me. Using Brave browser.
  - Chris_Chambers 7y ago
    What do you mean “we found” an issue? The person you’re responding to found the issue.
  - soulofmischief 7y ago
    Beautiful response. Good luck.
- deleted 7y ago
  [deleted]
baybal2 7y ago
Well what to say. You are just throwing potential performance away if you don't use SSE when you can. There is an idea that "renaming and reordering engine can make non-SSE code as fast as it without extra hassle." At least of X86, that can't be true as you physically can't access all execution ports with non-vector instructions.
- pdpi 7y ago
  Vector instructions come at a cost, though — there’s implications on power budget and on thermals, so it’s very much a “just because you can doesn’t mean you should” piece of tech. Specifically, sustained use of AVX instructions on 256 and 512 bit registers will cost you a chunk of clock frequency even for all, so you have to pass the hurdle of having enough AVX instructions that the downclocking is worth it overall
  - dr_zoidberg 7y ago
    AVX(1) and AVX2 don't cause throttling, just AVX512. Even so, on code that can do the best of them[0], they still result in better performance. Eventually they will implemented in a way that doesn't require throttling, maybe AMD when it finally supports them or Intel when the famed 7nm[1] process arrives. [0] numerical code usually, but go ahead and use them if you can express your problem in a way that makes sense in AVX512 [1] 7 as in "seven" since the 10nm is so troublesome that apparently no desktop/server chips will be made on it and just skips to 7, which should be comparable to TMSCs 5nm
    - gameswithgo 7y ago
      >AVX(1) and AVX2 don't cause throttling, yes they do, on intel cpus anyway. On Ryzen anything that makes more heat will cause throttling, rather than a step change in mode. >. Eventually they will implemented in a way that doesn't require throttling Probably not, there are fundamental physical limitations. I mean, you can put a good cooler on the cpu and disable the throttling, but then you could raise the non SIMD clock rate too.
  - gameswithgo 7y ago
notbigdata 7y ago
i'm quite surprise how many of HN comments are focused on nitpicking frontend implementations rather than the content itself. it's not very likely the author who works on vectorized execution also implemented the blog system.
tom_mellior 7y ago
> As the table reveals, every time this function performs a multiplication, only 8 out of 82 (9+30+28+8+7=82) instructions are doing the “real” multiplication. That's only about 10% of the total instructions. The other 90% are considered interpretation overhead. Once we vectorized this function, its performance was improved by nearly nine times. See PR #12543. This is a misleading way to present this data. If I understand this correctly, most of the 90% "interpretation overhead" are time spent evaluating the operands to the multiplication, and this is also vectorized. So it's not just that vectorizing the 10% can give you a 9x speedup overall, although in my opinion the text tries to suggest this. In any case, there must be even more going on here. The data being processed here seem to be Float64. On an AVX-2 processor like most of us have, you can only fit up to 4 64-bit floats into a vector register. This means that, even if your entire computation vectorizes very very nicely, you should only expect a 4x maximum speedup. Even if they have an AVX-512 server (they don't say) with twice the vector width, 8x would be the expected limit. In practice it would be considerably less because the processor reduces its frequency to avoid overheating on AVX-512-heavy computations. I'm not aware of hardware that uses even wider vectors. So an end-to-end 9x improvement for the entire function here seems impossible to achieve using vectorization alone. I question both the measurement and the suggestion that vectorization is the only thing that changes here. Maybe they accidentally (? they don't seem to understand in detail what's going on) stumbled upon a much more cache friendly version of the computation they were trying to do, or maybe previously they caused the GC to interfere, or... something. But 9x due to vectorization of a Float64 computation? I'm not buying it.
- justincormack 7y ago
  Column access is way more cache friendly for most database computations, yes, as the values being computed are contiguous. They don't give the partial speedup for switching from row to column before they vectorised, it is probably significant.
- vitus 7y ago
  The article describes three optimizations: - Changing the memory layout to be column-oriented (i.e. for greater cache friendliness, as the sibling comment mentions). - Iterating over batches (analogous, possibly equivalent to loop unrolling). - Vectorizing. Iterating over batches (especially going from batches of 1 -> 1024) could very well explain a large portion of the "interpretation overhead" that was removed, since it'd basically just be checking loop conditions and jumping back to the beginning of the loop; in that case, it can be a significant portion of the overall execution, and batching in this way reduces that overhead by 1000x. And sure, vectorizing might only add up to a 4x speedup, but taken with these other changes (especially don't discount cache coherence), I could totally see where the 10x comes from. So the submission title is somewhat misleading to attribute all of it to vectorization (the article title also cites the community), but I could see it being valid, since these were steps needed to take full advantage of vectorization. I do object to the measurement of execution in instructions, since in x86 not every instruction is created equal (multiplications are the poster child of "instructions that take a long time", and certain AVX instructions can cause throttling in Intel CPUs). That said, the article does cite a nearly 9x speedup, which is solid.
snidane 7y ago
I always wondered why people assume that the more high level abstractions or high level programming languages you use the less performance you should expect. C is faster than Java, Java will be faster than Python etc. The 'interpretation overhead' is supposed to kill your performance. But there is one weird exception. You have the APL family, which are a very high at level of abstraction but perform even faster than C. Especially because od using vectorized processing. When you work on vectors of 1000s items in one instruction, you amortize language interpretation cost away and since working with vectors is actually the only natural way to work with computers you get massive performance from those instructions using vectorized instructions or even running on gpu. (All memory access is naturally linear in computing. Random access memory is an unnatural computing myth which comes at enormous cost and has to be hardware accelerated to be even usable). Similar can be said about databases and SQL. Especially in OLAP processing, where you can linearize your data tables and columns and vectorize your processing. Because it is near impossible to overcome von Neumann bottleneck in traditional single computer languages like C or Java, any SQL or APL will beat the crap out of them if you span the processing over multiple cores and machines. Days of single machine processing are over and clusters of computers are the future. AWS (and potentially other clouds) are essentially Operating Systems for sich environent. It'd be nice for open source to catch up though.
- gameswithgo 7y ago
  >The 'interpretation overhead' is supposed to kill your performance. Java isn't interpreted >You have the APL family, which are a very high at level of abstraction but perform even faster than C. No they don't. You process an array of numbers in contiguous order in C (or anything else compiled with llvm or gcc or similar) it gets vectorized too. APL may encourage the programmer down the right data layout path for vectorization more often though. Which would certainly be a good quality on modern hardware.
  - smabie 7y ago
    I’ve personally experienced naive kdb+/Q (which is interpreted) code that is faster than a somewhat optimized C version.
gameswithgo 7y ago
I have an 'art/game' project in Rust that uses vectorized expression evaluation to draw random images. It turns the expression tree into a stack machine then evaluates the stack machine with SIMD instructions: https://github.com/jackmott/evolution/blob/master/src/stack_machine.rs https://github.com/jackmott/evolution/blob/master/src/stack_... The speedup is really big for this case sometimes because not only do you do math 4x/8x/16x faster (depending on instruction set) but you also traverse the stack machine (or tree if you are pure interpreting) 4x/8x/16x less often. The improvement when traversing a tree is extra extra big because of reduced memory hops. I used a SIMD library I made in Rust, which lets me write the stack machine once, and then run it in SSE2/SSE41 or AVX2 mode. You can select either at runtime or compile time: https://github.com/jackmott/simdeez https://github.com/jackmott/simdeez
- dahart 7y ago
  Sounds cool, do you have a gallery? I had a similar sounding project inspired by Karl Sims’ genetic images that I haven’t touched for many years now, but I’ve been meaning to revive and compile to GLSL or CUDA to get (I expect) much faster eval than is possible with CPU AVX or SSE instructions. Have you considered that route?
  - gameswithgo 7y ago
    the readme has some examples: https://github.com/jackmott/evolution https://github.com/jackmott/evolution Not really enough to show off the full range of possibilities but it is a start. The program is still a WIP I'll release it eventually.
    - dahart 7y ago
      Very cool, thanks for the link! The cell & fbm primitives look really useful. The only complex primitive like that I included so far was Perlin turbulence. If you’re interested, here’s a sampling of mine, https://flickr.com/photos/biv4b/albums/576553 https://flickr.com/photos/biv4b/albums/576553 I haven’t gotten around to any vectorized evaluation yet, it’s pure CPU recursive eval, the closest thing I did was to use multiple threads, but it’s not particularly fast compared to what a GPU would do.

95 points by Lilian_Lee 7y ago

I’ve seen a fair bit about TiDB but not much from actual users. Can someone who uses this in production explain why and what alternatives they evaluated (we use Citus so would be curious to hear).

jinqueeny 7y ago
You can check out the case studies from our users here: https://pingcap.com/success-stories/ https://pingcap.com/success-stories/

userbinator 7y ago

You can also get a 10x accessibility increase for viewing your site, by not doing shit like this: <div class="center-element" id="page-loader"> <svg id="hexagon" viewbox="0 0 129.78 150.37" ... </div> <div id="page-content" style="display:none"> (actual page content here) This is another one of these pages that shouldn't require JS, but deliberately hides the content and then uses JS to un-hide it. WTF!? I know this is a little off-topic but I found it ironic that a post about optimising performance would be presented so outrageously inefficiently and inaccessibly. (I just turned off the CSS to read it.)

lawn 7y ago
How does something like this get created in the first place?
- steve_taylor 7y ago
  Multivariate (i.e. A/B) testing tools. They change the page client-side, which introduces a problem they call “flicker”. It just means that for a moment you see the server-side rendered page as-is, then the tool hacks it into something else, depending on which group you’re in. This can obviously be jarring. The “flicker” is overcome by a page-hiding snippet that shows the page after the tool has done its dirty business or after a timeout (typically 3s). Often, these tools aren’t used for multivariate testing at all. They’re used because the marketing team doesn’t want to go through the web team, so they get an exec to force the web team to install the tool (along with 50 other pieces of marketing crapware) so marketing can hack its changes into the website after it’s loaded. It’s not uncommon for these tools to completely break the website, because the web team makes a change that breaks assumptions relied upon by the marketing team’s hacks. Often, the marketing team will have these changes made by a developer who they hire directly. They are unqualified to interview developers and this is one of many ways incompetent developers find employment.
  - Normal_gaussian 7y ago
    on the flip side many websites run completely without an in house dev team, using a corporate hosting provider and retainer based web companies. The ability to use an injection tool and hire devs for small changes on quick turnarounds can be massive in enabling the marketing department to move forwards. And yet another side shows sites deliberately engineered this way to allow agile behaviour by non-devs. I've seen a few where they track an internal metric so that a dev somes and consolidates it all before it gets too bad.
    - steve_taylor 7y ago
      The problem is it doesn’t work reliably because a lot of people use blockers. Instead of seeing the intended content, they see a blank page for a few seconds, followed by the original content that had already loaded a few seconds ago. Some websites don’t have a timeout, causing many users to see just a blank page unless they disable their blockers. Also, it’s terrible for SEO.
  - Causality1 7y ago
    I'm not sure I've ever seen A/B testing in web articles that wasn't a case of A being an accurate headline and B being the most outrageous thing you could possibly title it without outright lying, and B always wins.
    - colejohnson66 7y ago
      AreTechnica is guilty of this. They do A/B testing of headlines for 10 minutes, but their headlines aren’t the worst. I have seen some outrageous headlines regarding Republicans doing something they don’t like (Ars is a left leaning site) that are clearly designed to get clicks. It’s quite annoying.
      - Causality1 7y ago
        That's precisely the site I was thinking of, actually. Some of their writers like Jim Salter and Megan Guess are absolutely fantastic and others you pre-cringe before clicking the story.
_Nat_ 7y ago
This worked for me on Chrome with JavaScript disabled: 1. F12 for developer tools. 2. Found <div id="page-content" style="display:none"> and changed it to <div id="page-content"> 3. Clicked off to another element for the change to take effect.
DougBTX 7y ago
The page isn’t loading at all for me
estebarb 7y ago
It's there any way to read it from a phone? It's 5:04am and I don't want to open a laptop just for reading it...
manigandham 7y ago
I usually save articles to Pocket and read it there. If it can't render the article then I don't bother.
iamxy 7y ago
An SRE at PingCAP here. Got it. Thanks! We found that using JS to toggle page visibility has some usability issues. We just removed the JS loading animation and will deliver content with good compatibility and progressive enhancement. Sorry for the issues with the display!
- withdavidli 7y ago
  Nice to see quick response. Page loading on mobile for me. Using Brave browser.
- Chris_Chambers 7y ago
  What do you mean “we found” an issue? The person you’re responding to found the issue.
- soulofmischief 7y ago
  Beautiful response. Good luck.
deleted 7y ago
[deleted]

baybal2 7y ago

Well what to say. You are just throwing potential performance away if you don't use SSE when you can. There is an idea that "renaming and reordering engine can make non-SSE code as fast as it without extra hassle." At least of X86, that can't be true as you physically can't access all execution ports with non-vector instructions.

pdpi 7y ago
Vector instructions come at a cost, though — there’s implications on power budget and on thermals, so it’s very much a “just because you can doesn’t mean you should” piece of tech. Specifically, sustained use of AVX instructions on 256 and 512 bit registers will cost you a chunk of clock frequency even for all, so you have to pass the hurdle of having enough AVX instructions that the downclocking is worth it overall
- dr_zoidberg 7y ago
  AVX(1) and AVX2 don't cause throttling, just AVX512. Even so, on code that can do the best of them[0], they still result in better performance. Eventually they will implemented in a way that doesn't require throttling, maybe AMD when it finally supports them or Intel when the famed 7nm[1] process arrives. [0] numerical code usually, but go ahead and use them if you can express your problem in a way that makes sense in AVX512 [1] 7 as in "seven" since the 10nm is so troublesome that apparently no desktop/server chips will be made on it and just skips to 7, which should be comparable to TMSCs 5nm
  - gameswithgo 7y ago
    >AVX(1) and AVX2 don't cause throttling, yes they do, on intel cpus anyway. On Ryzen anything that makes more heat will cause throttling, rather than a step change in mode. >. Eventually they will implemented in a way that doesn't require throttling Probably not, there are fundamental physical limitations. I mean, you can put a good cooler on the cpu and disable the throttling, but then you could raise the non SIMD clock rate too.
- gameswithgo 7y ago

notbigdata 7y ago

i'm quite surprise how many of HN comments are focused on nitpicking frontend implementations rather than the content itself. it's not very likely the author who works on vectorized execution also implemented the blog system.

tom_mellior 7y ago

> As the table reveals, every time this function performs a multiplication, only 8 out of 82 (9+30+28+8+7=82) instructions are doing the “real” multiplication. That's only about 10% of the total instructions. The other 90% are considered interpretation overhead. Once we vectorized this function, its performance was improved by nearly nine times. See PR #12543. This is a misleading way to present this data. If I understand this correctly, most of the 90% "interpretation overhead" are time spent evaluating the operands to the multiplication, and this is also vectorized. So it's not just that vectorizing the 10% can give you a 9x speedup overall, although in my opinion the text tries to suggest this. In any case, there must be even more going on here. The data being processed here seem to be Float64. On an AVX-2 processor like most of us have, you can only fit up to 4 64-bit floats into a vector register. This means that, even if your entire computation vectorizes very very nicely, you should only expect a 4x maximum speedup. Even if they have an AVX-512 server (they don't say) with twice the vector width, 8x would be the expected limit. In practice it would be considerably less because the processor reduces its frequency to avoid overheating on AVX-512-heavy computations. I'm not aware of hardware that uses even wider vectors. So an end-to-end 9x improvement for the entire function here seems impossible to achieve using vectorization alone. I question both the measurement and the suggestion that vectorization is the only thing that changes here. Maybe they accidentally (? they don't seem to understand in detail what's going on) stumbled upon a much more cache friendly version of the computation they were trying to do, or maybe previously they caused the GC to interfere, or... something. But 9x due to vectorization of a Float64 computation? I'm not buying it.

justincormack 7y ago
Column access is way more cache friendly for most database computations, yes, as the values being computed are contiguous. They don't give the partial speedup for switching from row to column before they vectorised, it is probably significant.
vitus 7y ago
The article describes three optimizations: - Changing the memory layout to be column-oriented (i.e. for greater cache friendliness, as the sibling comment mentions). - Iterating over batches (analogous, possibly equivalent to loop unrolling). - Vectorizing. Iterating over batches (especially going from batches of 1 -> 1024) could very well explain a large portion of the "interpretation overhead" that was removed, since it'd basically just be checking loop conditions and jumping back to the beginning of the loop; in that case, it can be a significant portion of the overall execution, and batching in this way reduces that overhead by 1000x. And sure, vectorizing might only add up to a 4x speedup, but taken with these other changes (especially don't discount cache coherence), I could totally see where the 10x comes from. So the submission title is somewhat misleading to attribute all of it to vectorization (the article title also cites the community), but I could see it being valid, since these were steps needed to take full advantage of vectorization. I do object to the measurement of execution in instructions, since in x86 not every instruction is created equal (multiplications are the poster child of "instructions that take a long time", and certain AVX instructions can cause throttling in Intel CPUs). That said, the article does cite a nearly 9x speedup, which is solid.

snidane 7y ago

I always wondered why people assume that the more high level abstractions or high level programming languages you use the less performance you should expect. C is faster than Java, Java will be faster than Python etc. The 'interpretation overhead' is supposed to kill your performance. But there is one weird exception. You have the APL family, which are a very high at level of abstraction but perform even faster than C. Especially because od using vectorized processing. When you work on vectors of 1000s items in one instruction, you amortize language interpretation cost away and since working with vectors is actually the only natural way to work with computers you get massive performance from those instructions using vectorized instructions or even running on gpu. (All memory access is naturally linear in computing. Random access memory is an unnatural computing myth which comes at enormous cost and has to be hardware accelerated to be even usable). Similar can be said about databases and SQL. Especially in OLAP processing, where you can linearize your data tables and columns and vectorize your processing. Because it is near impossible to overcome von Neumann bottleneck in traditional single computer languages like C or Java, any SQL or APL will beat the crap out of them if you span the processing over multiple cores and machines. Days of single machine processing are over and clusters of computers are the future. AWS (and potentially other clouds) are essentially Operating Systems for sich environent. It'd be nice for open source to catch up though.

gameswithgo 7y ago
>The 'interpretation overhead' is supposed to kill your performance. Java isn't interpreted >You have the APL family, which are a very high at level of abstraction but perform even faster than C. No they don't. You process an array of numbers in contiguous order in C (or anything else compiled with llvm or gcc or similar) it gets vectorized too. APL may encourage the programmer down the right data layout path for vectorization more often though. Which would certainly be a good quality on modern hardware.
- smabie 7y ago
  I’ve personally experienced naive kdb+/Q (which is interpreted) code that is faster than a somewhat optimized C version.

gameswithgo 7y ago

I have an 'art/game' project in Rust that uses vectorized expression evaluation to draw random images. It turns the expression tree into a stack machine then evaluates the stack machine with SIMD instructions: https://github.com/jackmott/evolution/blob/master/src/stack_machine.rs https://github.com/jackmott/evolution/blob/master/src/stack_... The speedup is really big for this case sometimes because not only do you do math 4x/8x/16x faster (depending on instruction set) but you also traverse the stack machine (or tree if you are pure interpreting) 4x/8x/16x less often. The improvement when traversing a tree is extra extra big because of reduced memory hops. I used a SIMD library I made in Rust, which lets me write the stack machine once, and then run it in SSE2/SSE41 or AVX2 mode. You can select either at runtime or compile time: https://github.com/jackmott/simdeez https://github.com/jackmott/simdeez

dahart 7y ago
Sounds cool, do you have a gallery? I had a similar sounding project inspired by Karl Sims’ genetic images that I haven’t touched for many years now, but I’ve been meaning to revive and compile to GLSL or CUDA to get (I expect) much faster eval than is possible with CPU AVX or SSE instructions. Have you considered that route?
- gameswithgo 7y ago
  the readme has some examples: https://github.com/jackmott/evolution https://github.com/jackmott/evolution Not really enough to show off the full range of possibilities but it is a start. The program is still a WIP I'll release it eventually.
  - dahart 7y ago
    Very cool, thanks for the link! The cell & fbm primitives look really useful. The only complex primitive like that I included so far was Perlin turbulence. If you’re interested, here’s a sampling of mine, https://flickr.com/photos/biv4b/albums/576553 https://flickr.com/photos/biv4b/albums/576553 I haven’t gotten around to any vectorized evaluation yet, it’s pure CPU recursive eval, the closest thing I did was to use multiple threads, but it’s not particularly fast compared to what a GPU would do.