standard ranges

[Roman D. Boiko]

On Thursday, 28 June 2012 at 14:34:03 UTC, Andrei Alexandrescu 
wrote:
> Well of course I've exaggerated a bit. My point is that 
> mentioning "200 ns!!!" sounds to the uninformed ear as good as 
> "2000 ns" or "20 ns", i.e. "an amount of time so short by human 
> scale, it must mean fast". You need to compare e.g. against 
> random access in an array etc.
>
> Andrei

I have no benchmarks for plain array access on the same machine 
and compiler that authors used. However, it looks like two cache 
misses happen at most. If that is true, we may charge 100 ns each 
memory access + computation. I would claim that from those most 
time takes memory access, since the same algorithms take 35-50 ns 
for smaller arrays (up to 4Mbits which is about 512KB), but I'm 
not sure that my conclusions are definitely true.

Also, I made a mistake in another post. I should have said that 
it is possible to address arrays of up to 2^64 code units, but 
benchmarks are provided for data sizes in bits (i.e., up to 
1GBit).

Asymptotically algorithms should require slightly smaller space 
overhead for bigger arrays: space complexity is O(N/logN). But 
memory address resolution may become slower. This is true for 
both Rank/Select algorithms and raw array access.

Again, please note that price is paid only once per code unit 
resolution (for Select) or code point calculation (for Rank). 
Subsequent nearby accesses should be very cheap.