Top all-time · #3672
Attractive Chaos
Personal blog · attractivechaos.wordpress.comprogrammingsystems
Attractive Chaos is a personal blog at attractivechaos.wordpress.com about programming and systems. Since 2008, 21 different Hacker News readers have linked it 33 times, most often “Advanced techniques to implement fast hash tables”. The last post was in 2020, but the archive is still widely read.
Too few sampled comments (17) to say how often HN recommends it.?
Why HN links it
HN readers link this blog for its performance benchmarks in C and other languages: hash table comparisons, khash, matrix multiplication, LuaJIT and D speed, and a Sudoku solver comparison.
Summarised by Claude from a sample of 17 HN comments that link here. Each comment is marked recommending, critical or neutral (citing without judging); how this works.
Just another WordPress.com weblog
Most-linked posts?
- Advanced techniques to implement fast hash tables4 people · 4 mentions · first linked 2018-10-01
- Optimizing matrix multiplication in C3 people · 3 mentions · first linked 2016-08-28
- Comparison of Hash Table Libraries2 people · 2 mentions · first linked 2008-09-23
- Performance of Rust and Dart in Sudoku Solving2 people · 2 mentions · first linked 2013-04-06
What Hacker News says?
> Yes, but you are trading amazing performance in the average case against awful performance in the degenerate case. Poor hash functions or adversarial input could cause congestion in parts of the hash table. It is not just me. As I said, most high-performance hash tables these days (absl, F14, and all robin hood implementations) use linear probing. Providing a proper default hash function avoids most worse cases in…
Comment linking /2018/10/01/advanced-techniques-to-implement-fast-hash-tables/
on “How to implement a hash table in C”Submitted Advanced techniques to implement fast hash tables as a story · 166 points
HN discussionI wrote a blog post [1] on this a couple of years ago. This is a quite old technique [2] but was not widely used until recently. I was surprised that I hadn't found this earlier. [1] https://attractivechaos.wordpress.com/2019/12/28/deletion-fr... [2] https://en.wikipedia.org/wiki/Linear_probing#Deletion
Comment linking /2019/12/28/deletion-from-hash-tables-without-tombstones/
on “How to implement a hash table in C”Submitted Performance of Rust and Dart in Sudoku Solving as a story · 106 points
HN discussion> I wish this article was more opinionated. There's the Attractive Chaos blog for you: https://attractivechaos.wordpress.com/
Comment linking /
on “Implementing Hash Tables in C”Submitted Optimizing matrix multiplication in C as a story · 82 points
HN discussionNot really.. https://attractivechaos.wordpress.com/2013/04/06/performance...
Comment linking /2013/04/06/performance-of-rust-and-dart-in-sudoku-solving/
on “Firefox Nightly Gets New Baseline JIT Compiler”Submitted B-tree vs. Binary Search Tree as a story · 17 points
HN discussion> D went from a language that I remember back in 2015 was often promoted on places like reddit and here as a fresh alternative to C++ that was constantly evolving I wrote a blog post in 2012 about D [1]. In my personal experience, the high point of D was around 2008-2009. It was already declining in popularity in 2012, IMHO, due to intense clashes within the D community and the rise of Go, Rust and C++11 outside the…
Comment linking /2012/02/28/timeline-of-the-d-programming-language/
on “OpenD, a D language fork that is open to your contributions”Submitted Advanced techniques to implement fast hash tables (2018) as a story · 12 points
HN discussionI'm the author of Tdoku and maintainer of those benchmarks. If anyone has a well optimized DLX implementation I'd love to add it to the comparison. The few I've sampled from github were not competitive, but I have no idea how much effort when into them. This page from 2011 has some comparisons of backtracking and DLX solvers from that era, but it would be interesting to update: https://attractivechaos.wordpress.com/…
Comment linking /2011/06/19/an-incomplete-review-of-sudoku-solver-implementations/
on “Solving Every Sudoku Puzzle (2006)”Submitted Heap-free and lock-free parallelized C "for" loops as a story · 7 points
HN discussionAlso there is the header-only khash.h [3], complete with benchmarks: https://attractivechaos.wordpress.com/2008/08/28/comparison-... (Also provides kbtree.h, ksort.h, kstream.h, kvec.h) [3] https://attractivechaos.wordpress.com/programs/ Also there are the stb header-only libraries. There is a hash table implementation buried inside stb.h [4] https://github.com/nothings/stb
Comment linking /programs/
on “Write a hash table in C”Submitted Does packed struct hurt performance on x86_64? as a story · 7 points
HN discussion> Dart will not be 2x (or more) faster than JS. Why are you so sure of this? The people involved appear to be big believers that dynamic languages can be extremely performant provided they are designed with the VM in mind. LuaJit proves this out. A simple 1000x1000 matrix multiply in LuaJit is already 20x (not 2x!) faster than V8 and on par with C. http://attractivechaos.wordpress.com/2011/01/23/amazed-by-lu... http…
Comment linking /2011/01/23/amazed-by-luajit/
on “Brendan Eich on Ecma TC39, JavaScript.next, and Google Dash”Submitted Generic programming in C as a story · 7 points
HN discussionIn case anyone is looking for other novel ways to solve Sudoku. I wrote a CP language a while back that does pretty fast solving for the right kind of problem [1]. Folks might also find this Sudoku benchmarking blog post interesting [2], it includes links to solutions in a bunch of languages. 1) http://sabrlang.org/sudoku 2) http://attractivechaos.wordpress.com/2011/06/19/an-incomplet...
Comment linking /2011/06/19/an-incomplete-review-of-sudoku-solver-implementations
on “Logic Programming is Underrated”Submitted Revisiting hash table performance as a story · 3 points
HN discussionIn-memory B-tree is faster and uses less memory for small keys [1]. However, intrusive binary search trees (BSTs) are much more flexible and are the right choice for implementing kernels and malloc(). In addition, intrusive BSTs are often used to organize memory blocks scattered around. In-memory B-tree would lose its cache-efficiency in this case anyway. [1] https://attractivechaos.wordpress.com/2008/09/24/b-tree-v…
Comment linking /2008/09/24/b-tree-vs-binary-search-tree/
on “Tree.h in OpenBSD: dependency-free intrusive binary tree (2002)”Submitted Optimizing Matrix Multiplication as a story · 2 points
HN discussionI wrote a blog post in 2012 [1]. It gives my thoughts on the topic. In brief, D was quite popular around 2008 when no decent C++98 replacements existed. However, the D1-to-D2 transition, the Phobos/Tango (two core libraries) drama and the non-open-source components have ruined its reputation. I still love D but with the standardization of C++11 and the rise of Go and Rust, D won't have a chance again. [1]: https://a…
Comment linking /2012/02/28/timeline-of-the-d-programming-language/
on “Rebooting a 15 year-old game written in D – Part 1 Compiling”Submitted Advanced techniques to implement fast hash tables as a story · 2 points
HN discussionOK, a bit more here: https://attractivechaos.wordpress.com/2008/08/28/comparison-...
Comment linking /2008/08/28/comparison-of-hash-table-libraries/
on “Optimizing matrix multiplication in C”Submitted Comparison of Hash Table Libraries as a story · 2 points
HN discussionAs pointed out in the other comments on this thread, this benchmark benchmarks mostly standard RNG performance, not quality of the code generated by each compiler. Here you've got much more computationally intensive benchmark, showing that D is "as fast as C" like it could be said about Java: http://attractivechaos.wordpress.com/2013/04/06/performance-... It is close, but Java is just as close, too. Not a tremendous…
Comment linking /2013/04/06/performance-of-rust-and-dart-in-sudoku-solving/
on “Benchmarking level generation: Go, Rust, Haskell and D”Submitted The K8 JavaScript shell (2011) as a story · 1 points
HN discussionA really nice comparison of just C/C++ hash libraries is http://attractivechaos.wordpress.com/2008/08/28/comparison-o... Good discussion too. khash.h uses macros for C templating, but is quite fast.
Comment linking /2008/08/28/comparison-of-hash-table-libraries/
on “Benchmarking hash table implementations: C++, Java, LuaJIT”Submitted C API for reading remote files with kurl as a story · 1 points
HN discussionMaybe this? https://old.reddit.com/r/programming/comments/57gcjr/matrix_... https://attractivechaos.wordpress.com/2016/08/28/optimizing-...
Comment linking /2016/08/28/optimizing-matrix-multiplication/
on “Ask HN: Best low-level optimization tutorials?”Also an interesting graph from the two polls: http://attractivechaos.wordpress.com/2012/03/24/two-interest...
Comment linking /2012/03/24/two-interesting-polls-on-programming-languages/
on “Programming Languages sorted by Wilson Score Interval.”
