Hacker News Reader

Comment by pkaler | Hacker News Reader

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/

View on HN

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!

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

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.

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.

Optimized for what? Speed? While I can picture that happening, it has been my experience that this is not the case. The memory squishing optimizations I'm talking about require dumping the assembly output and I've never seen my stupid memcpy() routine suddenly turn into optimized-for-speed code. I'd be pretty upset if that were to happen...

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.

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.

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).

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.

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.

it should be memset(buffer,0,SIZE*sizeof(int))

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.

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.

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.)

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.

Removing the memsets from the networking layer of one of my projects basically halved the frametime of that system (which was a bottleneck).

I'm all for defensive programming, but when you need to be fast, you'll just have to make sure it's correct.

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

You'd unroll the loop. But knowing the average workload for memset(), it probably wouldn't be a perceptible win.

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.h... - loop unwinding is not worth it anymore.

So I ask you again pkaler: how would you speed this up?

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.

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.

I would build it into the memory controller. Better: in the memory itself.

Many modern platforms contain some logic, that can be (ab)used to do memset() directly in hardware without processor involvement (ie. in parallel with other code). But this tends to require so much setup and IO overhead so it simply isn't worthwhile to do.

Integrating memset/bzero logic into memory array itself will increase it's price drastically (but in some special cases it is done, generally when memory array already contains some other expensive non-memory logic).

Reply on news.ycombinator.com