6 ms·
"This is the story of a clever trick that's been around for at least 35 years, in which array values can be left uninitialized and then read during normal
by kcbanner 4y ago
"This is the story of a clever trick that's been around for at least 35 years, in which array values can be left uninitialized and then read during normal operations, yet the code behaves correctly no matter what garbage is sitting in the array. Like the best programming tricks, this one is the right tool for the job in certain situations. The sleaziness of uninitialized data access is offset by performance improvements: some important operations change from linear to constant time."
https://research.swtch.com/sparse https://research.swtch.com/sparse
- djmips 4y agoI've used this type of data structure in the past for things like managing sprite DMA on old consoles. It's very friendly to old systems with simple memory access patterns.
- decebalus1 4y agoI remember this from Programming Pearls and I was going to post about it after reading the comments. Great stuff.
- once_inc 4y agoRequires numbers inserted to be unsigned, and to have a maximum value within reason, and doubles memory usage. Very nifty trick though!
- 1024core 4y agoI was going to mention Sparse Arrays, thanks for mentioning it. One of my favorite data structures.
- Tao3300 4y ago> The sleaziness of uninitialized data access That's the perfect word for this kind of thing. It's not wrong, but it's sleazy alright.