4 ms·
Interestingly, the one thing that typical web frameworks do do very frequently is copy, concatenate, and compare strings. And savvy platform developers will op
by nostrademons 10y ago
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.
- MichaelGG 10y agoWhy 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?
- corysama 10y agohttp://stackoverflow.com/questions/8858778/why-are-complicated-memcpy-memset-superior http://stackoverflow.com/questions/8858778/why-are-complicat... counter claims https://news.ycombinator.com/item?id=8683565 https://news.ycombinator.com/item?id=8683565
- MichaelGG 10y agoAh that thread is great and answers my question. TL;DR seems to be that rep+mov is as fast as anything now.
- Tloewald 10y agoThis seems like something that compilers should do and CPU instruction sets should not.
- nostrademons 10y agoIt'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.
- MichaelGG 10y agoWhy? 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.
- anjc 10y agoThe 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.
- taneq 10y agoI 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?
- creshal 10y agoDMA 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.
- wbl 10y agoThe 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.
- nickzoic 10y agoIn 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.
- kragen 10y agoSee http://yosefk.com/blog/its-done-in-hardware-so-its-cheap.html 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.'
- majewsky 10y ago> 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?
- nostrademons 10y agoSorry, 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.)
- kragen 10y agoIf 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 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.
- nostrademons 10y ago