Timon Gehr:
As far as I can see, this just gets rid of a handful bitwise
and machine instructions and in return at least doubles the
address space requirements, also taking up cache-space (for
virtually indexed caches.)
Does this actually improve performance?
I have not tried it (that linked code on Rosettacode doesn't have
that "optimization"). When you try to create a data structure
some benchmarking is required.
Regarding the memory requirements, that circular queue doesn't
hold the items, only pointers to chunks of items (one chunk is
like 2^16 bytes or 2^20 bytes long), so usually it uses only some
kilobytes of memory. So wasting a bit of memory here is OK.
Bye,
bearophile
