4 ms·
Using Uninitialized Memory for Fun and Profit
- Drbble 15y agoThis is also known as the "cave exploration" problem, (maybe involving dwarfs) which was blogged and linked from I think either here or Reddit. I have lost the link though, does anyone have it?
- dthunt 15y agoThat sounds too juicy to ignore. If you find it, please post it here!
- jrabone 15y agoThe example of sparse arrays is not quite "uninitialised memory", more like "stale pointers". I remember implementing Knuth's Algorithm X (http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color... - compressed PS file) for fun, and being horrified (as a good little C programmer) by the pointer abuse. The algorithm builds a 2 dimensional linked list structure which selectively covers columns by disconnecting half the pointers, and leaving the other half dangling so it can be reconnected later. Of course it all works beautifully, I'm just not sure that I'd want to have to debug some medium-quality engineers' implementation of it...
- jmah 15y agoEarlier discussion here: http://news.ycombinator.com/item?id=1156628 http://news.ycombinator.com/item?id=1156628
- antirez 15y agoThe lzf compression lib uses a similar trick as well to void spending time zeroing memory.
- rbanffy 15y agoAs a hardware engineer, I'd suggest zeroing page-sized blocks of memory through a hardware interface without hogging the external bus. But, of course, that misses the point of the article. ;-) To say nothing about forcing a redesign of many memory products.
- JoachimSchipper 15y agoNote that this is not strictly valid C: the compiler/runtime system is allowed to initialize uninitialized memory with so-called trap representations, which cause undefined behavior on access. Of course, it does work on pretty much every real computer.
- dthunt 15y agoThere's more here than zeroing memory. People writing fast, single-threaded network stuff may see immediate value w/r to poll(), or any other situation where you need a packed, easily update-able list of things.
- cbr 15y agoIf you're getting memory from the OS it's going to be initializing it for you, so no speedup. Otherwise you get memory as it was left by some other process, potentially leaking passwords or other sensitive information
- lloeki 15y agoInterestingly enough malloc(3) on Lucid Lynx box says: malloc() allocates size bytes and returns a pointer to the allocated memory. The memory is not cleared. whereas Lion says nothing particular about it So I wrote a quickie: #include <stdlib.h> #include <stdio.h> int main() { int m = 1024*1024; //1M int t = 1024*m; //total count: here 1G char *v = calloc(1, t*sizeof(char)); //total size: 1GB for(int i=0; i<t; i++) { if (v[i] != 0) { printf("%016u @%x %x\n", i, v+i, v[i]); } else if (i % (t/10) == 0) { printf("%016u @%x\n", i ,v+i); } } } Ran multiple times with various sizes including big enough sizes (t) to statistically cover a good deal of physical RAM, and the trigger never triggers. I notice though that on Mac OS X the program starts right on the spot, while there is always a constant delay on Lucid. Looks like one zeroes on demand (by chunks probably) whereas the other zeroes initially.
- petsos 15y agocalloc differs from malloc, as it clears the memory. From the Mac OS X man page: The calloc() function contiguously allocates enough space for count objects that are size bytes of memory each and returns a pointer to the allocated memory. The allocated memory is filled with bytes of value zero.
- lloeki 15y agoAh sorry, bad version copy/paste on my part. I actually used calloc at some point to compare behaviors in allocation time with malloc, but with malloc it still has zeros everywhere. Nice for security, but how would one proceed when really wanting pedal-to-the-metal performance?
- jonstewart 15y agoThe uninitialized memory aspect is a good hook for an article, but the real meat of this data structure is that you get O(1) insertion, O(1) test/lookup, _and_ an O(1) clear operation. I was using a bit vector in a similar application, but clearing the bit vector was taking some time (I had to clear it inside my main loop). Swapping in the sparse array gave me a nice performance bump, even though it used 64 times the memory.