Top all-time · #1870
A Random Walk Through Geek-Space
Personal blog · sebastiansylvan.comprogramminggames
A Random Walk Through Geek-Space is a personal blog at sebastiansylvan.com about programming and games. Since 2013, 42 different Hacker News readers have linked it 48 times, most often “Robin Hood Hashing should be the default hash table implementation (2013)”. The last post was in 2022, but the archive is still widely read.
Most-linked posts?
- Robin Hood Hashing should be the default hash table implementation (2013)5 people · 5 mentions · first linked 2016-08-29
- The Perils of Future-Coding3 people · 3 mentions · first linked 2018-10-17
- Robin Hood hashing should be your default Hash Table implementation (2013)3 people · 3 mentions · first linked 2019-10-11
- Garbage collection thoughts3 people · 3 mentions · first linked 2013-05-28
- Why (most) High Level Languages Are Slow3 people · 3 mentions · first linked 2017-02-09
- Doing Garbage Collection Without Requiring Uniform Representation2 people · 2 mentions · first linked 2016-07-08
- Robin Hood Hashing should be your default Hash Table implementation2 people · 2 mentions · first linked 2013-07-26
- Brackets are awesome, don't use them2 people · 2 mentions · first linked 2024-09-29
- Naming Convention for Matrix Math2 people · 2 mentions · first linked 2017-07-28
What Hacker News says?
They are still very much required for games/real-time rendering :-) I hadn't heard ptex before, it's interesting stuff. Sounds like the reason it isn't in general usage for realtime stuff is the memory overhead: http://sebastiansylvan.com/post/casting-a-critical-eye-on-gp...
Comment linking /post/casting-a-critical-eye-on-gpu-ptex/
on “Spaceship Generator”Submitted Robin Hood Hashing should be the default hash table implementation (2013) as a story · 220 points
HN discussionHere is a blog post applying a similar idea to matrix math: https://www.sebastiansylvan.com/post/matrix_naming_conventio...
Comment linking /post/matrix_naming_convention/
on “Parse, Don’t Validate”Submitted Flags Are a Code Smell (2014) as a story · 58 points
HN discussion> generalized and future proof Reminds me of a blog post I read, https://www.sebastiansylvan.com/post/the-perils-of-future-co... At what point does it become over-engineering?
Comment linking /post/the-perils-of-future-coding/
on “Do We Worship Complexity?”Submitted Garbage collection thoughts as a story · 54 points
HN discussionHe also wrote a follow up article addressing performance issues surrounding probe size increasing when erasing elements. http://www.sebastiansylvan.com/post/more-on-robin-hood-hashi...
Comment linking /post/more-on-robin-hood-hashing-2/
on “Robin Hood Hashing should be the default hash table implementation (2013)”Submitted Why (most) High Level Languages Are Slow as a story · 34 points
HN discussion> or you would be comparing apples to oranges Do the other programs use that same hash table algorithm? http://www.sebastiansylvan.com/post/robin-hood-hashing-shoul...
Comment linking /post/robin-hood-hashing-should-be-your-default-hash-table-implementation/
on “New Rust hash table leads Benchmarks Game”Submitted Two Performance Walls Approaching (2009) as a story · 31 points
HN discussion> Issues with open addressing are issues like clustering if linear probing is used. Robin Hood hashing more or less solves that problem. > When we delete keys, we have to leave "tombstone" entries in their place, so that the linear probing can continue past them to find other items. Actually no. Even ignoring Robin Hood Hashing, you just swap a later element into place. idx = hash(value); delete(array[idx]); for(int…
Comment linking /post/robin-hood-hashing-should-be-your-default-hash-table-implementation/
on “Hash tables”Submitted Robin Hood Hashing should be your default Hash Table implementation as a story · 17 points
HN discussionSome resources which were on HN before about Robin-Hood hashing: About Robin-Hood hashing: http://www.sebastiansylvan.com/post/robin-hood-hashing-shoul... Rust's implementation of HashMap: http://cglab.ca/~abeinges/blah/robinhood-part-1/
Comment linking /post/robin-hood-hashing-should-be-your-default-hash-table-implementation/
on “Rust Standard Hash Table Could Go Quadratic”Submitted The Perils of Future-Coding as a story · 10 points
HN discussionI think people here seem to implicitly assume linked buckets, those are bad on modern architectures for several reasons. Look at (Hopscotch,) Robin Hood or Cuckoo Hashing for hashing with linear probing, high fill factor (~0.9) and _amortized_ O(1). I've seen a paper somewhere that proved Robin Hood worst-case O(log log n) afair. http://www.sebastiansylvan.com/post/robin-hood-hashing-shoul... https://en.m.wikipedia.…
Comment linking /post/robin-hood-hashing-should-be-your-default-hash-table-implementation/
on “Myths about Hash Tables”Submitted Robin Hood Hashing should be your default Hash Table implementation as a story · 6 points
HN discussionLinks would be good. And on that... Could you provide a link to heavy numerical operations - btw, ones that use native libraries don't count cause it ain't the C# implementation doing the work? As I've said there are some routines where C# performs fine but for heavy-weight modelling requiring intense arithmetic matrix/vector operations it is just too slow. What's more the benchmark for a single run does not always…
Comment linking /post/why-most-high-level-languages-are-slow/
on “Rust required to build Gecko”Submitted Brackets are awesome, don't use them as a story · 5 points
HN discussionI recommend Robin Hood open addressing scheme. It's particularly trivial to implement, and because it relies on linear probing, so it's memory-cache friendly. See more here: http://www.sebastiansylvan.com/post/robin-hood-hashing-shoul... Jeff Preshing has written many interesting blog posts about the subject. For example, see his blog post on Leapfrog Probing( http://preshing.com/20160314/leapfrog-probing/ )
Comment linking /post/robin-hood-hashing-should-be-your-default-hash-table-implementation/
on “Designing a fast hash table”Submitted Why (most) High Level Languages Are Slow as a story · 4 points
HN discussionIf you take the view that object references are options, then it's plain unsound to manipulate object references as though they weren't options! `NullPointerException` is just a dynamic plug on a static type safety hole. This blog post (I'm not the author) explains the issue (item 3) very well: http://www.sebastiansylvan.com/post/language-design-deal-bre...
Comment linking /post/language-design-deal-breakers/
on “Functional Programming Isn't the Answer (2014)”Submitted Garbage Collection Thoughts as a story · 4 points
HN discussionReminds me of point 3 in http://www.sebastiansylvan.com/post/language-design-deal-bre... : “You have to make sure that nullable pointers cannot be dereferenced . (...) Having every few statements potentially trigger a runtime crash is an expensive price to pay... for nothing! ” [emphasis in the original] Once you have proper non-nullable pointer types, `static_cast` is a single pointer bump once again.
Comment linking /post/language-design-deal-breakers/
on “A static_cast is not always just a pointer adjustment”Submitted Brackets are awesome, don't use them as a story · 3 points
HN discussionGoogle "classical inheritance harmful" and you'll find articles with plenty of code examples. The point of my article was not to bog the reader down in implementation details, but to communicate high-level concepts in rant-style prose. ;) Here's a bit of code, ranting against the same problems, but coming up with different solutions: http://berniesumption.com/software/inheritance-is-evil-and-m... Here's a nice quote…
Comment linking /2010/12/03/implementation-inheritance-considered-harmful/
on “The Two Pillars of JavaScript”Submitted The Perils of Future-Coding as a story · 3 points
HN discussion> What's the cost, probability and trade off between those possibilities? I read an old article that compared the various scenarios. https://www.sebastiansylvan.com/post/the-perils-of-future-co... TL;DR - it sides with YAGNI
Comment linking /post/the-perils-of-future-coding/
on “The Cost Yagni Was Never About – By Kent Beck”Submitted Flags Are a Code Smell (2014) as a story · 3 points
HN discussionI've not had any particular reason to specifically use this but I found Robin Hood Hashing to be quite an interesting concept. It improves performance by essentially reducing the distance from the key to its matching key-value pair. Advantages listed from [3]: - The number and variance of look-ups are reduced - Searches can be ended early, since 'hits' are found much quicker - The flat array structure eliminates nee…
Comment linking /post/more-on-robin-hood-hashing-2/
on “Ask HN: What is your favourite data structure and why?”Submitted Naming Convention for Matrix Math as a story · 3 points
HN discussion
