Taichi: Document refine_coordinate

[yuanming-hu]

Per the request in #593

[k-ye]

Actually, I think I figured out what has confused me. I hope my example could help explain the process:

x = ti.var(ti.i32)
ti.root.dense(ti.i, 4).bitmasked().dense(ti.i, 8).place(x)

@ti.kernel
def foo():
  for i in x:
    x[i] = 42

foo()

Here's the relevant fields for each SNode of its index 0:

| snode | size | num_bits | mask | acc_offset | start |
|-------|------|----------|------|-----------|-------|
| S0 | 1 | 1 | 0x1 | 0 | 5 |
| S1 | 4 | 2 | 0x3 | 0 | 3 |
| S2 | 8 | 3 | 0x7 | 0 | 0 |

For a concrete example where the input linear index l=17, if I'm following the flow correctly:

https://github.com/taichi-dev/taichi/blob/6577ad3977d8bc3aebfc6ba366fa50ea1315a99d/taichi/struct/struct_llvm.cpp#L110-L122

Then during element_listgen(), this should be its intermediate results

| snode | l | addition | in | out |
|-------|---|------------------------------|----|----------------|
| S0 | 0 | ((l >> 0) & 0x1) << 5 = 0 | 0 | 0 or 0 = 0 |
| S1 | 2 | ((l >> 0) & 0x3) << 3 = 16 | 2 | 2 or 16 = 16 |
| S2 | 1 | ((l >> 0) & 0x7) << 0 = 1 | 16 | 16 or 1 = 17 |

What I went wrong before was that, in each parent -> child listgen, I used the same l = 17. As a result, the final output I got was 41 instead of 17...

[yuanming-hu]

I think your understanding now is mostly correct, excapt for a few numbers in the table, updated below:

| snode | size | num_bits | mask | acc_offset | start |
|-------|------|----------|------|-----------|-------|
| S0_root | 1 | 0 | 0x0 | 0 | 5 |
| S1_dense | 4 | 2 | 0x3 | 0 | 3 |
| S2_dense | 8 | 3 | 0x7 | 0 | 0 |

| snode | l | addition | in | out |
|-------|---|------------------------------|----|----------------|
| S0 | 0 | ((l >> 5) & 0x0) << 5 = 0 | 0 | 0 or 0 = 0 |
| S1 | 2 | ((l >> 3) & 0x3) << 3 = 16 | 0 | 0 or 16 = 16 |
| S2 | 1 | ((l >> 0) & 0x7) << 0 = 1 | 16 | 16 or 1 = 17 |

[k-ye]

btw, i believe they should all be ((l >> 0)... :)

[yuanming-hu]

btw, i believe they should all be ((l >> 0)... :)

Oh sorry. I didn't realize what l is in the second table (2nd column) so I assumed we are working on 17 throughout this process....

[k-ye]

Oh sorry. I didn't realize what l is in the second table (2nd column) so I assumed we are working on 17 throughout this process....

My bad, I meant to use 17 as the 17-th leaf element of x.

The l in the table is actually the third argument of the refine coordinates function:
https://github.com/taichi-dev/taichi/blob/6577ad3977d8bc3aebfc6ba366fa50ea1315a99d/taichi/struct/struct_llvm.cpp#L107

[github-actions[bot]]

Warning: The issue has been out-of-update for 50 days, marking stale.