I've been using this (awesome) library for generating Hilbert locations in building a map tiling engine. As the README states, for every zoom, the Hilbert curve rotates. A core property of the Hilbert curve is that relative position of items in the curve is maintained as the zoom changes. For example, this property should hold:

lower_zoom_hilbert = hilbert / (4^n) * (4^n-1)

Or more nicely:

lower_zoom_hilbert = hilbert >> 2

Because the rotation happens, these nice properties do not apply. I instead have to calculate a Hilbert location at a higher zoom and shift down for a lower zoom tile.

Is it possible to tweak the LUT so that this rotation does not happen?

z3 x4 y3 h31 z2 x2 y1 h13 z1 x1 y0 h1

Here we are with a tile at zoom 1. The hilbert location resolves to 1.

At zoom 2, the hilbert location resolves to 13 due to the rotation.

If I were to sort geographic data by their Hilbert location at one zoom, the locality will change for another, negating the static quadtree.

And then one more zoom in, and the direction of the preceding tile comes from the north.

There is a compiler intrinsic (and, I believe, also machine instruction) that counts how many zeros there are in the beginning of a given number. Using this, we can get rid of the order parametre, as follows:

1. Examine how many leading zeros x and y have
2. Select the smaller of those two (which is equivalent to (x|y).leading_zeros())
3. Round it down to an even number if it is odd (equivalent to a & !1 interpreted as the amount of useless bits)
4. Subtract it from the total amount of bits of each coordinate (32 in this case, interpreted as the amount of useful bits) and tada! you have the ideal number for the order parametre. No panics, no asserts, no nothing.

All that remains to be seen is whether this causes a slow-down, but given that the asserts are gone I'd wager that its speed has at worst remained the same.

1. Could you also include the lindel crate in the benchmarks you produce? Mr Chernoch's code has some… inefficiencies, let's say, which I took upon myself to correct. I don't think it'll come anywhere remotely close to your own speed, but I also suspect it'll at least fall within the same ball-park as the other crates.
2. One of the parametres to your functions is the so-called “order” of the Hilbert curve. Correct me if I'm wrong: I think that in your specific case all that matters is whether the order is an even or odd number. Is this indeed what's happening?
3. Do you have any idea if the tricks you used here can be generalised for arbitrary dimensions? I suspect that generalising them to eg u8s or u16s would be trivial, but the part about the arbitrary dimensions will take a bit more thought methinks.

Thanks in advance!

OK, so this was way more difficult than I thought, and the code's become a bit uglier as a result. Nonetheless, the functions now ought to function not just for u32s as before but also for u8s, u16s and u64s.

Admittedly, I'd like it to be refactored at some point so the code can become cleaner. For now, however, this ought to suffice. In the meantime I'll try to think if there are other optimisations we can perform.

Oh, and also: Seeing as the LUTs for each function were only being used within that one function, I took the liberty of moving them inside those functions.

num-traits v0.2.0, which fast-hilbert depends on, doesn't support impl PrimInt for u128 but fast-hilbert requires it.

This caused a compilation error:

| error[E0277]: the trait bound `u128: PrimInt` is not satisfied
|   --> /root/.cargo/registry/src/github.com-1ecc6299db9ec823/fast_hilbert-1.0.0/src/lib.rs:59:16
|    |
| 59 |     type Key = u128;
|    |                ^^^^ the trait `PrimInt` is not implemented for `u128`
|    |
|    = help: the following other types implement trait `PrimInt`:
|              i16
|              i32
|              i64
|              i8
|              isize
|              u16
|              u32
|              u64
|            and 2 others
| note: required by a bound in `Unsigned::Key`

I'll send a PR to fix this! :rocket:

How hard would it be to get the performance gains of fast_hilbert, but also be able to create Xian Liu's variants?

https://www.sciencedirect.com/science/article/abs/pii/S0096300302008081?via%3Dihub

Looks like hilbert_2d does this.

https://crates.io/crates/hilbert_2d

I wonder if the variants provide significant performance differences regarding the use of the curve as a spatial index?

I thought I'd try to figure out a way to get rid of the state parametre in both the LUT's index and the results it outputs. I succeeded in achieving that, but to my astonishment it ended up consistently ~50% slower! I tried optimising things further here and there, but no consistent result came up. Here is the main.rs file that explains how I did all those things; in the lib.rs file you'll see the actual methods I used.

That said…

You said in your benchmarks that fast_hilbert is around 2-2.5 times faster than other comparable methods. My own benchmarks show the improvement to be on the order of 8-10 times faster! I strongly suspect that our benchmarks lead to different results. Thus, if this seems interesting to you, feel free to experiment as well and see; otherwise, just close the issue.

PS: The main reason I ultimately decided to show you the work I did is because I think that this will help illuminate the way to generalise to other dimensions.