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.
