1 of 6

Optimize table lookups

This guide teaches how costly table lookups are, and how to optimize them to improve the execution time of Concrete circuits.

The most costly operation in Concrete is the table lookup operation, so one of the primary goals of optimizing performance is to reduce the amount of table lookups.

Furthermore, the bit width of the input of the table lookup plays a major role in performance.

The code above prints:

Reducing TLU

This guide teaches how to improve the execution time of Concrete circuits by reducing the amount of table lookups.

Reducing the amount of table lookups is probably the most complicated guide in this section as it's not automated. The idea is to use mathematical properties of operations to reduce the amount of table lookups needed to achieve the result.

One great example is in adding big integers in bitmap representation. Here is the basic implementation:

def add_bitmaps(x, y):
    result = fhe.zeros((N,))
    carry = 0

    addition = x + y
    for i in range(N):
        addition_and_carry = addition[i] + carry
        carry = addition_and_carry >> 1
        result[i] = addition_and_carry % 2

    return result

There are two table lookups within the loop body, one for >> and one for %.

This implementation is not optimal though, since the same output can be achieved with just a single table lookup:

def add_bitmaps(x, y):
    result = fhe.zeros((N,))
    carry = 0

    addition = x + y
    for i in range(N):
        addition_and_carry = addition[i] + carry
        carry = addition_and_carry >> 1
        result[i] = addition_and_carry - (carry * 2)

    return result

It was possible to do this because the original operations had a mathematical equivalence with the optimized operations and optimized operations achieved the same output with less table lookups!

Here is the full code example and some numbers for this optimization:

import numpy as np
from concrete import fhe

N = 32

def add_bitmaps_naive(x, y):
    result = fhe.zeros((N,))
    carry = 0

    addition = x + y
    for i in range(N):
        addition_and_carry = addition[i] + carry
        carry = addition_and_carry >= 2
        result[i] = addition_and_carry % 2

    return result

def add_bitmaps_optimized(x, y):
    result = fhe.zeros((N,))
    carry = 0

    addition = x + y
    for i in range(N):
        addition_and_carry = addition[i] + carry
        carry = addition_and_carry >> 1
        result[i] = addition_and_carry - (carry * 2)

    return result

inputset = fhe.inputset(fhe.tensor[fhe.uint1, N], fhe.tensor[fhe.uint1, N])
for (name, implementation) in [("naive", add_bitmaps_naive), ("optimized", add_bitmaps_optimized)]:
    compiler = fhe.Compiler(implementation, {"x": "encrypted", "y": "encrypted"})
    circuit = compiler.compile(inputset)

    print(
        f"{name:>9} implementation "
        f"-> {int(circuit.programmable_bootstrap_count)} table lookups "
        f"-> {int(circuit.complexity):_} complexity"
    )

prints:

    naive implementation -> 63 table lookups -> 2_427_170_697 complexity
optimized implementation -> 32 table lookups -> 1_224_206_208 complexity

which is almost half the amount of table lookups and ~2x less complexity for the same operation!

Implementation strategies

This guide teaches how to improve the execution time of Concrete circuits by using different conversion strategies for complex operations.

Concrete provides multiple implementation strategies for these complex operations:

The default strategy is the one that doesn't increase the input bit width, even if it's less optimal than the others. If you don't care about the input bit widths (e.g., if the inputs are only used in this operation), you should definitely change the default strategy.

Choosing the correct strategy can lead to big speedups. So if you are not sure which one to use, you can compile with different strategies and compare the complexity.

For example, the following code:

import numpy as np
from concrete import fhe

def f(x, y):
    return x & y

inputset = fhe.inputset(fhe.uint3, fhe.uint4)
strategies = [
    fhe.BitwiseStrategy.ONE_TLU_PROMOTED,
    fhe.BitwiseStrategy.THREE_TLU_CASTED,
    fhe.BitwiseStrategy.TWO_TLU_BIGGER_PROMOTED_SMALLER_CASTED,
    fhe.BitwiseStrategy.TWO_TLU_BIGGER_CASTED_SMALLER_PROMOTED,
    fhe.BitwiseStrategy.CHUNKED,
]

for strategy in strategies:
    compiler = fhe.Compiler(f, {"x": "encrypted", "y": "encrypted"})
    circuit = compiler.compile(inputset, bitwise_strategy_preference=strategy)
    print(
        f"{strategy:>55} "
        f"-> {circuit.programmable_bootstrap_count:>2} TLUs "
        f"-> {int(circuit.complexity):>12_} complexity"
    )

prints:

                       BitwiseStrategy.ONE_TLU_PROMOTED ->  1 TLUs ->  535_706_740 complexity
                       BitwiseStrategy.THREE_TLU_CASTED ->  3 TLUs ->  599_489_229 complexity
 BitwiseStrategy.TWO_TLU_BIGGER_PROMOTED_SMALLER_CASTED ->  2 TLUs ->  522_239_955 complexity
 BitwiseStrategy.TWO_TLU_BIGGER_CASTED_SMALLER_PROMOTED ->  2 TLUs ->  519_246_216 complexity
                                BitwiseStrategy.CHUNKED ->  6 TLUs ->  358_905_521 complexity

or:

import numpy as np
from concrete import fhe

def f(x, y):
    return x == y

inputset = fhe.inputset(fhe.uint4, fhe.uint7)
strategies = [
    fhe.ComparisonStrategy.ONE_TLU_PROMOTED,
    fhe.ComparisonStrategy.THREE_TLU_CASTED,
    fhe.ComparisonStrategy.TWO_TLU_BIGGER_PROMOTED_SMALLER_CASTED,
    fhe.ComparisonStrategy.TWO_TLU_BIGGER_CASTED_SMALLER_PROMOTED,
    fhe.ComparisonStrategy.THREE_TLU_BIGGER_CLIPPED_SMALLER_CASTED,
    fhe.ComparisonStrategy.TWO_TLU_BIGGER_CLIPPED_SMALLER_PROMOTED,
    fhe.ComparisonStrategy.CHUNKED,
]

for strategy in strategies:
    compiler = fhe.Compiler(f, {"x": "encrypted", "y": "encrypted"})
    circuit = compiler.compile(inputset, comparison_strategy_preference=strategy)
    print(
        f"{strategy:>58} "
        f"-> {circuit.programmable_bootstrap_count:>2} TLUs "
        f"-> {int(circuit.complexity):>13_} complexity"
    )

prints:

                       ComparisonStrategy.ONE_TLU_PROMOTED ->  1 TLUs -> 1_217_510_420 complexity
                       ComparisonStrategy.THREE_TLU_CASTED ->  3 TLUs ->   751_172_128 complexity
 ComparisonStrategy.TWO_TLU_BIGGER_PROMOTED_SMALLER_CASTED ->  2 TLUs -> 1_043_702_103 complexity
 ComparisonStrategy.TWO_TLU_BIGGER_CASTED_SMALLER_PROMOTED ->  2 TLUs -> 1_898_305_707 complexity
ComparisonStrategy.THREE_TLU_BIGGER_CLIPPED_SMALLER_CASTED ->  3 TLUs ->   751_172_128 complexity
ComparisonStrategy.TWO_TLU_BIGGER_CLIPPED_SMALLER_PROMOTED ->  2 TLUs ->   682_694_770 complexity
                                ComparisonStrategy.CHUNKED ->  3 TLUs ->   751_172_128 complexity

As you can see, strategies can affect the performance a lot! So make sure to select the appropriate one for your use case if you want to optimize performance.

Round/truncating

This guide teaches how to improve the execution time of Concrete circuits by using some special operations that reduce the bit width of the input of the table lookup.

There are two extensions which can reduce the bit width of the table lookup input, fhe.round_bit_pattern(...) and fhe.truncate_bit_pattern(...), which can improve performance by sacrificing exactness.

For example the following code:

import numpy as np
from concrete import fhe

inputset = fhe.inputset(fhe.uint10)
for lsbs_to_remove in range(0, 10):
    def f(x):
        return fhe.round_bit_pattern(x, lsbs_to_remove) // 2

    compiler = fhe.Compiler(f, {"x": "encrypted"})
    circuit = compiler.compile(inputset)

    print(f"{lsbs_to_remove=} -> {int(circuit.complexity):>13_} complexity")

prints:

lsbs_to_remove=0 -> 9_134_406_574 complexity
lsbs_to_remove=1 -> 3_209_430_092 complexity
lsbs_to_remove=2 -> 1_536_476_735 complexity
lsbs_to_remove=3 -> 1_588_749_586 complexity
lsbs_to_remove=4 ->   848_133_081 complexity
lsbs_to_remove=5 ->   525_987_801 complexity
lsbs_to_remove=6 ->   358_276_023 complexity
lsbs_to_remove=7 ->   373_311_341 complexity
lsbs_to_remove=8 ->   400_596_351 complexity
lsbs_to_remove=9 ->   438_681_996 complexity

Approximate mode

This guide teaches how to improve the execution time of Concrete circuits by using approximate mode for rounding.

You can enable approximate mode to gain even more performance when using rounding by sacrificing some more exactness:

import numpy as np
from concrete import fhe

inputset = fhe.inputset(fhe.uint10)
for lsbs_to_remove in range(0, 10):
    def f(x):
        return fhe.round_bit_pattern(x, lsbs_to_remove, exactness=fhe.Exactness.APPROXIMATE) // 2

    compiler = fhe.Compiler(f, {"x": "encrypted"})
    circuit = compiler.compile(inputset)

    print(f"{lsbs_to_remove=} -> {int(circuit.complexity):>13_} complexity")

prints:

lsbs_to_remove=0 -> 9_134_406_574 complexity
lsbs_to_remove=1 -> 5_548_275_712 complexity
lsbs_to_remove=2 -> 2_430_793_927 complexity
lsbs_to_remove=3 -> 1_058_638_119 complexity
lsbs_to_remove=4 ->   409_952_712 complexity
lsbs_to_remove=5 ->   172_138_947 complexity
lsbs_to_remove=6 ->    99_198_195 complexity
lsbs_to_remove=7 ->    71_644_380 complexity
lsbs_to_remove=8 ->    55_860_516 complexity
lsbs_to_remove=9 ->    50_978_148 complexity

Bit extraction

This guide teaches how to improve the execution time of Concrete circuits by using bit extraction.

is a cheap way to extract certain bits of encrypted values. It can be very useful for improving the performance of circuits.

For example:

prints:

That's almost 8x improvement to circuit complexity!

Reducing TLU

This guide teaches how to improve the execution time of Concrete circuits by reducing the amount of table lookups.

One great example is in adding big integers in bitmap representation. Here is the basic implementation:

def add_bitmaps(x, y):
    result = fhe.zeros((N,))
    carry = 0

    addition = x + y
    for i in range(N):
        addition_and_carry = addition[i] + carry
        carry = addition_and_carry >> 1
        result[i] = addition_and_carry % 2

    return result

There are two table lookups within the loop body, one for >> and one for %.

This implementation is not optimal though, since the same output can be achieved with just a single table lookup:

def add_bitmaps(x, y):
    result = fhe.zeros((N,))
    carry = 0

    addition = x + y
    for i in range(N):
        addition_and_carry = addition[i] + carry
        carry = addition_and_carry >> 1
        result[i] = addition_and_carry - (carry * 2)

    return result

It was possible to do this because the original operations had a mathematical equivalence with the optimized operations and optimized operations achieved the same output with less table lookups!

Here is the full code example and some numbers for this optimization:

import numpy as np
from concrete import fhe

N = 32

def add_bitmaps_naive(x, y):
    result = fhe.zeros((N,))
    carry = 0

    addition = x + y
    for i in range(N):
        addition_and_carry = addition[i] + carry
        carry = addition_and_carry >= 2
        result[i] = addition_and_carry % 2

    return result

def add_bitmaps_optimized(x, y):
    result = fhe.zeros((N,))
    carry = 0

    addition = x + y
    for i in range(N):
        addition_and_carry = addition[i] + carry
        carry = addition_and_carry >> 1
        result[i] = addition_and_carry - (carry * 2)

    return result

inputset = fhe.inputset(fhe.tensor[fhe.uint1, N], fhe.tensor[fhe.uint1, N])
for (name, implementation) in [("naive", add_bitmaps_naive), ("optimized", add_bitmaps_optimized)]:
    compiler = fhe.Compiler(implementation, {"x": "encrypted", "y": "encrypted"})
    circuit = compiler.compile(inputset)

    print(
        f"{name:>9} implementation "
        f"-> {int(circuit.programmable_bootstrap_count)} table lookups "
        f"-> {int(circuit.complexity):_} complexity"
    )

prints:

    naive implementation -> 63 table lookups -> 2_427_170_697 complexity
optimized implementation -> 32 table lookups -> 1_224_206_208 complexity

which is almost half the amount of table lookups and ~2x less complexity for the same operation!

Implementation strategies

This guide teaches how to improve the execution time of Concrete circuits by using different conversion strategies for complex operations.

Concrete provides multiple implementation strategies for these complex operations:

Choosing the correct strategy can lead to big speedups. So if you are not sure which one to use, you can compile with different strategies and compare the complexity.

For example, the following code:

import numpy as np
from concrete import fhe

def f(x, y):
    return x & y

inputset = fhe.inputset(fhe.uint3, fhe.uint4)
strategies = [
    fhe.BitwiseStrategy.ONE_TLU_PROMOTED,
    fhe.BitwiseStrategy.THREE_TLU_CASTED,
    fhe.BitwiseStrategy.TWO_TLU_BIGGER_PROMOTED_SMALLER_CASTED,
    fhe.BitwiseStrategy.TWO_TLU_BIGGER_CASTED_SMALLER_PROMOTED,
    fhe.BitwiseStrategy.CHUNKED,
]

for strategy in strategies:
    compiler = fhe.Compiler(f, {"x": "encrypted", "y": "encrypted"})
    circuit = compiler.compile(inputset, bitwise_strategy_preference=strategy)
    print(
        f"{strategy:>55} "
        f"-> {circuit.programmable_bootstrap_count:>2} TLUs "
        f"-> {int(circuit.complexity):>12_} complexity"
    )

prints:

                       BitwiseStrategy.ONE_TLU_PROMOTED ->  1 TLUs ->  535_706_740 complexity
                       BitwiseStrategy.THREE_TLU_CASTED ->  3 TLUs ->  599_489_229 complexity
 BitwiseStrategy.TWO_TLU_BIGGER_PROMOTED_SMALLER_CASTED ->  2 TLUs ->  522_239_955 complexity
 BitwiseStrategy.TWO_TLU_BIGGER_CASTED_SMALLER_PROMOTED ->  2 TLUs ->  519_246_216 complexity
                                BitwiseStrategy.CHUNKED ->  6 TLUs ->  358_905_521 complexity

or:

import numpy as np
from concrete import fhe

def f(x, y):
    return x == y

inputset = fhe.inputset(fhe.uint4, fhe.uint7)
strategies = [
    fhe.ComparisonStrategy.ONE_TLU_PROMOTED,
    fhe.ComparisonStrategy.THREE_TLU_CASTED,
    fhe.ComparisonStrategy.TWO_TLU_BIGGER_PROMOTED_SMALLER_CASTED,
    fhe.ComparisonStrategy.TWO_TLU_BIGGER_CASTED_SMALLER_PROMOTED,
    fhe.ComparisonStrategy.THREE_TLU_BIGGER_CLIPPED_SMALLER_CASTED,
    fhe.ComparisonStrategy.TWO_TLU_BIGGER_CLIPPED_SMALLER_PROMOTED,
    fhe.ComparisonStrategy.CHUNKED,
]

for strategy in strategies:
    compiler = fhe.Compiler(f, {"x": "encrypted", "y": "encrypted"})
    circuit = compiler.compile(inputset, comparison_strategy_preference=strategy)
    print(
        f"{strategy:>58} "
        f"-> {circuit.programmable_bootstrap_count:>2} TLUs "
        f"-> {int(circuit.complexity):>13_} complexity"
    )

prints:

                       ComparisonStrategy.ONE_TLU_PROMOTED ->  1 TLUs -> 1_217_510_420 complexity
                       ComparisonStrategy.THREE_TLU_CASTED ->  3 TLUs ->   751_172_128 complexity
 ComparisonStrategy.TWO_TLU_BIGGER_PROMOTED_SMALLER_CASTED ->  2 TLUs -> 1_043_702_103 complexity
 ComparisonStrategy.TWO_TLU_BIGGER_CASTED_SMALLER_PROMOTED ->  2 TLUs -> 1_898_305_707 complexity
ComparisonStrategy.THREE_TLU_BIGGER_CLIPPED_SMALLER_CASTED ->  3 TLUs ->   751_172_128 complexity
ComparisonStrategy.TWO_TLU_BIGGER_CLIPPED_SMALLER_PROMOTED ->  2 TLUs ->   682_694_770 complexity
                                ComparisonStrategy.CHUNKED ->  3 TLUs ->   751_172_128 complexity

As you can see, strategies can affect the performance a lot! So make sure to select the appropriate one for your use case if you want to optimize performance.