Suppose the bits of a computer word are partitioned into d disjoint sets, each of which is used to represent one of a d-tuple of cartesian indices into d-dimensional space. Then, regardless of the partition, simple group operations and comparisons can be implemented for each index on a conventional processor in a sequence of two or three register operations.
These indexings allow any blocked algorithm from linear algebra to use some non-standard matrix orderings that increase locality and enhance their performance. The underlying implementations were designed for alternating bit postitions to index Morton-ordered matrices, but they apply, as well, to any bit partitioning. A hybrid ordering of the elements of a matrix becomes possible, therefore, with row-/column-major ordering within cache-sized blocks and Morton ordering of those blocks, themselves. So, one can enjoy the temporal locality of nested blocks, as well as compiler optimizations on row- or column-major ordering in base blocks.
dilated integers, Morton order, quadtrees, compilers, index arithmetic
Fast additions on masked integers. SIGPLAN Notices, 41(5):39–45, May 2006. ISSN 0362-1340. doi: 10.1145/1149982.1149987.
and .@article{adams2006additions, author = {Adams, Michael D. and Wise, David S.}, title = {Fast additions on masked integers}, journal = {SIGPLAN Notices}, pages = {39--45}, year = {2006}, volume = {41}, number = {5}, address = {New York, NY, USA}, month = may, publisher = {ACM}, issn = {0362-1340}, doi = {10.1145/1149982.1149987}, }