Timo Bingmann is a computer scientist who writes about algorithms, data structures, and tools, including Sound of Sorting and STX B+ tree.
HN links it for the Sound of Sorting visualization, the STX B+ tree, and the COBS index and NVMe access speed posts.
Here's how it was made: https://panthema.net/2013/sound-of-sorting/
It's history here on HN is intriguing, and a little sad. So many submissions, so little discussion. Do people feel that there's nothing to be said?
3 comments:
https://news.ycombinator.com/item?id=6829772
2 comments:
https://news.ycombinator.com/item?id=6819544
https://news.ycombinator.com/item?id=6536773
https://news.ycombinator.com/item?id=6138505
1 comment:
https://news.ycombinator.com/item?id=10768096
https://news.ycombinator.com/item?id=9385926
https://news.ycombinator.com/item?id=8805803
https://news.ycombinator.com/item?id=6140319
Many of the preceding comments were people just saying that there were lots of submissions, but no comments!
Even so, there are, indeed, so many submissions with no comments at…
I believe you could do this effectively with COBS (COmpact Bit Sliced signature index): https://panthema.net/2019/1008-COBS-A-Compact-Bit-Sliced-Signature-Index/
It's a pretty neat algorithm from a paper in 2019 for the application "to index k-mers of DNA samples or q-grams from text documents". You can take a collection of bloom filters built for documents and then combine them together to have a single filter that will tell you which docs it maps to. Like an inverted index meets a bloom filter.
I'm using it in a totally different domain for an upcoming release in InfluxDB (time series database).
There's also code online here: https://github.com/bingmann/cobs
Hi @jabberwcky! The plot refers to a B+tree implementation optimised for main-memory (https://panthema.net/2007/stx-btree/). We didn't show the performance for larger/smaller page sizes because in our machine they performed poorly. Indeed, you can see from the figure that the fastest B+tree configuration had page size set to 512 bytes. The one using 1024-byte pages is already much slower, that's why we didn't clutter the plot with page sizes larger than 1k ;)
Someone did test exactly that:
https://panthema.net/2019/0322-nvme-batched-block-access-speed/
From my experience as long as you can do that access multithreaded you won't really be penalized for random reads. Single threaded access I've seen as much as read performance halved (used fio for testing), but that didn't translate into multithreaded benchmarks
Nope that’s more like cache write speed. Single-threaded sequential access to RAM is typically more like 10-15GB/s for current server CPUs: https://panthema.net/2013/pmbw/results.html - it’s true that workstation machines tend to have somewhat higher sequential throughout compared to the server-heavy list at that URL, but it’s more like 20GB/s, not 50-60.
few sorting links with explanations and visualizations:
https://imgur.com/gallery/RM3wl
https://panthema.net/2013/sound-of-sorting/
https://www.creativeapplications.net/processing/sorting-visualisation-sortification-and-sonification-of-an-algorithm/