3 ms·

Sparse Sets (2021)

16 points by signa11 3y ago

pipo234 3y ago
Interesting Big-O time characteristics, but bit of a pity that addition, removal and membership check require 2 (random) memory accesses. Also, Big-O memory proportional to element type is a bit of a non-starter in many cases.
- j-pb 3y ago
  Isn't memory always proportional to element size, unless you just look at indexes and pretend that element storage is free?
pklausler 3y ago
Same data structure appears in Preston Briggs' 1992 PhD thesis (https://www.cs.utexas.edu/users/mckinley/380C/lecs/briggs-thesis-1992.pdf https://www.cs.utexas.edu/users/mckinley/380C/lecs/briggs-th...). I have used these fast sets many times over the years, but less often than before because they elicit valid but irrelevant warnings from Valgrind due to the (safe) use of uninitialized data.
arjvik 3y ago
This is slightly probabilistic. Say you're checking whether a byte is in a sparse set, then there's a 1/256 chance of a false positive. (That is, if you're not zeroing memory. If you are, you don't even need the dense array at all, can just store a sparse array of booleans.)
- bumbledraven 3y ago
  No. In order for the algorithm to report that a set with N elements contains an item x, it must find that both sparse[x] < N and dense[sparse[x]] = x; this cannot happen unless x is actually in the set, because dense[0...N-1] has been initialized during the insertion of the first N elements.
  - arjvik 3y ago
    I see, N is not capacity but number of elements inserted.
cbarrick 3y ago
The lookup method explicitly reads uninitialized memory. This is undefined behavior, right? How do you properly implement this method? I guess you should just initialize it to a sentinel value? But this breaks one of the guarantees presented in the intro...
- hansvm 3y ago
  Sane languages just let you read the memory. If you're using C or something, there are only problems if the compiler can prove the memory is uninitialized (either at comptime or via runtime checks it definitely does not insert). Otherwise, the only reasonable codegen is to return the value at that location in RAM. Just pragma the function doing the dirty work as noinline, and then optimizations can't cross that boundary and mess up your day.

Sparse Sets (2021)

16 points by signa11 3y ago

Interesting Big-O time characteristics, but bit of a pity that addition, removal and membership check require 2 (random) memory accesses. Also, Big-O memory proportional to element type is a bit of a non-starter in many cases.

j-pb 3y ago
Isn't memory always proportional to element size, unless you just look at indexes and pretend that element storage is free?

pklausler 3y ago

Same data structure appears in Preston Briggs' 1992 PhD thesis (https://www.cs.utexas.edu/users/mckinley/380C/lecs/briggs-thesis-1992.pdf https://www.cs.utexas.edu/users/mckinley/380C/lecs/briggs-th...). I have used these fast sets many times over the years, but less often than before because they elicit valid but irrelevant warnings from Valgrind due to the (safe) use of uninitialized data.

arjvik 3y ago

This is slightly probabilistic. Say you're checking whether a byte is in a sparse set, then there's a 1/256 chance of a false positive. (That is, if you're not zeroing memory. If you are, you don't even need the dense array at all, can just store a sparse array of booleans.)

bumbledraven 3y ago
No. In order for the algorithm to report that a set with N elements contains an item x, it must find that both sparse[x] < N and dense[sparse[x]] = x; this cannot happen unless x is actually in the set, because dense[0...N-1] has been initialized during the insertion of the first N elements.
- arjvik 3y ago
  I see, N is not capacity but number of elements inserted.

cbarrick 3y ago

The lookup method explicitly reads uninitialized memory. This is undefined behavior, right? How do you properly implement this method? I guess you should just initialize it to a sentinel value? But this breaks one of the guarantees presented in the intro...

hansvm 3y ago
Sane languages just let you read the memory. If you're using C or something, there are only problems if the compiler can prove the memory is uninitialized (either at comptime or via runtime checks it definitely does not insert). Otherwise, the only reasonable codegen is to return the value at that location in RAM. Just pragma the function doing the dirty work as noinline, and then optimizations can't cross that boundary and mess up your day.