Hacker News Reader

Comment by pcwalton | Hacker News Reader

Games are also representative of the apps that actually squeeze the performance out of CPUs. When you look at most desktop apps and Web servers, you see enormous wastes of CPU cycles. This is because development velocity, ease of development, and language ecosystems (Ruby on Rails, node.js, PHP, etc.) take priority over using the hardware efficiently in those domains. I don't think this is necessarily a huge problem; however, it does mean that CPU vendors are disincentivized to optimize for e.g. your startup's Ruby on Rails app, since the problem (if there is one) is that Ruby isn't using the functionality that already exists, not that the hardware doesn't have the right functionality available.

View on HN

Interestingly, the one thing that typical web frameworks do do very frequently is copy, concatenate, and compare strings. And savvy platform developers will optimize that heavily. I remember poking around in Google's codebase and finding replacements for memcmp/memcpy/STL + string utilities that were all nicely vectorized, comparing/copying the bulk of the string with SIMD instructions and then using a Duff's Device-like technique to handle the residual. (Written by Jeff Dean, go figure.)

No idea whether mainstream platforms like Ruby or Python do this...it wouldn't surprise me if there's relatively low hanging fruit for speeding up almost every webapp on the planet.

Why is this even a thing? Copying and the like is such a common operation. Why don't chip providers offer a single instruction that gets decoded to the absolute fastest way the chip can do? That'd even allow them to, maybe, do some behind-the-scenes optimization, bypassing caches or something. It's painful that such a common operation needs highly specialized code. I know you can just REP an operation but apparently CPUs don't optimize this the same way.

This is too obvious an issue, so there must be a solid reason. What is it?

http://stackoverflow.com/questions/8858778/why-are-complicat...

counter claims https://news.ycombinator.com/item?id=8683565

Ah that thread is great and answers my question. TL;DR seems to be that rep+mov is as fast as anything now.

This seems like something that compilers should do and CPU instruction sets should not.

It's really something the stdlib should do, which, when I've seen it implemented, is usually what happens.

The compiler should just provide good inlining support, so that if eg. you include the short-string optimization in your stdlib, the compiler can optimize it down to a couple bit operations, a test, and a word copy. If the test fails and your string is more than 7 bytes, it's perfectly fine to call a function - the function call overhead is usually dwarfed by the copy loop for large strings. And then if new hardware comes out and you vectorize it differently, you can get away with replacing that one function in the stdlib instead of recompiling every single program in existence.

Why? It's a common op that requires internal knowledge of every microarchitecture, isn't it? Seems like something that should be totally offloaded to the CPU so you're guaranteed best performance.

The message you were referring to was talking about code for copying strings. If you wanted an instruction to copy lots of strings, the CPU would need to know what a character is (which could be 7 bits, 8 bits, 16 or 32), what a string is, how it's terminated, what ascii and unicode is, be able to allow new character encoding standards etc etc. Then you would need other instructions for other high level datatypes. That's not what CPUs do, because you're limited by how much more logic/latency you can add to an architecture, how many distinct instructions you can implement with the bits available per instruction, how many addressing modes you want etc.

So instead, this information/knowledge about high level data types is encapsulated by standard libraries and then the compiler below that. Most CPUs have single instructions to copy a chunk of data from somewhere to somewhere else and a nice basic way to repeat this process efficiently, and it's up to the compiler to use this.

I remember way back in the DOS days there were a lot of clever things you could do with setting up DMA transfers which would then run in the background... With CPU/memory latency and bandwidth being so much more of an issue these days I can't see why this isn't still the case. Maybe it's all done automatically in the background now?

DMA is done automatically by modern hardware, PCIe(/Thunderbolt) and SATA just do it.

Somewhat related is e.g. the sendfile() syscall that's used by web servers/frameworks to pass a file directly from your fcgi application to the outgoing socket.

The CPU has a limited amount of silicon to spend on instruction decoding. That silicon is also part of every single instructions issue latency. Machines like the Cray with complex internal operations paid the cost in issue delays, and most workloads won't earn them back.

In the olden days of x86: "REPNZ SCASB" to get the length of a zero-terminated string and "REP MOVSB" to copy bytes from place to place. But I think more modern CPUs actually work faster with the RISCier equivalents.

See http://yosefk.com/blog/its-done-in-hardware-so-its-cheap.htm..., "It's done in hardware so it's cheap".

Summary: 'Why doesn't "hardware support" automatically translate to "low cost"/"efficiency"? The short answer is, hardware is an electric circuit and you can't do magic with that, there are rules.'

> finding replacements for memcmp/memcpy/STL + string utilities that were all nicely vectorized

Why don't they just patch the memcmp/memcpy in their libc?

Sorry, I wasn't clear. That's exactly what they do do. These aren't separate APIs; they are modified versions of libc and the STL that speed up the implementation. Facebook apparently has similar STL replacements that they've open-sourced as part of Folly.

(The string utilities I was referring to actually are separate APIs, focused around manipulating string pieces that are backed by buffers owned by other objects. It's like the slice concept in Go or Rust. With the growth in Google's engineering department, it got very difficult to ensure that everybody knew about them and used them correctly; this is probably easier if they're part of the stdlib. Indeed, they're in boost as string_ref, but most of Google's codebase predates boost - indeed, they were added by a Googler.)

If your allocator is fast, the IO-list approach used by Erlang is a lot faster at copying and concatenating strings than anything that involves copying the characters around. I used this to good effect in Ur-Scheme. But then processing the contents of the strings becomes potentially expensive, and you may have aliasing bugs if your strings are mutable.

Python 2.7.3 concatenates strings in string_concat using Py_MEMCPY, which is a macro defined at Include/pyport.h:292. That invokes memcpy, except for very short strings, where it just uses a loop, because on some platforms memcpying three bytes is a lot slower than just copying them. In http://canonical.org/~kragen/sw/dev3/propfont.c I got a substantial speedup from writing a short_memcpy function that does this kind of nonsense:

      if (nbytes == 4) {
        memcpy(dest, src, 4);
      } else if (nbytes < 4) {
        if (nbytes == 2) {
          memcpy(dest, src, 2);
        } else if (nbytes < 2) {

The main case in eglibc 2.13 memcpy, which is what Python is invoking on my machine, is as follows:

      /* Copy just a few bytes to make DSTP aligned.  */
      len -= (-dstp) % OPSIZ;
      BYTE_COPY_FWD (dstp, srcp, (-dstp) % OPSIZ);

      /* Copy whole pages from SRCP to DSTP by virtual address manipulation,
         as much as possible.  */

      PAGE_COPY_FWD_MAYBE (dstp, srcp, len, len);

      /* Copy from SRCP to DSTP taking advantage of the known alignment of
         DSTP.  Number of bytes remaining is put in the third argument,
         i.e. in LEN.  This number may vary from machine to machine.  */

      WORD_COPY_FWD (dstp, srcp, len, len);

      /* Fall out and copy the tail.  */
    }

  /* There are just a few bytes to copy.  Use byte memory operations.  */
  BYTE_COPY_FWD (dstp, srcp, len);

In sysdeps/i386/i586/memcopy.h, WORD_COPY_FWD uses inline assembly to copy 32 bytes per loop iteration, but using %eax and %edx, not using SIMD instructions. It explains:

    /* Written like this, the Pentium pipeline can execute the loop at a
       sustained rate of 2 instructions/clock, or asymptotically 480
       Mbytes/second at 60Mhz.  */

This is presumably what Jeff's code was a replacement for. Too bad he didn't contribute it to glibc, but he presumably wrote it at a time in Google's lifetime where the Google paranoia was at its absolute peak.

PAGE_COPY_FWD sounds awesome but it's only defined on Mach. Elsewhere PAGE_COPY_FWD_MAYBE just invokes WORD_COPY_FWD.

My tentative conclusion is that Ulrich scared everyone else away from wanting to work on memcpy so effectively that it's been unmaintained since sometime in the previous millennium.

Interesting - the last time I looked seriously at Erlang (~2005), its string handling was a mess. Strings were lists of characters, which ate 8 bytes of memory per character, couldn't be addressed in O(1), and were often slow to traverse because of cache misses. IOLists seem to be a big improvement on that. They're functionally equivalent to a Rope, right? Ropes are used all over the place at Google (where they're called Cords); I worked on a templating engine while I was there that would just assemble pieces into one for later flushing out to the network.

Erlang has always used IO lists for I/O, and they can include both strings and "binaries", i.e. byte arrays. IO lists are very similar to ropes, but because they don't even store the length in each node, they're even faster than ropes to concatenate, but linear-time to index into.

I don't necessarily agree that it's a problem of the language ecosystems. In my experience games are one of the few areas where it is likely to be CPU bottlenecked and not I/O bottlenecked.

My sample size is only the set of projects that I've personally worked on, but in the projects where I have intentionally profiled where the time is being spent, I have only ever run into UX-impacting CPU bottlenecks when working on games. This is spanning code I've written from assembly all the way up to Python. Not counting JS because the DOM is a bit of a black box to me. In almost every other case, the bottleneck was not being able to pull data out of physical storage or some network store fast enough. In some cases it was not being able to pull data from RAM fast enough. In a few cases it was not being able to pull data from a database fast enough due to needing to cover too big of a table, which I lump into the "waiting for I/O" category under the lightly investigated hypothesis that it's not because the CPU is having trouble iterating over the indices, but because the database can't keep the whole index in memory.

> My sample size is only the set of projects that I've personally worked on, but in the projects where I have intentionally profiled where the time is being spent, I have only ever run into UX-impacting CPU bottlenecks when working on games.

Try out any "enterprise" app that thinks its a good idea to load 25,000 widgets on one page. That'll show you the meaning of "CPU bottleneck".

> Try out any "enterprise" app that thinks its a good idea to load 25,000 widgets on one page. That'll show you the meaning of "CPU bottleneck".

Depending on the implementation it might also be a GPU bottleneck.

It's pretty crazy how video games can display thousands of objects and millions of vertices at 100+fps, yet web browsers and applications can struggle to display more than a handful.

Yep. That's largely because 2D vector graphics APIs from the '90s are poor fits for GPUs (and stream processors in general, really).

If you have a look at the code on many websites the answer is ludicrous amounts of bloat.

Its not crazy when you consider typical video game economics (hundreds of developers/long dev time/high budgets/high price per unit) vs. typical website economics (handful of developers at best/short dev time/low budget/microscopic price per "unit"). Video games are often intimately tied to the underlying hardware/software stack allowing further optimization whereas the same webpage can often operate unaltered on a multitude of devices. And video games are often judged by how many "objects and vertices" they can show and how fast they can show them, whereas websites have other criteria.

That's because the video game engines doesn't have to be hardened against malicious asset files. All the code in a video game runs at the same permissions level, which you definitely can't say about a random page on cnn.com.

Browser content has to support all the features and they add up pretty quickly. For example a large scrolling list with thousands of items can be solved by a gamedev by mandating all content be the same size and applying a tiling rule. A list in a webapp is likely to be held to a higher standard and so needs to consider heuristics to find the position of content, dynamic updates, etc.

That's what 10+ full-time engine devs working full-time on the project from the start can get you, I suppose.

I've seen a page that just displayed a grid of images. It took seconds of CPU time on an i7. The page doubled its load time if you had CPU throttling. I'm not sure what the ultimate reason was, but the end result was that, as far as the user saw, the page did a fancier looking <table> and required billions of cycles to do so.

While that technically may be a cpu bottleneck, I like to look at it as an implementation bottleneck. I can write a pong game that will be bottlenecked by any cpu if I make it calculate a million digits of pi at the start of each game loop, but it doesn't mean my game is more hardcore than Crysis.

It's obviously an implementation issue. The question is how do otherwise sane-appearing individuals end up writing code like that? How does it even pass a preliminary usage test? And so on. This wasn't some big enterprise, either.

That question haunts all of us... For instance... Lets say you need to query a db to get 4 known sets of things aggregated by other things... That should scream at you "in clause with the known params and group by" or.... if you take an approach I saw recently you spawn 4 worker threads each querying the same tables but with one of those 4 params then combining the records.... I'm afraid this board may constitute the remaining sane individuals...

Edit those known params were all used as a param for the same column

True, but in cases like that it seems like the CPU is hardly the problem in the big picture. ;)

Sounds like you and I mostly agree. Just that when you do a root cause analysis, "more efficient CPU usage" seems to rarely be the best place to optimize, compared to "do less I/O" or "stop putting 25,000 widgets on one page", or "smaller RAM footprint", and so on.

> In my experience games are one of the few areas where it is likely to be CPU bottlenecked and not I/O bottlenecked.

Agreed, in most cases. That's why I'm not sure what I described is really a problem :)

(I do think that mobile apps and the client-side portion of Web apps, for example, are often CPU/GPU-bottlenecked, though.)

You're right, I think we generally agree.

I was just picking at a nuance of what you said about wasted CPU cycles. Yes, some languages and toolchains these days are less efficient to trade for ease of development, but from my experience it seems like I/O to RAM/disk/network is still 80% of the problem and "less work per CPU instruction" is 20% of the problem.

I have seen plenty of 10x speedups in most apps from trivial changes. If you fail to use CPU cache correctly then can be getting ~1% utilization or less per logical CPU which is still plenty fast for the core logic of many applications.

That's because on web apps we have plenty of CPU cycles to burn. Our performance bottlenecks are disk/database and network speeds.

Modern games load GPU more than the CPU though.

Depends on the game and what's going on, but even with GPU heavy games the CPU can do a ton of work just getting all the data ready and packaged up for the GPU to chew on.

Yes, decompression can be a common load.

Causality points both ways, though. Games use the GPU because that's where the compute power is—hence, that's why graphics are so emphasized over other features. GPUs are so powerful to meet the needs of gamers. There's nothing inherently faster or better about a GPU because most tasks don't parallelize that easy—it just so happens that the tasks that DO parallelize easily are highly emphasized.

Reply on news.ycombinator.com