fixed_power_val seems slow

[Jiacheng Pan]

Hello,

I came across this issue when trying to compute a map of `t -> t-n`, where point `t-n` means `n` steps away from point `t` in lexicographical order.

In particular, I have this domain set:
```
domain = isl.Set('{ [i0, i1, i2, i3, i4] : 0 <= i0 <= 1 and 0 <= i1 <= 15 and 0 <= i2 <= 1 and 0 <= i3 <= 1 and 0 <= i4 <= 1 }')
```

And it seems isl hangs with following code:
```
prev = domain.lex_gt_set(domain).lexmax()
result = prev.fixed_power_val(128)
```

I think I am computing `t -> t-n` by first constructing `t -> t-1` and then computing the power-n of it (here n = 128).
And this seems very slow (or actually hangs).
It seems reducing the power n to 32 is much faster, while it looks to take longer time starting from n=64.

But it is much faster (<1s) with following code:
```
next = domain.lex_lt_set(domain).lexmin()
result = next.fixed_power_val(128).reverse()
```

Is it expected? (I am using islpy 2022.2.1)
Also, if I am trying to get the map of  `t -> t-n`, am I using the correct / recommended way? (still trying to learn isl...)

Please let me know if there is anything unclear…

Thanks!

Best Regards,
Jiacheng


PS: my full test code:
```
import islpy as isl

domain = isl.Set('{ [i0, i1, i2, i3, i4] : 0 <= i0 <= 1 and 0 <= i1 <= 15 and 0 <= i2 <= 1 and 0 <= i3 <= 1 and 0 <= i4 <= 1 }')

n = 128

next = domain.lex_lt_set(domain).lexmin()
result1 = next.fixed_power_val(n).reverse().coalesce()
print('result1 done')

prev = domain.lex_gt_set(domain).lexmax()
result2 = prev.fixed_power_val(n).coalesce()
print('result2 done')

print(result1.is_equal(result2))
```

[Sven Verdoolaege]

On Thu, Jan 19, 2023 at 07:38:14PM -0800, Jiacheng Pan wrote:
> And it seems isl hangs with following code:
> ```
> prev = domain.lex_gt_set(domain).lexmax()
> result = prev.fixed_power_val(128)
> ```
>
> I think I am computing `t -> t-n` by first constructing `t -> t-1` and then
> computing the power-n of it (here n = 128).
> And this seems very slow (or actually hangs).
> It seems reducing the power n to 32 is much faster, while it looks to take
> longer time starting from n=64.
>
> But it is much faster (<1s) with following code:
> ```
> next = domain.lex_lt_set(domain).lexmin()
> result = next.fixed_power_val(128).reverse()
> ```
>
> Is it expected? (I am using islpy 2022.2.1)

I don't know which version of isl (not islpy) you are using,
but I can sort of reproduce the issue. It depends a bit on the representation
of the input map.
I pushed out a change (to isl) that should help a bit.

> Also, if I am trying to get the map of `t -> t-n`, am I using the correct
> / recommended way? (still trying to learn isl...)

That depends on what extra information you have about the map.
IF you don't have any extra information, then this is probably
the best you can do. If you have some extra information,
it may be possible to exploit that.

You could also manually do the repeating applications that fixed_power is doing.
In this case, it seems that some "optimization" that was being performed
on the intermediate results caused those results to actually become
more complicated in the long run.
If you leave those out, you could get an answer more quickly,
at least for this particular input.

skimo

[Jiacheng Pan]

Thank you!!

I managed to locally cherry-pick you changes to isl-0.25 (which I was using earlier) and compile with islpy and barvionk. It works!

On Sunday, January 22, 2023 at 9:35:25 PM UTC+8 Sven Verdoolaege wrote:

On Thu, Jan 19, 2023 at 07:38:14PM -0800, Jiacheng Pan wrote:
> And it seems isl hangs with following code:
> ```
> prev = domain.lex_gt_set(domain).lexmax()
> result = prev.fixed_power_val(128)
> ```
>
> I think I am computing `t -> t-n` by first constructing `t -> t-1` and then
> computing the power-n of it (here n = 128).
> And this seems very slow (or actually hangs).
> It seems reducing the power n to 32 is much faster, while it looks to take
> longer time starting from n=64.
>
> But it is much faster (<1s) with following code:
> ```
> next = domain.lex_lt_set(domain).lexmin()
> result = next.fixed_power_val(128).reverse()
> ```
>
> Is it expected? (I am using islpy 2022.2.1)

I don't know which version of isl (not islpy) you are using,
but I can sort of reproduce the issue. It depends a bit on the representation
of the input map.
I pushed out a change (to isl) that should help a bit.

> Also, if I am trying to get the map of `t -> t-n`, am I using the correct
> / recommended way? (still trying to learn isl...)

That depends on what extra information you have about the map.
IF you don't have any extra information, then this is probably
the best you can do. If you have some extra information,
it may be possible to exploit that.

 

Thanks. I think so far that's all what I have... I will stick with using fixed_power.