#Weighted Random Choice

1 messages · Page 1 of 1 (latest)

uncut rover
#

I put together a reasonable implementation of Vose's Alias Method -- when you have a set of weights you would like to use for a weighted random choice, and when you want to precompute a data structure for making many such choices. The stdlib is nice for one-offs (like for a one-off kmeans++ initialization), but drawing from the same distribution repeatedly is costly.

https://github.com/hmusgrave/zalias

GitHub
GitHub - hmusgrave/zalias: efficient repeated weighted random choice

efficient repeated weighted random choice. Contribute to hmusgrave/zalias development by creating an account on GitHub.

verbal siren
#

neat! the alias table is an underappreciated data structure

#

if you want to learn about more optimized alias table builds, you might be interested in taking a look at my implementation here (though it's sparsely commented): https://github.com/ashpil/moonshine/blob/trunk/engine/rendersystem/alias_table.zig
turns out one can do a ton of typically overlooked optimizations on even the O(n) vose algorithm that significantly improves performance. mainly:

  1. naive/kahan sum both super slow, turns out your typical SIMD sum (which you can get by enabling fast math) is almost as good as kahan in terms of precision, and much faster than naive in terms of performance
  2. one can actually do this without any intermediary temporary allocations, which will also increase cache coherency
uncut rover
#

  1. I'll admit I hadn't benchmarked yet, but articles by QuestDB indicated SIMD Kahan summation (which we're definitely not doing yet) is negligibly slower than SIMD ordinary summation. Since there are definitely problems where Kahan summation is significantly more accurate, I'd be curious to know if that marketing is actually just fluff.

  2. Neat!!!!!! I can't wait to read how you did that.

verbal siren
#
  1. I'll admit I hadn't benchmarked yet, but articles by QuestDB indicated SIMD Kahan summation (which we're definitely not doing yet) is negligibly slower than SIMD ordinary summation. Since there are definitely problems where Kahan summation is significantly more accurate, I'd be curious to know if that marketing is actually just fluff.
    I actually haven't looked into SIMD kahan, if they say it's better I'm inclined to believe them
uncut rover
#

@verbal siren Oh I see, that's nice. You re-use the output buffer as a linked list. Placing indices/weights adjacent in memory is probably a good call too (pretty sure having adjacent data won't be good for my use case though; I'll check).

With respect to SIMD kahan, the solution QuestDB took is just to maintain N kahan sums and horizontally add them. It's not strictly speaking the same, but it's pretty fast and pretty accurate. Since kahan doesn't have much CPU overhead and the problem is mostly memory bandwidth bound on modern hardware the performance/accuracy tradeoff looks pretty favorable with it for some problems. Here's the marketing material I had in mind: https://questdb.io/blog/2020/05/12/interesting-things-we-learned-about-sums/

Things we learned about sums | QuestDB

What we learned implementing Kahan and Neumaier compensated sum algorithms, benchmark and comparison with Clickhouse.