Using Uninitialized Memory for Fun and Profit (2008) (opens in new tab)

(research.swtch.com)

46 pointsfrontsideair11y ago17 comments

17 comments

15 comments · 6 top-level

im3w1l11y ago· 5 in thread

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

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

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

marvy11y ago

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

1 more reply

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

gizmo68611y ago

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

IsTom11y ago

It only concerns automatic objects though, right?

userbinator11y ago· 4 in thread

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

prestonbriggs11y ago

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

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

1 more reply

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

prestonbriggs11y 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].

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

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

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

blt11y ago

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

j / k navigate · click thread line to collapse

17 comments

15 comments · 6 top-level

im3w1l11y ago· 5 in thread

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

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

crispweed11y ago

marvy11y ago

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

1 more reply

deckar0111y ago

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

gizmo68611y ago

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

IsTom11y ago

It only concerns automatic objects though, right?

userbinator11y ago· 4 in thread

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

prestonbriggs11y ago

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

frozenport11y ago

1 more reply

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

prestonbriggs11y 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].

gizmo68611y ago

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

crispweed11y ago

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

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

mannykannot11y ago

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.

blt11y ago

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

j / k navigate · click thread line to collapse