在github上提了个issue, 不过大概率是凉了. 也没人发表看法. 这里看看有没有大佬有什么看法. 不过这里的排版不怎么样, 贴个git的地址吧. https://github.com/taichi-dev/taichi/issues/4381
although the data of Sparse Spatial Data Struct has been sparse, but it still is dense for different purpose , if we want to find some the couples of data that satisfy some condition. Or we want to process a part of datas of field for some specific purpose . below is current code.
tp = ti.types.struct(...)
f = tp.field(shape=(M,N))
@ti.kernel
def kernel():
for i,j in f:
for ri, rj in f:
if compare(f[i,j], f[ri,rj]):
#do some thing
....
it is simple but it is a O(n^2) algorithm, and it must create n thread, n is size of field. and it has the half of compute being redundant at least. if only a couple of data satisfy condition, then 99% of compute is redundant. And if we find a triple data that satisfy some condition, this code will is below:
...
for i,j in f:
for i1, j1 in f:
for i2, j2 in f:
if compare(f[i,j], f[i1,j1], f[i2, j2]):
#do some thing
....
...
it is O(n^3) and the 5/6 compute is redundant at least. if we find m data, it only has 1/m! of compute is valid at most .
Can we do better ? yes, it is a universal problem that comparison each other among n datas. so we can abstract it to a funtion, we name it as ti.involvere. then we give a condition needing satisfied to finish it. then we will get a mask that is special optimized for access parted data. below is new code:
tp = ti.types.struct(...)
f = tp.field(shape=(M,N))
mask = f.mask()
@ti.func
def discriminant(a, b):
if ...
#do some thing
return a # or b or a,b or None
@ti.kernel
def kernel():
for i,j in f:
ti.involvere(discriminant, mask)
for i,j in mask:
...
the number of parameter of discriminant(a,b) rely on the number of referenced data. it is inconsequential that how to process a and b. our focus is what will be returned. obviously, it have four kinds return-value while 2 parameter.
now , we need to compile python to c++ to implement ti.involvere. unfortunately, i am not good at c++, so i write pseudo here.
#the number of parameter rely on python code.
def discriminant(any_type a, any_type b) -> int:
if ...
...
return 0
#the return value is only four kinds while 2 parameter.
#we use b0000,b0001,b0010,b0011 to stand for None, a,b,ab
class Involvere:
def __init__(discriminant, mask):
self.mask = mask
self.discriminant= discriminant
#get index of next WAIT_FOR_COMPARISON from mask, if arrive the end+1 of mask, return None.
def next():
self.next_pointer = self.mask.find(self.next_pointer)
return self.next_pointer
#here define how to select data for discriminant.
def volvere(int index_0):
self.next_pointer = index_0 # a anchor that indicating which data has been processed
index_1 = self.next()
#index_2 = self.next() if is not 2 data to participate in comparison,
#index_3 ...
while self.next_pointer:
index_of_obsolete = self.discriminant(self.mask.get_field_data(index_0),
self.mask.get_field_data(index_1))
#self.mask.get_field_data(index_2)
#self.mask. ...)
switch index_of_obsolete:
case 0: # no data is obloleted.
#if discriminant has 3 parameter, here is index_2, 4 parameter to index_3 ...
index_1 = self.next()
case index_of_obsolete & b0010:
self.mask[index_1] = OBSOLETE # define OBSOLETE 0
index_1 = self.next()
#case index_of_obsolete & b0100: # discriminant has 3 parameter
# self.mask[index_2] = OBSOLETE
# index_2 = self.next()
# ...
case index_of_obsolete & b0001: # if the first data is obsoleted, return
self.mask[index_0] = OBSOLETE
return
def kernel():
...
involvere = Involvere(discriminant, mask)
#i don't know taichi how to implement parallel execute, remaining the same is ok
threads = create_thread(field.i * field.j)
for t in threads:
#i don't know taichi how parallelly use the index of field.
#i assume t.i and t.i stand for i and j of f[i,j]
involvere.volvere(t.i * field.shape[1] + t.j) # see funtion code.
...
In addition, the Mask class has below ability:
1.it can be generated by field.mask() to extract active/deactive status.
2.several masks of the same field can be merged to a mask by AND, OR, NOT, XOR…
3.can access a field by mask of this field.