Hacker News Reader

Comment by ncmncm | Hacker News Reader

Why not just use an array of 2^32 bits -- a half gigabyte -- and leave off hashing altogether?

All it would cost is the excess runtime, which we should not mind giving up unless we smoke.

If necessary, you could have two or more. 256 of them would fit in 128G, which lots of servers have without even needing it all.

View on HN

The author elaborated in another post: it's also ipv6 addresses, ranges, cidr notation, and the data center id number. It's not as simple as just an ipv4 address.

IMHO this was critical information that muddled the article. I think most people who think critically about their data (ie, everyone who would be interested in the article) should have the same thought. I sure did.

Exactly what I thought as well. I don't know what you mean by excess runtime though, I don't think there would be any (compared to proposed solution).

You give up all the excess runtime you would have devoted to hashing, leaving only the time to fault in the page the bit indexes to.

The implication is that the original poster used hashing out of a preference for wasting time, speculated as an excuse to go out for a smoke.

Even better: use mmap to allocate a virtual huge array, which initially will use no memory at all, and let the OS allocate physical pages to it as needed.

It takes active effort to get all the pages faulted in at startup, and not lazily.

Some of us do that, to take the latency hit just the one time: MAP_POPULATE.

Excellent point that I'd completely missed.

2^32 == 4GiB

2^32 bytes is 4 GiB, but 2^32 bits is 512 MiB. In the GP's hypothetical array, I believe you would index (array[idx >> 3] >> (idx & 7)) != 0

Good point: they could store a whole byte, or a whole word, for each address, not just a bit, and still have lots of RAM left over.

>2^32 == 4GiB

That's bytes, not bits.

Reply on news.ycombinator.com