Reducing compilation time

Zama Concrete
1

I’m trying to implement sorting algorithms using Concrete to sort encrypted arrays. The algorithm seems to be working fine but problem is that the compilation time becomes extremely long as the array size increases (>=15). Here’s a snippet of the relevant code (odd/even sort algorithm)

@fhe.compiler({“arr”: “encrypted”})
def sort_array(arr):
n = arr.size

for phase in range(n):
    start = phase % 2  

    for i in range(start, n - 1, 2):
        a, b = arr[i], arr[i+1]
        c = (a > b)

        arr[i] = c * b + (1 - c) * a
        arr[i+1] = c * a + (1 - c) * b

return arr

lrange = int(input("Please enter the upper range limit: "))
lsize = int(input("Please enter the size of the list: "))

inputset = [np.random.randint(0, lrange, size=lsize) for _ in range(50)]
sort_compile = sort_array.compile(inputset)

My questions:

  1. Is there any way to reduce the compilation time for larger input sizes?
  2. Is the long compilation time primarily due to the inputset, the algorithm’s structure, or both?

Thank you

2

Hello @rraj ,

The concrete-python frontend use a tracing algorithm to generate the mlir dag as a side effect that unroll the loops, so the compilation time here will depends of the size of the array.

As workaround you can compile only the inner loop body as a fhe function let the control flow (which is in clear) outside the fhe function.

Cheers.