3 ms·
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 min
by ncmncm 7y ago
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.
- throwaway_pdp09 7y agoExcellent point that I'd completely missed.
- Hitton 7y agoExactly 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).
- ncmncm 7y agoYou 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.
- kevin_thibedeau 7y ago2^32 == 4GiB
- Hitton 7y ago>2^32 == 4GiB That's bytes, not bits.
- miloignis 7y ago2^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
- ncmncm 7y agoGood 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.
- hikarudo 7y agoEven 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.
- ncmncm 7y agoIt 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.
- nwallin 7y agoThe 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.