5 ms·

Forget the typo. This is the slowest, most naive implementation of memset possible. Is this actual shipping code? I've followed the changeset up to the top a

by pkaler 16y ago

Forget the typo. This is the slowest, most naive implementation of memset possible. Is this actual shipping code? I've followed the changeset up to the top and it looks like it's in platform/bootable/bootloader/legacy. Hopefully this isn't actually called anywhere, but the review date says May 13th. What's the point of optimizing the Java VM when functions like memset, malloc, memcmp, memcpy, memchr, etc, etc haven't even been optimized for the platform. EDIT: I understand that 95% of your time will be writing in a language like Ruby, Python, Javascript or a C based language. But dear god, please add Agner Fog's Optimization Manuals to your reading list. http://www.agner.org/optimize/ http://www.agner.org/optimize/

neilc 16y ago
Given that it is in "platform/bootable/bootloader/legacy", I'm not sure there is much point getting all worked up about performance -- presumably something much more efficient would be used for the vast majority of cases.
- joezydeco 16y ago
  I haven't updated my source tree in a long time, but the ARM devices were using bionic/libc/arch-arm/bionic/memset.S. This is pure ARM assembly optimized for the pipeline and cache. My ARM assembly is a little rusty, but it looks like they implement memset and bzero, the latter just calling memset with R1=0.
hoelle 16y ago
I'll offer the tip that even if you have a fast memset, you can and should avoid using it when possible. Seeing memset is usually a sign that someone is being lazy about watching the length of their buffers and/or verifying their copies aren't off-by-one.
- scott_s 16y ago
  If I understand you correctly, you think programmers should say: int i; for (i = 0; i < SIZE; ++i) { buffer[i] = 0; } Instead of: memset(buffer, 0, SIZE) Because it indicates better buffer management.
  - np3000 16y ago
    it should be memset(buffer,0,SIZE*sizeof(int))
    - scott_s 16y ago
      Only if it's a buffer of ints. I had assumed it was buffer of unstructured memory, which would be chars and of 1 byte each.
  - prodigal_erik 16y ago
    I took it as saying you should remember how much of the buffer you have actually used. If you only read what you write, it doesn't matter whether the rest of the buffer is filled with \0 or not, so you can skip the memset.
  - SamReidHughes 16y ago
    If I understand hoelle's point, it is that you shouldn't need to fill the buffer with a constant value in the first place. Why do people do it? The only time you generally need to prefill something is if you're using some algorithm whose initial state includes a prefilled array. It's hard to find a place where a byte array needs to be memset. If you need an array zeroed on first use, why didn't you use calloc? The only reason memset has for existing is when you need to reinitialize an existing array to zero. If things are so tight that you're wiping out an existing array and reusing it, which usually involves being deliberately less abstract than you'd naturally be, then, well, that's a pretty unusual situation. (While we're on memset, I'd like to point out that the weirdest thing is that while memset initializes value byte by byte, the places where you do need a prefilled array are always places where the array is an array of larger values.)
    - scott_s 16y ago
      Sometimes you manage your own memory, so you can't use calloc. Sometimes you're zeroing out stack allocated memory, such as the common practice when doing socket programming in C. Setting memory you own to a known value is just good, defensive programming. If I screw up - and in C, you're going to screw up - it's good to see a known value rather than unknown values.
ars 16y ago
How would you write this function? Fully portable, so no ASM.
- tptacek 16y ago
  You'd unroll the loop. But knowing the average workload for memset(), it probably wouldn't be a perceptible win.
  - ars 16y ago
    With todays CPU, particularly with branch prediction, and cache, loop unrolling is not always better. In fact I bet the performance would be worse, especially because you have to worry about setting areas of memory that are not a multiple of the loop unroll size. (I guess you could use duff's device.) I actually tested it while ignoring that, and the unrolled version took 34.551 seconds vs 34.239 for the regular version (but those number are meaningless since the variation in time between runs is greater than the difference in runtime between versions). And see: http://lkml.indiana.edu/hypermail/linux/kernel/0008.2/0171.html http://lkml.indiana.edu/hypermail/linux/kernel/0008.2/0171.h... - loop unwinding is not worth it anymore. So I ask you again pkaler: how would you speed this up?
    - sshumaker 16y ago
      I would imagine writing the native register size bytes per iteration would be a win, with a little cleanup for the remaining bytes. For a 32-bit architecture, you'd typically be doing 1/4 the iterations.
      - JoeAltmaier 16y ago
        Far more involved than that. There are alignment issues. Its several machine cycles faster to do aligned store of a large scalar e.g. 32-bit. So a responsible implementation would do a head check for alignment, store 1,2 or 3 bytes efficiently, then do aligned stores of 32-bit values (or 64-bit or whatever native size is appropriate), then a tail check for the small change. OR better yet switch(p & 3) and handle each case with unrolled code.
__david__ 16y ago
Because in boot code you generally don't care about speed, but size is a very important factor. I've personally had to rewrite standard library functions to be intentionally small and stupid just so a piece of boot code could fit into ROM. It's not fun, but there is a certain satisfaction when you rewrite putchar and think, I just saved 10k of code!
- signa11 16y ago
  > Because in boot code you generally don't care about speed, but size is a very important factor. why can't you have a '#ifdef PREFER_SIZE_OVER_SPEED' or something similar ?
  - __david__ 16y ago
    Practicality. Generally your stdlib is part of your cross compiler install. So now you'd need 2 versions of your stdlib--the small version and the speedy version. So now you aren't using -lc (which is usually built-in to the linker) foro your boot code but you are for your regular firmware. Now your makefile is more complex. And you are running a modified std library so it's a pain to upgrade. Blah blah blah the list goes on. Of course you could do all that, but it's so much easier to just override the 5 functions you actually use in your code. Because of the way linkers work and the way standard libraries are designed, if you define your own version of a library function then the linker won't pull in the library version--effectively choosing your local version over the one in the library. That keeps the standard library clean of patches and keeps the small, tight code near the project that actually needs it.
    - JoeAltmaier 16y ago
      Compilers have long ago memorized the code for memset (and memcopy and ...) and substitute optimized algorithms. As part of faking their benchmark stats for marketing purposes. So no worries, this code should result in kick-butt optimized assembler. Except for the obvious bug.
      - 16y ago
dfox 16y ago
Don't underestimate the compiler optimizations. GCC 4.3.1 on i386 with -O3 generates pretty involved optimized code that actually stores whole aligned 32bit words. (and I strongly suspect that this generated code is faster than rep stosb).

by pkaler 16y ago

neilc 16y ago

Given that it is in "platform/bootable/bootloader/legacy", I'm not sure there is much point getting all worked up about performance -- presumably something much more efficient would be used for the vast majority of cases.

joezydeco 16y ago
I haven't updated my source tree in a long time, but the ARM devices were using bionic/libc/arch-arm/bionic/memset.S. This is pure ARM assembly optimized for the pipeline and cache. My ARM assembly is a little rusty, but it looks like they implement memset and bzero, the latter just calling memset with R1=0.

hoelle 16y ago

I'll offer the tip that even if you have a fast memset, you can and should avoid using it when possible. Seeing memset is usually a sign that someone is being lazy about watching the length of their buffers and/or verifying their copies aren't off-by-one.

scott_s 16y ago
If I understand you correctly, you think programmers should say: int i; for (i = 0; i < SIZE; ++i) { buffer[i] = 0; } Instead of: memset(buffer, 0, SIZE) Because it indicates better buffer management.
- np3000 16y ago
  it should be memset(buffer,0,SIZE*sizeof(int))
  - scott_s 16y ago
    Only if it's a buffer of ints. I had assumed it was buffer of unstructured memory, which would be chars and of 1 byte each.
- prodigal_erik 16y ago
  I took it as saying you should remember how much of the buffer you have actually used. If you only read what you write, it doesn't matter whether the rest of the buffer is filled with \0 or not, so you can skip the memset.
- SamReidHughes 16y ago
  If I understand hoelle's point, it is that you shouldn't need to fill the buffer with a constant value in the first place. Why do people do it? The only time you generally need to prefill something is if you're using some algorithm whose initial state includes a prefilled array. It's hard to find a place where a byte array needs to be memset. If you need an array zeroed on first use, why didn't you use calloc? The only reason memset has for existing is when you need to reinitialize an existing array to zero. If things are so tight that you're wiping out an existing array and reusing it, which usually involves being deliberately less abstract than you'd naturally be, then, well, that's a pretty unusual situation. (While we're on memset, I'd like to point out that the weirdest thing is that while memset initializes value byte by byte, the places where you do need a prefilled array are always places where the array is an array of larger values.)
  - scott_s 16y ago
    Sometimes you manage your own memory, so you can't use calloc. Sometimes you're zeroing out stack allocated memory, such as the common practice when doing socket programming in C. Setting memory you own to a known value is just good, defensive programming. If I screw up - and in C, you're going to screw up - it's good to see a known value rather than unknown values.

ars 16y ago

How would you write this function? Fully portable, so no ASM.

tptacek 16y ago
You'd unroll the loop. But knowing the average workload for memset(), it probably wouldn't be a perceptible win.
- ars 16y ago
  With todays CPU, particularly with branch prediction, and cache, loop unrolling is not always better. In fact I bet the performance would be worse, especially because you have to worry about setting areas of memory that are not a multiple of the loop unroll size. (I guess you could use duff's device.) I actually tested it while ignoring that, and the unrolled version took 34.551 seconds vs 34.239 for the regular version (but those number are meaningless since the variation in time between runs is greater than the difference in runtime between versions). And see: http://lkml.indiana.edu/hypermail/linux/kernel/0008.2/0171.html http://lkml.indiana.edu/hypermail/linux/kernel/0008.2/0171.h... - loop unwinding is not worth it anymore. So I ask you again pkaler: how would you speed this up?
  - sshumaker 16y ago
    I would imagine writing the native register size bytes per iteration would be a win, with a little cleanup for the remaining bytes. For a 32-bit architecture, you'd typically be doing 1/4 the iterations.
    - JoeAltmaier 16y ago
      Far more involved than that. There are alignment issues. Its several machine cycles faster to do aligned store of a large scalar e.g. 32-bit. So a responsible implementation would do a head check for alignment, store 1,2 or 3 bytes efficiently, then do aligned stores of 32-bit values (or 64-bit or whatever native size is appropriate), then a tail check for the small change. OR better yet switch(p & 3) and handle each case with unrolled code.

__david__ 16y ago

Because in boot code you generally don't care about speed, but size is a very important factor. I've personally had to rewrite standard library functions to be intentionally small and stupid just so a piece of boot code could fit into ROM. It's not fun, but there is a certain satisfaction when you rewrite putchar and think, I just saved 10k of code!

signa11 16y ago
> Because in boot code you generally don't care about speed, but size is a very important factor. why can't you have a '#ifdef PREFER_SIZE_OVER_SPEED' or something similar ?
- __david__ 16y ago
  Practicality. Generally your stdlib is part of your cross compiler install. So now you'd need 2 versions of your stdlib--the small version and the speedy version. So now you aren't using -lc (which is usually built-in to the linker) foro your boot code but you are for your regular firmware. Now your makefile is more complex. And you are running a modified std library so it's a pain to upgrade. Blah blah blah the list goes on. Of course you could do all that, but it's so much easier to just override the 5 functions you actually use in your code. Because of the way linkers work and the way standard libraries are designed, if you define your own version of a library function then the linker won't pull in the library version--effectively choosing your local version over the one in the library. That keeps the standard library clean of patches and keeps the small, tight code near the project that actually needs it.
  - JoeAltmaier 16y ago
    Compilers have long ago memorized the code for memset (and memcopy and ...) and substitute optimized algorithms. As part of faking their benchmark stats for marketing purposes. So no worries, this code should result in kick-butt optimized assembler. Except for the obvious bug.
    - 16y ago

dfox 16y ago

Don't underestimate the compiler optimizations. GCC 4.3.1 on i386 with -O3 generates pretty involved optimized code that actually stores whole aligned 32bit words. (and I strongly suspect that this generated code is faster than rep stosb).