Using Uninitialized Memory for Fun and Profit (2008)

http://research.swtch.com/sparse

by frontsideair • 12 years ago

46 17 12 years ago

research.swtch.com

Due to multilevel caches I doubt this would be so applicable to modern systems - the index-set representation takes several times more memory and naturally requires lots of random accesses, which are bad for caches. In some ways, it's no longer a time-space tradeoff: smaller is faster.

Also, initialising the space doesn't take so long; REP STOS on x86 is fast since it can write an entire cache line at once: http://ptspts.blogspot.ca/2014/10/on-speed-of-memset.html

prestonbriggs3• 12 years ago

I'll bet it's still faster in plenty of circumstances. It's hard to beat superior asymptotic complexity.

frozenport• 12 years ago

The 'magic' here is that you can quickly iterate over the data because it lives in 'dense'. In dense cases 'm'='n' and we loose. The apparent faster clear performance is because the length ('n') is stored as an auxiliary value, which is not unique to this scheme. As pointed out before, the extra logic will break vectorization and result in poor performance.

IsTom2• 12 years ago

It's true if a reasonable part of data can fit into cache. What if you've got a 2 billion subset of 64-bit integers?

prestonbriggs3• 12 years ago

If your universe has 2^64 elements, you don't want to use bit vectors or this scheme due to giant memory consumption. Instead, you'll probably want to use a hash table.

One data structure can't be the best for every situation. It's why they pay engineers the big ducks [sic].

gizmo6862• 12 years ago

Python uses a similar trick in its internal allocater (pymalloc) [1]. Given a memory address, pymalloc determines if it controls it by computing what would be the base of the arena containing said address. It then finds the index of the arena (or trash) at a constant offset from the base. It then uses the index to check a vector of all the arenas that it controls.

[1]http://svn.python.org/projects/python/trunk/Misc/README.valg...

blt• 12 years ago

Ahhhh, I love hacks like this :) But it is super branchy; I would definitely profile before assuming it's an improvement.

im3w1l• 12 years ago

Reading from uninitialized memory in C seems to be a bad idea:

http://blog.frama-c.com/index.php?post/2013/03/13/indetermin...

crispweed3• 12 years ago

I didn't read all that, but it seems like the issue there is that, if the compiler sees you are reading from uninitialised memory, then it can effectively 'choose' a value for the contents of that memory to suit it's optimisation purposes. Is that right?

If so, then this isn't actually a problem in the case of sparse sets. With sparse sets we don't care what is in the uninitialised memory and if the compiler wants to get tricky and choose values for this memory (which I don't think actually applies in this context) that doesn't change the correctness of the data structure..

marvy• 12 years ago

If you read it, you'll see that things are much worse than that.

gizmo6862• 12 years ago

You should be able to avoid those issue if you use a volotile variable.

deckar01• 12 years ago

“Xoring an uninitialized variable with whatever other source of entropy you already have cannot hurt”, the conventional thinking goes. Conventional thinking is wrong. Your typical modern compiler deletes the code that gathers the original entropy, since it is only going to be xored with an uninitialized variable.

The sparse array in the OP can't be optimized in this way at compile time.

IsTom2• 12 years ago

It only concerns automatic objects though, right?

crispweed3• 12 years ago

Something in between traditional bit vectors and sparse sets is described here:

http://upcoder.com/9/fast-resettable-flag-vector/

This is designed for a fast clear, but doesn't actually have constant time clear, it's just O(n) clear with very small (amortized) constant. It's a bit more cache friendly, though, I think, and gave us some nice speedups in practice.

mannykannot• 12 years ago

I think I have seen this method used in a data structure called something like a 'B.* set' or 'B.* index', but I can't remember the exact name. Does anyone have a clue as to what I am (mis)remembering?

Update: I remembered that the algorithm had something to do with checking if an item is not in a set, which quickly led me to Bloom Filter - not particularly similar, as it turns out.

Using Uninitialized Memory for Fun and Profit (2008)

Related Stories